冪法求解矩陣主特征值的加速方法畢業(yè)論文

1、<p>　　冪法求解矩陣主特征值的加速方法</p><p><b>　　傅鵬</b></p><p>　　河南理工大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院信息與計(jì)算科學(xué)專業(yè)2009級(jí)1班</p><p>　　摘要：本論文主要研究的是冪法求解矩陣的主特征值和特征向量。物理、力學(xué)和工程技術(shù)中有許多需要我們求矩陣的按模最大的特征值（及稱為主特征值）和特征向量

2、。冪法是計(jì)算一個(gè)矩陣的模最大特征值和對(duì)應(yīng)的特征向量的一種迭代方法。它最大的優(yōu)點(diǎn)是方法簡(jiǎn)單，適合于大型稀疏矩陣的主特征值，但是收斂速度非常慢。所以我們要用加速的方法來(lái)加速收斂，加速方法包括原點(diǎn)平移加速、Rayleigh商加速和Aitken加速算法。</p><p>　　關(guān)鍵詞：冪法；原點(diǎn)平移加速；Rayleigh商加速；Aitken加速算法</p><p><b>　　§

3、1 引言</b></p><p>　　我們來(lái)介紹矩陣特征值和特征向量的計(jì)算方法，大家知道求一個(gè)矩陣的特征值的問題實(shí)質(zhì)上是求一個(gè)多項(xiàng)式的根的問題，而數(shù)學(xué)上已經(jīng)證明5階以上的多項(xiàng)式的根一般不能用有限次運(yùn)算求得。因此，矩陣特征值的計(jì)算方法本質(zhì)上都是迭代，而對(duì)于大型的稀疏矩陣就需要用冪法求解最簡(jiǎn)單。但是由于收斂速度非常的慢所以我們需要用加速的方法加快收斂速度而本次論文也是針對(duì)加速問題來(lái)通過(guò)對(duì)幾種方法的研究討論

4、。并且通過(guò)算法的實(shí)現(xiàn)來(lái)說(shuō)明那種加速算法收斂得快，哪個(gè)計(jì)算量比較節(jié)省。其實(shí)本文主要討論的問題是一個(gè)應(yīng)用中常見的一類數(shù)值計(jì)算問題。</p><p>　　§2 加速算法的背景</p><p><b>　　2.1冪法</b></p><p>　　冪法是計(jì)算一個(gè)矩陣的模最大特征值和對(duì)應(yīng)的特征向量的一種迭代方法。它適用于大型稀疏矩陣。為了說(shuō)明其基

5、本思想我們先假設(shè)是可對(duì)角化的，即有如下分解</p><p><b>　　其中</b></p><p><b>　　非奇異，再假定</b></p><p>　　現(xiàn)任取一向量由于的列向量構(gòu)成的一組基，故 可表示為</p><p><b>　　這里這樣，我們有</b></p&g

6、t;<p><b>　　由此可知 </b></p><p>　　這表明，當(dāng)而且充分大時(shí)，向量這是的一個(gè)很好的近似特征向量。然而，實(shí)際計(jì)算時(shí)，這是行不通的，其原因有二：一是我們事先并不知道的特征值；二是對(duì)充分大的計(jì)算的工作量太大。所以找出一種工作量較小的方法，而冪法求解收斂速度很慢所以我們還要找出一種加快速度的算法。</p><p><b>　　

7、迭代格式： </b></p><p><b>　　是的模最大分量，</b></p><p>　　其中是任意給定的初始向量，通常要求</p><p>　　定理 2.1.1 設(shè)有個(gè)線性無(wú)關(guān)的特征向量，主特征值滿足則對(duì)任何非零初始向量按下面構(gòu)造的向量序列</p><p><b>　　則有</b>

8、;</p><p><b>　　(1)</b></p><p><b>　　(2) </b></p><p>　　(注：此定理證明參閱文獻(xiàn)[5])</p><p>　　計(jì)算矩陣的主特征值。</p><p>　　用冪法求解矩陣A的計(jì)算結(jié)果如下表</p><p

9、><b>　　由此求得主特征值 </b></p><p><b>　　2.2冪法的應(yīng)用</b></p><p>　　物理，力學(xué)和工程技術(shù)中的很多問題在數(shù)學(xué)上都?xì)w結(jié)為求矩陣特征值問題。例如，振動(dòng)問題（大型橋梁或建筑物的振動(dòng)，機(jī)械振動(dòng)，電磁振蕩等），物理學(xué)中某些臨界值得確定，這些問題都?xì)w結(jié)為求矩陣的特征值的數(shù)學(xué)問題。而冪法求解實(shí)際應(yīng)用矩陣特征值

