工程計算9矩陣特征值與特征向量

1、9 矩陣特征值問題的數(shù)值解法矩陣特征值問題的數(shù)值解法 9.1 引言引言 9.2 冪法及其變形冪法及其變形 9.3 矩陣的兩種正交變換矩陣的兩種正交變換 9.4 QR方法方法 2021-8-162 9.1 引言引言 9.1.1 問題的背景和內(nèi)容提要問題的背景和內(nèi)容提要 9.1.2 特征值的擾動和條件數(shù)特征值的擾動和條件數(shù) 的的n個根，個根，A屬于特征值屬于特征值 的特征向量的特征向量x是線性方程組是線性方程組 2021-8-163 9.1 引言引言 n階實方陣階實方陣A Rn n的的n個特征值就是其個特征值就是其特征方程特征方程 的非零解。這里，的非零解。這里， C， x C n。 9.1.1

2、問題的背景和內(nèi)容提要問題的背景和內(nèi)容提要 矩陣矩陣A的的特征多項式特征多項式 是是 的的n次多項式。次多項式。 2021-8-164 9.1 引言引言 當(dāng)當(dāng)A為實矩陣時，為實矩陣時， ()=0為實系數(shù)為實系數(shù)n次代數(shù)方程，其次代數(shù)方程，其 復(fù)根是共軛成對出現(xiàn)。因此，實矩陣的特征值如果是復(fù)根是共軛成對出現(xiàn)。因此，實矩陣的特征值如果是 復(fù)數(shù)，必然是共軛成對出現(xiàn)的。復(fù)數(shù)，必然是共軛成對出現(xiàn)的。 在實際問題中，矩陣的按模最大特征根起著重要在實際問題中，矩陣的按模最大特征根起著重要 的作用。例如矩陣的譜半徑即矩陣的按模最大特征根的作用。例如矩陣的譜半徑即矩陣的按模最大特征根 的值，它決定了迭代矩陣是否收

3、斂。的值，它決定了迭代矩陣是否收斂。 矩陣的最小特征值在振動中有重要意義。矩陣的最小特征值在振動中有重要意義。 2021-8-165 9.1 引言引言 先求特征多項式先求特征多項式 ( )的根，然后求特征向量。但的根，然后求特征向量。但n較較 大時，工作量很大。大時，工作量很大。 矩陣特征值的求解方法矩陣特征值的求解方法 在實際應(yīng)用中，對在實際應(yīng)用中，對n較大情況只求部分特征值和特征較大情況只求部分特征值和特征 向量，而且往往是模最小或模最大部分。向量，而且往往是模最小或模最大部分。 本章介紹求本章介紹求部分部分特征值特征向量的特征值特征向量的冪法冪法和求小規(guī)模和求小規(guī)模 問題問題全部全部特征

4、值特征向量的特征值特征向量的QR方法方法。 2021-8-166 9.1 引言引言 定理定理1 設(shè)設(shè)為為ARn n的特征值 的特征值, 且且Ax=x (x 0)， 則有則有 - -p為為A- -pI的特征值，即的特征值，即(A- -pI)x=(- -p)x ； c為的為的cA特征值特征值(c0為常數(shù)為常數(shù))； 下面復(fù)習(xí)有關(guān)特征值的一些下面復(fù)習(xí)有關(guān)特征值的一些結(jié)論結(jié)論： k為為Ak的特征值，即的特征值，即Akx=kx ； 設(shè)設(shè)A為非奇異矩陣，那么為非奇異矩陣，那么0 , 且且-1為為A-1的特的特 征值，即征值，即A-1x=-1x . 2021-8-167 9.1 引言引言 定理定理2 設(shè)設(shè)i(

5、i=1,2,n)為為n階矩陣階矩陣A=(aij)的特征值，的特征值， 則有則有 稱為稱為A的的跡跡； 定理定理3 設(shè)設(shè)ARn n，則有 ，則有 2021-8-168 9.1 引言引言 定理定理4 設(shè)設(shè)A 為分塊上三角矩陣，即為分塊上三角矩陣，即 其中每個對角塊其中每個對角塊Aii均為方陣，則均為方陣，則 2021-8-169 9.1 引言引言 定理定理5 設(shè)設(shè)A與與B為相似矩陣，即存在非奇異矩陣為相似矩陣，即存在非奇異矩陣 P，使，使 B=P-1AP 則則 定理定理5說明，一個矩陣說明，一個矩陣A經(jīng)過相似變換，其特征經(jīng)過相似變換，其特征 值不變值不變. A與與B有相同的特征值；有相同的特征值；

