線性方程組的解法第1頁，共37頁。線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其重要的地位。線性方程組的解法大致分為迭代法與直接法兩大類雅可比(Jacobi)迭代法舉例說明雅可比迭代法的基本思路例4.1特點(diǎn):系數(shù)矩陣主對角元均不為零第2頁，共37頁。取迭代初值x1(0)=0，x2(0)=0，x3(0)=0將方程改寫成如下等價(jià)形式據(jù)此建立迭代公式第3頁，共37頁。x(0)000x(1)

0.77780.80000.8667x(2)0.96300.96440.9778x(3)0.99290.99350.9952x(4)········0.99870.99880.9991x1*＝1.0000，x2*＝1.0000，x3*＝1.0000準(zhǔn)確解可以看出，迭代每前進(jìn)一步，結(jié)果就逼近準(zhǔn)確解一步迭代過程收斂第4頁，共37頁。矩陣形式:以上這種迭代方法稱雅可比(Jacobi)迭代法?；舅枷耄簩⒎匠探M的求解問題轉(zhuǎn)化為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式。第5頁，共37頁。(i=1,2,···,n;k=0,1,2,···)(i=1,2,···,n)設(shè)有方程組將第i個(gè)方程的第i個(gè)變量xi分離出來，據(jù)此建立分量形式的雅可比迭代公式如果第6頁，共37頁。用矩陣形式來表示雅可比迭代公式設(shè)有方程組:AX=b其中A＝(aij)n為非奇異矩陣，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，唯一解為X*=(x1*,x2*,···,xn*)T將A分解為：A＝U+D+L其中第7頁，共37頁。于是(U+D+L)X=b得X＝－D－(U+L)X+D－b據(jù)此得矩陣形式的雅可比迭代公式X(k+1)＝－D－(U+L)X(k)+D－b記B＝－D－(U+L)，f＝D－b有B：迭代矩陣(k=0,1,2,······)X(k+1)=BX(k)+f任取X(0),迭代計(jì)算產(chǎn)生向量序列:若則迭代過程收斂。x*是方程組Ax=b的解X(1),X(2),······,X(k),······第8頁，共37頁。迭代法適用于解大型稀疏方程組(萬階以上的方程組,系數(shù)矩陣中零元素占很大比例,而非零元按某種模式分布)背景:電路分析、邊值問題的數(shù)值解和數(shù)學(xué)物理方程問題:(1)如何構(gòu)造迭代格式？(2)迭代格式是否收斂？(3)收斂速度如何？(4)如何進(jìn)行誤差估計(jì)？第9頁，共37頁。高斯塞德爾Gauss-Seidel迭代法Gauss-Seidel迭代法是通過對Jacobi迭代法稍加改進(jìn)得到的。Jacobi迭代法的每一步迭代新值x(k+1)=[x1(k+1),x2(k+1),

···,xn(k+1)]T

都是用前一步的舊值x(k)=[x1(k),x2(k),

···,xn(k)]T的全部分量計(jì)算出來的。那么在計(jì)算第i個(gè)分量xi(k+1)時(shí)，已經(jīng)計(jì)算出x1(k+1),x2(k+1),···,xi-1(k+1)(i-1)個(gè)分量，這些分量新值沒用在計(jì)算xi(k+1)上。將這些第10頁，共37頁。(i=1,2,…,n)(i=1,2,···,n;k=0,1,2,···)將這些分量利用起來，有可能得到一個(gè)收斂更快的迭代公式。具體作法：將分量形式的雅可比迭代公式右端前(i-1)個(gè)分量的上標(biāo)為k換成k+1，即分量形式的高斯-塞德爾迭代公式。第11頁，共37頁。用矩陣形式來表示高斯-塞德爾迭代公式DX(k+1)＝b-LX(k+1)-UX(k)即(D+L)X(k+1)＝-UX(k)+b如果(D+L)－存在，則X(k+1)＝－(D+L)－UX(k)+

