計(jì)算方法課件

1、 第五章 特征值與特征向量 冪法 /* Power Method */計(jì)算矩陣的主特征根及對(duì)應(yīng)的特征向量特征值：的根 為矩陣A的特征值特征向量：滿足的向量v為矩陣A的對(duì)于特征值 的特征向量是高次的多項(xiàng)式，它的求根是很困難的。沒(méi)有數(shù)值方法是通過(guò)求它的根來(lái)求矩陣的特征值。通常對(duì)某個(gè)特征值，可以用些針對(duì)性的方法來(lái)求其近似值。若要求所有的特征值，則可以對(duì)A做一系列的相似變換，“收斂”到對(duì)角陣或上（下）三角陣，從而求得所有特征值的近似。以下是一些預(yù)備知識(shí)1 但高次多項(xiàng)式求根精度低 , 一般不作為求解方法. 目前的方法是針對(duì)矩陣不同的特點(diǎn)給出不同的有效方法.2機(jī)器 求解3定理1 4重要結(jié)論虧損矩陣5 一個(gè)

2、虧損矩陣是一個(gè)沒(méi)有足夠特征向量的矩陣， 虧損矩陣在理論與計(jì)算上存在巨大的困難。6對(duì)于矩陣特征值界如何估計(jì)？在用迭代法求解矩陣特征值的過(guò)程中,給出包含特征值的區(qū)域是很重要的.現(xiàn)給出若干特征值位置估計(jì)的常用結(jié)果.回憶此前有關(guān)矩陣范數(shù)的性質(zhì),有:7或者A的特征值都在復(fù)平面上n個(gè)圓盤的并集之中.8(2)如果A的m個(gè)圓盤組成一個(gè)連通的并集S，且S與余下的 包含A的m個(gè)特征值.n-m個(gè)圓盤是分離的,則S內(nèi)特別：若A的一個(gè)圓盤 與其它圓盤是分離的即孤立的,則 精確地包含A的一個(gè)特征值.9由上述定理結(jié)論可知A的三個(gè)特征值位于三個(gè)圓盤的并集中，10所以D1內(nèi)恰包含A的一個(gè)實(shí)特征值由于D1是孤立的所以，11 矩陣

3、的按模最大特征值往往表現(xiàn)為閾值。如：矩陣的譜半徑。冪法就是一種求矩陣按模最大特征值的方法，它是最經(jīng)典的方法。 冪法要求A有完備的特征向量系。即A有n個(gè)線性無(wú)關(guān)的特征向量。在實(shí)踐中，常遇到的實(shí)對(duì)稱矩陣和特征值互不相同的矩陣就具有這種性質(zhì)。設(shè)A的特征值和特征向量如下：特征值：特征向量：冪法可以求，基本思想很簡(jiǎn)單。 原始冪法 /* the original method */12設(shè)線性無(wú)關(guān)，取初值，作迭代設(shè)：則有：13（1）若：則k足夠大時(shí)，有可見(jiàn)幾乎僅差一個(gè)常數(shù)所以：任意分量相除特征向量乘以任意數(shù)，仍是特征向量14（2）若：則k足夠大時(shí)，有所以：所以：15（3）若：則k足夠大時(shí)，有所以：幾乎僅差一

4、個(gè)常數(shù)任意分量相除16（4）當(dāng)矩陣的特征值不滿足上述情況時(shí),還可能出現(xiàn)的其它的 情形有：17這樣，我們有算法：1、給出初值，計(jì)算序列2、若序列表現(xiàn)為，相鄰兩個(gè)向量各個(gè)分量比趨向于常數(shù)，則3、若序列表現(xiàn)為，奇偶序列各個(gè)分量比趨向于常數(shù)，則4、若序列表現(xiàn)為其他，退出不管18求矩陣A的按模最大的特征值解 取x(0)=(1,0)T ,計(jì)算x(k)=Ax(k-1), 結(jié)果如下例可取0.41263 ,x1(0.017451,0.014190)T .19在冪法中，我們構(gòu)造的序列可以看出因此，若序列收斂慢的話，可能造成計(jì)算的溢出或歸020改進(jìn)冪法的規(guī)范運(yùn)算易知：所以，有：最大分量為121即（1）若：22時(shí)，有

5、時(shí)，有收斂分別收斂反號(hào)的兩個(gè)數(shù)23（2）若：分別收斂到兩個(gè)數(shù)，且絕對(duì)值不同。24求：則：25這樣，我們有算法：1、給出初值，計(jì)算序列2、若序列收斂，則3、若序列的奇偶序列分別收斂，且兩個(gè)數(shù)絕對(duì)值相同，則4、若序列的奇偶序列分別收斂，且兩個(gè)數(shù)絕對(duì)值不同，則26Ch.5 Power Method Normalization Algorithm: Power MethodTo approximate the dominant eigenvalue and an associated eigenvectorof the nn matrix A given a nonzero initial vecto

6、r.Input: dimension n; matrix a ; initial vector V0 ; tolerance TOL; maximum number of iterations Nmax.Output: approximate eigenvalue and approximate eigenvector (normalized) or a message of failure.27 Algorithm: Power Method (continued)Step 1 Set k = 1;Step 2 Find index such that | V0 index | = | V0

7、 | ;Step 3 Set V0 = V0 / V0 index ; /* normalize V0 */Step 4 While ( k Nmax) do steps 5-11Step 5 V = A V0 ; /* compute Vk from Uk1 */ Step 6 = V index ;Step 7 Find index such that | V index | = | V | ;Step 8 If V index = 0 then Output ( “A has the eigenvalue 0”; V0 ) ; STOP. /* the matrix is singular and user should try a new V0 */Step 9 err = | V0 V / V index | ; V0 = V / V index ; /* compute Uk */Step 10 If (err TOL) then Output ( ; V0 ) ; STOP. /* successful */Step 11 Se