6、 如果如果y是是B的特征向量，則的特征向量，則Py是是A的特征向量的特征向量. 2021-8-1610 9.1 引言引言 一個虧損矩陣是一個沒有足夠特征向量的矩陣，一個虧損矩陣是一個沒有足夠特征向量的矩陣， 虧損矩陣在理論上和計算上都存在困難虧損矩陣在理論上和計算上都存在困難. 定義定義2 如果實矩陣如果實矩陣A有一個重數(shù)為有一個重數(shù)為k的特征值的特征值, 且對應(yīng)于且對應(yīng)于的的A的線性無關(guān)的特征向量個數(shù)的線性無關(guān)的特征向量個數(shù)|2|n|， 則對任何非零向量則對任何非零向量v0(a1 0)，冪法的算式成立，冪法的算式成立. 應(yīng)用應(yīng)用冪法冪法計算計算A的主特征值的主特征值1及其對應(yīng)的特征向及其對應(yīng)

7、的特征向 量時，如果量時，如果|1|1(或或|1|2|n|，則對任意非零初，則對任意非零初 始向量始向量v0=u0(a1 0)，根據(jù)冪法計算公式，根據(jù)冪法計算公式 則有則有 2021-8-1643 9.2冪法及其變形冪法及其變形 定理定理9.2.2 若若ARn n的 的主特征值主特征值 1為實的為實的m重根重根, 即即 1= 2= m, 且且 | 1 | | m+1 | | m+2 | | n |, 又設(shè)又設(shè)A有有n個線性無關(guān)的特征向量個線性無關(guān)的特征向量, 此時此時冪法仍然適用冪法仍然適用. 2021-8-1644 9.2冪法及其變形冪法及其變形 算法算法9.2.1 (冪法冪法)設(shè)設(shè)ARn

8、n。 。 1) 給定初始向量給定初始向量v0=u0 ，u0 =(1,1, ,1)T, 收斂閾值收斂閾值 0. 迭代。迭代。 (1) vk=Auk-1, (2) mk=max(vk), 否則，計算否則，計算 uk=vk/mk，k=k+1，到，到2)。 3) 如果如果輸出輸出 1 =mk， x1 =vk，停止。，停止。 2) k=1。計算。計算 2021-8-1645 9.2冪法及其變形冪法及其變形 例例 用冪法計算矩陣用冪法計算矩陣 的主特征值與其對應(yīng)的特征向量的主特征值與其對應(yīng)的特征向量. 解解取取 v0=u0=(0,0,1)T , 則則 2021-8-1646 9.2冪法及其變形冪法及其變形

9、 k 1 2, 4, 1, 4 0.5, 1, 0.25 2 4.5, 9, 7.75 90.5, 1, 0.8611 3 5.7222, 11.4444, 8.36111.44440.5, 1, 0.7360 4 5.4621, 10.9223, 8.2306 10.92230.5, 1, 0.7536 5 5.5075, 11.0142, 8.2576 11.01420.5, 1, 0.7494 6 5.4987, 10.9974, 8.2494 10.99740.5, 1, 0.7501 7 5.5002, 11.0005, 8.2501 11.00050.5, 1, 0.7500 8

10、5.5000, 11.0000, 8.2500 11.00000.5, 1, 0.7500 從而 2021-8-1647 9.2冪法及其變形冪法及其變形 設(shè)設(shè)| 1| | 2| | 3|,且且 20，當(dāng)?shù)螖?shù)，當(dāng)?shù)螖?shù)k充分大時，有充分大時，有 |max(xk) - - 1|c| 2/ 1|k- -1 當(dāng)當(dāng)| 2|接近接近| 1|時，收斂很慢。時，收斂很慢。 考慮加速方法考慮加速方法 2021-8-1648 9.2冪法及其變形冪法及其變形 Aitke外推法。對冪法的計算結(jié)果進行外推加速。外推法。對冪法的計算結(jié)果進行外推加速。 由于由于 解得解得 1的近似值的近似值 2021-8-1649

