《數(shù)值計算方法》課件3方程組的迭代解法

應(yīng)用背景及數(shù)學(xué)模型

在自然科學(xué)和工程技術(shù)中，許多問題的解決往往歸結(jié)為線性方程組的求解問題，如電路網(wǎng)絡(luò)、結(jié)構(gòu)設(shè)計、數(shù)據(jù)分析、應(yīng)力分析、自由振動等問題，另外，許多有效的數(shù)值計算方法，其關(guān)鍵步驟就是要求解解線性方程組，如三次樣條插值、常微分方程邊值問題的差分法和有限元法、最小二乘等問題。

線性方程組的數(shù)學(xué)模型如下：引入矩陣及向量符號后,其矩陣形式為：按階數(shù)分為：高階：n>1000中階：500-1000低階：n<500按系數(shù)矩陣的形狀和性質(zhì)分為：對稱正定三對角對角占優(yōu)按系數(shù)矩陣零元素的多少分為：稠密型稀疏型3方程組的迭代解法

（IterativeSolutionofEquations）

數(shù)學(xué)方法及存在問題

由克萊姆(Gramer)法則可知：若線性方程組(3-2)的系數(shù)行列式D=det(A)非零，則線性方程組(3-2)有且有惟一解，且xj=Dj/D。但該方法僅乘(除)法運(yùn)算的次數(shù)高達(dá)(n+1)n!(n-1)次，當(dāng)n較大時，其計算量是相當(dāng)驚人的。如n=20時，計算量大約為1021，用每秒一億次浮點運(yùn)算的計算機(jī)也需要計算30萬年。

數(shù)值方法基本思想

線性方程組的數(shù)值解法分為兩大類，即迭代法和直接法

迭代法（第3章）思想：類似于一元方程的迭代法，構(gòu)造迭代公式，用序列逼近特點：占內(nèi)存少、程序設(shè)計簡單適用：中、大規(guī)模問題，尤其是高階稀疏矩陣問題：迭代過程（矩陣）的收斂性與收斂速度

直接法（第4章）思想：對系數(shù)矩陣進(jìn)行分解、變換，經(jīng)有限次算術(shù)運(yùn)算，求出精確解特點：準(zhǔn)確、可靠、無方法誤差適用：中、小規(guī)模問題，尤其是稠密系數(shù)矩陣問題：舍入誤差對病態(tài)方程組的影響，算法可能不穩(wěn)定

常見的線性方程組數(shù)值方法分類3.1.1向量的范數(shù)向量的范數(shù)、1范數(shù)、2范數(shù)、范數(shù)、p范數(shù)向量序列的極限和收斂性定理、范數(shù)的等價性定理3.1.2矩陣的范數(shù)

3.1.3矩陣級數(shù)的收斂性

矩陣序列的極限矩陣級數(shù)的收斂性定理Neumann引理矩陣的范數(shù)、1范數(shù)（列和范數(shù)）、2范數(shù)、范數(shù)（行和范數(shù)）矩陣的范數(shù)的性質(zhì)、矩陣的普半徑矩陣范數(shù)的等價性、矩陣范數(shù)和普半徑的關(guān)系定理3.1

向量和矩陣的范數(shù)向量與矩陣的范數(shù)3.1

向量和矩陣的范數(shù)例3-2P393.2線性方程組的迭代解法3.2.1雅克比(Jacobi)迭代法

迭代法的基本思想是構(gòu)造迭代公式，用某種極限過程去逐步逼近線性方程組的精確解。線性方程組迭代公式的基本形式為：

Jacobi迭代公式的構(gòu)造Jacobi迭代法又稱簡單迭代法，是其它方法的基礎(chǔ)。將(3-1)變形為其中：B稱為迭代矩陣f稱為迭代向量從而得到Jacobi迭代公式（3-5）例3-3

用Jacobi迭代法求解

