第四章 線性方程組的迭代解法

第四章線性方程組的迭代解法第一頁，共四十七頁，2022年，8月28日迭代法的基本思想Jacobi迭代和Gauss－Seidel迭代迭代法的收斂性超松弛迭代第四章線性方程組的迭代解法第二頁，共四十七頁，2022年，8月28日4.1迭代法的基本思想：例：求解方程組其精確解是x*=(3,2,1)T。現(xiàn)將原方程組改寫為簡寫為x=B0x+f，其中第三頁，共四十七頁，2022年，8月28日任取初始值，如取x(0)=(0,0,0)T，代入x=B0x+f右邊，若等式成立則求得方程組的解，否則，得新值x(1)=(x1(1),x2(1),x3(1))T=(2.5,3,3)T，再將x(1)代入，反復(fù)計(jì)算，得一向量序列{x(k)}和一般的計(jì)算公式（迭代公式）：簡寫為x(k+1)=B0x(k)+f

k=0,1,2,……x(10)=(3.000032,1.999838,0.999813)T迭代到第10次時(shí)有||ε(10)||

∞=||x(10)–x*||=0.000187第四頁，共四十七頁，2022年，8月28日定義：（1）對于給定方程組x=Bx+f，用迭代公式x(k+1)=Bx(k)+f

(k=0,1,2,……)逐步代入求近似解的方法稱迭代法；（2）若k∞時(shí)limx(k)存在（記為x*），稱此迭代法收斂，顯然x*就是方程組的解，否則稱迭代法發(fā)散；（3）B稱為迭代矩陣。問題：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？第五頁，共四十七頁，2022年，8月28日設(shè)Ax=b，A非奇異，且對角元不為零，將原方程組改寫為4.2Jacobi迭代與Gauss－Seidel迭代4.2.1Jacobi迭代法第六頁，共四十七頁，2022年，8月28日又代入，反復(fù)繼續(xù)，得迭代格式：稱Jacobi迭代法。選取初始向量代入上面方程組右端得第七頁，共四十七頁，2022年，8月28日J(rèn)acobi迭代法的矩陣表示：第八頁，共四十七頁，2022年，8月28日故計(jì)算公式為：(i=1,2,……,n)，(k=0,1,2,……表迭代次數(shù))矩陣表示：第九頁，共四十七頁，2022年，8月28日則BJ=I-D-1

A =D-1(L+U)，

fJ=D-1b，稱BJ為Jacobi迭代矩陣。（aii≠0）將方程組Ax＝b的系數(shù)矩陣A分解為：A=D-L-U第十頁，共四十七頁，2022年，8月28日例1:用Jacobi迭代法求解方程組,誤差不超過10-4。解:第十一頁，共四十七頁，2022年，8月28日第十二頁，共四十七頁，2022年，8月28日第十三頁，共四十七頁，2022年，8月28日依此類推,得方程組滿足精度的解為x12迭代次數(shù)：12次

x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-005第十四頁，共四十七頁，2022年，8月28日若在迭代時(shí)盡量利用最新信息，則可將迭代格式變?yōu)?.2.2Gauss－Seidel迭代法稱Gauss－Seidel迭代法。第十五頁，共四十七頁，2022年，8月28日計(jì)算公式：（i=2,3,……,n-1）(i=1,2,…,n)即第十六頁，共四十七頁，2022年，8月28日其中BG-S=(D-L)-1

U稱Gauss－Seidel迭代矩陣。(D–L)x(k+1)=b＋

Ux(k)故Gauss－Seidel迭代格式：第十七頁，共四十七頁，2022年，8月28日例2.用Gauss-Seidel迭代法求解例1.解:第十八頁，共四十七頁，2022年，8月28日x1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005通過迭代,至第7步得到滿足精度的解x7：從例1和例2可以看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快。Jacobi迭代法和Gauss-Seidel迭代法統(tǒng)稱為簡單迭代法。第十九頁，共四十七頁，2022年，8月28日J(rèn)acobi迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];y=x;fork=1:6fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=t;y(i)=(b(i)-s)/A(i,i);endx=yend0.77780.80000.86670.96300.96440.97190.99290.99350.99520.99870.99880.99910.99980.99980.99981.00001.00001.0000第二十頁，共四十七頁，2022年，8月28日Gauss-Seidel迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];n=length(b);x=b;er=1;k=0;whileer>0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endxend3.11112.41111.23481.18291.04181.01501.00631.00211.00061.00031.00011.00001.00001.00001.00001.00001.00001.0000第二十一頁，共四十七頁，2022年，8月28日4.3迭代法的收斂性設(shè)解線性方程組的迭代格式將上面兩式相減,得而方程組的精確解為X*，則第二十二頁，共四十七頁，2022年，8月28日則因此迭代法收斂的充要條件可轉(zhuǎn)變?yōu)橐恚旱袷绞諗康某湟獥l件為第二十三頁，共四十七頁，2022年，8月28日定理：迭代格式收斂的充要條件為迭代矩陣的譜半徑(B)<1。證:對任何n階矩陣B，都存在非奇矩陣P，使

