數(shù)值分析：第六章 矩陣特征值問(wèn)題的解法

第六章矩陣特征值問(wèn)題的解法

1給出若有使得：則稱為矩陣的特征值,

為相應(yīng)的特征向量。特征值為特征方程的根?！?特征值問(wèn)題及相關(guān)結(jié)果2關(guān)于特征值及特征向量的若干結(jié)果3一、特征值的估計(jì)及擾動(dòng)問(wèn)題

1、特征值的估計(jì)稱之為Gerschgorin圓盤(pán)（蓋爾圓）.

定理1（Gerschgorin

圓盤(pán)定理）

為實(shí)方陣，則在某個(gè)Gerschgorin圓盤(pán)之中.的任一特征值必落4

定理2（第二圓盤(pán)定理）

設(shè)為階實(shí)方陣，如果的個(gè)Gerschgorin圓盤(pán)與其他圓盤(pán)不相連，則恰好有的個(gè)特征值落在該個(gè)圓盤(pán)的并集之中。即特別地，孤立圓盤(pán)僅含有一個(gè)特征值.為的一個(gè)重新排列，,則中含有的個(gè)特征值.5

例如

有四個(gè)圓盤(pán):

6

實(shí)對(duì)稱矩陣的極大-極小定理：

為矩陣關(guān)于向量的Rayleigh（雷利）商.為階實(shí)對(duì)稱矩陣，則其特征值皆為實(shí)數(shù)，記做，并且存在規(guī)范正交特征向量系滿足：

設(shè)為階實(shí)矩陣，，則稱定義7證明:

假設(shè)為的規(guī)范正交特征向量組，則對(duì)任何向量，有

設(shè)為階實(shí)對(duì)稱矩陣，其特征值為，則定理38于是因而,特別地，若取，這時(shí)從而.同理可證中間特征值如何求？

9

定理4（Courant-Fisher極大極小定理）.設(shè)為階實(shí)對(duì)稱矩陣，為其個(gè)特征值.用表示的任意維子空間，則有或者證明：略.

102、特征值的擾動(dòng)問(wèn)題例：

討論：的大小.特征方程11設(shè)則.若在的上角，則特征值并無(wú)擾動(dòng).

12定理（Bauer-Fike）

則經(jīng)擾動(dòng)后的矩陣的一個(gè)特征值滿足不等式.其中為矩陣的范數(shù).

設(shè)矩陣具有完全特征向量系，矩陣使得13經(jīng)常使用的但定理對(duì)一般仍成立.若為對(duì)稱矩陣，可選為正交矩陣，這時(shí)，于是有結(jié)論：

若為實(shí)對(duì)稱矩陣，而為的任何一個(gè)擾動(dòng)，則對(duì)的任何一個(gè)特征值，有推論14§2乘冪法與反乘冪法一、乘冪法

1、乘冪法的基本思想與計(jì)算格式設(shè)有完全特征向量系，即的特征向量構(gòu)成線性空間的基底并設(shè)：15若，則.即逐漸與平行。16計(jì)算格式：（規(guī)格化）下面證明：引入記號(hào)：表示的絕對(duì)值最大的分量。

17例如：，則：并且：的最大分量為1。（規(guī)格化）由于的最大分量為1，故有：從而：

證明：18若，則有：

注意到：19即并且線性收斂速度。

若不滿足，乘冪法將復(fù)雜些。如果

此時(shí)

20又

收斂速度決定于的大小。

21

算法：乘冪法

給定一非零的初始向量，獲得

nn矩陣

A的主特征征值及其相應(yīng)的特征向量.Input:

維數(shù)n;矩陣

a[][];初始向量V0[];誤差容限TOL;

迭代的最大次數(shù)

Nmax.Output:

近似特征值

和規(guī)格化的近似特征向量或失敗信息。22

算法:乘冪法

Step1Setk=1;Step2Findindexsuchthat|V0[index]|=||V0||;Step3SetV0[]=V0[]/V0[index];/*規(guī)格化

V0*/Step4While(kNmax)dosteps5-11

Step5V[]=AV0[];/*由Uk1

計(jì)算

Vk*/

Step6=V[index];

Step7

Findindexsuchthat|V[index]|=||V||;

Step8IfV[index]==0thenOutput(“Ahastheeigenvalue0”;V0[]);STOP.

/*矩陣是奇異的，用戶嘗試新的

V0*/

Step9

err=||V0V[]/V[index]||;

V0[]=V[]/V[index];/*計(jì)算

Uk

*/

Step10If(err<TOL)thenOutput

(

;V[]);STOP./*成功*/

Step11Setk++;Step12Output(Maximumnumberofiterationsexceeded);STOP./*失敗*/

23例如：求方陣按模最大的特征值及相應(yīng)的特征向量。

解：取作為初始向量，可見(jiàn)與的對(duì)應(yīng)分量之比為1，特征值為43.38，特征向量為。241.00001.00001.00001.00001.000010.44600.44600.44630.44830.482010.18590.18590.18600.18570.2143143.8843.8843.9244.5756