Jacobi迭代法的特點簡單可并行計算有三種固定格式的迭代方法3.2.2高斯-賽德爾(Gauss-Seidel)迭代法

Gauss-Seidel迭代公式的構(gòu)造

該方法基于分量的上標(biāo)越大，越接近于精確解。故用分量和計算分量。從而得到Gauss-Seidel迭代公式（3-6）

Gauss-Seidel迭代法的特點通常較Jacobi迭代快、節(jié)省空間不具備并行計算功能例3-4P41

Gauss-Seidel迭代算法步驟與流程圖

P42圖3-1兩種迭代算法程序及算例演示3.2.3超松弛迭代法

超松弛迭代公式的構(gòu)造超松弛迭代法是對Gauss-Seidel迭代法的一種改進(jìn)，是求解大型稀疏矩陣方程組的有效方法之一。其思想是：為求得，先把用Gauss-Seidel迭代的記作，即再令于是得到超松弛迭代公式或

超松弛迭代算法步驟P44令則原方程組可寫成分量表示便于編程矩陣表示便于判定收斂性3.3迭代公式的矩陣表示1.Jacobi迭代法的矩陣表示整理得由(3-8)得Gauss-Seidel迭代公式為便得到Gauss-Seidel迭代的矩陣表示。式中2.Gauss-Seidel迭代法的矩陣表示故超松弛迭代法的矩陣形式可寫成即于是得到超松弛的矩陣表示其中當(dāng)0<w<1時，稱為低松弛迭代法，能改善迭代法的收斂性當(dāng)w>1時，稱為超松弛迭代法，可提高收斂速度當(dāng)w=1時，退化為Gauss-Seidel迭代法3超松弛迭代法矩陣表示

超松弛迭代公式可變形為3.4迭代法的收斂性判定

定理3-2（迭代法收斂基本定理）對于任何初始向量x(0)和常數(shù)項f，由迭代公式（3-3）產(chǎn)生的向量序列收斂{x(k)}的充分必要條件是定理表明：迭代是否收斂只與迭代矩陣的譜半徑有關(guān)，即與系數(shù)矩陣A及其演變過程有關(guān)，與迭代初值x(0)和常數(shù)項f無關(guān)。迭代矩陣B的譜半徑越小，迭代過程收斂越快。3.4.1迭代法的收斂性結(jié)合預(yù)備知識3.1節(jié)的定理容易得到：例3-2

給定方程組分別采用Jacobi和Gauss-Seidel迭代法求解時的收斂性。例3-3

給定方程組分別采用Jacobi和Gauss-Seidel迭代法求解時的收斂性。Jacobi法發(fā)散Gauss-Seidel法收斂Jacobi法收斂Gauss-Seidel法發(fā)散定理3-4（迭代法收斂充分條件）若||B||<1，則由迭代公式（3-3）產(chǎn)生的向量序列收斂{x(k)}收斂于方程組x=Bx+f的精確解x*,且有誤差估計注意：該定理是充分但不必要的條件。例3-9（P49）從上面的例子可以看出，用迭代基本定理來判定迭代方法的收斂性理論上是可行的，實際上是困難的，因為當(dāng)階數(shù)較大時B的特征值幾乎是無法用手工計算的，即使是用數(shù)值方法求特征值，計算量也不小。但由于可以用||B||作為譜半徑上界的一個估計，得到下面的定理。定理3-6若方程組Ax=b的系數(shù)矩陣是嚴(yán)格對角占優(yōu)的，則該方程組有唯一解且求解方程組的雅克比迭代和高斯-賽德爾迭代均收斂。定理

若方程組Ax=b的系數(shù)矩陣是嚴(yán)格對角占優(yōu)的，則當(dāng)0<w<=1時，求解方程組的SOR迭代收斂；若A對稱正定時，則當(dāng)0<w<2時，求解方程組的SOR迭代收斂。定理

若方程組Ax=b的系數(shù)矩陣非奇異且主對角線