10、是十分有效方法之一，但是收斂速度太慢，所以在實(shí)際應(yīng)用中它所需要的時(shí)間非常的長(zhǎng)，而且計(jì)算過(guò)程中所消耗的時(shí)間造成了實(shí)際問題的完成進(jìn)度。因而我們需要通過(guò)用加速算法來(lái)加快收斂速度，讓實(shí)際問題提前或者按時(shí)完成。為了加快冪法求解矩陣主特征值的收斂速度，讓冪法更有效廣泛的運(yùn)用在實(shí)際應(yīng)用生活中，我們現(xiàn)在就來(lái)認(rèn)識(shí)幾種加速方法，如原點(diǎn)平移法、Rayleigh商加速、Aitken加速算法、一種改進(jìn)的Aitken加速算法和一種新的改進(jìn)的Aitken加速算法并且

11、對(duì)他們進(jìn)行比較，看哪種加速方法收斂得快，哪種計(jì)算量比較節(jié)省等。下面我們就來(lái)說(shuō)說(shuō)這幾種加速方法。</p><p>　　§3 常見的幾種加速算法</p><p><b>　　3.1原點(diǎn)平移法</b></p><p>　　定理 3.1.1 設(shè), 個(gè)互不相同的特征值滿足并且模最大特征值 是半單的（即的幾何重?cái)?shù)等于它的代數(shù)重?cái)?shù)）。如果初始向量

12、在的特征子空間上的投影不為零，則定理（2.1.2）產(chǎn)生的向量序列收斂到的一個(gè)特征向量 ，而且由定理（2.1.2）產(chǎn)生的數(shù)值序列收斂到。</p><p>　　（注：此定理證明參閱[1]）</p><p>　　由定理（2.1.1）可知冪法的收斂速度主要取決于的大小。在定理（2.1.1）的條件下，這個(gè)數(shù)總是小于1的，它越小收斂也就越快。當(dāng)它接近于1時(shí)收斂是很慢的。所以為了加快冪法的收斂速度，通常

13、用位移的方法，即應(yīng)用冪法于上。如果適當(dāng)選取可使之模最大特征值與其他特征值之模的距離更大，就可起到加速的目的。</p><p><b>　　首先我們引進(jìn)矩陣</b></p><p>　　其中為選擇參數(shù)。設(shè)的特征值為則的相應(yīng)特征值為而且，的特征向量相同。</p><p>　　如果需要計(jì)算的主特征值，就要適當(dāng)選擇，使仍然是的主特征值，且使</p

14、><p>　　對(duì)應(yīng)用冪法，使得在計(jì)算的主特征值的過(guò)程中得到加速。這種方法通常稱為原點(diǎn)平移法。對(duì)于的特征值的某種分布，它是十分有效的。</p><p>　　對(duì)于參數(shù)的選擇依賴于對(duì)矩陣特征值分布的大致了解。通?？梢杂肎erschgorin（蓋爾）圓盤定理得到矩陣的特征值分布情況。</p><p>　　定理3.1.2（Gerschgorin圓盤定理）設(shè)為階實(shí)矩陣，則</

15、p><p>　　的每一個(gè)特征值必定屬于下述個(gè)閉圓盤（稱為Gerschgorin圓）</p><p><b>　　的并集之中；</b></p><p>　　由矩陣的所有Gerschgorin圓組成的連通部分中任取一個(gè)，如果由個(gè)Gerschgorin圓構(gòu)成，則在這個(gè)連通部分中有且僅有的個(gè)特征值（Gerschgorin圓相重時(shí)重復(fù)計(jì)數(shù)，特征值相同時(shí)也重復(fù)

16、計(jì)數(shù)）。</p><p>　　求得矩陣的主特征值 后，可得矩陣的主特征值同時(shí)得到對(duì)應(yīng)的特征向量的近似。</p><p>　?。ㄗⅲ捍硕ɡ碜C明參閱文獻(xiàn)[1]）</p><p>　　事實(shí)上，如果對(duì)于矩陣的特征值能夠分離得很清楚，就可以利用原點(diǎn)平移法求得矩陣的所有特征值及其相應(yīng)的特征向量。但需要說(shuō)明的是，雖然常常能夠選擇有利的值，使冪法得到加速，但設(shè)計(jì)一個(gè)自動(dòng)選擇適當(dāng)參數(shù)

