第四章 線性方程組迭代解法

第四章線性方程組迭代解法第1頁，課件共75頁，創(chuàng)作于2023年2月第四章目錄§1向量序列與矩陣序列的極限§2Jacobi迭代法§3Gauss~Seidel迭代法§4松馳法§5迭代法的收斂條件及誤差估計(jì)5.1矩陣的譜半徑5.2迭代法的收斂條件5.3誤差估計(jì)第2頁，課件共75頁，創(chuàng)作于2023年2月第四章

方程組的迭代解法概述

這一章討論線性方程組的另一類解法——迭代法，由于

迭代法能充分避免系數(shù)矩陣中零元的存貯與計(jì)算，因此特別

適用于求解系數(shù)矩陣階數(shù)很高而零元素又很多（即大型稀疏）

的線性方程組。解線性方程組的迭代法的基本思想與解方程的迭代法相

似，首先將方程組Ax=b化為等價(jià)方程組x=Mx+g，其中M

為n階方陣，b=(b1,b2,…,bn)T，g

Rn，任取初始向量x(0)

Rn，

代入迭代公式：產(chǎn)生向量序列{x(k)}，若此序列收斂于x*，則有x*=Mx*+g，即

x*為原方程組的解。因此，可根據(jù)精度要求選擇一個(gè)合適的x(k)

（k充分大時(shí)）作為近似解，這就是解線性方程組的迭代法，

上式稱為迭代格式，M稱為迭代矩陣，若序列{x(k)}極限存

在，稱此迭代過程收斂，否則稱為發(fā)散。

第3頁，課件共75頁，創(chuàng)作于2023年2月§1向量與矩陣的范數(shù)與求解方程類似，需要討論的問題是：如何建立迭代公式，向量序列的收斂條件是什么，若向量序列{x(k)}收斂，如何進(jìn)行誤差估計(jì)？第4頁，課件共75頁，創(chuàng)作于2023年2月4.1向量與矩陣的范數(shù)

這三個(gè)性質(zhì)刻畫了向量長度的基本特征，并可以用其將平面向量長度的概念推廣到一般n維向量，于是有如下定義：定義1下屏將給出范數(shù)的種類：第5頁，課件共75頁，創(chuàng)作于2023年2月常用的向量范數(shù)容易證明它們都滿足上述三條性質(zhì)?？梢钥闯觯?范數(shù)是平面向量長度計(jì)算公式在形式上的推廣，也是線性代數(shù)中的內(nèi)積定義。此處引入多種范數(shù)來刻畫向量的大小，是為了在不同情況下用不同的范數(shù)研究問題。向量范數(shù)的證明：（只對(duì)第三條）對(duì)∞范數(shù)：前面2條顯然，對(duì)第三條，由于對(duì)任意實(shí)數(shù)x,y，絕對(duì)值不等式：|x+y|≤|x|+|y|成立，因而有:分別稱為向量x的2范數(shù)，1范數(shù)，無窮范數(shù)。第6頁，課件共75頁，創(chuàng)作于2023年2月對(duì)2范數(shù)利用實(shí)數(shù)的柯西不等式：于是，有：常用的向量范數(shù)（續(xù)）第7頁，課件共75頁，創(chuàng)作于2023年2月Rn中范數(shù)的等價(jià)性

例如可證明如下等價(jià)性：

所以，2范數(shù)與

范數(shù)是等價(jià)的。不難證明：——亦即1范數(shù)與

范數(shù)是等價(jià)的。事實(shí)上:Rn中任意兩種范數(shù)都是等價(jià)的。第8頁，課件共75頁，創(chuàng)作于2023年2月矩陣范數(shù)

定義2對(duì)任意n階方陣A=(aij)n

n，若對(duì)應(yīng)一個(gè)非負(fù)實(shí)數(shù)||A||，滿足：則稱||A||為矩陣A的范數(shù)。與向量范數(shù)定義比較，前三條性質(zhì)只是向量范數(shù)定義的推廣，而第四條性質(zhì)則是矩陣乘法性質(zhì)的要求，它使矩陣范數(shù)在數(shù)值計(jì)算中使用更方便。第9頁，課件共75頁，創(chuàng)作于2023年2月常用的矩陣范數(shù)常用的矩陣范數(shù)有：它們分別叫做矩陣的