11、9.2 冪法及其變形冪法及其變形 算法算法9.2.2 (冪法冪法)設(shè)設(shè)ARn n。 。 1) 給定初始向量給定初始向量v0=u0 Rn，通常，通常u0 =(1,1, ,1)T, 收斂收斂 閾值閾值 0. 迭代。迭代。 (1) vk=Auk-1, (2) mk=max(vk), 2) k=1。計算。計算 2021-8-1650 9.2 冪法及其變形冪法及其變形 否則，計算否則，計算 uk=vk/mk，k=k+1，到，到2)。 3) 如果如果 輸出輸出 1 =mk， x1 =vk，停止。，停止。 2021-8-1651 9.2冪法及其變形冪法及其變形 9.2.2反冪法和原點位移 反冪法和原點位移

12、反冪法用來求按模最小的特征值及其特征向量。反冪法用來求按模最小的特征值及其特征向量。 設(shè)設(shè)ARn n非奇異，有 非奇異，有n個線性無關(guān)的特征向量，特個線性無關(guān)的特征向量，特 征值滿足條件征值滿足條件 |1|2|n-1|n|0， 則則A- -1的特征值滿足的特征值滿足 即即 是是 A- -1的主特征值，的主特征值，xn是其主特征向量。是其主特征向量。 對對A- -1應(yīng)用冪法即可得到應(yīng)用冪法即可得到A的按模最小的特征值及其特的按模最小的特征值及其特 征向量征向量,這就是反冪法。這就是反冪法。 2021-8-1652 9.2冪法及其變形冪法及其變形 計算公式為計算公式為 并有并有 收斂因子為收斂因子

13、為 =|n-1/n| 2021-8-1653 9.2冪法及其變形冪法及其變形 反冪法的另一個應(yīng)用是與反冪法的另一個應(yīng)用是與“原點位移原點位移”配合求指定配合求指定 點附近的某特征值及其特征向量。點附近的某特征值及其特征向量。 對于給定的常數(shù)對于給定的常數(shù)s，稱，稱A- -sI為矩陣為矩陣A的原點位移。由的原點位移。由 Ax= x (A- -sI)x=( - -s)x 即，即，如果如果ARn n的特征值為 的特征值為 1， 2， ， n ， 則則A- -sI 的的特征值為特征值為 1- -s， 2- -s， n- -s 。 特征向量不變。特征向量不變。 2021-8-1654 9.2冪法及其變形

14、冪法及其變形 如果如果A的某個的某個特征值滿足特征值滿足 | i- -s | l- -s |0，i =1,2, ,n，i l 即即 l是是A的離點的離點s嚴(yán)格最近的嚴(yán)格最近的特征值，此時對矩陣特征值，此時對矩陣A- -sI 使用反冪法，稱為帶原點位移的反冪法。使用反冪法，稱為帶原點位移的反冪法。 2021-8-1655 9.2冪法及其變形冪法及其變形 例例 用反冪法求矩陣用反冪法求矩陣A的接近的接近 于于p=1.2679的特征值及其特征的特征值及其特征 向量，取向量，取5位浮點數(shù)計算值，位浮點數(shù)計算值， 精確特征值精確特征值 其中其中 解：取列選主元的三角分解解：取列選主元的三角分解 2021

15、-8-1656 9.2冪法及其變形冪法及其變形 由由 Uv1=(1，1，1)T， 得得 v1=(12692，- -9290.3，3400.8)T， u1=(1，- -0.73198，0.26795)T 由由 LUv2=Pu1， 得得 v2=(20404，- -14937，5467.4)T， u2=(1，- -0.73206，0.26796)T 由此得特征值由此得特征值 3(=1.2679492)的近似值的近似值 對應(yīng)特征向量為對應(yīng)特征向量為 2021-8-1657 9.2冪法及其變形冪法及其變形 能否按此方法求出次大特征值和特征向量能否按此方法求出次大特征值和特征向量 限制：設(shè)限制：設(shè)| 1|

