計算方法冪法與反冪法

計算方法冪法與反冪法第一頁，共三十四頁，編輯于2023年，星期一冪法的基本思想:任取一個非零初始向量，由矩陣A的乘冪構造一向量序列稱為迭代向量。問題的提法：設,其特征值為,對應特征向量為即

，且線性無關。求矩陣A的主特征值及對應的特征向量。2023/6/62第二頁，共三十四頁，編輯于2023年，星期一1.A特征值中為強占優(yōu),即(1)冪法:問題：即

，且，線性無關。特征值滿足：設,其特征值為,對應特征向量為的特征向量。,即為強占優(yōu)。求矩陣的主特征值及對應2023/6/63第三頁，共三十四頁，編輯于2023年，星期一則（且設）線性無關,即為Rn中一個基，于是對任意的初始向量有展開式。(用的線性組合表示)首先討論2023/6/64第四頁，共三十四頁，編輯于2023年，星期一其中

當k=2,3,…時，即從而由假設,得2023/6/65第五頁，共三十四頁，編輯于2023年，星期一則k足夠大時，有可見幾乎僅差一個倍數(shù)所以：2023/6/66第六頁，共三十四頁，編輯于2023年，星期一且收斂速度由比值確定。所以有其次討論主特征值的計算。表示的第i個分量，則相鄰迭代向量的分量的比值為

2023/6/67特征向量乘以任意非零常數(shù)仍對應于同一特征值的特征向量因此，冪法是一種迭代方法。第七頁，共三十四頁，編輯于2023年，星期一則有

即相鄰迭代向量分量的比值收斂到主特征值,且收斂速度由斂可能很慢。比值來度量,r越小收斂越快,當而接近于1時,收2023/6/68第八頁，共三十四頁，編輯于2023年，星期一（1）設有n個線性無關的特征向量；（3）冪法：（2）設A的特征值滿足則

定理7：2023/6/69第九頁，共三十四頁，編輯于2023年，星期一2.A的主特征值為實的r重根，即問題：,求矩陣的主特征值及對應即

，且，線性無關。特征值滿足：設,其特征值為,對應特征向量為的特征向量。2023/6/610第十頁，共三十四頁，編輯于2023年，星期一對任意的初始向量有不全為零），則有（且設其中，且從而因此，當k充分大時,接近于與對應的特征向量的某個線性組合(不全為零)。2023/6/611第十一頁，共三十四頁，編輯于2023年，星期一解取v0=(1,0)T,計算vk=Avk-1,結果如下例：求矩陣A的按模最大的特征值k(vk)1(vk)2(vk)1/(vk-1)1(vk)2/(vk-1)201010.250.220.102500.0833330.410.4166530.0422920.0343890.412600.4126740.0174510.0141900.412630.41263可取10.41263,v1(0.017451,0.014190)T

2023/6/612第十二頁，共三十四頁，編輯于2023年，星期一在冪法中，我們構造的序列可以看出因此，若序列收斂慢的話，可能造成計算的溢出或歸02023/6/613第十三頁，共三十四頁，編輯于2023年，星期一于無窮（或趨于零），這樣造成計算機中的“溢出”。為了克服這個問題，利用向量的方向與長度無關這一性質，將迭代向量的長度規(guī)范化（“規(guī)一化”）以改進冪法。用冪法計算A的主特征值及對應的特征向量時,如果,,迭代向量的各個不等于零的分量將隨而趨3.冪法的改進所謂向量長度規(guī)范化,就是將向量的分量同除以一個常數(shù),使向量長度為1,向量長度有多種度量法,可以采用或,2023/6/614第十四頁，共三十四頁，編輯于2023年，星期一任取初始向量：迭代規(guī)范化則有迭代向量序列及規(guī)范化向量序列。2023/6/615第十五頁，共三十四頁，編輯于2023年，星期一即（1）若：2023/6/616收斂分別收斂反號的兩個數(shù)第十六頁，共三十四頁，編輯于2023年，星期一（2）若：分別收斂到兩個數(shù)，且絕對值不同。2023/6/617第十七頁，共三十四頁，編輯于2023年，星期一（2）設A特征值滿足

定理8（1）設有n個線性無關的特征向量；且

