第六章線性方程組的數(shù)值解

第六章線性方程組的數(shù)值解第一頁，共一百八十頁，編輯于2023年，星期五本章解決的問題：線性代數(shù)方程組的基本解法。§1引言第二頁，共一百八十頁，編輯于2023年，星期五矩陣形式表示為:AX=b,其中當A非奇異時，detA≠0，方程組有唯一解。n個未知量n個方程的線性代數(shù)方程組第三頁，共一百八十頁，編輯于2023年，星期五解線性方程組的兩類方法：直接法:經(jīng)過有限次運算后可求得方程組精確解的方法(不計舍入誤差!)迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）第四頁，共一百八十頁，編輯于2023年，星期五一.Gauss消去法過程:1.消元:§2.Gauss消去法第五頁，共一百八十頁，編輯于2023年，星期五=思路首先將方程組Ax=b

化為上三角方程組，此過程稱為消去過程，再求解上三角方程組，此過程稱為回代過程.第六頁，共一百八十頁，編輯于2023年，星期五2.回代過程:第七頁，共一百八十頁，編輯于2023年，星期五矩陣形式表示為:AX=b,其中當A非奇異時，detA≠0，方程組有唯一解。n個未知量n個方程的線性代數(shù)方程組二.一般線性方程組的Gauss消去法計算過程第八頁，共一百八十頁，編輯于2023年，星期五第一步：記乘數(shù)為:第九頁，共一百八十頁，編輯于2023年，星期五相當于第一個方程×(-乘數(shù)mi1)加到第i方程上去得到等價方程:第十頁，共一百八十頁，編輯于2023年，星期五第十一頁，共一百八十頁，編輯于2023年，星期五上述消元過程除第一個方程不變以外,

第2至第n個方程全消去了變量x1，而系數(shù)

和常數(shù)項全得到新值.第十二頁，共一百八十頁，編輯于2023年，星期五第十三頁，共一百八十頁，編輯于2023年，星期五第十四頁，共一百八十頁，編輯于2023年，星期五第k-1次消元得到第十五頁，共一百八十頁，編輯于2023年，星期五k次消元第十六頁，共一百八十頁，編輯于2023年，星期五第十七頁，共一百八十頁，編輯于2023年，星期五系數(shù)矩陣與常數(shù)項：第十八頁，共一百八十頁，編輯于2023年，星期五回代過程算法第十九頁，共一百八十頁，編輯于2023年，星期五問題1.消元過程能按順序進行到底的充要條件是什么？答：問題2.在原方程組的系數(shù)矩陣中如何反映出這個條件呢?稱為消元過程的主元素。第二十頁，共一百八十頁，編輯于2023年，星期五A的k階順序主子矩陣Ak的行列式值是:就是要求A的所有順序主子式均不為0，第二十一頁，共一百八十頁，編輯于2023年，星期五定理1(高斯消去法)設(shè)Ax=b，其中A∈Rn×n。如果約化的主元素akk≠0(k=1,2…,n)，則可通過高斯消去法(不進行交換兩行的初等交換)將方程組Ax=b約化為三角形矩陣方程組且消元和求解公式為(1)消元計算k=1,2,…,n-1第二十二頁，共一百八十頁，編輯于2023年，星期五(2)回代第二十三頁，共一百八十頁，編輯于2023年，星期五四、Gauss消去法乘法計算量(1)消元計算：在第k步(k=1,2….n-1)1、計算乘數(shù)：需作n-k次除法運算；2、消元：需作有(n-k)2次乘法運算3、計算b(k):需作(n-k)次乘法運算；第二十四頁，共一百八十頁，編輯于2023年，星期五高斯消去法解方程組Ax=b的計算量即總共為除法運算次數(shù)為n次.乘法運算次數(shù)為(n-1)+…+1=n(n-1)/2次；共需要作n(n＋1)/2次乘除法運算。（2）回代過程的計算通常也說Gauss消去法的運算次數(shù)與n3同階,記為O(n3)第二十五頁，共一百八十頁，編輯于2023年，星期五第二十六頁，共一百八十頁，編輯于2023年，星期五第二十七頁，共一百八十頁，編輯于2023年，星期五第二十八頁，共一百八十頁，編輯于2023年，星期五6.3選主元高斯消去法第二十九頁，共一百八十頁，編輯于2023年，星期五為避免這種情況的發(fā)生,可通過交換方程的次序，選取絕對值大的元素作主元.基于這種思想導(dǎo)出了主元素法在高斯消去法消去過程中可能出現(xiàn)的情況，這時高斯消去法將無法進行；即使主因素但很小，其作除數(shù)，也會導(dǎo)致其它元素數(shù)量級的嚴重增長和舍誤差的擴散第三十頁，共一百八十頁，編輯于2023年，星期五例：單精度解方程組/*精確解為和*/8個8個用Gaussian消元法計算：8個小主元可能導(dǎo)致計算失敗。第三十一頁，共一百八十頁，編輯于2023年，星期五選主元高斯消去法基本思想：每次消元前按一定的范圍選取絕對值最大的元素作為主元素,以便減少舍入誤差的影響。主要有列主元高斯消去法和全主元高斯消去法.第三十二頁，共一百八十頁，編輯于2023年，星期五1.列主元消元法思想若交換k行和j行行的交換，不改變方程組的解，同時又有效地克服了Gauss消元地缺陷,這種方法稱為列主元Gauss消去法。例：一、列主元消元法思想在第k步消元前，在系數(shù)矩陣第k列的對角線以下的元素中找出絕對值最大的元。

