矩陣特征值的計(jì)算

1、矩陣特征值的計(jì)算1第1頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五主要內(nèi)容 正交變換 Sturm序列與二分法QR 算法 Givens 變換 Householder 變換 基本算法 具有移位的QR算法2第2頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五實(shí)對(duì)稱陣特征值的計(jì)算 通過正交變換，將實(shí)對(duì)稱矩陣約化為三對(duì)角陣，利用Sturm定理隔離特征值，最后用二分法求出所需特征值。3第3頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五 Givens變換4第4頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五引例令 0 05第5頁，共36頁，2022年，5月20日，9點(diǎn)1

2、9分，星期五Givens 變換定義：稱矩陣為 Givens 變換，或 旋轉(zhuǎn)變換。ijij6第6頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Givens 變換 性質(zhì)(1) 只有四個(gè)元素與單位矩陣不同(2) 正交：(3) 如果A是對(duì)稱陣，則 也是對(duì)稱陣(4) 用 G 左乘一個(gè)矩陣時(shí)，只改變?cè)摼仃囍袃尚械闹?5) 用 G 右乘一個(gè)矩陣時(shí)，只改變?cè)摼仃囍袃闪械闹?第7頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Givens 變換定理：設(shè) x = (x1, ., xi , . , xj , . , xn)T，且 xi , xj 不全為零，則存在 Givens 變換 G = G (

3、i, j, )，使得 8第8頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Givens 變換 計(jì)算步驟(1) 構(gòu)造 矩陣。一般地，對(duì)第i行Givens變換，構(gòu)造 ，其中 (2) Givens變換： 。經(jīng)過變換可以把 上的元素化為0。通過 次變換，可以約化為三對(duì)角陣。9第9頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五例 1 應(yīng)用Givens方法把矩陣約化為三對(duì)角陣。解：設(shè) ，令 ， 得 ，則Givens 變換10第10頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Givens 變換由 ，令 ，得 則同理，得11第11頁，共36頁，2022年，5月20日，9點(diǎn)19分

4、，星期五 Householder變換12第12頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換 1985年，A.S.Householder提出用初等Hermite陣代替Givens陣將對(duì)稱陣約化為三對(duì)角陣，只需要（n-2）次變換（Givens方法需要（1/2(n-1)(n-2)）次變換）就能達(dá)到簡(jiǎn)化目的。13第13頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換定義：設(shè) 且 ，稱矩陣為Householder變換。14第14頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換 性質(zhì)(1) 對(duì)稱

5、：(2) 正交：(3) 對(duì)合：(4) 保模：(5) 15第15頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換定理：設(shè) x, y Rn, x y 且 |x|2 = |y|2，則存在 n 階 Householder 變換 H，使得 y = Hx 16第16頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換定理：對(duì)任意的非零向量 x Rn，存在 Householder 變換 H，使得 Hx = e1 其中 = sgn(x1)|x|2, e1= (1, 0, ., 0)T ， 的選取是為了防止在實(shí)際計(jì)算中 與 x1 互相抵消 若

6、x1=0, 則取 = |x|217第17頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換 計(jì)算步驟(1) 構(gòu)造 矩陣。 ，其中 為k維向量(2) Householder變換。 經(jīng)過變換可以把 上的元素化為0。 其中 通過（n-2）次變換，可以約化為三對(duì)角陣。18第18頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換例 2 對(duì)例1中的矩陣，用Householder 變換約化為三對(duì)角陣。解： ，得向量 ，因此 , ，得19第19頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Householder 變換 當(dāng)矩陣比較稠密

7、時(shí)，具有更高的效率20第20頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五 Sturm序列與二分法21第21頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Sturm序列與二分法 設(shè)C是n階對(duì)稱陣A通過前面兩種方法之一，約化為的三對(duì)角陣。22第22頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Sturm序列與二分法其特征多項(xiàng)式多項(xiàng)式序列 是一個(gè)Sturm序列。應(yīng)用Sturm定理，可以求出在 內(nèi)實(shí)根的個(gè)數(shù)和隔離出C的特征值區(qū)間，原則上可以用二分法求出全部或者部分特征值。規(guī)定23第23頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Sturm序列與二分法例3 考

8、察矩陣C的特征值分布 解：C的特征多項(xiàng)式 對(duì)應(yīng)的各階主子式： 構(gòu)成一個(gè)Sterm序列。24第24頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五Sturm序列與二分法考察當(dāng) 時(shí)，多項(xiàng)式序列的変號(hào)數(shù) + - + - + 4 + 0 - 0 + 2 + + + + + 0 + + + + + 0由表可知，在 內(nèi)有兩個(gè)特征值，在（-2,0）內(nèi)有兩個(gè)特征值，在 沒有特征值。然后用二分法可以求得所需精度的特征值。25第25頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五一般矩陣特征值的計(jì)算 對(duì)任意非奇異矩陣，用QR算法迭代，它將收斂于一個(gè)上三角陣，主對(duì)角線上的元素近似為矩陣的特征值。26

9、第26頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五 QR算法27第27頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法定理：設(shè) 矩陣A是n 階 非奇異實(shí)矩陣，則存在正交分解 A = QR其中 Q 是正交矩陣 ，R 是非奇異上三角矩陣 。若限定 R 的對(duì)角線元素為正數(shù)，則此分解唯一 。 28第28頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法設(shè) ( j = 1, . , n )(1) 構(gòu)造 H1 使得 H1 a1 = 1e1 ，令(2) 構(gòu)造 使得 ，令 QR 分解29第29頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法以此類推，經(jīng)

10、過 n-1 步，可得 Householder 矩陣 H1, H2, . , Hn-1 ，使得令 ，即得30第30頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法例4 用 Householder 變換計(jì)算 的 QR 分解。 解：設(shè) ，則31第31頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法同理，構(gòu)造32第32頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法基本算法 設(shè) 為n階實(shí)矩陣，對(duì)A進(jìn)行QR分解， ,再令 即完成一次迭代。 一般地迭代式， 由此得到矩陣序列 。 收斂于上三角矩陣（或分塊 上三角矩陣），從而可以求出A的全部特征值與特征向量。 其中k=1,2,3,.每一次迭代計(jì)算量較大，常常先把實(shí)矩陣A用Househouder法約化為擬上三角陣。33第33頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法定理： 設(shè) ，進(jìn)行QR分解并迭代記 , 則有（1） 相似于A；（2） 的QR分解為 。34第34頁，共36頁，2022年，5月20日，9點(diǎn)19分，星期五QR算法具有移位的QR算法 設(shè)A為n階實(shí)矩陣，令 ，取適當(dāng)?shù)臄?shù) 對(duì)矩陣作QR分解令 ，這樣完成一次迭代。 一般地， 可以證明 與 相似， 中所有的矩