43.8843.8843.9244.5756

19.5719.5719.6019.9827

8.1568.1578.1680.835712

543210乘冪法計(jì)算實(shí)例25（1）（2）（3）當(dāng)矩陣的特征值不滿足條件時(shí)，還可能出現(xiàn)的其他情形有：情況就十分復(fù)雜。26二、乘冪法的加速收斂線性收斂速度,取決于的大小.（1）原點(diǎn)位移法考慮矩陣：和特征值：和

和具有相同的特征向量。

27

即若，則。若有，并且，則可以加速收斂速度。

原點(diǎn)位移即是用乘冪法計(jì)算的特征值。

則現(xiàn)在關(guān)鍵是如何選取。

事實(shí)上，若求得的主特征值28特別，若的特征值均為實(shí)數(shù)，且滿足

應(yīng)選，滿足

這時(shí)取，使得：達(dá)極小值。29此時(shí)：即：

30（2）Rayleigh商加速設(shè)為實(shí)對(duì)稱矩陣，作Rayleigh商以下證明：

設(shè)為的規(guī)范正交特征向量系，仍設(shè)：，易知：31因此：故有：

32三、反乘冪法

假設(shè)有完全特征向量系，并設(shè)：注意：，則：則：

為的主特征值。

33計(jì)算格式：則：實(shí)際計(jì)算格式：34

若已知,考慮，

的特征值：又若：

這時(shí)為的主特征值。35計(jì)算格式：

有：

（1）（2）

（當(dāng)時(shí)）由（1）得：

反乘冪法可求得任意特征值和相應(yīng)的特征向量，收斂快，精度高。36

§2乘冪法

計(jì)算矩陣的主特征根及對(duì)應(yīng)的特征向量乘冪法條件：A有特征根|1|>|2|…|n|0，對(duì)應(yīng)n個(gè)線性無(wú)關(guān)的特征向量………|i/1|<1i>1當(dāng)k

充分大時(shí)，有這是A關(guān)于1的近似特征向量思路：從任意出發(fā)，要求37

定理設(shè)ARnn為非虧損矩陣，其主特征根

1為實(shí)根，且|1|>|2|…|n|。則從任意非零向量(滿足)出發(fā),迭代收斂到主特征向量，收斂到1。注：結(jié)論對(duì)重根

1=2=…=r

成立。若有1=2，則此法不收斂。38

規(guī)范化為避免大數(shù)出現(xiàn)，需將迭代向量規(guī)范化，即每一步先保證，再代入下一步迭代。一般用。記：則有：

算法：乘冪法

給定一非零的初始向量，獲得

nn矩陣

A的主特征征值及其相應(yīng)的特征向量.Input:

維數(shù)n;矩陣

a[][];初始向量V0[];誤差容限TOL;

迭代的最大次數(shù)

Nmax.Output:

近似特征值

和規(guī)格化的近似特征向量或失敗信息。39

算法:乘冪法

Step1Setk=1;Step2Findindexsuchthat|V0[index]|=||V0||;Step3SetV0[]=V0[]/V0[index];/*規(guī)格化

V0*/Step4While(kNmax)dosteps5-11

Step5V[]=AV0[];/*由Uk1

計(jì)算

Vk*/

Step6=V[index];

Step7

Findindexsuchthat|V[index]|=||V||;

Step8IfV[index]==0thenOutput(“Ahastheeigenvalue0”;V0[]);STOP.

/*矩陣是奇異的，用戶嘗試新的

V0*/

Step9

err=||V0V[]/V[index]||;

V0[]=V[]/V[index];/*計(jì)算

Uk

*/

Step10If(err<TOL)thenOutput

(

;V[]);STOP./*成功*/

Step11Setk++;Step12Output(Maximumnumberofiterationsexceeded);STOP./*失敗*/

40求矩陣A的按模最大的特征值解取x(0)=(1,0)T,計(jì)算x(k)=Ax(k-1),結(jié)果如下例kx1(k)x2(k)x1(k)/x1(k-1)x2(k)/x2(k-1)01010.250.220.102500.0833330.410.4166530.0422920.0343890.412600.4126740.0174510.0141900.412630.41263可取0.41263,x1(0.017451,0.014190)T.41例如

求方陣按模最大的特征值及相應(yīng)的特征向量.

解取作為初始向量，可見(jiàn)與的對(duì)應(yīng)分量之比為1，特征值為43.38，特征向量為.421.00001.00001.00001.00001.000010.44600.44600.44630.44830.482010.18590.18590.18600.18570.2143143.8843.8843.9244.5756

43.8843.8843.9244.5756

19.5719.5719.6019.9827

8.1568.1578.1680.835712

543210乘冪法計(jì)算實(shí)例43

原點(diǎn)位移法決定收斂的速度，特別是|2/1|

希望|2/1|

越小越好。不妨設(shè)1>2

…

n

，且|2|