第三十三頁，共一百八十頁，編輯于2023年，星期五交換2.列主元消元法步驟:第一步:從第一列中選出絕對值最大的元素第三十四頁，共一百八十頁，編輯于2023年，星期五第k步從的第k列，，中選取絕對值最大項，記錄所在行，即若交換第k行與行的所有對應(yīng)元素，再進行順序消元。具體如下:

第三十五頁，共一百八十頁，編輯于2023年，星期五當k-1列消元后增廣矩陣為第k次消元時，先選列主元素，即在第k列以下的各元素中尋找絕對值最大的元素作為主元素,即確定ik，使中之最大者。

為第三十六頁，共一百八十頁，編輯于2023年，星期五第三十七頁，共一百八十頁，編輯于2023年，星期五第三十八頁，共一百八十頁，編輯于2023年，星期五二、全主元高斯消去法全主元消去法，在第k列(k=1,2,…，n-1)消元時，從系數(shù)矩陣的右下角(n-k+1)階子矩陣中，選取絕對值最大的元素作為主元素。1、全主元高斯消去法基本思想:第三十九頁，共一百八十頁，編輯于2023年，星期五設(shè)有線性方程組Ax=b，其中A為非奇異矩陣。方程組的增廣矩陣為2、全主元高斯消去法步驟:第四十頁，共一百八十頁，編輯于2023年，星期五第1步(k=1)：首先在A中選主元素，即選擇i1,j1使再交換(A,b)的第1行與第i1行元素，交換A的第1列與第j1列元素，將ai1j1調(diào)到(1,1)位置(交換后增廣陣為簡單起見仍記為(A,b))；然后,進行消元計算。第四十一頁，共一百八十頁，編輯于2023年，星期五第四十二頁，共一百八十頁，編輯于2023年，星期五第四十三頁，共一百八十頁，編輯于2023年，星期五Gauss全主元消去法：優(yōu)點------計算結(jié)果更可靠；缺點------挑主元花機時更多，次序有變動，程序復(fù)雜。第四十四頁，共一百八十頁，編輯于2023年，星期五矩陣的三角分解第四十五頁，共一百八十頁，編輯于2023年，星期五§4三角分解法一.高斯消元法的矩陣形式從矩陣理論來看Gauss消元法的第k步消去過程相當于左乘初等變換矩陣Lk第四十六頁，共一百八十頁，編輯于2023年，星期五第四十七頁，共一百八十頁，編輯于2023年，星期五第四十八頁，共一百八十頁，編輯于2023年，星期五第四十九頁，共一百八十頁，編輯于2023年，星期五A

的

LU