范數(shù)，1范數(shù)，2范數(shù)，F(xiàn)范數(shù)，矩陣F范數(shù)是向量2范數(shù)的推廣，矩陣

范數(shù)，1范數(shù)計(jì)算容易，而矩陣2范數(shù)與ATA的特征值有關(guān)，所以又稱為譜范數(shù)，它的計(jì)算較困難，但因?yàn)樗幸恍┖玫男再|(zhì)，所以也是常用的范數(shù)。第10頁，課件共75頁，創(chuàng)作于2023年2月常用的矩陣范數(shù)（續(xù)）可以證明，這些范數(shù)都滿足定義2。以||A||

為例，前2條性質(zhì)顯然成立，而對(duì)：第11頁，課件共75頁，創(chuàng)作于2023年2月最大行和矩陣范數(shù)的證明第12頁，課件共75頁，創(chuàng)作于2023年2月最大行和矩陣范數(shù)的證明第13頁，課件共75頁，創(chuàng)作于2023年2月范數(shù)的相容性

在誤差估計(jì)中，由于矩陣與向量會(huì)同時(shí)用到，我們總希望有上面的不等式成立，但對(duì)任意的向量范數(shù)與矩陣范數(shù)卻未必如此，因而特別地把滿足此不等式的范數(shù)稱為相容的，可以證明，上述常用的范數(shù)是相容的，即有：在使用范數(shù)時(shí)，應(yīng)選用相容的矩陣范數(shù)與向量范數(shù)。分別稱為的關(guān)于P范數(shù)的絕對(duì)誤差與相對(duì)誤差。有了矩陣范數(shù)，就可以用它描述矩陣的誤差，設(shè)是A的近似矩陣，稱為的殘差陣，則：第14頁，課件共75頁，創(chuàng)作于2023年2月求范數(shù)舉例例10第15頁，課件共75頁，創(chuàng)作于2023年2月向量序列與矩陣序列的極限與求解方程類似，需要討論的問題是：如何建立迭代公式，向量序列的收斂條件是什么，若向量序列{x(k)}收斂，如何進(jìn)行誤差估計(jì)？§1向量序列與矩陣序列的極限由于Rn中的向量可與Rn的點(diǎn)建立一一對(duì)應(yīng)關(guān)系，因此由點(diǎn)列的收斂概念及向量范數(shù)的等價(jià)性，可得到向量序列的收斂概念。定義3第16頁，課件共75頁，創(chuàng)作于2023年2月向量序列與矩陣序列的極限（續(xù)）

n維點(diǎn)列收斂的一種等價(jià)描述是其對(duì)應(yīng)坐標(biāo)序列均收斂，向量序列也有類似的結(jié)論。定理1

第17頁，課件共75頁，創(chuàng)作于2023年2月矩陣序列的收斂概念及定理定義3完全類似地，可以定義矩陣序列的收斂：與向量序列類似，也有：定理2第18頁，課件共75頁，創(chuàng)作于2023年2月4.3矩陣的譜半徑

迭代法的收斂性與迭代矩陣的特征值有關(guān)：設(shè)A為n階方陣，

i(i=1,2,…，n)為A的特征值，稱特征值模的最大值為矩陣A的譜半徑，記為：定義5第19頁，課件共75頁，創(chuàng)作于2023年2月矩陣的譜半徑（續(xù)）

矩陣的譜半徑與范數(shù)之間有如下關(guān)系：設(shè)x為對(duì)應(yīng)于特征值

的A的特征向量，則由：

這個(gè)不等式對(duì)A的任何范數(shù)、任意特征值都成立，因此，可得矩陣A的譜半徑與A的范數(shù)之間的一個(gè)重要關(guān)系：A的譜半徑不超過A的任一種范數(shù)。即：第20頁，課件共75頁，創(chuàng)作于2023年2月公式的重要性說明

它之所以重要是因?yàn)椋?/p>

(A)難計(jì)算，而||A||∞、||A||1計(jì)算容易，并且對(duì)于任意正數(shù)

