線性方程組的簡單迭代法

線性方程組的簡單迭代法第一頁，共三十二頁，2022年，8月28日引言3.1簡單迭代法考慮線性方程組（1.1）其中

為非奇異矩陣，當為低階稠密矩陣時，第2章所討論的選主元消去法是有效方法.但對于的階數(shù)很大，零元素較多的大型稀疏矩陣方程組，利用迭代法求解則更為合適.

迭代法通常都可利用中有大量零元素的特點.

第二頁，共三十二頁，2022年，8月28日兩個簡單的例子例1已知

，任取

，則由

例2已知方程

在

附近有根.那么我們就能從

開始，通過迭代公式

逐步得到所要求的根.

假定我們已會計算第三頁，共三十二頁，2022年，8月28日

例1求解方程組（1.2）記為,方程組的精確解是.其中現(xiàn)將(1.2)改寫為第四頁，共三十二頁，2022年，8月28日（1.3）或?qū)憺?其中第五頁，共三十二頁，2022年，8月28日將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足).任取初始值，例如取再將分量代入(1.3)式右邊得到，反復利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式)得到新的值第六頁，共三十二頁，2022年，8月28日（1.4）簡寫為其中表示迭代次數(shù)迭代到第10次有第七頁，共三十二頁，2022年，8月28日從此例看出，由迭代法產(chǎn)生的向量序列逐步逼近方程組的精確解.第八頁，共三十二頁，2022年，8月28日迭代法的基本思想是構造一個向量序列{X(k)}，使其收斂到某個極限向量X*，而X*就是AX=b的準確解。問題：如何構造迭代序列？迭代序列在什么情況下收斂？

第九頁，共三十二頁，2022年，8月28日簡單迭代法的迭代格式n階線性代數(shù)方程組a11x1+a12x2+.…..+a1nxn=b1a21x1+a22x2+.…..+a2nxn=b2

……an1x1+an2x2+.…..+annxn=bn若用矩陣和向量的記號來表示，可寫成AX=b第十頁，共三十二頁，2022年，8月28日設,并將寫為三部分

迭代矩陣第十一頁，共三十二頁，2022年，8月28日易知，雅各布（Jacobi）迭代有A=D-L-UL+U=D-AG為迭代矩陣第十二頁，共三十二頁，2022年，8月28日第十三頁，共三十二頁，2022年，8月28日的雅可比(Jacobi)迭代公式如下:研究雅可比迭代法的分量計算公式.記或第十四頁，共三十二頁，2022年，8月28日于是，解的雅可比迭代法的分量計算公式為第十五頁，共三十二頁，2022年，8月28日方程組的迭代式的展開式如下：第十六頁，共三十二頁，2022年，8月28日第十七頁，共三十二頁，2022年，8月28日由可知計算過程可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.第十八頁，共三十二頁，2022年，8月28日例1

用J法求解線性方程組方程組的精確解為x*=(1,1,1)T.

解：第十九頁，共三十二頁，2022年，8月28日取初始向量x(0)=(0,0,0)T,迭代可得計算結果列表如下:第二十頁，共三十二頁，2022年，8月28日kx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可見,迭代7次使得迭代序列逐次收斂于方程組的解,。第二十一頁，共三十二頁，2022年，8月28日簡單迭代法的算法如下：輸入矩陣A，右端項b，維數(shù)n，初始迭代向量X(0),容許誤差e，容許最大迭代次數(shù)N。置k=1。對i=1,2,…,n若，輸出X，停機，否則轉(zhuǎn)5。若，轉(zhuǎn)3；否則輸出失敗信息，停機。第二十二頁，共三十二頁，2022年，8月28日對于任何由變形得到的等價方程組，迭代法產(chǎn)生的向量序列不一定都能逐步逼近方程組的解.如對方程組第二十三頁，共三十二頁，2022年，8月28日一般迭代法收斂性的基本定理迭代法的收斂性設其中為非奇異矩陣，記為精確解，于是且設有等價的方程組（2.1）第二十四頁，共三十二頁，2022年，8月28日設有解的迭代法問題是：迭代矩陣滿足什么條件時，由迭代法產(chǎn)生的向量序列收斂到引進誤差向量由(2.1)式減(2.2)式得到誤差向量的遞推公式（2.2）第二十五頁，共三十二頁，2022年，8月28日因此，研究迭代法(2.2)收斂性問題就是要研究迭代矩陣滿足什么條件時，有設有矩陣序列,如果個數(shù)列極限存在且有則稱收斂于，記為定義1第二十六頁，共三十二頁，2022年，8月28日

定理1（2.3）(迭代法基本定理)設有方程組及一階定常迭代法（2.4）對任意選取初始向量，矩陣的譜半徑迭代法(2.4)收斂的充要條件是所謂“譜半徑”，就是最大特征值（對于實數(shù)而言）,如果是特征值是復數(shù)的話，譜半徑就是特征值的最大模。第二十七頁，共三十二頁，2022年，8月28日

推論設，其中為非奇異矩陣且非奇異，則(1)解方程組的雅可比迭代法收斂的充要條件是，其中定義2：若n階矩陣A=(aij)滿足:則稱矩陣A是嚴格對角占優(yōu)矩陣.定理2設A是嚴格對角占優(yōu)矩陣,則解線性方程組Ax=b的J迭代法收斂.第二十八頁，共三十二頁，2022年，8月28日計算機實現(xiàn)程序用雅各比迭代法下面線性方程組

第二十九頁，共三十二頁，2022年，8月28日#include<stdio.h>#include<math.h>#defineeps1e-3#definemax100voidJacobi(float*a,intn,floatx[]){ inti,j,k=0; doubleepsilon,s; double*y=newdouble[n]; for(i=0;i<n;i++)x[i]=0; while(1) { epsilon=0; k++; for(i=0;i<n;i++) { s=0; for(j=0;j<n;j++) { if(j==i)continue; s+=*(a+i*(n+1)+j)*x[j]; } y[i]=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i)); epsilon+=fabs(y[i]-x[i]); } for(i=0;i<n;i++)x[i]=y[i]; if(epsilon<eps) {printf("迭代次數(shù)為:%d\n",k);return;} if(k>=max) {printf("迭代發(fā)散");return;} }deletey;}第三十頁，共三十二頁，2022年，8月28日voidmain(){ inti; floata[4][5]={10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25}; /*floata[9][10]={31,-13,0,0,0,-10,0,0,0,-15, -13,35,-9,0,-11,0,0,0,0,27, 0,-9,31,-10,0,0,0,0,0,-23, 0,0,-10,79,-30,0,0,0,-9,0, 0,0,0,-30,57,-7,0,-5,0,-20, 0,0,0,0,7,47,-30,0,0,12, 0,0,0,0,0,-30,41,0,0,-7, 0,0,0,0,-5,0,0,27,-2,7,