分解第五十頁，共一百八十頁，編輯于2023年，星期五第五十一頁，共一百八十頁，編輯于2023年，星期五證明：由§1中定理可知，LU分解存在。下面證明唯一性。若不唯一，則可設(shè)A=L1U1=L2U2，推出上三角矩陣對角線上為1的下三角矩陣注：（1）L為單位下三角陣而U為一般上三角陣的分解稱為Doolittle

分解（2）L為一般下三角陣而U為單位上三角陣的分解稱為Crout分解。

定理2(矩陣的LU分解)設(shè)A∈Rn×n。如果A的順序主子式det(Ai)≠0,(i=1,2,…,n-1)，則A可分解為一個單位下三角陣L與一個上三角陣U的乘積，即A=LU，且分解是惟一的。第五十二頁，共一百八十頁，編輯于2023年，星期五杜利特爾分解(Doolittle)常用的另一種三角分解：克勞特分解(Crout)第五十三頁，共一百八十頁，編輯于2023年，星期五通過比較法直接導(dǎo)出L和U的計算公式。1.思路二.Doolittle分解法：第五十四頁，共一百八十頁，編輯于2023年，星期五第五十五頁，共一百八十頁，編輯于2023年，星期五第五十六頁，共一百八十頁，編輯于2023年，星期五2.一般計算公式比較第1行：比較第1列：第五十七頁，共一百八十頁，編輯于2023年，星期五第五十八頁，共一百八十頁，編輯于2023年，星期五第五十九頁，共一百八十頁，編輯于2023年，星期五第六十頁，共一百八十頁，編輯于2023年，星期五第六十一頁，共一百八十頁，編輯于2023年，星期五設(shè)A非奇異，并有三角分解A=LU，則方程組Ax=b就化為

LUx=b

只須求解兩個簡單的三角形方程組：（1）解Ly=b求出y，(2)解Ux=y，求出x.三.LU分解求解線性方程組第六十二頁，共一百八十頁，編輯于2023年，星期五(1).解Ly=b求出y，第六十三頁，共一百八十頁，編輯于2023年，星期五展開方程組Ly=b,得第六十四頁，共一百八十頁，編輯于2023年，星期五(2).解Ux=y，求出x.展開方程組Ux=y,得第六十五頁，共一百八十頁，編輯于2023年，星期五第六十六頁，共一百八十頁，編輯于2023年，星期五總運算量為：第六十七頁，共一百八十頁，編輯于2023年，星期五四.例題第六十八頁，共一百八十頁，編輯于2023年，星期五第六十九頁，共一百八十頁，編輯于2023年，星期五第七十頁，共一百八十頁，編輯于2023年，星期五第七十一頁，共一百八十頁，編輯于2023年，星期五第七十二頁，共一百八十頁，編輯于2023年，星期五練習(xí)1：

試求矩陣的杜利特爾分解，克勞特分解練習(xí)2:用杜利特爾分解法求解方程組第七十三頁，共一百八十頁，編輯于2023年，星期五定理3：設(shè)A為非奇異陣，則必存在置換矩陣P，使得其中L為單位下三角陣，U為非奇異的上三角陣。第七十四頁，共一百八十頁，編輯于2023年，星期五§5求解三對角方程組的追趕法第七十五頁，共一百八十頁，編輯于2023年，星期五在實際問題中如樣條插值及常微分方程邊值問題的數(shù)值解中，會遇到求解三對角線形線組：b1x1+c1x2=f1a2x1+b2x2+c2x3=f2a3x2+b3x3+c3x4=f3an-1xn-2+bn-1xn-1+cn-1xn=fn-1anxn-1+bnxn=fn§5求解三對角方程組的追趕法第七十六頁，共一百八十頁，編輯于2023年，星期五

