線性方程組迭代解法

第六章線性與非線性方程組的迭代解法/*IterativeMethodforSolvingLinearandNonlinear

AlgebraicSystems*/求解迭代法從一個(gè)初始向量出發(fā),按照一定的遞推格式,產(chǎn)生逼近方程組的近似解序列。迭代法是一種逐次逼近的方法,與直接法比較,具有:程序簡(jiǎn)單,存儲(chǔ)量小的優(yōu)點(diǎn)。特別適用于求解系數(shù)矩陣為大型稀疏矩陣

/*sparsematrices*/

的方程組。思路與解f(x)=0

的不動(dòng)點(diǎn)迭代相似，將方程組等價(jià)改寫成形式，從而建立迭代格式

，從出發(fā)，生成迭代序列§6.1Jacobi和Gauss-Seidel迭代法一、Jacobi迭代法設(shè)方程組將系數(shù)矩陣分裂為：其中如果原方程組可化為其中相應(yīng)的迭代格式上述方法稱為Jacobi迭代法，簡(jiǎn)稱J法或簡(jiǎn)單迭代法分量形式：二、Gauss-Seidel迭代法G-S迭代法是J迭代法的一種改進(jìn)在J迭代公式中，計(jì)算時(shí)，利用已經(jīng)算出來的新的值，從而得到G-S迭代法。G-S迭代法的分量形式：例1：利用Jacobi和Gauss-Seidel迭代法求解方程組解：Jacobi迭代格式G-S迭代格式計(jì)算結(jié)果取初值Jacobi迭代法

要求精度迭代次數(shù)

0.0019(1.00025071.00006941.0002507)0.000110(0.99995411.00012530.9999541)0.0000114(0.99999811.00000200.9999981)方程組的近似解G-S迭代法的迭代矩陣：計(jì)算結(jié)果Gauss-Seidel迭代法

要求精度迭代次數(shù)

0.0015(0.99979160.99984791.0000664)0.00017(0.99999290.99999491.0000022)0.000018(1.00000131.00000090.9999996)方程組的近似解取初值由迭代公式迭代矩陣§6.2

Jacobi和Gauss-Seidel迭代法的收斂性分析

收斂的充要條件與誤差估計(jì)上述兩種方法都可以寫成如下迭代形式：稱為單步定常線性迭代法，為迭代矩陣，為常數(shù)項(xiàng)。

當(dāng)?shù)疆a(chǎn)生的序列收斂到向量，即，則稱該迭代法收斂，否則為發(fā)散。？引理迭代法收斂的充要條件是證明：

為方程組的解，設(shè)迭代法收斂，則有由相容性知，求解方程組的單步線性定常迭代法收斂的充要條件是。（1）迭代法是否收斂取決于迭代矩陣的譜半徑，與初始向量和常數(shù)項(xiàng)無關(guān)。（2）而對(duì)于同一個(gè)方程組，不同的迭代法對(duì)應(yīng)的迭代矩陣的譜半徑一般不會(huì)相同，因而收斂性也不同。上述定理說明：例2：說明用J法和G-S法求解下列方程組的收斂性：解：計(jì)算特征值：J法不收斂后面兩個(gè)特征值算錯(cuò)了，應(yīng)該是是復(fù)數(shù)G-S法的迭代矩陣為G-S法收斂若迭代矩陣的范數(shù)，并假定的第k次迭代向量與精確解的誤差滿足：范數(shù)滿足，則迭代法證明：代入前述不等式即得。利用矩陣的范數(shù)判定迭代收斂只是一個(gè)充分條件，通常采用矩陣的1-范數(shù)、-范數(shù)來判定。若迭代矩陣的范數(shù)，并假定的第k次迭代向量與精確解的誤差滿足：范數(shù)滿足，則迭代法證明：與前面類似。設(shè)為Jacobi法的迭代矩陣，若則Gauss-Seidel迭代收斂，而且有估計(jì)式其中且有，這里是矩陣的元素。設(shè)為Jacobi法的迭代矩陣，若則Gauss-Seidel迭代收斂，而且有估計(jì)式其中如果是對(duì)稱矩陣，且有正的對(duì)角元，則求解方程組的J法收斂的充要條件是矩陣和均為正定的，其中如果是對(duì)稱正定矩陣，則求解方程組的G-S法收斂。設(shè)滿足稱為嚴(yán)格對(duì)角占優(yōu)矩陣如果且至少有一個(gè)嚴(yán)格不等式成立，則稱為弱對(duì)角占優(yōu)矩陣。設(shè)，如果能找到排列陣，使得其中與均為方陣，稱為可約的否則稱為不可約的例如：矩陣是可約的若系數(shù)矩陣是可約的，則可通過行與列重排化為上面(*)式，從而可將方程組簡(jiǎn)化為低階方程組。（可約矩陣的等價(jià)定義）設(shè)矩陣，，如果存在的兩個(gè)非空子集和，滿足使得則稱矩陣可約，否則稱不可約。例如：矩陣矩陣不可約設(shè)為嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角占優(yōu)，則，且非奇異。設(shè)為嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角占優(yōu)的對(duì)稱矩陣，且對(duì)角元素皆為正，則正定。推論若為嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角占優(yōu)的，則Jacobi迭代和Gauss-Seidel迭代收斂。迭代法的收斂速度：設(shè)迭代法收斂，即（/*RateofAverageConvergence*/）稱之為迭代法的平均收斂率。上式說明：可看作第k次迭代誤差范數(shù)的壓縮率平均