《數(shù)值計(jì)算方法》課件9矩陣特征值的數(shù)值計(jì)算

9矩陣特征值的數(shù)值計(jì)算

（NumericalComputationofEigenvaluesofMatrix

）

本章主要內(nèi)容

9.1特征值估計(jì)9.2冪法與原點(diǎn)平移法9.3矩陣的QR分解

9.4QR算法

重點(diǎn)：矩陣的兩種正交變換、冪法

難點(diǎn)：QR分解與QR算法9.1特征值的基本知識與估計(jì)9.1.1特征值的基本知識

特征值定義則

特征向量x1,x2,…xn

線性無關(guān)是矩陣A可對角化的充要條件。此時(shí)稱其為A的完全特征向量組。

相似矩陣有相同的特征值。

實(shí)對稱矩陣的特征值為實(shí)數(shù)。9.1特征值的基本知識與估計(jì)9.1.2特征值估計(jì)

定義9-1

蓋爾圓定理9-1蓋爾圓定理例9-1

估計(jì)特征值范圍。

結(jié)論：各個(gè)蓋爾圓相互分離是最好不過了。定理9-2第2蓋爾圓定理。例9-2

估計(jì)特征值范圍。

蓋爾圓分離的方法：構(gòu)造相似變換B=DAD-1。其中，D為第2種形式的初等方陣。例9-3

蓋爾圓分離。例9-4

設(shè)A按行嚴(yán)格對角占優(yōu)，則A可逆（特征值不為0）。9.2冪法及原點(diǎn)平移法9.2.1冪法

冪法的基本思想：是構(gòu)造一個(gè)向量序列使之逼近主特征向量，據(jù)此求出主特征向量和主特征值的近似值。是一種迭代的方法，又稱乘冪法。9.2冪法及原點(diǎn)平移法9.2.1冪法

9.2冪法及原點(diǎn)平移法9.2.1冪法

冪法的算法步驟：例9-5

冪法計(jì)算結(jié)果。

冪法的特點(diǎn)：

優(yōu)點(diǎn)：算法簡單、便于機(jī)器實(shí)現(xiàn)，適合大型稀疏矩陣的最大特征值。

缺點(diǎn)：算法效率低，收斂速度取決于次特征值與主特征值的比值。9.2冪法及原點(diǎn)平移法9.2.2反冪法

反冪法原理：通過求A-1的按模最大的特征值，來獲得A的按模最小的特征值。因?yàn)樵诠こ虘?yīng)用中，按模最大和最小的特征值和特征向量是關(guān)注的重點(diǎn)。

反冪法算法步驟：

反冪法是對冪法的補(bǔ)充，其困難在于每迭代一步相當(dāng)于求解一個(gè)線性方程組，計(jì)算量較大。9.2冪法及原點(diǎn)平移法9.2.3原點(diǎn)平移法

1原點(diǎn)平移加速

原點(diǎn)平移加速的原理是令B=A-pE，在保證B的主特征值與A的主特征值對應(yīng)的基礎(chǔ)上，使B的次特征值與主特征值之比減小或達(dá)到最小，從而起到加速求主特征值的目的。不難得到：

冪法與反冪法可以求矩陣的最大和最小特征值，對其他特征值就無能為力了。但是可以將原點(diǎn)平移技術(shù)與反冪法結(jié)合起來，就可求出任一個(gè)特征值（如果對所有的特征值有大概的估計(jì)的話）。

具體的作法：假設(shè)A在p附近有一個(gè)特征值，做原點(diǎn)平移B=A-pE，用反冪法求B的最小特征值，給其加上p，就是要求的特征值。例9-6，例9-7原點(diǎn)平移加速。2原點(diǎn)平移的反冪法例9-8，例9-9原點(diǎn)平移加速。9.3矩陣的QR分解

9.3.1矩陣的初等反射變換

矩陣的初等反射變換，又稱鏡面反射變換，或Householder（豪斯荷爾德）變換，是一種正交變換。顯然，初等反射矩陣H具有對稱性和正交性，這樣y=Hx是一個(gè)正交變換。

初等反射變換主要用在以下兩個(gè)方面：

等模反射變換

向量的約化消元9.3矩陣的QR分解

9.3.1矩陣的初等反射變換

等模反射變換

定理9-3（等模反射定理）設(shè)x,y是兩個(gè)互異的n維列向量，且2范數(shù)相等，則存在一個(gè)初等反射陣H，使得Hx=y。

例9-11等模反射變換。注意不唯一性。

向量的約化消元

9.3矩陣的QR分解

9.3.2矩陣的平面旋轉(zhuǎn)變換

矩陣的平面旋轉(zhuǎn)變換，又稱Givens（吉文斯）變換，也一種正交變換。

顯然，選取合適的c，s使經(jīng)Givens變換后的向量的第j個(gè)分量為0。起到對向量的約化消元的目的。例9-12用平面旋轉(zhuǎn)變換對向量約化消元。9.3矩陣的QR分解

9.3.3矩陣的QR分解定理9-4

對于任一n階實(shí)方陣A,有A=QR。其中Q,R分別為正交陣及上三角陣。定理9-5

（矩陣的QR分解）若n階實(shí)方陣A可逆有，則A的QR分解是唯一的（當(dāng)?shù)膶蔷€元素為正數(shù)時(shí)）。例9-13分別用兩種方法求矩陣的QR分解。方法一：利用初等反射變換方法二：利用平面旋轉(zhuǎn)變換例9-14用QR分解求解線性方程組。9.4QR算法

9.4.1基本QR算法在極限狀態(tài)下，Ak逼近一個(gè)上三角陣，從而求得A的特征值（這里的Ak之間是相似的）。QR算法實(shí)質(zhì)上是對Ak進(jìn)行QR分解。定理9-6

任意實(shí)方陣都可以通過正交相似變換與上海森伯格矩陣相似。例9-16用初等反射變換化矩陣為上海森伯格矩陣。QR分解：Ak=QkRk交換相乘：Ak+1=RkQk=QTkAkQk例9-15試證矩陣與其約化成為的上Hessenberg陣有相同的特征值。

QR算法是求解矩陣全部特征值的有效方法

QR算法是一個(gè)迭代過程。主要分為一下兩步9.4.2兩步QR算法1.矩陣與上Hessenberg矩陣的正交相似

定義9-5

上海森伯格（Hessenberg）矩陣。推論實(shí)對稱矩陣與三對角陣正交相似。9.4QR算法

9.4.2兩步QR算法2.矩陣與上Hessenberg矩陣的正交相似

引入上Hessenberg陣的原因是，若對上Hessenberg陣進(jìn)行分解，由于的次對角線以下元素均為零，只需使用次構(gòu)造方便的平面旋轉(zhuǎn)變換即可完成分解，顯然這要比對一般矩陣進(jìn)行分解簡便得多。利用這個(gè)特點(diǎn)給出的兩步算法，可以降低基本算法的計(jì)算過程中對矩陣做分解