17、的過(guò)程是困難的。下面考慮的特征值是實(shí)數(shù)時(shí)，怎樣選擇使冪法計(jì)算 得到加速。</p><p><b>　　設(shè)的特征值滿足</b></p><p><b>　　（3.1.1）</b></p><p>　　則不管如何，的主特征值為或當(dāng)我們希望計(jì)算及時(shí)，首先應(yīng)選擇使</p><p><b>　　且使

18、收斂速度的比值</b></p><p>　　顯然，當(dāng)即時(shí)為最小，這時(shí)收斂速度的比值為</p><p>　　當(dāng)?shù)奶卣髦禎M足（3.1.1）且能初步估計(jì)時(shí)，我們就能確定 的近似值。</p><p>　　當(dāng)希望計(jì)算時(shí)，應(yīng)選擇</p><p>　　使得應(yīng)用冪法計(jì)算得到加速。</p><p>　　3.2 Rayleig

19、h商加速</p><p>　　定義 設(shè)為階實(shí)對(duì)稱矩陣，對(duì)于任一非零向量，稱</p><p>　　為對(duì)應(yīng)于向量的Rayleigh商。</p><p>　　定理 3.2.1 設(shè)為對(duì)稱矩陣（其特征值次序記為）則</p><p><b>　　(對(duì)任何非零)；</b></p><p>　　（注：此定理證明參

20、閱文獻(xiàn)[5]）</p><p>　　由定理3.2.1知，對(duì)稱矩陣的及 可用Rayleigh商的極值來(lái)表示。下面我們將把Rayleigh商應(yīng)用到用冪法計(jì)算實(shí)對(duì)稱矩陣的主特征值的加速收斂上來(lái)。</p><p>　　定理 3.2.2 設(shè) 為對(duì)稱矩陣，特征值滿足</p><p>　　對(duì)應(yīng)的特征向量滿足應(yīng)用冪法（公式（2.1.2））計(jì)算的主特征值，則規(guī)范化向量 的Raylei

21、gh商給出 的</p><p>　?。ㄗⅲ捍硕ɡ碜C明參閱[5]）</p><p>　　3.3 Aitken加速算法</p><p>　　Aitken加速算法在諸多方面得到了廣泛的應(yīng)用，尤其是從對(duì)冪法加速的諸多方法中突穎而出。但是在實(shí)際應(yīng)用中，由于冪法針對(duì)的大多是大型矩陣，而計(jì)算速度要求較快，精度要求較高，傳統(tǒng)的Aitken方法越來(lái)越不能滿足需要。</p>

22、<p>　　3.3.1 Aitken加速算法</p><p>　　設(shè)序列線性收斂到極限，而且對(duì)所有有如果存在實(shí)數(shù)，且滿足：</p><p><b>　　則定義為</b></p><p>　　的序列 收斂到，且比快，而且</p><p>　　算法實(shí)現(xiàn):把上述方法應(yīng)用于冪法迭代格式中的序列即可做到對(duì)冪法的加速。

23、具體算法偽代碼如下:</p><p>　　輸入初始向量誤差限,最大迭代次數(shù).</p><p><b>　　置</b></p><p><b>　　求整數(shù),使</b></p><p><b>　　計(jì)算置</b></p><p><b>　　計(jì)算&

24、lt;/b></p><p>　　若輸入停機(jī)；否則轉(zhuǎn)（7）.</p><p><b>　　若</b></p><p>　　置轉(zhuǎn)（3）；否則停止.</p><p>　　用此加速算法計(jì)算矩陣的主特征值。</p><p><b>　　計(jì)算結(jié)果如下表</b></p>

25、<p><b>　　由此A的主特征值</b></p><p>　　3.3.2改進(jìn)的Aitken加速算法</p><p>　　文獻(xiàn)[6]給出一種改進(jìn)的Aitken 算法，具體算法偽代碼如下:</p><p>　　輸入初始向量誤差限,最大迭代次數(shù).</p><p><b>　　置</b>&

26、lt;/p><p><b>　　求整數(shù),使</b></p><p><b>　　計(jì)算置</b></p><p><b>　　計(jì)算</b></p><p>　　若輸入停機(jī)；否則轉(zhuǎn)（7）.</p><p><b>　　若</b></p

27、><p>　　置轉(zhuǎn)（3）；否則停止.</p><p>　　用此改進(jìn)的加速算法計(jì)算矩陣的主特征值。</p><p><b>　　計(jì)算結(jié)果如下表格：</b></p><p><b>　　由此得到結(jié)果</b></p><p>　　經(jīng)過(guò)比較我發(fā)現(xiàn)改進(jìn)的加速算法還不如不改進(jìn)的。所以我重新閱