(D+L)－b記B＝(D+L)－，f＝(D+L)－b則(k=0,1,2,···)X(k+1)=BX(k)+f矩陣形式的高斯-塞德爾迭代公式。B：迭代矩陣第12頁，共37頁。例第13頁，共37頁。例第14頁，共37頁。第15頁，共37頁。Jacobi迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];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)=t;y(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-y(i)),er);endx=y;x'end0.77780.80000.86670.96300.96440.97190.99290.99350.99520.99870.99880.99910.99980.99980.99981.00001.00001.00001.00001.00001.0000第16頁，共37頁。Gauss-Seidel迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];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);endx'end0.77780.87780.97700.98390.99610.99870.99940.99980.99991.00001.00001.00001.00001.00001.0000第17頁，共37頁。從計(jì)算結(jié)果可以明顯看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。一般而言，Gauss-Seidel迭代法收斂速度比Jacobi迭代法快，但這兩種迭代法的收斂范圍并不完全重合，而只是部分相交，有的時(shí)候Jacobi迭代法可能比Gauss-Seidel迭代法收斂速度更快。甚至可以舉出Jacobi迭代法收斂而Gauss-Seidel迭代法發(fā)散的例子。第18頁，共37頁。Gauss-Seidel迭代法和Jacobi迭代法的異同：Jacobi迭代法：公式簡單，每次只需做矩陣和向量的一次乘法；特別適合于并行計(jì)算；不足之處：需存放X(k)和X(k+1)兩個(gè)存儲空間。Gauss-Seidel迭代法：只需一個(gè)向量存儲空間，一旦計(jì)算出了xj(k+1)立即存入xj(k)的位置，可節(jié)約一套存儲單元；有時(shí)起到加速收斂的作用。是一種典型的串行算法，每次迭代中必須依次計(jì)算解的各個(gè)分量。第19頁，共37頁。超松馳(SOR)迭代法超松馳迭代法是迭代方法的一種加速方法，其計(jì)算公式簡單，但需要選擇合適的松馳因子，以保證迭代過程有較快的收斂速度。設(shè)有方程組AX=b其中A＝(aij)n為非奇異矩陣，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，記X(k)為第k步迭代近似值，則

r(k)=b－AX(k）表示近似解X(k)的殘余誤差，引進(jìn)如下形式的加速迭代公式第20頁，共37頁。X(k+1)＝X(k)+w(b－AX)w稱作松馳因子。其分量形式為選擇適當(dāng)?shù)乃神Y因子，可期望獲得較快的收斂速度。如果在計(jì)算分量xi(k+1)時(shí)，考慮利用已經(jīng)計(jì)算出來的分量x1(k+1),x2(k+1),···,xi-1(k+1)，又可得到一個(gè)新的迭代公式特別當(dāng)aii≠0時(shí)，將上面迭代公式應(yīng)用于方程組(i=1,2,···,n)第21頁，共37頁。由此得下列超松馳(SOR)迭代公式(i=1,2,···,n;k=0,1,2,3,··········)當(dāng)w>1時(shí)，稱超松馳法；當(dāng)w<1時(shí)，稱低松馳法；當(dāng)w＝1時(shí)，就是Gauss-Seidel迭代公式。所以超松馳(SOR)迭代法可以看成是Gauss-Seidel迭代法的加速，而Gauss-Seidel迭代法是超松馳方法的特例。第22頁，共37頁。定理4.8若A是對稱正定矩陣,則當(dāng)0<w<2時(shí)SOR迭代法解方程組Ax=b是收斂的定理4.9若A是嚴(yán)格對角占優(yōu)矩陣,則當(dāng)0<w<1時(shí)SOR迭代法解方程組Ax=b

是收斂的第23頁，共37頁。例4.3用SOR方法解方程組(w=1.4)w=input('input:w:=');A=[2-10;-12-1;0-12];b=[1;0;1.8];x=[1;1;1];er=1;k=0;whileer>0.0005er=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)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendkk=10x=1.19991.39991.5999ω=1.2,只需k=6第24頁，共37頁。塊迭代法簡介設(shè)A∈Rn×n,x∈Rn,b∈Rn將方程組Ax=b中系數(shù)矩陣A分塊其中,Aii∈Rni×ni,Aij∈Rni×nj

,xi∈Rni,bi∈Rni第25頁，共37頁。將A分解,A=DB–LB–UB

Jacobi塊迭代DBx(k+1)=(LB+UB)x(k)+bi=1,2,···,r(2)Gauss-Seidel塊迭代DBx(k+1)=LBx(k+1)+UBx(k)+bi=1,2,···,r第26頁，共37頁。迭代法的收斂性Convergenceofiterativemethod迭代矩陣譜半徑Spectralradius對角占優(yōu)矩陣diagonallydominantmatrix

第27頁，共37頁。原始方程:Ax=b迭代格式:x(k+1)=Bx(k)+f定理4.1(迭代法基本定理)迭代法x(k+1)=Bx(k)+f收斂的充要條件是ρ(B)<1迭代法有著算法簡單，程序設(shè)計(jì)容易以及可節(jié)省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn)。但是迭代法也存在著收斂性和收斂速度等方面的問題。因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的。第28頁，共37頁。證對任何n階矩陣B都存在非奇矩陣P使B=P–1JP其中,J

為B的Jordan標(biāo)準(zhǔn)型其中,Ji為Jordan塊其中,λi是矩陣B的特征值,由B=P–1JP第29頁，共37頁。Bk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f收斂<=>(i=1,2,···,r)(i=1,2,···,r)譜半徑

(B)<1第30頁，共37頁。例線性方程組Ax=b,分別取系數(shù)矩陣為試分析Jacobi迭代法和Seidel迭代法的斂散性(1)第31頁，共37頁。(2)A2=[2,-1,1;1,1,1;1,1,-2]第32頁，共37頁。兩種迭代法之間沒有直接聯(lián)系對矩陣A1,求A1x=b

的Jacobi迭代法收斂,而Ga