，存在一種矩陣范數(shù)很接近

(A)，使得成立：對(duì)任意n階方陣A，一般不存在矩陣范數(shù)使

(A)=||A||，但若A為對(duì)稱矩陣，則有：

下面的結(jié)論對(duì)建立迭代法的收斂條件十分重要：定理3第21頁，課件共75頁，創(chuàng)作于2023年2月定理3（續(xù)）證明：第22頁，課件共75頁，創(chuàng)作于2023年2月由5.1的結(jié)果，可以得到如下收斂定理：定理4對(duì)任意初始向量x(0)和右端項(xiàng)g，由迭代格式：證明：第23頁，課件共75頁，創(chuàng)作于2023年2月推論1第24頁，課件共75頁，創(chuàng)作于2023年2月可以看出，后兩個(gè)方程組與第一個(gè)方程組相比，系數(shù)矩陣或右端向量僅有0.0005以下的誤差，但準(zhǔn)確解卻相差很大。4.2方程組的誤差分析數(shù)值穩(wěn)定的算法是否一定能求得精度比較高的解呢？回答是不一定，解的精度還與方程組本身的性態(tài)有關(guān)，下面來考察幾個(gè)例：例11第25頁，課件共75頁，創(chuàng)作于2023年2月例12若其系數(shù)，常數(shù)項(xiàng)改用三位有效數(shù)字的小數(shù)表示，則方程組為：第26頁，課件共75頁，創(chuàng)作于2023年2月右端項(xiàng)b產(chǎn)生0.1%的變化

引起解的變化最大變化184%。初始數(shù)據(jù)的誤差（相對(duì)）<0.3%=0.003，而解的相對(duì)誤差卻超過50%。例13第27頁，課件共75頁，創(chuàng)作于2023年2月方程組的性態(tài)討論

——病態(tài)、良態(tài)在許多實(shí)際問題中，線性方程組的系數(shù)矩陣和右端項(xiàng)的元素大多為前面計(jì)算的結(jié)果，因此上述例中的微小誤差是避免不了。而對(duì)上述例中的方程組，無論用多么穩(wěn)定的算法求解，計(jì)算中產(chǎn)生的微小誤差就使解面目全非，所以這些方程組的性態(tài)是很差的。當(dāng)方程組Ax=b的系數(shù)矩陣與右端向量b的微小變動(dòng)（小擾動(dòng)）而引起解嚴(yán)重失真時(shí)，稱此方程組為病態(tài)方程組，其系數(shù)矩陣A稱為病態(tài)矩陣，否則稱為良態(tài)方程組，A稱為良態(tài)矩陣，為了定量刻畫方程組“病態(tài)”的程度，下面對(duì)方程組Ax=b在系數(shù)矩陣A及右端項(xiàng)b有擾動(dòng)的幾種情形進(jìn)行討論。第28頁，課件共75頁，創(chuàng)作于2023年2月此不等式表明，當(dāng)右端項(xiàng)有擾動(dòng)時(shí)，解的相對(duì)誤差不超過b的相對(duì)誤差的倍。首先考察右端項(xiàng)b的擾動(dòng)對(duì)解的影響，設(shè)b有擾動(dòng)

b，A為準(zhǔn)確,記引起解x的擾動(dòng)為

x,即：第29頁，課件共75頁，創(chuàng)作于2023年2月方程組的性態(tài)討論（續(xù)2）當(dāng)b為精確的而A有微小擾動(dòng)

A時(shí)，在

A充分小時(shí)也同樣可推得：緊接下屏討論：第30頁，課件共75頁，創(chuàng)作于2023年2月第31頁，課件共75頁，創(chuàng)作于2023年2月方程組的性態(tài)討論續(xù)（3）而當(dāng)A,b同時(shí)有微小擾動(dòng)

A，

b時(shí)，則可進(jìn)一步導(dǎo)出更一般的誤差估計(jì)式：注意到：第32頁，課件共75頁，創(chuàng)作于2023年2月在

