解線性方程組的迭代方法

關(guān)于解線性方程組的迭代方法

定義:設(shè)｛xk｝是Rn上的向量序列，

又設(shè)x*＝（x1*，x2*,…，xn*)Ｔ是Rn上的向量.

則稱向量x*是向量序列｛xk｝的極限，若一個(gè)向量序列有極限,稱這個(gè)向量序列是收斂的.向量序列的極限如果向量序列｛xk｝收斂于向量x*的充分必要定理1（i=1,2,…,n）條件是第2頁,共40頁，2024年2月25日，星期天矩陣序列的極限定義:設(shè)｛Ak｝是

上的矩陣序列.若存在矩陣則稱矩陣A是矩陣序列｛Ak｝的極限，記為若一個(gè)矩陣序列有極限,稱這個(gè)矩陣序列是收斂的.使得矩陣序列｛Ak｝收斂于矩陣A的充分必要定理2（i,j=1,2,…,n）條件是這里第3頁,共40頁，2024年2月25日，星期天證：依次取x為，其中則所以定理3的充要條件是對任何x∈Rn，有設(shè)矩陣定理4，則的充要條件是ρ(A)<1第4頁,共40頁，2024年2月25日，星期天證：矩陣A相似于其Jordan標(biāo)準(zhǔn)型,即存在可逆矩陣P,使得J為對角分塊矩陣(Ji稱為Jordan塊):其中:ni為特征值λi的重?cái)?shù),且n1+n2+…+nr=n由于第5頁,共40頁，2024年2月25日，星期天所以而第6頁,共40頁，2024年2月25日，星期天一、簡單迭代思想設(shè)矩陣A可逆，把矩陣A分裂為則

迭代過程B稱為迭代矩陣。給定初值就得到向量序列第7頁,共40頁，2024年2月25日，星期天定義：若稱簡單迭代法收斂，否則，稱逐次逼近法不收斂或發(fā)散。問題：是否是方程組x=Bx+f的解？結(jié)論1：任意給定初始向量，若由迭代公式(1)產(chǎn)生的迭代序列收斂到，則是方程組x=Bx+f的解。證：又如何判定所給迭代格式(1)是否收斂哪？第8頁,共40頁，2024年2月25日，星期天迭代法收斂的條件定理1：對任意初始向量，由（1）得到的迭代序列收斂的充要條件是迭代矩陣的譜半徑證：因此結(jié)論2：設(shè)矩陣，則注：要檢驗(yàn)一個(gè)矩陣的譜半徑小于1比較困難，所以我們希望用別的辦法判斷迭代格式是否收斂。第9頁,共40頁，2024年2月25日，星期天定理2：若迭代法的迭代矩陣滿足（矩陣的某一種算子范數(shù)），則迭代格式產(chǎn)生的序列收斂于x=Bx+f的精確解x*，且有誤差估計(jì)式：證：由定理1、結(jié)論1和知迭代格式產(chǎn)生的序列收斂于x=Bx+f

的精確解x*

。且第10頁,共40頁，2024年2月25日，星期天整理即得估計(jì)式。Remark:

因?yàn)榫仃嚪稊?shù)，都可以直接用矩陣的元素計(jì)算，因此，用定理2，容易判別迭代法的收斂性。定理2的條件只是充分的，而不是必要的，也就是說：如果，則迭代法收斂；但若，我們并不能斷定迭代法就一定發(fā)散，此時(shí)需要用定理1來判定迭代法的斂散性。

第11頁,共40頁，2024年2月25日，星期天

迭代格式的收斂速度與初始值x(0)有關(guān)，同時(shí)也與||B||和

(B)有關(guān)，一般來說，||B||和

(B)越小，收斂速度越快。Def：稱為迭代法的漸近收斂速度。第12頁,共40頁，2024年2月25日，星期天二、Jacobi迭代法例1：用迭代法解方程組解:將方程組化為等價(jià)形式:構(gòu)造迭代格式:取初始值代入計(jì)算，得第13頁,共40頁，2024年2月25日，星期天注：如何判斷迭代過程終止？利用定理2的誤差估計(jì)式可以判斷迭代過程是否可以終止，但這種方法比較麻煩，通常采用的方法是通過前后兩次迭代近似值的差來判斷，即利用：終止迭代過程。上述這種求解方程組的方法稱為Jacobi迭代法。第14頁,共40頁，2024年2月25日，星期天Jacobi迭代法的步驟：3、判斷迭代格式的收斂性。取初值x(0)帶入計(jì)算。1、寫出等價(jià)方程組—即將第i個(gè)方程的xi