28、讀了文獻(xiàn)[6]發(fā)現(xiàn)證明中有一步假設(shè)是不合適的，而定理的結(jié)論是依賴于這個(gè)假設(shè)的，因此，我們認(rèn)為，這樣的算法在實(shí)際應(yīng)用中不具有應(yīng)用價(jià)值。具體的解釋說(shuō)明請(qǐng)關(guān)注附錄。</p><p>　　3.3.3新的改進(jìn)的Aitken加速算法</p><p>　　由于改進(jìn)的加速?zèng)]有達(dá)到我們想要的結(jié)果。所以我又參閱文獻(xiàn)[7]了解到一種解非線性方程的新算法，經(jīng)過(guò)反復(fù)與本文對(duì)比發(fā)現(xiàn)此新算法可以推及應(yīng)用到求矩陣的主特征

29、值上，具體計(jì)算步驟如下：</p><p>　　輸入初始向量誤差限,最大迭代次數(shù).</p><p><b>　　置</b></p><p><b>　　求整數(shù),使</b></p><p><b>　　計(jì)算置</b></p><p><b>　　置

30、</b></p><p><b>　　計(jì)算置</b></p><p><b>　　計(jì)算</b></p><p>　　若輸入停機(jī)；否則轉(zhuǎn)（7）.</p><p><b>　　若</b></p><p>　　置轉(zhuǎn)（3）；否則停止.</p&g

31、t;<p>　　例4.用此改進(jìn)的加速算法計(jì)算矩陣的主特征值。</p><p><b>　　計(jì)算結(jié)果如下表格：</b></p><p>　　由此得到結(jié)果新的加速算法既可以加快收斂速度而且使結(jié)果更接近于真實(shí)值。</p><p><b>　　§4 結(jié)論</b></p><p>　　

32、通過(guò)用vc++將幾種加速算法實(shí)現(xiàn)，并作了一個(gè)對(duì)比得出以下結(jié)論：</p><p>　　(1)原點(diǎn)平移加速算法是一個(gè)矩陣變換方法。這種變換容易計(jì)算，又不破壞矩陣的稀疏性而且收斂速度比較快，但是參數(shù)的選擇依賴于對(duì)的特征值分布的大致了解，而且設(shè)計(jì)一個(gè)自動(dòng)選擇適當(dāng)參數(shù)的過(guò)程比較困難，所以在參數(shù)的選擇過(guò)程中會(huì)遇到很多麻煩和困難造成花費(fèi)很多時(shí)間。</p><p>　　(2)Rayleigh商加速算法是系

33、統(tǒng)特征值問題中一個(gè)非常重要的概念。該方法適用于求解最大特征值和相應(yīng)的特征向量，一般情況下收斂速度是二階，矩陣對(duì)稱正定時(shí)到達(dá)三階。Rayleigh商加速算法的收斂速度與反冪法相同，而且不用選取特定的迭代初值是求解這類問題更出色的一種方法。</p><p>　　(3)Aitken加速算法比原點(diǎn)平移加速收斂得更快，而且它的計(jì)算量也不是太大。但是有時(shí)Aitken加速方法可能會(huì)失敗，如當(dāng)?shù)蛄科鸱^大的時(shí)候初值和真實(shí)值有

34、較大距離時(shí)Aitken加速就可能失敗。</p><p>　　（4）改進(jìn)的Aitken加速算法由于沒有達(dá)到加速的目的，所以我們現(xiàn)在還不能用此改進(jìn)的加速算法。我們對(duì)于此改進(jìn)的加速算法還需完善。</p><p>　　（5）新的改進(jìn)的Aitken加速算法既大大減少了計(jì)算量又加快了收斂速度和讓計(jì)算結(jié)果更接近于真實(shí)值。</p><p>　　總之這幾種方法都可以達(dá)到使冪法加速求解

35、矩陣主特征值的目的，而其中最好的是新的改進(jìn)的加速算法，并且我認(rèn)為這種方法用于實(shí)際問題和其它算法領(lǐng)域的加速當(dāng)中，相信會(huì)有更好的效果。而本文介紹的改進(jìn)的Aitken加速還需要進(jìn)一步完善。</p><p><b>　　附錄：</b></p><p>　　程序（1）#include<math.h></p><p>　　#include<