b充分小時(shí)，此式右端實(shí)際上即為：方程組的性態(tài)討論續(xù)（4）第33頁，課件共75頁，創(chuàng)作于2023年2月矩陣的條件數(shù)在三種情況下得到的這三個(gè)不等式反映了解的相對(duì)誤差與A及b的相對(duì)誤差的關(guān)系；數(shù)||A||||A-1||越小，解的相對(duì)誤差也越小；反之?dāng)?shù)||A||||A-1||越大，解的相對(duì)誤差也越大，實(shí)際上這個(gè)數(shù)反映了解對(duì)方程組原始數(shù)據(jù)的敏感程度，揭示了矩陣A和方程組本身的性態(tài)，稱之為方程組或矩陣A的條件數(shù)，記作：cond(A)越大，A的病態(tài)程度越嚴(yán)重。至于cond(A)多大才算病態(tài)，這是一個(gè)相對(duì)概念，沒有一個(gè)嚴(yán)格的數(shù)量界限。第34頁，課件共75頁，創(chuàng)作于2023年2月判斷病態(tài)矩陣的幾點(diǎn)參考求條件數(shù)要計(jì)算逆陣的范數(shù)，很不方便，如下一些現(xiàn)象可作為判斷病態(tài)矩陣的參考。（1）在用主元消去法時(shí)消元過程出現(xiàn)小主元（如例12）（2）矩陣A中元素間數(shù)量級(jí)相差很大；（3）A的行列式det(A)滿足（行列式值相對(duì)很大）：（4）矩陣的某些行（或列）近似相關(guān)（如例11）。第35頁，課件共75頁，創(chuàng)作于2023年2月利用條件數(shù)判斷矩陣的性態(tài)舉例A的條件數(shù)很大，所以方程組是病態(tài)的。的特例，它是典型的“病態(tài)”陣，n越大，“病態(tài)”越嚴(yán)重，如n=6時(shí)，cond(A)=29×106，對(duì)嚴(yán)重“病態(tài)”的方程組，即使用主元素法求解也難以保證數(shù)值穩(wěn)定性。第36頁，課件共75頁，創(chuàng)作于2023年2月§3雅可比（Jacobi）迭代法設(shè)有n階線性方程組：簡記為：其系數(shù)矩陣A非奇異，不妨設(shè)aii≠0(1,2,…,n)可將上式改寫為等價(jià)方程組：第37頁，課件共75頁，創(chuàng)作于2023年2月雅可比（Jacobi）迭代法（續(xù)）也可寫作為：可簡記為：由此可建立迭代格式：第38頁，課件共75頁，創(chuàng)作于2023年2月Jacobi迭代法定義

選取初始向量x(0)代入（4-4）右端，可得x(1)=Bx(0)+g，再將x(1)代入（3-4）右端，可得x(2)=Bx(1)+g，如此繼續(xù)下去，就產(chǎn)生一個(gè)向量序列{x(k)}，按（3-2）或（3-3）格式迭代求解的方法稱為雅可比（Jacobi）迭代法，又叫簡單迭代法。迭代式（3-4）中的B稱為迭代矩陣，它可直接由（3-2）或（3-3）得到，也可用系數(shù)矩陣A來表示：若將系數(shù)矩陣A分解為A=D–L–U，其中：第39頁，課件共75頁，創(chuàng)作于2023年2月Jacobi迭代法定義（續(xù)）式（3-5）為簡單迭代法的矩陣形式。第40頁，課件共75頁，創(chuàng)作于2023年2月Jacobi迭代法舉例用Jacobi迭代法求解線性方程組：

例1解：由第一個(gè)方程解x1，第二個(gè)方程解x2，第三個(gè)方程解x3得Joacbi迭代格式為：繼續(xù)迭代下去，迭代結(jié)果見表3-1：取x(0)=(0,0,0)T代入迭代式（3-6）或（3-7）得：第41頁，課件共75頁，創(chuàng)作于2023年2月Jacobi迭代法舉例00.00000.00000.000017.20008.30008.400029.710010.700011.5000310.570011.570012.4820410.853511.853412.8282510.951011.951012.9414610.983411.983412.9504710.994411.998112.9934810.998111.994112.9978910.999411.999412.9992表3-1k

x1(k)

x2(k)

x3(k)