（3）及由改進冪法得到的規(guī)范化向量序列及迭代向量序列，則有且收斂速度由比值確定。2023/6/618第十八頁，共三十四頁，編輯于2023年，星期一應用冪法時,應注意以下兩點:2023/6/619第十九頁，共三十四頁，編輯于2023年，星期一(2)加速方法(原點平移法)應用冪法計算A主特征值的收斂速度主要由比值來確定，當r<1但接近于1時,收斂可能很慢，一個補救的辦法是采用加速收斂的方法。引進矩陣B=A-pI，其中P是可選擇的參數(shù)。2023/6/620設A的特征值為則B的特征值為且A,B特征向量相同。A與B除了對角線元素外，其它元素都相同，第二十頁，共三十四頁，編輯于2023年，星期一原點平移法的思想如果需要計算A的主特征值，適當選擇p使?jié)M足：（1）是B的主特征值，即對B應用冪法,使得在計算B的主特征值的過程中得到加速。這種方法通常稱為原點平移法。對于特征值的某種分布，它是十分有效的。2023/6/621第二十一頁，共三十四頁，編輯于2023年，星期一原點平移法(加速法)顯然,不管B如何選取,矩陣B=A-pI的主特征值為當要求計算及x1時，首先考慮應選取p滿足:其次,使或求極值問題1.設A的特征值是實數(shù)且滿足：求特征值的最大值2023/6/622第二十二頁，共三十四頁，編輯于2023年，星期一當

時，即時，值達到最小。

即當?shù)奶卣髦禎M足時,最佳的p值為

說明:

當能初步估計時，就可選擇P*的近似值。另外，的推導可以理解為,因為收斂速度由確定,如果能把原點向靠攏,使小下去,則可加快收斂速度。但是當原點移來，收斂速度又慢下去，因此把原點移到與的中點最合適，如圖示，取作為新原點。到某點使時，就代替了，而就成了,若大起2023/6/623第二十三頁，共三十四頁，編輯于2023年，星期一且使當

時，即最佳參數(shù)說明：1在實際應用中,A的特征值并不知道，所以,p是無法確定的，該方法只是告訴我們，當發(fā)現(xiàn)收斂速度慢時，可以適當移動原點加速收斂。要求，選取P滿足2.設A的特征值是實數(shù)且滿足：求特征值的最小值

2由以上討論知,用原點平移法可以求最大特征值與最小特征值.2023/6/624第二十四頁，共三十四頁，編輯于2023年，星期一例

設4階方陣A有特征值首先計算A的比值令作變換則B的特征值為所以對B應用冪法，可使冪法得到加速2023/6/625第二十五頁，共三十四頁，編輯于2023年，星期一原點平移的加速方法,是一種矩陣變換方法。這種變換容易計算,又不破壞A的稀疏性，但參數(shù)p的選擇依賴于對A的特征值的分布有大致了解。2023/6/626第二十六頁，共三十四頁，編輯于2023年，星期一(3)反冪法(或逆迭代)設為非奇異矩陣,A的特征值滿足：,對應特征向量線性無關，則A-1的特征值為，特征向量1、反冪法用來計算矩陣A按模最小的特征值及對應的特征向量計算A的按模最小的特征值的問題就是計算A-1按模最大的特征值問題。反冪法迭代公式：任取初始向量，2023/6/627第二十七頁，共三十四頁，編輯于2023年，星期一若有n個線性無關的特征向量且其特征值滿足：則由反冪法構造的向量序列滿足：且收斂速度由比值確定。2應用反冪法求一個近似特征值對應的特征向量。問題：已知的特征值的一個近似值（通常用其它方法得到），求對應的特征向量（近似）2023/6/628第二十八頁，共三十四頁，編輯于2023年，星期一若A的特征值為，則A-pI的特征值為取，且設與其它特征值是分離的，即如果(A-pI)

-1存在,則特征值為對應的特征向量即,說明對(A-pI)-1應用冪法得到反冪法計算公式：是(A-pI)-1的主特征根。2023/6/629第二十九頁，共三十四頁，編輯于2023年，星期一即其中線性方程組對(A-pI)-1應用冪法得到反冪法計算公式：取初始向量2023/6/630第三十頁，共三十四頁，編輯于2023年，星期一于是312023/6/6第三十一頁，共三十四頁，編輯于2023年，星期一定理10（1）設有n個線性無關特征向量,即且收斂速度由比值確定。（2）?。樘卣髦档囊粋€近似值），設(A-pI)-1存在序列滿足：且,則由反冪法迭代公式（2.12）構造向量2023/6/632第三十二頁，共三十四頁，編輯于2023年，星期一大體位置時，用此法最合適（該方法是一個有效的方法）(1)定理10可以計算特征向量xj。當知道A的某一個特征值的（2）取為特征值的一個近似值,當A的特征值分離情反冪法迭代公式可通過解方程組(A-pI)vk=uk-1來求vk。為了節(jié)況較好時,r

很小,則它本身收斂速度很快。同時改進了特征值。省計算量，可先將(A-pI)進行三角分解P(A-pI)=LU。其中P為置換陣，于是每次迭代求vk相當于求解兩個三角形方