36、;iostream.h></p><p>　　int vector_max_component(const int n,const double *v)</p><p><b>　　{</b></p><p>　　double max=fabs(v[0]);</p><p>　　for(int i=0,index=

37、0;i<n;i++)if(max<fabs(v[i])){index=i;max=fabs(v[i]);}</p><p>　　return index;</p><p><b>　　}</b></p><p>　　double vector_inner_product(const int n,const double *u,con

38、st double *v)</p><p><b>　　{</b></p><p>　　double value=0;</p><p>　　for(int i=0;i<n;i++)value+=u[i]*v[i];</p><p>　　return value;</p><p><b&

39、gt;　　}</b></p><p>　　double vector_infty_norm(const int n,const double *v)</p><p><b>　　{</b></p><p>　　double value=fabs(v[0]);</p><p>　　for(int i=1;i&l

40、t;n;i++)</p><p><b>　　{</b></p><p>　　if(value<fabs(v[i]))value=fabs(v[i]);</p><p><b>　　}</b></p><p>　　return value;</p><p><b&

41、gt;　　}</b></p><p>　　double *matrix_multiply_vector(const int& m,const int& n,double **A,double *v)</p><p><b>　　{</b></p><p>　　double *vector;</p>&l

42、t;p>　　vector=new double [m];</p><p>　　for(int i=0;i<m;i++)vector[i]=vector_inner_product(n,A[i],v);</p><p>　　return vector;</p><p><b>　　}</b></p><p>　

43、　double *square_matrix_multiply_vector(const int& n,double **A,double *v)</p><p><b>　　{</b></p><p>　　return matrix_multiply_vector(n,n,A,v);</p><p><b>　　}</

44、b></p><p>　　double **matrix_principal_eigen(const int n,double **A)</p><p><b>　　{</b></p><p>　　double *v=new double[n],**eig=new double*[2];//先定義兩個(gè)向量，分別存儲(chǔ)乘冪前后的迭代向量;&l

45、t;/p><p>　　eig[0]=new double[1];//存放主特征值;</p><p>　　eig[1]=new double[n];//存放主特征向量;</p><p>　　eig[0][0]=0;</p><p>　　for(int i=0;i<n;i++)eig[1][i]=1+i;//用（1,2,...,n)作為初始試探

46、向量v；</p><p>　　double old_lambda;</p><p>　　int index;//定義一個(gè)指標(biāo)變量，來(lái)提取乘冪后的最大分量指標(biāo)；</p><p>　　int step=0;</p><p><b>　　do{</b></p><p><b>　　step++

47、;</b></p><p>　　old_lambda=eig[0][0];</p><p>　　//double norm=vector_1_norm(n,eig[1]);//規(guī)范化，防止特征值大的時(shí)候計(jì)算機(jī)存儲(chǔ)有溢出；</p><p>　　double norm=vector_infty_norm(n,eig[1]);//規(guī)范化，防止特征值大的時(shí)候計(jì)算

48、機(jī)存儲(chǔ)有溢出；</p><p>　　for(i=0;i<n;i++)v[i]=eig[1][i]/norm;//更新；</p><p>　　eig[1]=square_matrix_multiply_vector(n,A,v);//乘冪；</p><p>　　index=vector_max_component(n,eig[1]);//提取最大分量指標(biāo)；<

49、;/p><p>　　eig[0][0]=eig[1][index]/v[index];//計(jì)算這次乘冪后最大分量與乘冪前該分量的比值；</p><p>　　//cout<<"第"<<step++<<"步，分量v["<<index<<"] = "<<v[index]

50、<<", vv["<<index<<"] = "<<vv[index]<<",主特征值lambda的近似值為："<<lambda<<endl;</p><p>　　//}while(fabs(vv[index])<vector_1_norm(n,vv)&&a

51、mp;fabs((lambda-old_lambda)/lambda)>1e-15&&step<10000);//x循環(huán)終止條件為三選一；</p><p>　　}while(fabs((eig[0][0]-old_lambda)/eig[0][0])>1e-8&&step<10000);//x循環(huán)終止條件為二選一；</p><p>　

52、　cout<<"經(jīng)過(guò)"<<step<<"步乘冪方法計(jì)算,得到主特征值近似值為:"<<eig[0][0]<<endl;</p><p>　　return eig;</p><p><b>　　}</b></p><p>　　void main()&

53、lt;/p><p><b>　　{</b></p><p>　　cout.precision(16);</p><p><b>　　int i,n;</b></p><p>　　cout<<"請(qǐng)輸入矩陣規(guī)模n:"<<endl;</p><p

54、><b>　　cin>>n;</b></p><p>　　double **A=new double*[n];</p><p>　　cout<<"請(qǐng)輸入 "<<n<<" X "<<n<<" 的矩陣元素："<<endl;&

55、lt;/p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　A[i]=new double[n];</p><p>　　for(int j=0;j<n;j++)cin>>A[i][j];</p><p><b>

56、;　　}</b></p><p>　　double **eig=matrix_principal_eigen(n,A);</p><p>　　cout<<"矩陣主特征值為："<<eig[0][0]<<endl;</p><p>　　cout<<"矩陣主特征向量為："&