A為三對角陣，且滿足對于具有以上條件的方程組，我們介紹下述的追趕法求解。追趕法具有計算量少，方法簡單，算法穩(wěn)定等特點。第七十七頁，共一百八十頁，編輯于2023年，星期五第七十八頁，共一百八十頁，編輯于2023年，星期五第七十九頁，共一百八十頁，編輯于2023年，星期五第八十頁，共一百八十頁，編輯于2023年，星期五第八十一頁，共一百八十頁，編輯于2023年，星期五第八十二頁，共一百八十頁，編輯于2023年，星期五第一步:對A作Crout分解第八十三頁，共一百八十頁，編輯于2023年，星期五直接比較等式兩邊的元素，可得到計算公式（p.184）可得到計算公式第八十四頁，共一百八十頁，編輯于2023年，星期五第二步:追—即解：第三步:趕—即解：第八十五頁，共一百八十頁，編輯于2023年，星期五追趕法公式實際上就是把高斯消元法用到求解三對角線方程組上去的結(jié)果，這時由于A特別簡單，因此使得求解的計算公式非常簡單，而且計算量僅有5n-4次乘除法。3n-3次加減法，工作量小，電算時，需要3個一維數(shù)組存儲A的系數(shù)，兩個一維數(shù)組保存中間結(jié)果。第八十六頁，共一百八十頁，編輯于2023年，星期五例6

用追趕法解方程組第八十七頁，共一百八十頁，編輯于2023年，星期五練習(xí):用追趕法解線組第八十八頁，共一百八十頁，編輯于2023年，星期五§6對稱正定陣的平方根法第八十九頁，共一百八十頁，編輯于2023年，星期五設(shè)有方程組Ax=b，其中，A∈Rn×n。若A滿足下述條件，則稱A為對稱正定矩陣。一.對稱正定陣②對任意非零向量x∈Rn，則有(Ax,x)=xTAx>0。①A對稱，即AT=A；第九十頁，共一百八十頁，編輯于2023年，星期五回顧：對稱正定陣A的幾個重要性質(zhì)（1）A1

亦對稱正定，且aii>0（2）A

的順序主子陣

Ak

亦對稱正定（3）A

的特征值i

>0

(i=1,2,…,n)（4）A

的全部順序主子式