16、 | 2| | 3|,在求出在求出 1，u1條件下條件下 2021-8-1658 9.2冪法及其變形冪法及其變形 9.2.3 對稱矩陣的修正冪法對稱矩陣的修正冪法 對于實對稱矩陣，冪法得到的近似特征向量對于實對稱矩陣，冪法得到的近似特征向量u1的的 Rayleigh商給出特征值商給出特征值 1的較好的近似值。的較好的近似值。 非零向量非零向量uRn關(guān)于關(guān)于實對稱矩陣實對稱矩陣A Rn n的 的Rayleigh 商為商為 2021-8-1659 9.3 矩陣的兩種正交變換矩陣的兩種正交變換 其中，其中，D 是對角矩陣，其主對角線元素是對角矩陣，其主對角線元素 j(j=1，2，n) 是矩陣是矩陣

17、A 的特征值，而正交矩陣的特征值，而正交矩陣U的第的第j列就是列就是A的屬于的屬于j的特的特 征向量征向量(j=1，2，n)。 。 由代數(shù)學(xué)知識，對于一個實對稱矩陣由代數(shù)學(xué)知識，對于一個實對稱矩陣 A = (aij)n n，一定，一定 存在正交矩陣存在正交矩陣 U UTAU = D 求實對稱矩陣求實對稱矩陣A的特征值問題等于尋找正交矩陣的特征值問題等于尋找正交矩陣U，使，使 UTAU = D為對角陣為對角陣 2021-8-1660 9.3 矩陣的兩種正交變換矩陣的兩種正交變換 其中，其中，D 是對角矩陣，其主對角線元素是對角矩陣，其主對角線元素 j(j=1，2，n) 是矩陣是矩陣 A 的特征值

18、，而正交矩陣的特征值，而正交矩陣U的第的第j列就是列就是A的屬于的屬于j的特的特 征向量征向量(j=1，2，n)。 Jacobi方法是用于計算實對稱矩陣的全部特征值及對應(yīng)方法是用于計算實對稱矩陣的全部特征值及對應(yīng) 特征向量的一種變換方法。特征向量的一種變換方法。Jacobi方法的基本思想是，通過方法的基本思想是，通過 一組平面旋轉(zhuǎn)變換（正交相似變換）將對稱矩陣一組平面旋轉(zhuǎn)變換（正交相似變換）將對稱矩陣 A化為對角化為對角 矩陣，進而求出其全部特征值。矩陣，進而求出其全部特征值。 由代數(shù)學(xué)知識，對于一個實對稱矩陣由代數(shù)學(xué)知識，對于一個實對稱矩陣 A = (aij)n n，一定，一定 存在正交矩陣

19、存在正交矩陣 U UTAU = D 求實對稱矩陣求實對稱矩陣A的特征值問題等于尋找正交矩陣的特征值問題等于尋找正交矩陣U，使，使 UTAU = D為對角陣為對角陣 2021-8-1661 9.3矩陣的兩種正交變換矩陣的兩種正交變換 有實對稱矩陣有實對稱矩陣A = (aij)n n，它的一對非主對角線元素 ，它的一對非主對角線元素 apq=aqp(pq)不為零。取不為零。取n n的正交矩陣的正交矩陣 2021-8-1662 9.3矩陣的兩種正交變換矩陣的兩種正交變換 Upq是是n維空間中的二維坐標(biāo)旋轉(zhuǎn)變換矩陣。設(shè)維空間中的二維坐標(biāo)旋轉(zhuǎn)變換矩陣。設(shè)xRn，則，則 Upqx相當(dāng)于將坐標(biāo)軸相當(dāng)于將坐標(biāo)