57、lt;<endl;</p><p>　　for(i=0;i<n;i++)cout<<eig[1][i]<<endl;</p><p><b>　　}</b></p><p>　　程序（2）#include<math.h></p><p>　　#include<iost

58、ream.h></p><p>　　int vector_max_component(const int n,const double *v)</p><p><b>　　{</b></p><p>　　double max=fabs(v[0]);</p><p>　　for(int i=0,index=0;i&l

59、t;n;i++)if(max<fabs(v[i])){index=i;max=fabs(v[i]);}</p><p>　　return index;</p><p><b>　　}</b></p><p>　　double vector_inner_product(const int n,const double *u,const do

60、uble *v)</p><p><b>　　{</b></p><p>　　double value=0;</p><p>　　for(int i=0;i<n;i++)value+=u[i]*v[i];</p><p>　　return value;</p><p><b>　　

61、}</b></p><p>　　double vector_infty_norm(const int n,const double *v)</p><p><b>　　{</b></p><p>　　double value=fabs(v[0]);</p><p>　　for(int i=1;i<n;i

62、++)</p><p><b>　　{</b></p><p>　　if(value<fabs(v[i]))value=fabs(v[i]);</p><p><b>　　}</b></p><p>　　return value;</p><p><b>　　

63、}</b></p><p>　　double *matrix_multiply_vector(const int& m,const int& n,double **A,double *v)</p><p><b>　　{</b></p><p>　　double *vector;</p><p&g

64、t;　　vector=new double [m];</p><p>　　for(int i=0;i<m;i++)vector[i]=vector_inner_product(n,A[i],v);</p><p>　　return vector;</p><p><b>　　}</b></p><p>　　doub

65、le *square_matrix_multiply_vector(const int& n,double **A,double *v)</p><p><b>　　{</b></p><p>　　return matrix_multiply_vector(n,n,A,v);</p><p><b>　　}</b>

66、</p><p>　　double **matrix_principal_eigen(const int n,double **A)</p><p><b>　　{</b></p><p>　　double *v=new double[n],**eig=new double*[2];//先定義兩個(gè)向量，分別存儲(chǔ)乘冪前后的迭代向量;</p&

67、gt;<p>　　eig[0]=new double[1];//存放主特征值;</p><p>　　eig[1]=new double[n];//存放主特征向量;</p><p>　　eig[0][0]=0;</p><p>　　for(int i=0;i<n;i++)eig[1][i]=1;//用（1,2,...,n)作為初始試探向量v；<

68、;/p><p>　　double a,a0=0,a1=0,a2,lmd,lmd0=1;</p><p>　　int index;//定義一個(gè)指標(biāo)變量，來(lái)提取乘冪后的最大分量指標(biāo)；</p><p>　　for(i=0;i<100;i++)</p><p><b>　　{</b></p><p>　

69、　index=vector_max_component(n,eig[1]);</p><p>　　a=fabs(eig[1][index]);</p><p>　　for(int j=0;j<n;j++)eig[1][j]/=a;</p><p>　　eig[1]=square_matrix_multiply_vector(n,A,eig[1]);</p

70、><p>　　index=vector_max_component(n,eig[1]);</p><p>　　a2=fabs(eig[1][index]);</p><p>　　//lmd=a0-pow(a1-a0,2.0)/(2*a2-3*a1+a0);//New-Aitken method;</p><p>　　lmd=a0-pow(a1-a

71、0,2.0)/(a2-2*a1+a0);//Aitken method;</p><p>　　eig[0][0]=lmd;</p><p>　　cout<<"經(jīng)過(guò)"<<i<<"步計(jì)算，求得主特征值為："<<lmd<<endl;</p><p>　　if(fabs(lm

72、d-lmd0)<1e-8)break;</p><p><b>　　a0=a1;</b></p><p><b>　　a1=a2;</b></p><p><b>　　lmd0=lmd;</b></p><p><b>　　}</b></p&g

73、t;<p>　　return eig;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　cout.precision(16);</p><p><b>　　

74、int i,n;</b></p><p>　　cout<<"請(qǐng)輸入矩陣規(guī)模n:"<<endl;</p><p><b>　　cin>>n;</b></p><p>　　double **A=new double*[n];</p><p>　　cout&l