det(Ak

)>0(i=1,2,…,n)二.對稱正定陣重要性質(zhì)第九十一頁，共一百八十頁，編輯于2023年，星期五三對稱正定陣的LDLT分解設(shè)A為對稱正定矩陣，則由定理知，A有惟一的三角分解為利用A的對稱性,將U分解為U=DU0其中第九十二頁，共一百八十頁，編輯于2023年，星期五于是，（6.6.2）第九十三頁，共一百八十頁，編輯于2023年，星期五第九十四頁，共一百八十頁，編輯于2023年，星期五由矩陣三角分解的惟一性，則從而對稱正定矩陣A有惟一分解式（6.6.3）由式(6.6.2)可知第九十五頁，共一百八十頁，編輯于2023年，星期五于是，對角陣D還可以分解為代入式(6.6.3)，則有第九十六頁，共一百八十頁，編輯于2023年，星期五定理6(對稱正定陣的三角分解)設(shè)A為n階對稱正定矩陣，則有三角分解：①A=LDLT，其中L為單位下三角陣，D為對角陣，或②A=LLT，其中，L為下三角陣且當限定L的對角元素為正時，這種分解是惟一的，這種矩陣分解稱為(Cholesky)分解。第九十七頁，共一百八十頁，編輯于2023年，星期五下面推導(dǎo)實現(xiàn)分解計算A=LLT的遞推公式及求解公式。設(shè)有Ax=b，其中A∈Rn×n為對稱正定矩陣，于是有三角分解四.計算A=LLT的遞推公式，及求解公式。其中，lii>0(i=1,2,…,n)。第九十八頁，共一百八十頁，編輯于2023年，星期五由矩陣乘法，則有L的第1列元素同理，可確定L的第j列元素lij(i=j,…,n)。(當j＜k時，則ljk=0)第九十九頁，共一百八十頁，編輯于2023年，星期五第一百頁，共一百八十頁，編輯于2023年，星期五第一百零一頁，共一百八十頁，編輯于2023年，星期五Cholesky分解法缺點及優(yōu)點優(yōu)點：可以減少存儲單元。缺點：存在開方運算，可能會出現(xiàn)根號下負數(shù)。第一百零二頁，共一百八十頁，編輯于2023年，星期五由分解公式有所以說明ljk是有界的,數(shù)量級不會增長,因此平方根法計算是數(shù)值穩(wěn)定的第一百零三頁，共一百八十頁，編輯于2023年，星期五例7:用平方根法求以下方程組的解.求得x=(1.0,-1.0,2.0)第一百零四頁，共一百八十頁，編輯于2023年，星期五Cholesky分解法要用到開方運算，為避免開方運算，可將A分解為A=LDLT(其中L為單位下三角矩陣)，再分別解方程組LY=b及DLTX=Y或，這種方法稱為改進平方根法.第一百零五頁，共一百八十頁，編輯于2023年，星期五§7.向量和矩陣的范數(shù)第一百零六頁，共一百八十頁，編輯于2023年，星期五為了研究線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，——向量和矩陣的范數(shù)。第一百零七頁，共一百八十頁，編輯于2023年，星期五定義7.1(向量范數(shù))如果向量x∈Rn的某個實值函數(shù)N(x)≡‖x‖滿足條件①正定條件：‖x‖≥0且‖x‖=0x=0向量;②齊次性：‖αx‖=｜α｜‖x‖，α為實數(shù)或復(fù)數(shù);③三角不等式：‖x+y‖≤‖x‖+‖y‖，對任意向量x,y∈Rn。稱N(x)≡‖x‖是Rn上的一個向量范數(shù)(或向量的模)。一:向量范數(shù)1.向量范數(shù)定義第一百零八頁，共一百八十頁，編輯于2023年，星期五④利用三角不等式可推得(見圖6.2)|‖x‖-‖y‖|≤‖x-y‖第一百零九頁，共一百八十頁，編輯于2023年，星期五定義7.2設(shè)x=(x1,x2,…,xn)T∈Rn，定義Rn上3種常用的向量范數(shù)2:幾種常用的向量范數(shù)③向量的“2”范數(shù)②向量的“∞”范數(shù)①向量的“1”范數(shù)第一百一十頁，共一百八十頁，編輯于2023年，星期五第一百一十一頁，共一百八十頁，編輯于2023年，星期五第一百一十二頁，共一百八十頁，編輯于2023年，星期五定義3(向量序列的極限)設(shè){x(k)}為向量序列，記x(k)=(x1(k),x2(k),…,xn(k))T∈Rn及x*=(x1*,…,xn*)T∈Rn。如果n個數(shù)列極限存在且則稱{x(k)}收斂于x*，記為3:向量序列的極限第一百一十三頁，共一百八十頁，編輯于2023年，星期五定理7設(shè){x(k)}是Rn中一向量序列，且x*∈Rn，則證只就υ=∞證明。顯然有第一百一十四頁，共一百八十頁，編輯于2023年，星期五1.定義7.4(矩陣的范數(shù)) 如果矩陣A∈Rn×n的某個非負實值函數(shù)N(A)=‖A‖滿足下述條件①正定性：‖A‖≥0，且‖A‖=0A=0矩陣；②齊次性：‖αA‖=α‖A‖，α為實數(shù)或復(fù)數(shù)；③三角不等式：‖A+B‖≤‖A‖+‖B‖，對任意矩陣A,B∈Rn×n；④‖AB‖≤‖A‖‖B‖。則稱N(A)=‖A‖是Rn×n上一個矩陣范數(shù)(或模)。二:矩陣的范數(shù)第一百一十五頁，共一百八十頁，編輯于2023年，星期五2.相容范數(shù)第一百一十六頁，共一百八十頁，編輯于2023年，星期五3.算子范數(shù)注:||A||滿足相容性的條件第一百一十七頁，共一百八十頁，編輯于2023年，星期五定理8(矩陣范數(shù)計算公式)設(shè)x∈Rn，A∈Rn×n，則其中λmax(ATA)表示ATA的最大特征值。4.(矩陣范數(shù)計算公式)對應(yīng)于3種常見的向量范數(shù)，有3種矩陣范數(shù)第一百一十八頁，共一百八十頁，編輯于2023年，星期五三例題第一百一十九頁，共一百八十頁，編輯于2023年，星期五第一百二十頁，共一百八十頁，編輯于2023年，星期五§8線性代數(shù)方程組的迭代解法

迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。第一百二十一頁，共一百八十頁，編輯于2023年，星期五一.迭代法的基本思想(1)將線性方程組轉(zhuǎn)化為便于迭代的等價方程組，線性方程組迭代法的思想:A非奇異,方程組有惟一解

(2)改寫成迭代格式(3)對任選一組初始值，按迭代格式逐步迭代,得到向量序列{x(k)}第一百二十二頁，共一百八十頁，編輯于2023年，星期五(4)如果

存在極限則稱迭代法是收斂的，否則就是發(fā)散的。即:這種方法稱為迭代法第一百二十三頁，共一百八十頁，編輯于2023年，星期五當時，,則,故是方程組的解。收斂時，在迭代公式第一百二十四頁，共一百八十頁，編輯于2023年，星期五實例分析例題10求解方程組矩陣形式：第一百二十五頁，共一百八十頁，編輯于2023年，星期五首先將Ax=b轉(zhuǎn)化為等價方程組解：有精確解第一百二十六頁，共一百八十頁，編輯于2023年，星期五第一百二十七頁，共一百八十頁，編輯于2023年，星期五迭代公式如果取初始向量第一百二十八頁，共一百八十頁，編輯于2023年，星期五迭代結(jié)果分析：并不是每一個迭代公式所構(gòu)造的迭代序列都收斂。于是，計算方法的目的就是要尋求一個使得構(gòu)造序列收斂的方法。因此產(chǎn)生了各種各樣的迭代方法，根據(jù)迭代矩陣的不同構(gòu)造方法，形成了不同的迭代方法。這里介紹兩種迭代方法：雅可比迭代方法、高斯-塞德爾迭代方法以及超松弛迭代方法。并有記：第一百二十九頁，共一百八十頁，編輯于2023年，星期五設(shè)方程組的系數(shù)矩陣A非奇異，可將A分裂成

記作A=D-L-U第一百三十頁，共一百八十頁，編輯于2023年，星期五Ax=b線性方程組：A=D-L-U或A=M-N記等價線性方程組：Mx=Nx+bM可選擇為一個非奇異矩陣，且使Mx=f容易求解，一般選擇為A的某種近似構(gòu)造迭代過程：第一百三十一頁，共一百八十頁，編輯于2023年，星期五雅可比迭代的矩陣形式為J為雅可比迭代矩陣。

第一百三十二頁，共一百八十頁，編輯于2023年，星期五考察一般的方程組，將n元線性方程組

寫成2.雅可比迭代的分量形式第一百三十三頁，共一百八十頁，編輯于2023年，星期五據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式分量形式。若,分離出變量第一百三十四頁，共一百八十頁，編輯于2023年，星期五展開為：(k=0,1,2,…)第一百三十五頁，共一百八十頁，編輯于2023年，星期五如上例的雅可比迭代公式為第一百三十六頁，共一百八十頁，編輯于2023年，星期五8.2高斯-塞德爾（Gauss-Seidel）迭代法一.高斯-塞德爾迭代法的基本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,n

k=0,1,2,…)第一百三十七頁，共一百八十頁，編輯于2023年，星期五思想：設(shè)想把x1(k+1)算出后立即代替x1(k)用于后面分量的計算，當x2(k+1)算出后立即代替x2(k)用于后面分量的計算，…，期望這樣會收斂得快些。第一百三十八頁，共一百八十頁，編輯于2023年，星期五二.Gauss—Seidel迭代法的矩陣表示將A分裂成A=D-L-U，則等價于

(D-L-U)x=b，如果取M=D－L（下三角矩陣），于是：N=M-A=U,于是：因為,所以