20、軸 oxp和和 oxq在在 xp、xq所在平面旋轉(zhuǎn)了一個所在平面旋轉(zhuǎn)了一個 角度角度 ，其他坐標(biāo)軸保持不變，故稱，其他坐標(biāo)軸保持不變，故稱Upq為平面旋轉(zhuǎn)矩陣。為平面旋轉(zhuǎn)矩陣。 用用 Upq對對A 作正交相似變換，得到作正交相似變換，得到 A1= UTpqAUpq= (a(1)ij)n n a(1)pp= appcos2 + aqqsin2 + 2apqcos sin a(1)qq = appsin2 + aqqcos2 + 2apqcos sin a(1)pi= a(1)ip= apicos + aqisin a(1)qi= a(1)iq= apisin + aqicos a(1)ij= a

21、(1)ji = aij a(1)pq = a(1)qp=0.5(aqq app) sin2 +2apqcos2 (i，jp，q) 2021-8-1663 9.3矩陣的兩種正交變換矩陣的兩種正交變換 可見，與矩陣可見，與矩陣A相比，矩陣相比，矩陣A1的第的第p行、第行、第p列和第列和第q行、第行、第q列列 的元素發(fā)生了變化，其余元素不變。的元素發(fā)生了變化，其余元素不變。 當(dāng)取當(dāng)取 滿足關(guān)系式滿足關(guān)系式 可以得到可以得到 a(1)pq = a(1)qp=0，也就是說，用平面旋轉(zhuǎn)變換矩陣，也就是說，用平面旋轉(zhuǎn)變換矩陣Upq 對對A進行正交相似變換，可以將進行正交相似變換，可以將A 的兩個非主對角線元

22、素的兩個非主對角線元素apq 和和aqp化為零化為零 2021-8-1664 9.3矩陣的兩種正交變換矩陣的兩種正交變換 求實對稱矩陣求實對稱矩陣A的特征值和特征向量是一個迭代過程，其迭代的特征值和特征向量是一個迭代過程，其迭代 步驟如下步驟如下 (1) 在在A的非主對角線元素中，找出按模最大的元素的非主對角線元素中，找出按模最大的元素apq (2) 計算計算 并由此求出并由此求出 sin 、cos 以及相應(yīng)的平面旋轉(zhuǎn)矩陣以及相應(yīng)的平面旋轉(zhuǎn)矩陣Upq (3)計算矩陣計算矩陣 A1的元素的元素a(1)ij (4) 若若 則停止計算，所求特征值為則停止計算，所求特征值為 ia(1)ii，i=1，2

23、，n 否則，令否則，令 A =A1，重復(fù)執(zhí)行上述各步驟，重復(fù)執(zhí)行上述各步驟. 2021-8-1665 9.3矩陣的兩種正交變換矩陣的兩種正交變換 當(dāng)條件當(dāng)條件 滿足時，滿足時，A1幾乎是一個對角矩陣。因此，可取幾乎是一個對角矩陣。因此，可取A1的主對角線的主對角線 元素作為元素作為A的特征值的近似值，即的特征值的近似值，即 ia(1)ii，i=1，2，n 記第記第 k次迭代所得的平面旋轉(zhuǎn)矩陣為次迭代所得的平面旋轉(zhuǎn)矩陣為Upkqk，設(shè)經(jīng)過，設(shè)經(jīng)過N次迭代，次迭代， 上述條件得到滿足，那么，經(jīng)過上述條件得到滿足，那么，經(jīng)過N 次迭代所得的矩陣次迭代所得的矩陣AN為為 記記 則則U是正交矩陣，并且有

24、是正交矩陣，并且有 AN= UTAU U 的第的第j列就是列就是A的屬于特征值的屬于特征值 ia(1)ii的近似特征向量，并且的近似特征向量，并且 所有的特征向量都是單位正交的。所有的特征向量都是單位正交的。 2021-8-1666 9.3矩陣的兩種正交變換矩陣的兩種正交變換 在旋轉(zhuǎn)變換中可以逐步形成在旋轉(zhuǎn)變換中可以逐步形成U，而不必保存每一次的變換矩，而不必保存每一次的變換矩 陣陣Upkqk。記。記 R0= I 令令 Rk= Rk 1Upkqk， k = 1，2，N 則則 U = RN. 計算矩陣計算矩陣 Rk的元素的元素r(k)ij的公式為的公式為 2021-8-1667 9.3矩陣的兩種

