解非線性方程組的迭代法第1頁(yè)，共49頁(yè)，2023年，2月20日，星期四迭代法的構(gòu)造

迭代法的基本思想是用逐次逼近的方法求線性方程組的解。設(shè)有方程組,將其轉(zhuǎn)化為等價(jià)的便于迭代的形式（這種轉(zhuǎn)化總能實(shí)現(xiàn)，如令）并由此構(gòu)造迭代公式

其中，稱(chēng)為迭代矩陣，稱(chēng)為迭代向量。對(duì)任意的初始向量，由迭代式可求得向量序列若，則就是方程組Ax=b的解.第2頁(yè)，共49頁(yè)，2023年，2月20日，星期四§4.1解線性方程組的三種迭代法4.1.1．雅克比（Jacobi）迭代法（以三階方程組為例）設(shè)有方程組：第3頁(yè)，共49頁(yè)，2023年，2月20日，星期四假設(shè)任選一向量X(0)作為解的初值.則方程組可寫(xiě)為：代入式(4.1)中得方程組的一次近似.第4頁(yè)，共49頁(yè)，2023年，2月20日，星期四把X(1)

再代入到(4.1)中得方程組的二次近似.重復(fù)這一過(guò)程,假設(shè)得到了m次近似X(m)。代入到(4.1)中可得m+1次近似X(m+1)。稱(chēng)此迭代公式為原方程組的雅可比迭代公式.第5頁(yè)，共49頁(yè)，2023年，2月20日，星期四對(duì)于n階方程組則雅可比迭代公式為:第6頁(yè)，共49頁(yè)，2023年，2月20日，星期四若用矩陣來(lái)記錄雅可比矩陣,可作如下的推導(dǎo):令A(yù)=D-L-U,其中第7頁(yè)，共49頁(yè)，2023年，2月20日，星期四則有AX=DX-LX-UX=b.即DX=b+(L+U)X從而有DX(m+1)=b+(L+U)X(m).若則D可逆,于是得稱(chēng)BJ為雅可比迭代矩陣.這種迭代格式稱(chēng)為雅可比迭代格式。第8頁(yè)，共49頁(yè)，2023年，2月20日，星期四在某種條件下，按雅可比迭代所產(chǎn)生的向量序列的極限會(huì)存在，且等于原方程組的解。這種求解方法被稱(chēng)為雅可比迭代法，或簡(jiǎn)單迭代法。定義4.1如果向量序列{X(m)}={(x1(m)

,x2(m)

,…xn(m)

}

有

xi(m)

→xi*

（i=1,2,3,…n）(m→∞)

則稱(chēng)向量X*=(x1*,x2*,…xn*)為向量序列{X(m)}的極限,記為:第9頁(yè)，共49頁(yè)，2023年，2月20日，星期四例用簡(jiǎn)單迭代法解下列方程組

解將方程組寫(xiě)成等價(jià)形式第10頁(yè)，共49頁(yè)，2023年，2月20日，星期四取初始值x(0)=0,按迭代公式

第11頁(yè)，共49頁(yè)，2023年，2月20日，星期四4.1.2高斯——賽德?tīng)柕▽?duì)雅可比迭代法作如下的改進(jìn):將初值代入4.1的第一個(gè)方程可得,用代入第二個(gè)方程得,用代入第三個(gè)方程得,這樣一直做下去,直到得到滿(mǎn)意的解為止.之所以作這樣的改進(jìn)是希望更快的得到近似解.第12頁(yè)，共49頁(yè)，2023年，2月20日，星期四這種迭代的方法用公式寫(xiě)出來(lái)就是:第13頁(yè)，共49頁(yè)，2023年，2月20日，星期四對(duì)給定的初值,用此迭代公式求線性方程組的方法被稱(chēng)為高斯—塞德?tīng)柕ā＃℅—S）一般地,對(duì)n階線性方程組的迭代格式改為:第14頁(yè)，共49頁(yè)，2023年，2月20日，星期四用矩陣表示此方法為：即：稱(chēng)BG為高斯——塞德?tīng)柕仃嚨?5頁(yè)，共49頁(yè)，2023年，2月20日，星期四例用賽德?tīng)柕ń夥匠探M解將原方程組寫(xiě)成等價(jià)形式并按(3―75)構(gòu)造賽德?tīng)柕降?6頁(yè)，共49頁(yè)，2023年，2月20日，星期四第17頁(yè)，共49頁(yè)，2023年，2月20日，星期四例1：分別用兩種迭代法求下列線性方程組。初值均取(0，0，0)T解:用matlab解,程序如下第18頁(yè)，共49頁(yè)，2023年，2月20日，星期四%用雅可比法解P91例1a=[9,-1,-1;-1,8,0;-1,0,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-b);U=-(triu(a)-b);xo=[0;0;0];bo=[7;7;8];ep=0.0001;dx=1;k=0;whiledx>epk=k+1;x=D\(L+U)*xo+D\bo;dx=abs(norm(x)-norm(xo));xo=x;endk,x%用G_S法解P91例1a=[9,-1,-1;-1,8,0;-1,0,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-b);U=-(triu(a)-b);xo=[0;0;0];bo=[7;7;8];ep=0.0001;dx=1;k=0;whiledx>epk=k+1;x=(D-L)\U*xo+(D-L)\bo;dx=abs(norm(x)-norm(xo));xo=x;endk,x第19頁(yè)，共49頁(yè)，2023年，2月20日，星期四