B=P–1JP其中，J為B的Jordan標(biāo)準(zhǔn)型。其中,Ji

為Jordan塊第二十四頁，共四十七頁，2022年，8月28日其中,λi

是矩陣B的特征值,由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f

收斂<=>(i=1,2,···,r)(i=1,2,···,r)譜半徑(B)<1第二十五頁，共四十七頁，2022年，8月28日定理：設(shè)x*為方程組Ax=b的解，若||B||<1,則 對迭代格式x(k+1)=Bx(k)+f

，有（1）（2）推論若||B||<1，則迭代法x(k+1)=Bx(k)+f

收斂。（因?yàn)?B)≤||B||）第二十六頁，共四十七頁，2022年，8月28日證由||B||<1,有||x(k+1)–x(k)||=||(x*–x(k))–(x*–

x(k+1))||≥||(x*–x(k))||–||(x*–

x(k+1))||

≥||(x*–x(k))||–||B||||(x*–

x(k))||=(1-||B||)||(x*–

x(k))||所以||x(k+1)–x*||≤||B||||x(k)–x*||x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(k)–x*

)第二十七頁，共四十七頁，2022年，8月28日所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1)

)||x(k+1)–x(k)||≤||B||||x(k)–x(k-1)||故可得誤差估計(jì)式:第二十八頁，共四十七頁，2022年，8月28日注：

（1）式說明，只要||B||不是很接近1，當(dāng)X(k+1)

和X(k)

很接近時(shí)，X(k)

也越接近X*，故可用||

X(k+1)

-X(k)

||中止迭代。（2）式說明，||B||越小，X(k)

收斂越快，可作誤差估計(jì)式。第二十九頁，共四十七頁，2022年，8月28日例3.判別下列方程組用Jacobi法和Gauss-Seidel法求解是否收斂:解:(1)求Jacobi法的迭代矩陣第三十頁，共四十七頁，2022年，8月28日所以即Jaobi迭代法收斂。(2)求Gauss-Seidel法的迭代矩陣：顯然BJ的幾種常用算子范數(shù)||BJ||>1，故用其特征值判斷。第三十一頁，共四十七頁，2022年，8月28日所以Gauss-Seidel迭代法發(fā)散。注：在例1和例2中,Gauss-Seidel迭代法收斂速度比Jacobi迭代法要高，但例3卻說明Gauss-Seidel迭代法發(fā)散時(shí)而Jacobi迭代法卻收斂，因此,不能說Gauss-Seidel迭代法比Jacobi迭代法更好?？傻霉实谌摚菜氖唔?，2022年，8月28日定義設(shè)A=(aij)n×nRn×n

，若 (i=1,2,…,n)則稱A為對角占優(yōu)矩陣，若不等式嚴(yán)格成立，則稱A為嚴(yán)格對角占優(yōu)矩陣。迭代法收斂的其他結(jié)論：定理若Ax=b中A為嚴(yán)格對角占優(yōu)矩陣，則Jacobi迭代和Gauss－Seidel迭代均收斂。證明：因?yàn)橄禂?shù)矩陣A嚴(yán)格對角占優(yōu)，所以第三十三頁，共四十七頁，2022年，8月28日故Jacobi迭代法收斂(1)對于Jacobi迭代法,其迭代矩陣為第三十四頁，共四十七頁，2022年，8月28日即從而因此由于可得(2)對于G—S迭代法,其迭代矩陣為第三十五頁，共四十七頁，2022年，8月28日矛盾由前述定理知，G—S迭代法收斂定理若A為對稱正定陣，則Gauss－Seidel迭代收斂。第三十六頁，共四十七頁，2022年，8月28日考慮解線性方程組的Gauss-Seidel迭代法4.4超松弛迭代法（SOR）－迭代法的加速第三十七頁，共四十七頁，2022年，8月28日令因此第三十八頁，共四十七頁，2022年，8月28日上式稱為逐次超松弛法(SOR迭代法),由G-S迭代法的矩陣形式第三十九頁，共四十七頁，2022年，8月28日第四十頁，共四十七頁，2022年，8月28日上式為逐次超松弛法(SOR迭代法)的矩陣形式令第四十一頁，共四十七頁，2022年，8月28日SOR法化為G-S迭代法G-S法為SOR法的特例,SOR法為G-S法的加速例1.用G-S法和SOR法求下列方程組的解,要求精度1e-6第四十二頁，共四十七頁，2022年，8月28日解:(1)G-S迭代法第四十三頁，共四十七頁，2022年，8月28日

1110.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431……….0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946k=71x=0.9999950.9999941.999995滿足精度的解迭代次數(shù)為