25、正交變換矩陣的兩種正交變換 用用 Jacobi方法計算方法計算n n矩陣矩陣A的特征值和特征向量的特征值和特征向量,計算量主要計算量主要 是乘法的次數(shù)，約為是乘法的次數(shù)，約為8n次次. 關(guān)于關(guān)于 Jacobi方法的收斂性，有以下的定理方法的收斂性，有以下的定理. 定理定理 8.1 設(shè)設(shè)A = (aij)n n是實對稱矩陣，由是實對稱矩陣，由 Jacobi方法的第方法的第k次次 迭代得到的矩陣記為迭代得到的矩陣記為 Ak= (a(k)ij)n n，又記，又記 則有則有 2021-8-1668 9.3矩陣的兩種正交變換矩陣的兩種正交變換 證證 令令 注意到注意到 可得可得 2021-8-1669

26、9.3矩陣的兩種正交變換矩陣的兩種正交變換 實對稱矩陣經(jīng)過正交相似變換后，其元素的平方和不變，即實對稱矩陣經(jīng)過正交相似變換后，其元素的平方和不變，即 故有故有 又因又因 k+1 + k+1 = k + k 故得故得 2021-8-1670 9.3矩陣的兩種正交變換矩陣的兩種正交變換 從而有從而有 其中，其中， 0是矩陣是矩陣A的非主對角線元素平方之和。由于的非主對角線元素平方之和。由于 所以有所以有 2021-8-1671 9.3矩陣的兩種正交變換矩陣的兩種正交變換 為了減少搜索非對角線絕對值最大元素時間為了減少搜索非對角線絕對值最大元素時間, 對經(jīng)典的對經(jīng)典的Jacobi 方法可作進一步改進

27、方法可作進一步改進. 1.循環(huán)循環(huán)Jacobi方法：按方法：按 (1,2)，(1,3)，(1,n)，(2,3) ， (2,4)， ，(2,n)，(n-1,n) 的順序的順序, 對每個對每個(i,j)的非零元素的非零元素aij作作Jacobi變換變換,使其零化使其零化,逐次重逐次重 復(fù)掃描下去復(fù)掃描下去,直至直至S(A)j+1 即即B的形狀為的形狀為 則稱則稱B是是可約的可約的，否則，是，否則，是不可約的不可約的。 對于可約的對于可約的Hessenberg形，可把求解形，可把求解B的特征值問題約簡成較的特征值問題約簡成較 小矩陣特征值問題。小矩陣特征值問題。 2021-8-1686 9.3矩陣的

28、兩種正交變換矩陣的兩種正交變換 9.3.2 化矩陣為化矩陣為Hessenberg形形 即稱即稱B為上為上Hessenberg矩陣，簡稱矩陣，簡稱Hessenberg形形 定理表明，任何實方陣可通過正交相似變換化為定理表明，任何實方陣可通過正交相似變換化為Hessenberg形形 定理定理9.3.3 對于任何矩陣對于任何矩陣A Rn n，存在正交陣，存在正交陣Q，使得，使得 B=QTAQ 為為Hessenberg形形。 證：記證：記A1=A，x1為為A1的第一列對角線以下的第一列對角線以下(不含對角線不含對角線)的的n-1維維 向量向量 對于可約的，可把求解對于可約的，可把求解B的特征值問題約簡

29、成較小矩陣特征值的特征值問題約簡成較小矩陣特征值 問題。問題。 2021-8-1687 9.3矩陣的兩種正交變換矩陣的兩種正交變換 9.3.2 化矩陣為化矩陣為Hessenberg形形 推論推論9.3.3 對于任何對稱矩陣對于任何對稱矩陣A Rn n，存在正交陣，存在正交陣Q，使得，使得 B=QTAQ 為對稱三對角矩陣為對稱三對角矩陣。 2021-8-1688 9.3矩陣的兩種正交變換矩陣的兩種正交變換 9.3.2 化矩陣為化矩陣為Hessenberg形形 實方陣的實方陣的 Hessenberg形不是唯一的。但有下面定理形不是唯一的。但有下面定理 定理定理9.3.4 對于對于A Rn n，設(shè)有