在多數(shù)情況下用高斯—賽德?tīng)柕ū妊趴吮鹊ㄊ諗靠臁５灿邢喾吹那闆r，即高斯—賽德?tīng)柕ū妊趴吮鹊ㄊ諗柯踔吝€有雅克比迭代法收斂，高斯—賽德?tīng)柕òl(fā)散的情形。第20頁(yè)，共49頁(yè)，2023年，2月20日，星期四4.1.3超松弛迭代法

弛迭代法是高斯—賽德?tīng)柕ǖ囊环N改進(jìn),是解大型稀疏矩陣方程組的有效方法之一.

現(xiàn)在研究如何求向量首先，由高斯—賽德?tīng)柕ㄇ蟪鲆粋€(gè)值，記第21頁(yè)，共49頁(yè)，2023年，2月20日，星期四首先，由高斯—賽德?tīng)柕ㄇ蟪鲆粋€(gè)值，記第22頁(yè)，共49頁(yè)，2023年，2月20日，星期四用此公式求解線性方程組的方法稱(chēng)為帶有松弛因子ω的松弛迭代法.

當(dāng)ω>1時(shí)稱(chēng)為超松弛迭代法;(SOR法)當(dāng)ω<1時(shí)稱(chēng)為低松弛迭代法;當(dāng)ω=1時(shí)就是G—S迭代法.

當(dāng)某些方程組用高斯—賽德?tīng)柕ú皇諗繒r(shí)，可以用低松弛方法獲得收斂，第23頁(yè)，共49頁(yè)，2023年，2月20日，星期四將上式寫(xiě)成矩陣的形式，得：于是得SOR迭代的矩陣表示

第24頁(yè)，共49頁(yè)，2023年，2月20日，星期四例用SOR法求解方程第25頁(yè)，共49頁(yè)，2023年，2月20日，星期四%用SOR法解P96例2a=[4,-2,-4;-2,17,10;-4,10,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);xo=[0;0;0];bo=[10;3;-7];omiga=1.46;ep=0.000001;dx=1;k=0;whiledx>epk=k+1;x=(D-omiga*L)\(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)\bo*omiga;dx=abs(norm(x)-norm(xo));xo=x;endk,x第26頁(yè)，共49頁(yè)，2023年，2月20日，星期四Matlab的關(guān)于三種迭代法的通用程序%雅可比法解方程的通用程序%A為線性方程組,X為初值function[x,k]=ya2(A,X)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)<N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledx>epk=k+1;x=D\(L+U)*xo+D\bo;dx=norm(x-xo);xo=x;end1.雅可比迭代法的通用程序第27頁(yè)，共49頁(yè)，2023年，2月20日，星期四2.高斯_塞德?tīng)柕ǖ耐ㄓ贸绦?G_S法解方程組的通用程序%A為線性方程組,X為初值function[x,k]=ya4(A,X)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)<N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledx>epk=k+1;x=(D-L)\U*xo+(D-L)\bo;dx=norm(x-xo);xo=x;end第28頁(yè)，共49頁(yè)，2023年，2月20日，星期四3.SOR法解線性方程組的通用程序%SOR法解方程組的通用程序%A為線性方程組,X為初值%omiga為松弛因子function[x,k]=ya3(A,X,omiga)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)<N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledx>epk=k+1;x=(D-omiga*L)\(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)\bo*omiga;dx=norm(x-xo);xo=x;end第29頁(yè)，共49頁(yè)，2023年，2月20日，星期四4.2迭代法的收斂條件