迭代9次，得近似解x(9)=(10.9994,11.9994,12,9992)T，此方程組的準(zhǔn)確解為x=(11,12,13)T，從表3-1可以看出，隨著迭代次數(shù)的增加，迭代結(jié)果越來越接近精確解。第42頁，課件共75頁，創(chuàng)作于2023年2月收斂條件迭代格式收斂的充要條件是G的譜半徑<1。對(duì)于Jacobi迭代，我們有一些保證收斂的充分條件定理：若A滿足下列條件之一，則Jacobi迭代收斂。①A為行對(duì)角占優(yōu)陣②A為列對(duì)角占優(yōu)陣第43頁，課件共75頁，創(chuàng)作于2023年2月證明：＃證畢第44頁，課件共75頁，創(chuàng)作于2023年2月例4

討論Jacobi迭代法的收斂性。

解：首先要求出迭代矩陣，對(duì)Jacobi迭代法：第45頁，課件共75頁，創(chuàng)作于2023年2月第46頁，課件共75頁，創(chuàng)作于2023年2月§3高斯塞德爾(Gauss-Seidel)迭代法

Jacobi迭代法的優(yōu)點(diǎn)是公式簡單，迭代矩陣容易得到，它又稱為同時(shí)替換法：在每一步迭代計(jì)算過程中，計(jì)算x(k+1)時(shí)是用x(k)的全部分量代入求x

(k+1)的全部分量。因此需同時(shí)保留兩個(gè)近似解向量x(k)和x(k+1)。第47頁，課件共75頁，創(chuàng)作于2023年2月第48頁，課件共75頁，創(chuàng)作于2023年2月Gauss-Seidel迭代法求解例2用Gauss-Seidel迭代法求解例1

解：Gauss-Seidel迭代格式為：仍取x

(0)=(0,0,0)T，

計(jì)算結(jié)果見下表：

00.00000.00000.000017.20009.020011.6440210.430811.671912.8205310.931311.957212.9778410.991311.994712.9972510.998911.999312.9996610.999911.999913.0000kx1(k)x2(k)x3(k)

表3-2

顯然，用Gauss-Seidel迭代法比Jacobi迭代法收斂快，這個(gè)結(jié)論在多數(shù)情況下是成立的，但也有Gauss-Seidel迭代比Jacuobi迭代收斂慢，甚至還有Jacobi迭代收斂，Gauss-Seidel迭代發(fā)散的情形。第49頁，課件共75頁，創(chuàng)作于2023年2月求例2中的Gauss-Seidel法的迭代陣M的兩種方法第50頁，課件共75頁，創(chuàng)作于2023年2月求例2中的Gauss-Seidel法的迭代陣M的兩種方法續(xù)1方法2：可按代入法求M，以避免計(jì)算逆矩陣，在Gauss-Seidel迭代式（3-10）中，第二個(gè)式子中的以第一個(gè)式子代替?？蓪⒌诙接叶松蠘?biāo)都化為k（可以不管常數(shù)）：第51頁，課件共75頁，創(chuàng)作于2023年2月求例2中的Gauss-Seidel法的迭代陣M的兩種方法續(xù)2由于（3-10）第一式及（3-11），（3-12）的右端上標(biāo)均為k，即為同時(shí)替換迭代式，類似于Jacobi迭代法可直接由它們得迭代陣為：第52頁，課件共75頁，創(chuàng)作于2023年2月收斂條件迭代格式收斂的充要條件是G的譜半徑<1。我們看一些充分條件定理：若A滿足下列條件之一，則Gauss-Seidel迭代收斂。①A為行或列對(duì)角占優(yōu)陣②A對(duì)稱正定陣第53頁，課件共75頁，創(chuàng)作于2023年2月證明：設(shè)G的特征多項(xiàng)式為，則為對(duì)角占優(yōu)陣，則時(shí)為對(duì)角占優(yōu)陣即即＃證畢注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂。第54頁，課件共75頁，創(chuàng)作于2023年2月兩種迭代法舉例例4

討論Jacobi迭代法與Gauss-Seidel迭代法的收斂性。

解：首先要求出迭代矩陣，然后利用推論1（（充分條件）及定理4（充分必要條件）進(jìn)行討論。