30、正交陣，設(shè)有正交陣 Q=q1，q2 ， ，qn 和和 V=v1，v2 ， ，vn 使得使得 B=QTAQ C=VTAV 都是都是Hessenberg矩陣。矩陣。 記記k為使為使bk+1,k=0(k=1,2,n-1)的最小整數(shù)，的最小整數(shù)，(B不可約時令不可約時令 k=n，并令，并令bn+1,n=0)。 如果如果q1=v1，則有，則有 2021-8-1689 9.3矩陣的兩種正交變換矩陣的兩種正交變換 9.3.3 矩陣的矩陣的QR分解分解 定理定理9.3.3(QR分解定理分解定理) 對于任何對稱矩陣對于任何對稱矩陣A Rn n，存在正，存在正 交陣交陣Q和上三角矩陣和上三角矩陣R，使得，使得 A

31、=QR 如果矩陣如果矩陣A非奇異，并且非奇異，并且R的對角線元素取正值，則的對角線元素取正值，則A的的 QR分解是唯一的分解是唯一的。 2021-8-1690 9.4 QR算法算法 9.4.1 QR算法及其收斂性 算法及其收斂性 對于任何對稱矩陣對于任何對稱矩陣A Rn n，存在正交陣，存在正交陣Q，使得，使得 QTAQ=diag( 1， 2 ， n) 其中其中 1, 2，, n是是A的全部特征值，的全部特征值，Q的列為對應(yīng)的特征向量。的列為對應(yīng)的特征向量。 定理定理9.4.1 (實實Schur分解定理分解定理) 對于任對于任 何矩陣何矩陣A Rn n，存在正交陣，存在正交陣Q，使得，使得 其

32、中的對角塊其中的對角塊Rii(i=1,2,m)為為1 1或或2 2的子矩陣，一階子矩陣的子矩陣，一階子矩陣 的元素是的元素是A的特征值，二階子矩陣的兩個特征值是的特征值，二階子矩陣的兩個特征值是A的一對復(fù)的一對復(fù) 共軛特征值共軛特征值 2021-8-1691 9.4 QR算法算法 QR算法是目前求一般矩陣全部特征值的最有效并廣泛 算法是目前求一般矩陣全部特征值的最有效并廣泛 應(yīng)用的方法之一。應(yīng)用的方法之一。 在實際應(yīng)用中，經(jīng)常把一般的矩陣經(jīng)過正交相似變換化在實際應(yīng)用中，經(jīng)常把一般的矩陣經(jīng)過正交相似變換化 成上成上Hessenberg矩陣，再應(yīng)用矩陣，再應(yīng)用QR算法求其特征值和特征向量算法求其特

33、征值和特征向量. 算法算法9.4.1 基本基本QR算法算法 設(shè)設(shè)A Rn n 初始化：化初始化：化A為為Hessenenberg矩陣矩陣A1 迭代過程：對于迭代過程：對于k=1,2, 2021-8-1692 9.4 QR算法算法 基本基本QR算法的性質(zhì)算法的性質(zhì) A的的k次冪次冪Ak的的QR分解分解 定理定理9.4.2 在基本在基本QR算法中，記算法中，記 都是都是Hessenberg形形 相似性，即相似性，即QR變換下特征值不變變換下特征值不變 即即Hessenberg形在形在QR變換下保持不變變換下保持不變 即即QR變換實際上是對變換實際上是對A的冪的冪Ak進行進行QR分解分解 2021-

34、8-1693 9.4 QR方法方法 定理定理9.4.3 設(shè)對稱矩陣設(shè)對稱矩陣A Rn n 的特征值滿足的特征值滿足 對應(yīng)的規(guī)范正交化特征向量為由對應(yīng)的規(guī)范正交化特征向量為由x1，x2 ， xn。如果單位。如果單位 坐標(biāo)向量坐標(biāo)向量 | 1| 2| 3| n|0 中的中的 1 0，則由算法，則由算法9.4.1生成的矩陣序列生成的矩陣序列Ak具有收斂性質(zhì)具有收斂性質(zhì) 2021-8-1694 9.4 QR方法方法 定理定理9.4.4 設(shè)矩陣設(shè)矩陣的的A Rn n的的特征值滿足特征值滿足 對應(yīng)的規(guī)范正交化特征向量為由對應(yīng)的規(guī)范正交化特征向量為由x1，x2 ， xn。 如果矩陣如果矩陣X=x1，x2 ，

