解線性方程組的迭代法

1、第3章 解線性方程組的迭代法清華大學工程碩士數(shù)學課程-數(shù)值分析 數(shù)值方法§1 Jacobi迭代法和Gauss-Seidel迭代法（I）迭代概念 （1） ， ， ， ， ，M非奇異如果令 ，那么上式寫成（2） 此方程組等價于任給，（3） 由（3）可以確定，當，即 時，有同樣滿足 定義 式（3） 稱為求解 （1） 的簡單形式迭代法，B稱為迭代矩陣。（II）Jacobi迭代法寫成分量形式有假定 ，那么有迭代法為任給 即：上式迭代方法稱為Jacobi迭代例1.1用Jacobi迭代法解方程組解 Jacobi迭代方法為取 方程組 的準確解為。 若取 那么 ?？扇?為方程組的近似解。為進行收斂性分

2、析，把迭代方法寫成向量形式。 ，稱為Jacobi迭代的迭代矩陣（III）Gauss-Seidel迭代法Jacobi迭代有可以看出，當計算時，已經(jīng)計算出來了，一般可以認為要比更接近于。由此可以設(shè)想把已經(jīng)計算出來的分量在計算公式中立刻應(yīng)用，這樣就有這個迭代公式稱為Gauss-Seidel迭代公式例1.2取可見，Gauss-Seidel迭代法比Jacobi迭代法“好” 把Gauss-Seidel迭代方法寫成令 稱為Gauss-Seidel迭代的迭代矩陣， 例1.3 用Jacobi 迭代法和Gauss-Seidel迭代法解此方程組有唯一解 Jacobi 事實上， Gauss-Seidel:§

3、2 迭代方法收斂性（I）向量序列和矩陣序列的極限中向量序列 ， 簡單記為 。同樣，中序列 定義2.1 設(shè) 為上的向量范數(shù)。如果存在 滿足那么稱收斂于，記由于范數(shù)等價性，所以收斂性與所選擇范數(shù)無關(guān)。定義2.1 設(shè)為上矩陣范數(shù)，如果存在滿足那么稱收斂于A，記為收斂性與所擇范數(shù)無關(guān)。定理2.1 充分必要條件是證：必要性。對任一種矩陣算子范數(shù)有充分性， 取 ，其第個分量為1，其它分量為零的向量。那么表示的第列各元素極限為零，取 表示的全部元素極限為零。定理2.2 設(shè) ， 那么下面三個命題等價（1） （2） （3）至少存在一種從屬的矩陣范數(shù)，使。證明 用反證法：設(shè)B有一特征值，。那么存在特征向量，所以當

4、，不收斂到零向量。根據(jù)定理2.1，不收斂到零矩陣，矛盾于（1）。對任，存在一種從屬的矩陣范數(shù)使由（2），適當選擇，使 從而有 從而有 （II）迭代法的收斂性 ，A非奇異， 滿足（1） 等價（2） 迭代公式（3） 定義2.3 由迭代公式（3）產(chǎn)生的序列 滿足那么稱迭代法（3）是收斂的。設(shè) 為（2） 的解，即由（3）減去上式有其中 由此可以遞推得其中與無關(guān)，所以迭代法（3）收斂相當于定理2.3 下面三個命題等價（1） 迭代法 收斂（2） 至少存在一種從屬的矩陣范數(shù)，使得。證明：命題（1）等價于根據(jù)定理2.1 這條件等價于。由定理2.2，此定理證得最常用的定理敘述如下：定理2.4 迭代法 ；對任 收

5、斂的充分必要條件是 。實際判別一個迭代法是否收斂，條件 較難驗證。但 可以用B的元素來表示，所以用來作為收斂的充分條件較為方便。例子2.4 其中 試討論用Jacobi 迭代法和Gauss-Seidel迭代法求解上述方程組的收斂性解 Jacobi迭代收斂 Gauss-Seidel迭代不收斂。例 2.5 其中試討論用Jacobi迭代法和Gauss-Seidel迭代法求解方程組的收斂性解 ， Jacobi迭代不收斂。 Gauss-Seidel迭代收斂例2.6 設(shè)方程組（1） 寫出解方程組的Jacobi迭代矩陣，討論迭代收斂條件。（2） 寫出解方程組的Gauss-Seidel迭代矩陣，討論迭代收斂條件

6、。解（1）； Jacobi迭代收斂充要條件為 ，即 （2） ， 即Gauss-Seidel迭代收斂的充要條件為， 即 。（III）迭代的誤差估計定理2.5 設(shè)是方程組 的唯一解， 為上的向量范數(shù)，對應(yīng)的從屬矩陣范數(shù)。那么由產(chǎn)生的向量序列 滿足 ，證明： ，迭代收斂， ； 由 非奇異。并由迭代格式重復運用可得（IV）特殊方程組迭代法的收斂性如果A具有特殊性質(zhì)，那么可利用這些性質(zhì)來判別迭代法的收斂性。定義2.4 （1）如果A的元素滿足則稱A是嚴格對角占優(yōu)（2）如果A的元素滿足且上式中至少有一個不等號嚴格成立，那么稱A為（弱）對角占優(yōu)定理2.6 設(shè) 為嚴格對角占優(yōu)，那么A是非奇異的證：用反證法。設(shè)A