對(duì)Jacobi迭代法：第55頁，課件共75頁，創(chuàng)作于2023年2月例4（Jacobi迭代法續(xù)）第56頁，課件共75頁，創(chuàng)作于2023年2月例4（G-S迭代法續(xù)）對(duì)G-S迭代法：

第57頁，課件共75頁，創(chuàng)作于2023年2月兩種迭代法說明注1：對(duì)G-S法，為避免求逆陣可按下面兩個(gè)方法：第58頁，課件共75頁，創(chuàng)作于2023年2月兩種迭代法說明（續(xù)）第59頁，課件共75頁，創(chuàng)作于2023年2月§4松馳法

通過引入?yún)?shù)，在Gauss-Seidel法的基礎(chǔ)上作適當(dāng)修改，在不增加過多的計(jì)算量的條件下，可得到一種新的，收斂更快的迭代法。將Gauss-Seidel迭代格式（3-9）改寫為：第60頁，課件共75頁，創(chuàng)作于2023年2月松馳法（續(xù)）

通過選擇適當(dāng)?shù)膮?shù)

使此迭代格式收斂更快。

稱為松馳因子，

<1時(shí)稱為低松馳，

>1時(shí)稱為超松馳法，

=1是Gauss-Seidel迭代，簡稱為SOR法（SuccessiveOver-Relaxation）。第61頁，課件共75頁，創(chuàng)作于2023年2月將（3-13）代入（3-14）可得：

其矩陣形式為：

所以SOR法的迭代矩陣為：第62頁，課件共75頁，創(chuàng)作于2023年2月用SOR法解線性方程組（例3）

例3

取

=1.4,x

(0)=(1,1,1)T，用SOR法解線性方程組第63頁，課件共75頁，創(chuàng)作于2023年2月例3（續(xù)1）繼續(xù)下去，計(jì)算結(jié)果如下：01.00001.00001.000011.00001.00001.560021.00001.39201.618431.27441.46821.640641.21801.41361.593451.20231.39161.606861.19321.40341.600771.20511.40271.601681.19991.40001.599491.20001.39961.6001表3-3kx1(k)

x2(k)

x3(k)

第64頁，課件共75頁，創(chuàng)作于2023年2月例3（續(xù)2）所以，方程組近似解為:

松馳因子

的選取對(duì)收斂速度影響極大，如何選取

使收斂速度加快，或達(dá)到最快？這是非常重要的，但又很困難，目前尚無可供實(shí)用的計(jì)算最佳松馳因子的辦法，通常的作法是采用試算法：即從同一初值出發(fā)，選不同的松馳因子進(jìn)行試算，迭代相同的次數(shù)，來比較殘量r

(k)=b

Ax(k)的大小，選取使r(k)最小（各分量總體相差最?。┑乃神Y因子。這樣做較簡單，但比較有效。小結(jié)如下：第65頁，課件共75頁，創(chuàng)作于2023年2月迭代法的收斂條件（續(xù)2）定理4表明，迭代法收斂與否只決定于迭代矩陣

的譜半徑，與初始向量及方程組的右端項(xiàng)無關(guān)。對(duì)同一方程組，由于不同的迭代法其迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。推論2第66頁，課件共75頁，創(chuàng)作于2023年2月

定理4雖然給出了判別迭代法收斂的充要條件，但實(shí)際使用時(shí)很不方便，因?yàn)榍竽婢仃嚭吞卣髦档碾y度并不亞于用直接法求解線性方程組。而推論1僅為充分條件。很多情況下如例3，由推論1無法判別收斂性。下面對(duì)一些特殊的方程組，從方程組本身出發(fā)給出幾個(gè)常用的判別條件，而不必求迭代陣的特征值或范數(shù)。直接用矩陣A判定斂散性且至少有一個(gè)i值，使上式中不等號(hào)嚴(yán)格成立，則稱A為弱對(duì)角占優(yōu)陣。若對(duì)所有i，上式中不等號(hào)均嚴(yán)格成立，則稱A為嚴(yán)格對(duì)角占優(yōu)陣。

定義4第67頁，課件共75頁，創(chuàng)作于2023