35、 xn的的逆矩陣逆矩陣X-1可分解為可分解為 X-1=LU 其中其中L為單位下三角矩陣，為單位下三角矩陣，U為上三角矩陣。則由算法為上三角矩陣。則由算法9.4.1生生 成的矩陣序列成的矩陣序列Ak基本收斂基本收斂為上三角矩陣，當(dāng)為上三角矩陣，當(dāng)A為對稱矩陣時為對稱矩陣時 收斂收斂為對角陣。對角元的極限為為對角陣。對角元的極限為 | 1| 2| 3| n|0 收斂速度由收斂因子收斂速度由收斂因子| i+1/ i | (i=1,2,n-1)的大小確定，收斂的大小確定，收斂 是線性的是線性的 2021-8-1695 作業(yè)：作業(yè)：p420 9.2、9.5、9.8、9.9、9.12 2021-8-169

36、6 2021-8-1697 9.4 QR方法方法 定理定理 8.2 設(shè)設(shè)A 為為n n實矩陣，它的特征值實矩陣，它的特征值j(j=1， 2，n)滿足滿足|1|2| |n| 0，則由基本，則由基本QR方方 法產(chǎn)生的矩陣序列法產(chǎn)生的矩陣序列Ak收斂于一個上三角矩陣收斂于一個上三角矩陣(其主其主 對角線以上的元素可以不收斂對角線以上的元素可以不收斂)。若。若A是對稱矩陣，是對稱矩陣， 則序列則序列Ak收斂于一個對角矩陣收斂于一個對角矩陣. 定理定理 8.3 對于任何對于任何n n 實矩陣實矩陣A，由基本，由基本QR方法產(chǎn)方法產(chǎn) 生的矩陣序列生的矩陣序列Ak收斂于分塊上三角矩陣（其主對角收斂于分塊上三

37、角矩陣（其主對角 線子塊以上的元素可以不收斂），并且每個主對角線子塊以上的元素可以不收斂），并且每個主對角 線子塊有等模的特征值線子塊有等模的特征值. 2021-8-1698 9.4 QR方法方法 要實現(xiàn)一步要實現(xiàn)一步QR 方法的迭代，就需要做一次方法的迭代，就需要做一次QR 分解，再做一分解，再做一 次矩陣相乘，當(dāng)次矩陣相乘，當(dāng)A是一般矩陣時，計算量是很大的。是一般矩陣時，計算量是很大的。 為了減少計算量，在實際計算時，總是先將原矩陣為了減少計算量，在實際計算時，總是先將原矩陣A經(jīng)過相似經(jīng)過相似 變換，化為上變換，化為上Hessenberg矩陣矩陣 A1 =(a(1)ij)n n， 其中，當(dāng)

38、其中，當(dāng)i j+1 時，時，a(1)ij =0。然后對。然后對A1使用使用 QR 方法。容易方法。容易 看出，從上看出，從上Hessenberg矩陣矩陣A1出發(fā)，經(jīng)過迭代所得的出發(fā)，經(jīng)過迭代所得的Ak(k=2， 3，)全都是上全都是上Hessenberg矩陣。事實上，設(shè)矩陣。事實上，設(shè)Ak是上是上 Hessenberg矩陣，則由于矩陣，則由于Rk 1是上是上Hessenberg矩陣，故矩陣，故 Qk= Ak Rk 1 是上是上Hessenberg矩陣，因而矩陣，因而 Ak+1= RkQk 也是上也是上Hessenberg矩陣。矩陣。 2021-8-1699 9.4 QR方法方法 9.3.3 帶原點平移的帶原點平移的QR 已經(jīng)證明，基本已經(jīng)證明，基本QR方法的收斂速度一般是線性收斂的方法的收斂速度一般是線性收斂的.為了加為了加 速收斂，引進帶原點平移的速收斂，引進帶原點平移的QR 方法方法