前面介紹了三種迭代法.從例子看到這三種迭代法都有成功的時(shí)候.但我們也可以預(yù)計(jì),某種迭代法可能會(huì)失效.下面我們?cè)噲D從理論上來(lái)探討這一問(wèn)題.三種迭代法的統(tǒng)一寫(xiě)法為:第30頁(yè)，共49頁(yè)，2023年，2月20日，星期四定義設(shè)給定Rn中的向量序列{}，即其中若對(duì)任何i(i=1,2,…,n)都有或者說(shuō)向量序列{}依坐標(biāo)收斂于向量，記為則向量

稱(chēng)為向量序列{}的極限，4.2.1迭代法收斂的概念第31頁(yè)，共49頁(yè)，2023年，2月20日，星期四證:再由范數(shù)的等價(jià)性有引理向量序列{x(m)}依坐標(biāo)收斂于x*的充要條件是向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。如果滿(mǎn)足此式，稱(chēng)x(m)依范數(shù)收斂于x*第32頁(yè)，共49頁(yè)，2023年，2月20日，星期四定義4.2設(shè)x*是方程組Ax=b的解,對(duì)于給定的初始向量x(0),若由某種迭代法產(chǎn)生的向量序列{x(m)}有則稱(chēng)該方法收斂,否則稱(chēng)該方法發(fā)散.第33頁(yè)，共49頁(yè)，2023年，2月20日，星期四4.2.2迭代法收斂的判定定理定理4.1設(shè)若則對(duì)任意的初始向量,該迭代過(guò)程收斂于的唯一解,且有估計(jì)式第34頁(yè)，共49頁(yè)，2023年，2月20日，星期四證:先證若則E-B非奇異.用反證法:設(shè)E-B是奇異的,則存在非零向量x,使(E-B)x=0.即有x=Bx.兩邊取范數(shù),再由范數(shù)的性質(zhì)得由于得與矛盾第35頁(yè)，共49頁(yè)，2023年，2月20日，星期四由于E-B是非奇異的，所以方程組(E-B)x=f的解存在且唯一.設(shè)為x*,即x*=Bx*+f,進(jìn)而有取范數(shù)得:由于0<q<1,所以第36頁(yè)，共49頁(yè)，2023年，2月20日，星期四所以迭代過(guò)程收斂.又于是有即(1)式成立.第37頁(yè)，共49頁(yè)，2023年，2月20日，星期四再由于所以有即(2)式成立.

(2)式提示我們可以利用來(lái)控制誤差第38頁(yè)，共49頁(yè)，2023年，2月20日，星期四例寫(xiě)出用雅可比迭代法和G-S迭代法解線性方程組收斂的迭代格式。解：對(duì)A分解于是第39頁(yè)，共49頁(yè)，2023年，2月20日，星期四由此得所以用雅可比迭代法和G-S迭代法求解方程組都收斂。分別為：第40頁(yè)，共49頁(yè)，2023年，2月20日，星期四定義4.3如果方陣A滿(mǎn)足則稱(chēng)A按行嚴(yán)格對(duì)角占優(yōu).(類(lèi)似地可定義按列嚴(yán)格對(duì)角占優(yōu))注意:是對(duì)角占優(yōu),不是嚴(yán)格對(duì)角占優(yōu).第41頁(yè)，共49頁(yè)，2023年，2月20日，星期四定理4.2若方程組Ax=b的系數(shù)矩陣按行(列)嚴(yán)格對(duì)角占優(yōu),則雅可比迭代法收斂,G-S迭代法也收斂.證:先證雅可比迭代法收斂.因?yàn)?所以由定理4.1,Ax=b存在唯一解x*.且用雅可比迭代法求解收斂.可證G-S迭代法收斂(略)第42頁(yè)，共49頁(yè)，2023年，2月20日，星期四以上兩個(gè)定理都是收斂的充分條件.

下面給出一個(gè)充分必要條件：定理4.3對(duì)于任意的初始向量,由產(chǎn)生的向量序列收斂的充分必要條件是第43頁(yè)，共49頁(yè)，2023年，2月20日，星期四例：寫(xiě)出用雅可比迭代法求解方程組一定收斂的迭代格式。解：對(duì)A進(jìn)行分解從而第44頁(yè)，共49頁(yè)，2023年，2月20日，星期四由BJ的特征多項(xiàng)式得特征值為：1=2，2=-2。所以(BJ)=2>1由此例可以看到:對(duì)原方程組直接寫(xiě)出雅可比迭代公式是不收斂的