數值計算中解線性代數方程組的一類迭代法。當方程組的未知量個數甚多而又有大量的零係數時，常用這類方法求解。

　　基本迭代格式　設線性代數方程組為

(1)

此處 x 1， x 2，…， x n為未知量， α ij( i， j＝1，2，…， n)和 f 1， f 2，…， f n為已知量，又設 α ii( i=1，2，…， n)均不為零，則由迭代公式

(2)

和給定的初值 x ， x ，…， x ，就可求出 x ， x ，…， x ，由後者又可求出 x ， x ，…， x ，如此繼續直到滿足精度要求為止，例如對所有的 i， 或 （若 ）或剩餘

的絕對值｜ ｜小於某給定的小數ε時就終止迭代而將 取作方程組(1)的解。迭代格式(2)稱為同時超松弛法或JOR法，其中的 ω為一實參數，稱為松弛因子，當 ω＝1時就是通常所謂的簡單迭代法，或稱雅可比法。

　　若在迭代格式(2)中，將第i個方程迭代出的

的值代替其後各方程中的 ，就得到迭代格式

(3)

它稱為逐次超松弛法，或SOR法，一般所說的超松弛法就是指這種方法，當 ω＝1時稱為高斯-賽德爾法或賽德爾法，有時將 ω>1的情形稱為超松弛法，而將 ω＜1的情形稱為亞松弛法或低松弛法。迭代格式也可用矩陣形式來寫，設

(4)

為 n階方陣， ， 為 n維列向量，則(1)可寫為

　 (5)

記 A的對角線元素所成的對角矩陣為 D，又 B＝ D－ A，則(2)可寫為

(6)

或

，(7)

再設 L和 U分別為 B的下三角形和上三角形矩陣，則 A= D- L- U，而(3)可寫為

。(8)

　　收斂性　迭代格式(7)和(8)可統一地寫為

(9)

的形式，其中 G稱為迭代矩陣，對應於(7)和(8)分別有 G= D -1[(1- ω) D+ ω B]和 G＝( D- ω L) -1[(1- ω) D+ ω U]。以ρ( M)表示方陣 M的譜半徑，其定義為 M的按模最大特征值的模，則迭代過程(9)收斂的充分必要條件為

ρ(G)＜1。

(10)由此可得收斂的一個充分條件為這裡‖ G‖是 G的任意一

‖G‖＜1，　　　　　　(11)

種范數。對上面松弛法的迭代格式可以得出一些有關收斂性的命題如下：

　　① 若A為嚴格對角優勢矩陣（見對角優勢矩陣）或不可約弱對角優勢矩陣，|D-1B|為矩陣D-1B的元素取絕對值所成的矩陣，則JOR法和SOR法在

0＜ω＜2/(1+ρ)|D-1B|

范圍內收斂，並且在所述條件下，上式右端是一個大於1的數；

　　② 若A為埃爾米特矩陣，且αii(i＝1，2，…，n)均為正，則JOR法收斂的充分必要條件為A和2ω-1D-A正定；

　　③ SOR法收斂的必要條件為0＜ω＜2；

　　④ 若A為埃爾米特矩陣，αii(i=1，2，…，n)均為正，則SOR法收斂的充分必要條件為A正定和0＜ω＜2。

　　松弛因子的選取　ω的值選取得適當可使松弛法有較好的收斂性，然而如何選取最優的ω，還是一個困難的問題。通常用五點差分格式解二維二階橢圓型方程得到的線性代數方程組的系數矩陣是塊三對角矩陣，主對角塊是三對角陣，非主對角塊為對角陣。對這種方程組若記簡單迭代和超松弛迭代的迭代矩陣為J和Lω，則它們的特征值λ(J)和λ(Lω)之間有關系

。(12)

由此可以研究 ω的選取問題，例如可以證明：在上述情形下使超松弛迭代收斂最快的松弛因子為

。 (13)

此時

，(14)

這裡ρ( J)和ρ( )分別為矩陣 J和 的譜半徑。這些結果還可推廣到所謂“相容次序”的矩陣。盡管如此，在實際計算中仍難以精確確定 ω b的值，而往往是通過一些試算或用其他方法先估計ρ( J)，再來估計 ω b。也可用若幹 ω值試迭代，從中選取使斂速較快者。從(12)式還可看出， ω b在1與2之間，且從大於 ω b的一側選取 ω，然後逐步減小，較為有利。

　　當取ω=1時，由(12)有λ(L1)=(λ(J))2。即對相容次序的矩陣來說，賽德爾迭代比簡單迭代斂速快一倍。在很多情況下，賽德爾迭代比簡單迭代收斂快。實際上，若A=M-N，且A-1、M-1和N的元素均非負，則迭代過程

　　　(15)

收斂，且 N的元素愈少愈小，收斂愈快。不難看出，前述的迭代格式都是(15)的特殊情形，並且賽德爾迭代較之簡單迭代相應的 N的元素要少得多，從而收斂也要快些，當然在不滿足這些條件的情況之下，也可能出現相反的情形。

　　此外，若將A分成塊來形成分塊矩陣，而將(6)(7)(8)中的D、B、L和U分別取為A的主對角塊、－A的非主對角塊、下三角塊和上三角塊所形成的矩陣，則迭代(15)的收斂速度可能更快。這樣得出的迭代格式稱為塊松弛迭代，相應地有塊簡單迭代，塊超松弛迭代等。對照之下，前面的迭代就稱為點松弛迭代，上面關於最佳松弛因子的討論對塊松弛迭代也是適用的。

　　上述的一些迭代法有時收斂都很慢，這就需要用一些輔助方法來加速收斂，例如半迭代加速、共軛梯度法加速等。

　　

參考書目

　馮康等編：《數值計算方法》，國防工業出版社，北京，1978。

　D.M.Young，Iterative Solution of large Linear Systems，Academic Press，New York，1971.

　R.S.瓦格著，蔣爾雄、遊兆永、張玉德譯：《矩陣迭代分析》，上海科學技術出版社，上海，1966。(R.S.Varga，Matrix Iterative Analysis，Prentice - Hall，Englewood Cliffs，New Jersey，1962.)