75、t;<"請(qǐng)輸入 "<<n<<" X "<<n<<" 的矩陣元素："<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　A[i]=new

76、double[n];</p><p>　　for(int j=0;j<n;j++)cin>>A[i][j];</p><p><b>　　}</b></p><p>　　double **eig=matrix_principal_eigen(n,A);</p><p>　　cout<<&qu

77、ot;矩陣主特征值為："<<eig[0][0]<<endl;</p><p>　　cout<<"矩陣主特征向量為："<<endl;</p><p>　　for(i=0;i<n;i++)cout<<eig[1][i]<<endl;</p><p><b&g

78、t;　　}</b></p><p>　　程序（3）#include<math.h></p><p>　　#include<iostream.h></p><p>　　int vector_max_component(const int n,const double *v)</p><p><b>

79、　　{</b></p><p>　　double max=fabs(v[0]);</p><p>　　for(int i=0,index=0;i<n;i++)if(max<fabs(v[i])){index=i;max=fabs(v[i]);}</p><p>　　return index;</p><p><b

80、>　　}</b></p><p>　　double vector_inner_product(const int n,const double *u,const double *v)</p><p><b>　　{</b></p><p>　　double value=0;</p><p>　　for(

81、int i=0;i<n;i++)value+=u[i]*v[i];</p><p>　　return value;</p><p><b>　　}</b></p><p>　　double vector_infty_norm(const int n,const double *v)</p><p><b>

82、;　　{</b></p><p>　　double value=fabs(v[0]);</p><p>　　for(int i=1;i<n;i++)</p><p><b>　　{</b></p><p>　　if(value<fabs(v[i]))value=fabs(v[i]);</p&

83、gt;<p><b>　　}</b></p><p>　　return value;</p><p><b>　　}</b></p><p>　　double *matrix_multiply_vector(const int& m,const int& n,double **A,double

84、 *v)</p><p><b>　　{</b></p><p>　　double *vector;</p><p>　　vector=new double [m];</p><p>　　for(int i=0;i<m;i++)vector[i]=vector_inner_product(n,A[i],v);<

85、;/p><p>　　return vector;</p><p><b>　　}</b></p><p>　　double *square_matrix_multiply_vector(const int& n,double **A,double *v)</p><p><b>　　{</b>&

86、lt;/p><p>　　return matrix_multiply_vector(n,n,A,v);</p><p><b>　　}</b></p><p>　　double **matrix_principal_eigen(const int n,double **A)</p><p><b>　　{</

87、b></p><p>　　double *v=new double[n],**eig=new double*[2];//先定義兩個(gè)向量，分別存儲(chǔ)乘冪前后的迭代向量;</p><p>　　eig[0]=new double[1];//存放主特征值;</p><p>　　eig[1]=new double[n];//存放主特征向量;</p><

88、p>　　eig[0][0]=0;</p><p>　　for(int i=0;i<n;i++)eig[1][i]=1;//用（1,2,...,n)作為初始試探向量v；</p><p>　　double a0=0,a1=0,a2,a3,lmd,lmd0=1;</p><p>　　int index;//定義一個(gè)指標(biāo)變量，來(lái)提取乘冪后的最大分量指標(biāo)；<

89、/p><p>　　double e=1e-14;</p><p>　　for(i=0;i<100;i++)</p><p><b>　　{</b></p><p>　　index=vector_max_component(n,eig[1]);</p><p>　　a0=eig[1][index]

90、;cout<<a0<<endl;</p><p>　　for(int j=0;j<n;j++)eig[1][j]/=a0;</p><p>　　eig[1]=square_matrix_multiply_vector(n,A,eig[1]);</p><p>　　index=vector_max_component(n,eig[1]);

91、</p><p>　　a1=eig[1][index];cout<<a1<<endl;</p><p>　　a2=(a0+a1)/2.0;cout<<a2<<endl;</p><p>　　for(j=0;j<n;j++)eig[1][j]/=a1;</p><p>　　eig[1]=sq

92、uare_matrix_multiply_vector(n,A,eig[1]);</p><p>　　index=vector_max_component(n,eig[1]);</p><p>　　a3=eig[1][index];</p><p>　　for(j=0;j<n;j++)eig[1][j]/=a3;</p><p>　　c

93、out<<a3<<endl;</p><p>　　//lmd=a0-pow(a1-a0,2.0)/(a3-2*a1+a0);//Aitken method;</p><p>　　lmd=a0-(a1-a0)*(a2-a0)/(a3+a0-a1-a2);//My method;</p><p>　　eig[0][0]=lmd;</p>

94、;<p>　　cout<<"經(jīng)過(guò)"<<i<<"步計(jì)算，求得主特征值為："<<lmd<<endl;</p><p>　　if(fabs(lmd-lmd0)<e)break;</p><p>　　lmd0=lmd;</p><p><b>

95、;　　}</b></p><p>　　return eig;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　cout.precision(16);</p>

96、<p><b>　　int i,n;</b></p><p>　　cout<<"請(qǐng)輸入矩陣規(guī)模n:"<<endl;</p><p><b>　　cin>>n;</b></p><p>　　double **A=new double*[n];</p&

97、gt;<p>　　cout<<"請(qǐng)輸入 "<<n<<" X "<<n<<" 的矩陣元素："<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p>

98、<p>　　A[i]=new double[n];</p><p>　　for(int j=0;j<n;j++)cin>>A[i][j];</p><p><b>　　}</b></p><p>　　double **eig=matrix_principal_eigen(n,A);</p><