>|n|。12nOp=(2

+

n)/2思路令B=A

pI

，則有|IA|=|I(B+pI)|=|(p)IB|A

p=B

。而，所以求B的特征根收斂快。我們?cè)鯓又?/p>

p在這里呢？44

Rayleigh商加速

設(shè)為實(shí)對(duì)稱矩陣，作Rayleigh商以下證明：

設(shè)為的規(guī)范正交特征向量系，仍設(shè)：，易知：45因此：

故有：

46反冪法

若

A有|1||2|…>|

n|，則A1有對(duì)應(yīng)同樣一組特征向量。11111lll…>-nnA1的主特征根

A的絕對(duì)值最小的特征根Q:

在每一步我們?cè)鯓佑?jì)算?A:

先對(duì)A進(jìn)行三角分解，再解線性系統(tǒng).47計(jì)算格式：則：實(shí)際計(jì)算格式：48若知道某一特征根i

的大致位置p

，即對(duì)任意j

i

有|

ip|<<|

jp|，并且如果(A

pI)1存在，則可以用反冪法求(A

pI)1的主特征根1/(ip

)，收斂將非?？?。思路49計(jì)算格式：

有：

（1）（2）

（當(dāng)時(shí)）由（1）得：

反乘冪法可求得任意特征值和相應(yīng)的特征向量，收斂快，精度高.50§3矩陣的約化與Householder矩陣的正交變換

矩陣的約化

目的：利用相似變換，將矩陣約化為“盡可能簡(jiǎn)單”的形式的過(guò)程，稱為矩陣的約化.

特征值特征向量51

Householder矩陣

稱為Householder矩陣.

性質(zhì)：1）（Hermite矩陣）

性質(zhì)：2）正交性：52正交矩陣作用于上，仍有：即不改變向量的長(zhǎng)度.

定理

設(shè)，則總存在Householder矩陣H使：證明：若，則只需取即可.

據(jù)此應(yīng)有：若，并確定

使53即：

應(yīng)與向量平行.

因?yàn)?，所?/p>

又因?yàn)?，所以可取這時(shí)即為所求的Householder矩陣.

54可以設(shè)計(jì)，使得變?yōu)樗枰男螤?

求（找），使得：55這里：56還可構(gòu)造，使得：

即要求，且的后面?zhèn)€元素為零.

57設(shè)：作

使得：令58則顯然，這樣構(gòu)造的仍然是Householder矩陣.

約化矩陣為上Hessenberg形式

相似變換：其中，當(dāng)

定理

：對(duì)任何矩陣，可以構(gòu)造正交矩陣

使得為上Hessenberg矩陣，其中為Householder矩陣.

59證明:

第1步約化的過(guò)程如下:記其中為階Householder矩陣，使得：

構(gòu)造的Householder矩陣6061構(gòu)造Householder矩陣其中為階Householder矩陣，使得：

第2步約化:62則具有如下形式：約化n-2步后,Householder矩陣，使記，顯然為正交矩陣.

63646566矩陣的分解

分解：，，為正交矩陣，為上三角陣.

作法：用表示的列向量，令取Householder矩陣使得

其中，則：67然后,構(gòu)造Householder矩陣其中為階Householder矩陣，使得：

68則，具有如下形式：構(gòu)造出一串Householder矩陣，使記，顯然為正交矩陣.

69平面旋轉(zhuǎn)變換法或Givens變換法70

§4方法方法的基本思想

首先作的分解：（對(duì)角元非負(fù)）

取：然后作的分解.

一般地：于是得矩陣序列：

71可以證明：

(1)∽

(2)為一階或二階方陣.

于是的特征值即為的特征值.

72定理

設(shè)的個(gè)特征值具有性質(zhì)：

則：證：（略）73

Hessenberg矩陣的方法

先把經(jīng)相似變換約化為Hessenberg矩陣，即：

∽且有很多零元.

設(shè)為Hessenberg矩陣,作分解:

74問(wèn)題在于是否仍為Hessenberg矩陣？

可以證明：

若為Hessenberg矩陣，

則：仍為Hessenberg矩陣。

75帶原點(diǎn)位移的方法（略）

方法收斂的速度同于冪法.

76

帶原點(diǎn)位移的方法

77787980

上Hessenberg矩陣的方法

先將經(jīng)相似變換約化為上Hessenberg矩陣，即：

∽且有很多零元.

設(shè)為上Hessenberg矩陣,作分解:

81問(wèn)題在于是否仍為上Hessenberg矩陣？

可以證明：

若為上Hessenberg矩陣，

則：仍為上Hessenberg矩陣。

8283§5實(shí)對(duì)稱矩陣特征值問(wèn)題的解法

一、Jacobi方法二、求實(shí)對(duì)稱矩陣特征值的二分法

84二、求實(shí)對(duì)稱矩陣特征值的二分法

設(shè)已知存在，，使得：不妨設(shè)：

85

Sturm序列定義：多項(xiàng)式序列即為的特征多項(xiàng)式.