第八章ppt線性方程組迭代法

第八章ppt線性方程組迭代法第一頁，共三十六頁，編輯于2023年，星期四一、基本思想若方程組Ax=b可寫成等價形式x=Bx+f，(8-1)則給定一個初始向量x(0)，可以得到迭代公式x(k+1)=Bx(k)+f，k=0，1，…(8-2)若上式確定的向量序列{x(k)}收斂于x，則x顯然是(8-1)的解，從而為方程組Ax=b的解。形如(8-2)的逐次逼近的方法稱為簡單迭代法，B稱為該迭代法的迭代矩陣。§8.1線性方程組迭代解法第二頁，共三十六頁，編輯于2023年，星期四2.需要討論的問題：怎樣建立迭代格式，迭代過程是否收斂，誤差分析，如何加快收斂速度等等。迭代法是一種逐次逼近的方法,與直接法(高斯消元法)比較,具有:程序簡單,存儲量小的優(yōu)點(diǎn)。特別適用于求解系數(shù)矩陣為大型稀疏矩陣的方程組。常用迭代方法：

雅可比迭代，高斯-賽德爾迭代，松弛迭代等。

第三頁，共三十六頁，編輯于2023年，星期四二、Jacobi（雅可比）迭代法建立迭代格式：可以縮寫為：按此格式迭代求解的方法稱為雅可比迭代法,簡稱J法。第四頁，共三十六頁，編輯于2023年，星期四例1用雅可比迭代法解線性方程組解生成雅可比迭代格式：kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15……………….……111.0999931.1999931.299991121.0999981.1999981.299997從上表可以看出，迭代序列收斂于x*，若取x(12)作為近似解，則誤差不超過10-5第五頁，共三十六頁，編輯于2023年，星期四寫成矩陣形式：BJacobi迭代陣，簡記為BJ第六頁，共三十六頁，編輯于2023年，星期四Jacobi迭代法的算法第七頁，共三十六頁，編輯于2023年，星期四三、Gauss–Seidel（高斯—塞德爾）迭代法第八頁，共三十六頁，編輯于2023年，星期四…………寫成矩陣形式：BGauss-Seidel迭代陣，簡記為BGS第九頁，共三十六頁，編輯于2023年，星期四Gauss-Seidel迭代法的分量形式為：例2分別給出以下線性方程組的Jacobi迭代格式和Gauss-Seidel迭代格式：

解原方程等價于第十頁，共三十六頁，編輯于2023年，星期四上一頁下一頁

返回

建立Jacobi迭代格式如下

建立Gauss-Seidel迭代格式如下

第十一頁，共三十六頁，編輯于2023年，星期四例3用高斯-塞德爾迭代法求解例1中的方程組

建立Gauss-Seidel迭代格式

解迭代8次可得在本例中Gauss-Seidel迭代法比Jacobi迭代法收斂快。這個結(jié)論在多數(shù)情況下成立，但高斯-塞德爾的收斂更快是有條件的。注：兩種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時，Jacobi法可能不收斂；而Jacobi法收斂時，Gauss-Seidel法也可能不收斂。第十二頁，共三十六頁，編輯于2023年，星期四§8.2向量和矩陣的范數(shù) 為了研究線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量——向量和矩陣的范數(shù)。在一維數(shù)軸上，實(shí)軸上任意一點(diǎn)x到原點(diǎn)的距離用|x|表示。而任意兩點(diǎn)x1，x2之間距離用|x1-x2|表示。第十三頁，共三十六頁，編輯于2023年，星期四而在二維平面上，平面上任意一點(diǎn)P(x,y)到原點(diǎn)的距離用表示。而平面上任意兩點(diǎn)P1(x1,y1),P2(x2,y2)的距離用表示。推廣到n維空間，則稱為向量范數(shù)。第十四頁，共三十六頁，編輯于2023年，星期四定義8.2.1中的三個條件描述了向量范數(shù)的三個性質(zhì)，分別稱為非負(fù)性、齊次性和三角不等式。常見的向量范數(shù) 1-范數(shù)2-范數(shù)∞-范數(shù)第十五頁，共三十六頁，編輯于2023年，星期四矩陣范數(shù)第十六頁，共三十六頁，編輯于2023年，星期四常見的矩陣范數(shù)第十七頁，共三十六頁，編輯于2023年，星期四第十八頁，共三十六頁，編輯于2023年，星期四向量的收斂性第十九頁，共三十六頁，編輯于2023年，星期四矩陣序列的收斂性第二十頁，共三十六頁，編輯于2023年，星期四矩陣的譜半徑和矩陣序列收斂性第二十一頁，共三十六頁，編輯于2023年，星期四第二十二頁，共三十六頁，編輯于2023年，星期四迭代法收斂的充要條件:定理的收斂條件一、一般迭代法§8.3線性方程組迭代法收斂條件第二十三頁，共三十六頁，編輯于2023年，星期四例6設(shè)方程組的系數(shù)矩陣為判別Jacobi迭代與Gauss-Seidel迭代是否收斂。解Jacobi迭代矩陣為第二十四頁，共三十六頁，編輯于2023年，星期四所以，Jacobi迭代法發(fā)散。

高斯-塞德爾迭代矩陣為

所以，高斯-塞德爾迭代法收斂。

困難：具體問題中，很難計算。

第二十五頁，共三十六頁，編輯于2023年，星期四定理

（充分條件）若存在某一個矩陣范數(shù)使得||B||<1,則迭代收斂，且有下列誤差估計：①②證明：①②第二十六頁，共三十六頁，編輯于2023年，星期四①上述定理只是判別迭代格式收斂的充分條件，但若，則不能下結(jié)論說迭代法發(fā)散，只能用進(jìn)行判斷。②由上述定理知‖B‖越小，收斂越快。同時可獲得迭代解的事后誤差估計，當(dāng)（即迭代法收斂較快）時，可用如下停機(jī)準(zhǔn)則控制迭代結(jié)束：注意：第二十七頁，共三十六頁，編輯于2023年，星期四解：按照迭代公式有：所以，J法和GS法必收斂，并且，GS法比J法收斂快。第二十八頁，共三十六頁，編輯于2023年，星期四由此可見，實(shí)際的計算結(jié)果也表明GS比J法收斂快。第二十九頁，共三十六頁，編輯于2023年，星期四上一頁下一頁

返回

二、Jacobi迭代法和Gauss-Seidel迭代法的收斂性1、Jacobi方法收斂的條件

充要條件：充分條件：2、Gauss-Seidel方法收斂的條件充要條件：充分條件：第三十頁，共三十六頁，編輯于2023年，星期四三、其他收斂的判別條件定義：設(shè)A=(aij)nn，若i=1，2，…，n，則稱A按行嚴(yán)格對角占優(yōu)

注：若A按行嚴(yán)格對角占優(yōu)，則A可逆定理：設(shè)Ax=b，若A按行嚴(yán)格對角占優(yōu)，則對于任意的x(0)，J-迭代均收斂。第三十一頁，共三十六頁，編輯于2023年，星期四證明：第三十二頁，共三十六頁，編輯于2023年，星期四定理

（充分條件）若A為對稱正定陣，則解的Gauss-Seidel迭代法收斂。定理

（充要條件）若A是對角元為正的實(shí)對稱陣，則解的Jacobi迭代法收斂第三十三頁，共三十六頁，編輯于2023年，星期四例7.

判別用Jacobi迭代法與Gauss-Seidel迭代法是否收斂，若收斂則寫出其迭代格式。解:(1).Jacobi迭代法