線性方程組的簡單迭代法

線性方程組的簡單迭代法第1頁，共32頁，2023年，2月20日，星期六引言3.1簡單迭代法考慮線性方程組（1.1）其中

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

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

第2頁，共32頁，2023年，2月20日，星期六兩個簡單的例子例1已知

，任取

，則由

例2已知方程

在

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

開始，通過迭代公式

逐步得到所要求的根.

假定我們已會計算第3頁，共32頁，2023年，2月20日，星期六

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

第9頁，共32頁，2023年，2月20日，星期六簡單迭代法的迭代格式n階線性代數(shù)方程組a11x1+a12x2+.…..+a1nxn=b1a21x1+a22x2+.…..+a2nxn=b2

……an1x1+an2x2+.…..+annxn=bn若用矩陣和向量的記號來表示，可寫成AX=b第10頁，共32頁，2023年，2月20日，星期六設(shè),并將寫為三部分

迭代矩陣第11頁，共32頁，2023年，2月20日，星期六易知，雅各布（Jacobi）迭代有A=D-L-UL+U=D-AG為迭代矩陣第12頁，共32頁，2023年，2月20日，星期六第13頁，共32頁，2023年，2月20日，星期六的雅可比(Jacobi)迭代公式如下:研究雅可比迭代法的分量計算公式.記或第14頁，共32頁，2023年，2月20日，星期六于是，解的雅可比迭代法的分量計算公式為第15頁，共32頁，2023年，2月20日，星期六方程組的迭代式的展開式如下：第16頁，共32頁，2023年，2月20日，星期六第17頁，共32頁，2023年，2月20日，星期六由可知計算過程可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.第18頁，共32頁，2023年，2月20日，星期六例1

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

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

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

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

第29頁，共32頁，2023年，2月20日，星期六#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;}第30頁，共32頁，2023年，2月20日，星期六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,