7、是奇異陣，那么存在 使得記 的第k個方程這與A嚴格對角占優(yōu)矛盾。A非奇異定理2.7 設(shè)A嚴格對角占優(yōu)。那么求解的Jacobi迭代和Gauss-Seidel迭代均收斂。證明： Jacobi迭代的迭代矩陣其中 Gauss-Seidel迭代收斂性A嚴格對角占優(yōu)， 考慮G的特征值設(shè)為G的特征值。那么 。由于 ， （為G的特征值）令要證 ，從而有。Gauss-Seidel迭代收斂用反證法。設(shè)滿足。利用A是嚴格對角占優(yōu)這表明，矩陣C嚴格對角占優(yōu)， 為非奇異， ，這說明滿足時不是G的特征值例2.7 用Jacobi迭代法和Gauss-Seidel迭代法 求解其中解 Jacobi迭代Gauss-Seidel數(shù)值

8、結(jié)果看出。二個方法均收斂。事實上A為嚴格對角占優(yōu)。此外，Gauss-Seidel迭代比Jacobi迭代收斂更快。（V）迭代法收斂速度，任取 稱為誤差向量。并有此外，注意到 是任取的，因此可以認為 是任取的。即 給出了迭代次后誤差向量范數(shù)與初始誤差向量范數(shù)之比的最小上界（上確界）一般要求其中 ，一般為一相當小的數(shù)。已經(jīng)證明 采用算子范數(shù)有 。 那么當 時 有 從而有 改寫上面條件 為兩邊取對數(shù)可以看出，收斂快慢與 有關(guān)定理2.8 設(shè) 為任一矩陣范數(shù)（算子范數(shù)），那么有定義2.5 稱為迭代法 的漸近收斂速度；稱為上述迭代法的平均收斂速度。一般都采用漸近收斂速度來討論迭代的收斂速度。由定義可以看出，

9、迭代方法的譜半徑越小，收斂速度越大。例2.8 討論用Jacobi迭代法和Gauss-Seidel迭代法解方程組的收斂性。如果收斂，試比較哪種方法收斂較快。其中解（1）Jacobi迭代方法收斂（2）Gauss-Seidel迭代 ， Gauss-Seidel迭代法收斂 Gauss-Seidel方法收斂快。并有： §3 超松弛（SOR）迭代法（I）超松弛（Successive over-Relaxation. SOR）迭代法Gauss-Seidel： 求解過程中 Gauss-Seidel迭代（包括Jacobi迭代）收斂速度較小，為此可用加權(quán)來加速。上述Gauss-Seidel迭代結(jié)果不作為

10、此次迭代計算值，而僅作為中間值。記為，最后結(jié)果為與上次結(jié)果的加權(quán)平均由于是Gauss-Seidel迭代結(jié)果，因此上式寫成分量形式有推導SOR的矩陣形式SOR的迭代法的迭代矩陣定理3.1 （Kahan） 設(shè) ，其對角元素皆非零。那么對所有實數(shù)，有證： ，其中L為嚴格下三角陣，U為嚴格上三角陣， 非奇異 對任矩陣 有 det設(shè) 為的n個特征值，那么有推論。如果求解的SOR方法收斂，那么有證明：SOR收斂，定理3.2 （Ostrowski-Reich）設(shè) ，A對稱正定，且，那么求解的SOR方法收斂。證明 設(shè)分別為的特征值和特征向量。A對稱但不是對稱的。因此可以是復數(shù)和復向量。A對稱，用對上式作內(nèi)積有

11、A對稱正定，D對稱正定記 有 記 從而得出要求 ，即分子< 分母 分子分母由于； A對稱，正定， 分子分母 。 SOR方法收斂。推論 設(shè)A對稱，正定；那么求解 的Gauss-Seide迭代法收斂。定理3.3 設(shè)，對稱正定。對稱正定，那么求解 的Jacobi迭代收斂。例3.1 用 和的SOR迭代法求解方程組 ，其中方程組的準確解為A對稱正定 ，因此迭代是收斂的。， 即為Gauss-Seidel迭代取 。SOR迭代公式為取 可以看出，時，SOR收斂較快。定理3.4 如果方程組 中矩陣A對稱正定并是三對角陣，那么。SOR方法的最佳松弛因子。采用的這個選擇， 隨的變化而變化。存在使，稱為最佳松弛因子。 變化如下圖02在的右邊呈線性變化，在的左邊，變化非常劇烈。因此一般取稍大于。對于例子3.1 是對稱、正定的三對角矩陣。；在計算中，取稍大于。在例子3.1中，取較好。例3.2 設(shè)方程組 ，其中（1） 寫出Jacobi迭代法的分量形式，求出Jacobi迭代矩陣的譜半徑；（2） 求出SOR迭代法的最佳松弛因子及解 （1）（2） 例3.3 設(shè)方程組 ，其中 試證明，當 時，用Gauss-Seidel求解收斂； 當時，Jacobi迭