則高斯-塞德爾迭代形式為：故令G稱為高斯-塞德爾迭代矩陣第一百三十九頁，共一百八十頁，編輯于2023年，星期五三.高斯-賽德爾(Seidel)迭代公式分量形式迭代公式即令第一百四十頁，共一百八十頁，編輯于2023年，星期五例題11：用高斯-塞德爾迭代公式(GS)解方程組第一百四十一頁，共一百八十頁，編輯于2023年，星期五高斯-塞德爾迭代公式(GS)第一百四十二頁，共一百八十頁，編輯于2023年，星期五GS迭代法和Jacobi迭代法的比較：通常當兩種方法都收斂時，GS迭代法往往收斂快一些。但有時Jacobi迭代法收斂而GS迭代法發(fā)散；有時又相反。例如方程組雅可比迭代公式方程組收斂而GS迭代公式發(fā)散。

發(fā)散，但GS迭代公式收斂。的雅可比迭代公式第一百四十三頁，共一百八十頁，編輯于2023年，星期五8.3超松弛迭代法（SOR方法）

使用迭代法的困難在于難以估計其計算量。有時迭代過程雖然收斂，但由于收斂速度緩慢，使計算量變得很大而失去使用價值。因此，迭代過程的加速具有重要意義。逐次超松弛迭代（SuccessiveOverrelaxaticMethod，簡稱SOR方法）法，可以看作是帶參數(shù)的高斯—塞德爾迭代法，實質(zhì)上是高斯-塞德爾迭代的一種加速方法。

第一百四十四頁，共一百八十頁，編輯于2023年，星期五一.超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果與高斯-塞德爾迭代方法的迭代值適當加權(quán)平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。其具體計算公式如下：

⑴用高斯—塞德爾迭代法定義輔助量。第一百四十五頁，共一百八十頁，編輯于2023年，星期五⑵把取為與的加權(quán)平均，即

合并表示為：

式中系數(shù)ω稱為松弛因子，當ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。

當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。

第一百四十六頁，共一百八十頁，編輯于2023年，星期五二.超松弛迭代法的矩陣表示設(shè)線性方程組AX=b的系數(shù)矩陣A非奇異,且主對角元素,則將A分裂成A=D-L-U,則超松弛迭代公式用矩陣表示為或故

顯然對任何一個ω值,(D-ωL)非奇異,(因為假設(shè))于是超松弛迭代公式為第一百四十七頁，共一百八十頁，編輯于2023年，星期五令則超松弛迭代公式可寫成第一百四十八頁，共一百八十頁，編輯于2023年，星期五例12用SOR法求解線性方程組

k=0,1,2,…，

初值第一百四十九頁，共一百八十頁，編輯于2023年，星期五8.4迭代法的收斂性

我們知道,對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂。現(xiàn)在分析它們的收斂性。

對于方程組經(jīng)過等價變換構(gòu)造出的等價方程組

在什么條件下迭代序列收斂？先引入如下定理

第一百五十頁，共一百八十頁，編輯于2023年，星期五設(shè)有方程組x=Bx+f,

x*=Bx*+f,迭代公式于是由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時于是當?shù)仃嘊滿足引入誤差向量所以必有迭代法收斂則第一百五十一頁，共一百八十頁，編輯于2023年，星期五迭代公式,若迭代矩陣B的一種范數(shù)(2)(3)且有誤差估計式(1){x(k)}收斂于方程的唯一解X*則定理10(迭代法收斂的充分條件)一、迭代收斂的充分條件第一百五十二頁，共一百八十頁，編輯于2023年，星期五因為,則det(I-B)≠0,I-B為非奇異矩陣,故x＝Bx＋f有惟一解,即與迭代過程相比較,有兩邊取范數(shù)

∴

第一百五十三頁，共一百八十頁，編輯于2023年，星期五由迭代格式，有

兩邊取范數(shù)，代入上式，得證畢由定理知，當時，其值越小，迭代收斂越快，在程序設(shè)計中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結(jié)束的條件第一百五十四頁，共一百八十頁，編輯于2023年，星期五例13：已知方程組考察用Jacobi迭代法求解時的收斂性第一百五十五頁，共一百八十頁，編輯于2023年，星期五例題14：求的譜半徑第一百五十六頁，共一百八十頁，編輯于2023年，星期五第一百五十七頁，共一百八十頁，編輯于2023年，