99、p>　　cout<<"矩陣主特征值為："<<eig[0][0]<<endl;</p><p>　　cout<<"矩陣主特征向量為："<<endl;</p><p>　　for(i=0;i<n;i++)cout<<eig[1][i]<<endl;</p

100、><p><b>　　}</b></p><p>　　(四)改進(jìn)的Aitken加速算法的證明：</p><p><b>　　我們只需證明</b></p><p>　　以上證明用到了的假設(shè)，并且其結(jié)論是以此為基礎(chǔ)成立的，而這個(gè)假設(shè)我們認(rèn)為是不合適的（易知這樣的條件甚至?xí)?dǎo)致原來(lái)簡(jiǎn)單迭代序列的發(fā)散），這樣情

101、況下，討論迭代的加速顯然是不恰當(dāng)?shù)摹Ｒ虼?，我們?yōu)榱藢⒋怂惴ǜ纳?，結(jié)合參考文獻(xiàn)[7]中關(guān)于非線性方程迭代方法的加速技巧，給出了3.3.3算法。</p><p>　　致謝：本論文是在牛老師的悉心指導(dǎo)下完成的，牛老師對(duì)學(xué)術(shù)的嚴(yán)謹(jǐn)和精益求精的工作作風(fēng)給我留下了深刻的印象。從選題后的題目分析到開題報(bào)告，從寫作提綱，再到畢業(yè)論文的編寫、修改，每一步都有牛老師的細(xì)心指導(dǎo)和認(rèn)真解析，在此我表示衷心的感謝。</p>

102、<p>　　四年大學(xué)生活即將結(jié)束，回顧幾年的歷程，老師們給了我們很多指導(dǎo)和幫助。他們嚴(yán)謹(jǐn)?shù)闹螌W(xué)，優(yōu)良的作風(fēng)和敬業(yè)的態(tài)度，為我們樹立了為人師表的典范。在此，我對(duì)所有數(shù)信學(xué)院的老師表示感謝，祝您們身體健康，工作順利！</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]徐樹方，高立，張平文.數(shù)值線性代數(shù)[M].北京大學(xué)出版社.2000.<

103、;/p><p>　　[2]曹志浩.矩陣特征值問題[M].上?？茖W(xué)技術(shù)出版社.1980.</p><p>　　[3]王萼方，石生明.高等代數(shù)(第三版)[M].高等教育出版社.2003.</p><p>　　[4]華東師范大學(xué)師范系.數(shù)學(xué)分析(第三版)[M].高等教育出版社.2001.</p><p>　　[5]李慶揚(yáng)，王能超，易大義.數(shù)值分析(第四

104、版)[M].華中科技大學(xué)出版社.1982.</p><p>　　[6]王小平 ,劉峰.一種改進(jìn)的Aitken加速算法[J].2009,9(22),6859-6860.</p><p>　　[7]胡邵勇，儀維憲，宋福香.解非線性方程的一種新算法[J].1997,18(4),54-58.</p><p>　　Power method to solve the matri

105、x main eigenvalue’s acceleration method</p><p><b>　　Fu Peng</b></p><p>　　School of Mathematics and Information Science, Henan Polytechnic University</p><p>　　Abstract:Re

106、search of this paper is through the power method for solving matrix eigenvalue and eigenvector. There are many need in physics, mechanics and engineering we find the according to the modulus maximum characteristic value

107、of matrix eigenvalues (and said) and the feature vector. Power method is to calculate the modulus maximum eigenvalue of a matrix and the corresponding eigenvector of an iterative method. Its biggest advantage is simple,