線性方程組的解法

線性方程組的解法解線性方程組的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss-Seidel迭代迭代法的矩陣表示MatrixformoftheIterativeMethods線性方程組的解法線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其重要的地位。線性方程組的解法大致分為迭代法與直接法兩大類雅可比(Jacobi)迭代法舉例說(shuō)明雅可比迭代法的基本思路例4.1特點(diǎn):系數(shù)矩陣主對(duì)角元均不為零線性方程組的解法取迭代初值x1(0)=0，x2(0)=0，x3(0)=0將方程改寫(xiě)成如下等價(jià)形式據(jù)此建立迭代公式線性方程組的解法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)確解一步

迭代過(guò)程收斂線性方程組的解法矩陣形式:以上這種迭代方法稱雅可比(Jacobi)迭代法?；舅枷耄簩⒎匠探M的求解問(wèn)題轉(zhuǎn)化為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式。線性方程組的解法(i=1,2,···,n;k=0,1,2,···)(i=1,2,···,n)設(shè)有方程組將第i個(gè)方程的第i個(gè)變量xi分離出來(lái)，據(jù)此建立分量形式的雅可比迭代公式如果線性方程組的解法用矩陣形式來(lái)表示雅可比迭代公式設(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其中線性方程組的解法于是(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)生向量序列:若則迭代過(guò)程收斂。x*是方程組Ax=b

的解X(1),X(2),······,X(k),······線性方程組的解法線性方程組的解法迭代法適用于解大型稀疏方程組(萬(wàn)階以上的方程組,系數(shù)矩陣中零元素占很大比例,而非零元按某種模式分布)背景:電路分析、邊值問(wèn)題的數(shù)值解和數(shù)學(xué)物理方程問(wèn)題:(1)如何構(gòu)造迭代格式？

(2)迭代格式是否收斂？

(3)收斂速度如何？

(4)如何進(jìn)行誤差估計(jì)？線性方程組的解法高斯塞德?tīng)朑auss-Seidel迭代法Gauss-Seidel迭代法是通過(guò)對(duì)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ì)算出來(lái)的。那么在計(jì)算第i個(gè)分量xi(k+1)時(shí)，已經(jīng)計(jì)算出

x1(k+1),x2(k+1),···,xi-1(k+1)(i-1)個(gè)分量，這些分量新值沒(méi)用在計(jì)算xi(k+1)上。將這些線性方程組的解法(i=1,2,…,n)(i=1,2,···,n;k=0,1,2,···)將這些分量利用起來(lái)，有可能得到一個(gè)收斂更快的迭代公式。具體作法：將分量形式的雅可比迭代公式右端前(i-1)個(gè)分量的上標(biāo)為k換成k+1，即分量形式的高斯-塞德?tīng)柕?。線性方程組的解法用矩陣形式來(lái)表示高斯-塞德?tīng)柕紻X(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矩陣形式的高斯-塞德?tīng)柕?。B：迭代矩陣線性方程組的解法例線性方程組的解法例線性方程組的解法線性方程組的解法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線性方程組的解法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線性方程組的解法從計(jì)算結(jié)果可以明顯看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。一般而言，Gauss-Seidel迭代法收斂速度比Jacobi迭代法快，但這兩種迭代法的收斂范圍并不完全重合，而只是部分相交，有的時(shí)候Jacobi迭代法可能比Gauss-Seidel迭代法收斂速度更快。甚至可以舉出Jacobi迭代法收斂而Gauss-Seidel迭代法發(fā)散的例子。線性方程組的解法Gauss-Seidel迭代法和Jacobi迭代法的異同：Jacobi迭代法：公式簡(jiǎn)單，每次只需做矩陣和向量的一次乘法；特別適合于并行計(jì)算；不足之處：需存放X(k)和X(k+1)兩個(gè)存儲(chǔ)空間。Gauss-Seidel迭代法：只需一個(gè)向量存儲(chǔ)空間，一旦計(jì)算出了xj(k+1)立即存入xj(k)的位置，可節(jié)約一套存儲(chǔ)單元；有時(shí)起到加速收斂的作用。是一種典型的串行算法，每次迭代中必須依次計(jì)算解的各個(gè)分量。線性方程組的解法超松馳(SOR)迭代法超松馳迭代法是迭代方法的一種加速方法，其計(jì)算公式簡(jiǎn)單，但需要選擇合適的松馳因子，以保證迭代過(guò)程有較快的收斂速度。設(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)如下形式的加速迭代公式線性方程組的解法X(k+1)＝X(k)+w(b－AX)w稱作松馳因子。其分量形式為選擇適當(dāng)?shù)乃神Y因子，可期望獲得較快的收斂速度。如果在計(jì)算分量xi(k+1)時(shí)，考慮利用已經(jīng)計(jì)算出來(lái)的分量x1(k+1),x2(k+1),···,xi-1(k+1)，又可得到一個(gè)新的迭代公式特別當(dāng)aii≠0時(shí)，將上面迭代公式應(yīng)用于方程組(i=1,2,···,n)線性方程組的解法由此得下列超松馳(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迭代法是超松馳方法的特例。線性方程組的解法定理4.8

若A是對(duì)稱正定矩陣,則當(dāng)0<w<2時(shí)SOR迭代法解方程組Ax=b是收斂的定理4.9

若A是嚴(yán)格對(duì)角占優(yōu)矩陣,則當(dāng)0<w<1時(shí)SOR迭代法解方程組Ax=b

是收斂的線性方程組的解法例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線性方程組的解法

塊迭代法簡(jiǎn)介設(shè)A∈Rn×n,x∈Rn,b∈Rn將方程組Ax=b中系數(shù)矩陣A分塊其中,Aii∈Rni×ni,Aij∈Rni×nj

,xi∈Rni,bi∈Rni線性方程組的解法將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線性方程組的解法迭代法的收斂性Convergenceofiterativemethod迭代矩陣譜半徑Spectralradius對(duì)角占優(yōu)矩陣diagonallydominantmatrix

線性方程組的解法原始方程:Ax=b迭代格式:x(k+1)=Bx(k)+f定理4.1(迭代法基本定理)迭代法x(k+1)=Bx(k)+f收斂的充要條件是

ρ(B)<1迭代法有著算法簡(jiǎn)單，程序設(shè)計(jì)容易以及可節(jié)省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn)。但是迭代法也存在著收斂性和收斂速度等方面的問(wèn)題。因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的。線性方程組的解法證對(duì)任何n階矩陣B都存在非奇矩陣P使

B=P–1JP其中,J

為B的Jordan標(biāo)準(zhǔn)型其中,Ji

為Jordan塊其中,λi

是矩陣B的特征值,由B=P–1JP線性方程組的解法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線性方程組的解法例線性方程組Ax=b,分別取系數(shù)矩陣為試分析Jacobi迭代法和Seidel迭代法的斂散性(1)線性方程組的解法(2)A2=[2,-1,1;1,1,1;1,1,-2]線性方程組的解法兩種迭代法之間沒(méi)有直接聯(lián)系對(duì)矩陣A1,求A1x=b

的Jacobi迭代法收斂,而Gauss-Seidel迭代法發(fā)散;對(duì)矩陣A2,求A2x=b

的Jacobi迭代法發(fā)散,而Gauss-Seidel迭代法收斂.線性方程組的解法證由(k)=B(k-1),得

||(k)||≤||B||||(k-1)