解出。2、寫出相應(yīng)的迭代格式分量式：假設(shè)A非奇異,且aii≠0,i=1,2,…,n第15頁,共40頁，2024年2月25日，星期天Jacobi迭代矩陣形式第16頁,共40頁，2024年2月25日，星期天記則有迭代格式：

上式稱為Jacobi迭代格式，其中BJ稱為Jacobi迭代矩陣。第17頁,共40頁，2024年2月25日，星期天注：Jacobi迭代矩陣BJ

：其中的元素恰為原方程組系數(shù)矩陣A中的主對角線元素?fù)Q為0，而其余元素即為除以該行主對角元素后的相反數(shù)。Jacobi迭代法在計(jì)算xi(k+1)時(shí)所用分量仍為上一次近似值的各個(gè)分量，但此時(shí)，我們已經(jīng)求出了新近似值的分量x1(k+1),x2(k+1),…,xi-1(k+1)，計(jì)算xi(k+1)時(shí)，用新分量x1(k+1),x2(k+1),…,xi-1(k+1)代替原來相應(yīng)的分量，則得到一種新的迭代格式，即Gauss-Seidel迭代格式。第18頁,共40頁，2024年2月25日，星期天三、Gauss-Seidel迭代法假設(shè)Jacobi迭代新分量代替舊分量↖第19頁,共40頁，2024年2月25日，星期天矩陣表示：記上式整理可得：這是一種簡單迭代格式，其中的BG-S稱為G—S迭代矩陣。第20頁,共40頁，2024年2月25日，星期天例2：用G-S迭代法解方程組：解：原方程可化為等價(jià)形式：建立迭代格式：第21頁,共40頁，2024年2月25日，星期天取初始向量x(0)=(0,0,0)T代入迭代格式，得：兩種迭代法收斂性判定：

希望直接對系數(shù)矩陣A研究這倆種迭代收斂條件。引理：

A按行（列）嚴(yán)格對角占優(yōu)（）證：（提示）第22頁,共40頁，2024年2月25日，星期天定理4：若A為(行或列)嚴(yán)格對角占優(yōu)矩陣，則相應(yīng)的G-S迭代格式收斂。

定理3:

A按行(列)嚴(yán)格對角占優(yōu)，則Jacobi迭代收斂。證：(僅證按行占優(yōu)，反證)

設(shè)是任一特征值，x

是相應(yīng)特征向量。設(shè)若則第23頁,共40頁，2024年2月25日，星期天定理5：設(shè)A是有正對角元的n階對稱矩陣，則Jacobi迭代收斂A和2D-A同為正定矩陣。證：記則即，從而有相同的譜半徑。由A的對稱性，也對稱，因而特征值全為實(shí)數(shù)，記為則的任一特征值為。第24頁,共40頁，2024年2月25日，星期天定理6：若A為對稱正定矩陣，則相應(yīng)的G-S迭代格式收斂。正定。又，故正定。A正定正定，特征值小于1.若

正定,特征值小于1,所以特征值大于－1。第25頁,共40頁，2024年2月25日，星期天證明:由A=D–L–LT

BG-S=(D–L)-1LT設(shè)λ為BG-S的任一特征值,x為其特征向量,則(D–L)-1LTx=λx

LTx=λ(D–L)x

A正定,故

p=xTDx>0,記xTLTx=a,則有xTLTx=λxT(D–L)xxTAx=xT(D–L–LT)x=p–a–a=p–2a>0所以第26頁,共40頁，2024年2月25日，星期天所以,迭代矩陣BG-S的譜半徑ρ(BG-S)<1,從而當(dāng)方程組

