關(guān)于解線性方程組的迭代方法第一頁(yè)，共40頁(yè)幻燈片

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

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

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

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

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

的精確解x*

。且第十頁(yè)，共40頁(yè)幻燈片整理即得估計(jì)式。Remark:

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

第十一頁(yè)，共40頁(yè)幻燈片

迭代格式的收斂速度與初始值x(0)有關(guān)，同時(shí)也與||B||和(B)有關(guān)，一般來(lái)說(shuō)，||B||和(B)越小，收斂速度越快。Def：稱為迭代法的漸近收斂速度。第十二頁(yè)，共40頁(yè)幻燈片二、Jacobi迭代法例1：用迭代法解方程組解:將方程組化為等價(jià)形式:構(gòu)造迭代格式:取初始值代入計(jì)算，得第十三頁(yè)，共40頁(yè)幻燈片注：如何判斷迭代過(guò)程終止？利用定理2的誤差估計(jì)式可以判斷迭代過(guò)程是否可以終止，但這種方法比較麻煩，通常采用的方法是通過(guò)前后兩次迭代近似值的差來(lái)判斷，即利用：終止迭代過(guò)程。上述這種求解方程組的方法稱為Jacobi迭代法。第十四頁(yè)，共40頁(yè)幻燈片Jacobi迭代法的步驟：3、判斷迭代格式的收斂性。取初值x(0)帶入計(jì)算。1、寫出等價(jià)方程組—即將第i個(gè)方程的xi

解出。2、寫出相應(yīng)的迭代格式分量式：假設(shè)A非奇異,且aii≠0,i=1,2,…,n第十五頁(yè)，共40頁(yè)幻燈片Jacobi迭代矩陣形式第十六頁(yè)，共40頁(yè)幻燈片記則有迭代格式：

上式稱為Jacobi迭代格式，其中BJ稱為Jacobi迭代矩陣。第十七頁(yè)，共40頁(yè)幻燈片注：Jacobi迭代矩陣BJ

：其中的元素恰為原方程組系數(shù)矩陣A中的主對(duì)角線元素?fù)Q為0，而其余元素即為除以該行主對(duì)角元素后的相反數(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)代替原來(lái)相應(yīng)的分量，則得到一種新的迭代格式，即Gauss-Seidel迭代格式。第十八頁(yè)，共40頁(yè)幻燈片三、Gauss-Seidel迭代法假設(shè)Jacobi迭代新分量代替舊分量↖第十九頁(yè)，共40頁(yè)幻燈片矩陣表示：記上式整理可得：這是一種簡(jiǎn)單迭代格式，其中的BG-S稱為G—S迭代矩陣。第二十頁(yè)，共40頁(yè)幻燈片例2：用G-S迭代法解方程組：解：原方程可化為等價(jià)形式：建立迭代格式：第二十一頁(yè)，共40頁(yè)幻燈片取初始向量x(0)=(0,0,0)T代入迭代格式，得：兩種迭代法收斂性判定：

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

A按行（列）嚴(yán)格對(duì)角占優(yōu)（）證：（提示）第二十二頁(yè)，共40頁(yè)幻燈片定理4：若A為(行或列)嚴(yán)格對(duì)角占優(yōu)矩陣，則相應(yīng)的G-S迭代格式收斂。

定理3:

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

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

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

正定,特征值小于1,所以特征值大于－1。第二十五頁(yè)，共40頁(yè)幻燈片證明:由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所以第二十六頁(yè)，共40頁(yè)幻燈片所以,迭代矩陣BG-S的譜半徑ρ(BG-S)<1,從而當(dāng)方程組

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

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

若A是嚴(yán)格對(duì)角占優(yōu)矩陣,則當(dāng)0<ω<1時(shí)SOR迭代法解方程組Ax=b是收斂的.迭代矩陣：第二十九頁(yè)，共40頁(yè)幻燈片例3：用松弛迭代法解方程組：解：松弛法迭代格式為：第三十頁(yè)，共40頁(yè)幻燈片★設(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)=0x=0;I方程組問(wèn)題:Ax=bII極值問(wèn)題:

★設(shè)A是n階對(duì)稱陣(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0x=0五最速下降法第三十一頁(yè)，共40頁(yè)幻燈片定理9.

設(shè)A=(aij)n×n為實(shí)對(duì)稱正定矩陣,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

第三十二頁(yè)，共40頁(yè)幻燈片令g(t)=f(u+tx),當(dāng)t=0時(shí),g(0)=f(u)達(dá)到極小值,所以

,即(Au–b,x)=0Au–b=0所以,u是方程組

Ax=b

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

(0)

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

r

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

x處，梯度方向是

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

f(x)下降最快方向。第三十三頁(yè)，共40頁(yè)幻燈片梯度:由f(x)的表達(dá)式，易知對(duì)于任意x(0)

∈Rn,f(x)在x

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

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

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

≠0

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

，使函數(shù)第三十四頁(yè)，共40頁(yè)幻燈片取最小值。令解得：又所以，α=α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)，則第三十五頁(yè)，共40頁(yè)幻燈片x(1)=x(0)+α0

r(0)繼續(xù)下去則得迭代格式：第三十六頁(yè)，共40頁(yè)幻燈片結(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í)，最速下降法收斂緩慢。第三十七頁(yè)，共40頁(yè)幻燈片六共軛梯度法A是n階對(duì)稱正定矩陣,非零向量p1,p2∈Rn▲

n