Ax=b的系數(shù)矩陣A是實(shí)對稱正定矩陣時(shí),G-S迭代法收斂Remark:G-S迭代法的計(jì)算過程比Jacobi迭代法更簡單。計(jì)算過程中只需用一個(gè)一維數(shù)組存放迭代向量。G-S迭代不一定比Jacobi迭代收斂快。Jacobi迭代和G-S迭代的收斂范圍并不一致，即Jacobi迭代收斂，G-S迭代不一定收斂，反之亦然。前面的定理1、定理2對于Jacobi迭代和G-S迭代都適用。第27頁,共40頁，2024年2月25日，星期天(i=1,2,···,n;k=1,2,3,···)四超松馳(SOR)迭代法G-S迭代格式第28頁,共40頁，2024年2月25日，星期天定理7.

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

若A是嚴(yán)格對角占優(yōu)矩陣,則當(dāng)0<ω<1時(shí)SOR迭代法解方程組Ax=b是收斂的.迭代矩陣：第29頁,共40頁，2024年2月25日，星期天例3：用松弛迭代法解方程組：解：松弛法迭代格式為：第30頁,共40頁，2024年2月25日，星期天★設(shè)x,y∈Rn,記(x,y)=xTy(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0

x=0;I方程組問題:Ax=bII極值問題:

★設(shè)A是n階對稱陣(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0

x=0五最速下降法第31頁,共40頁，2024年2月25日，星期天定理9.

設(shè)A=(aij)n×n為實(shí)對稱正定矩陣,b,x∈Rn,則x使二次函數(shù)取極小值

x是線性方程組

Ax=b的解。

證明:(1)u是方程組Ax=b的解

Au–b=0.任意x∈Rn,令y=x–u

(Ay,y)≥0(2)設(shè)u使f(x)取極小值.任取非零

x∈Rn,任意

t∈R

第32頁,共40頁，2024年2月25日，星期天令g(t)=f(u+tx),當(dāng)t=0時(shí),g(0)=f(u)達(dá)到極小值,所以

,即(Au–b,x)=0

Au–b=0所以,u是方程組

Ax=b

的解.最速下降法基本思想：從初值點(diǎn)x

(0)

出發(fā),以負(fù)梯度方向

r

為搜索方向，選擇步長t1,得x(1)=x(0)+t1r,求函數(shù)f(x)極小值在

x處，梯度方向是

f(x)增長最快方向；負(fù)梯度方向是

f(x)下降最快方向。第33頁,共40頁，2024年2月25日，星期天梯度:由f(x)的表達(dá)式，易知對于任意x(0)

∈Rn,f(x)在x

(0)處的負(fù)梯度方向?yàn)橛況(0)

=b-Ax(0)，即r(0)的方向就是負(fù)梯度的方向，也是Ax=b的對應(yīng)于x(0)的殘向量。若r(0)

=0，則x(0)即為Ax=b的解，若r(0)

≠0

，則從x(0)出發(fā)，沿r(0)方向的x為：其中α為參數(shù)，這里x表明在r(0)方向上以α為步長，對x(0)做了一次修正，為確定α

，使函數(shù)第34頁,共40頁，2024年2月25日，星期天取最小值。令解得：又所以，α=α0時(shí)f(x)取最小值，令x

(1)=x

(0)+α0r(0)，從x(1)出發(fā)沿f(x)在x(1)處的負(fù)梯度方向r(1)

=b-Ax(1)上求使f(x)的值最小的點(diǎn)，記為x(2)，則第35頁,共40頁，2024年2月25日，星期天x(1)=x(0)+α0

r(0)繼續(xù)下去則得迭代格式：第36頁,共40頁，2024年2月25日，星期天結(jié)論1：第m+1次和第m次負(fù)梯度方向是正交的，即

(r(m+1),r

(m))=0結(jié)論2：最速下降法有誤差估計(jì)式這里λ1和λn

為A的最大和最小特征值，||·||A

定義為注：由結(jié)論2可以看出，當(dāng)λ1和λn

相差較大時(shí)，最速下降法收斂緩慢。第37頁,共40頁，2024年2月25日，星期天六共軛梯度法A是n階對稱正定矩陣,非零向量p