鬆弛法

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

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

(1)

此處為未知量，和為已知量，又設均不為零，則由迭代公式

(2)

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

的絕對值小於某給定的小數ε時就終止迭代而將

取作方程組(1)的解。迭代格式(2)稱為同時超鬆弛法或JOR法，其中的ω為一實參數，稱為鬆弛因子，當時就是通常所謂的簡單迭代法，或稱雅可比法。

若在迭代格式(2)中，將第i個方程迭代出的的值代替其後各方程中的，就得到迭代格式

(3)

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

(4)

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

(5)

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

(6)

或

, (7)

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

。 (8)

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

(9)

的形式，其中G稱為迭代矩陣，對應於(7)和(8)分別有和。以ρ(M)表示方陣M的譜半徑，其定義為M的按模最大特徵值的模，則迭代過程(9)收斂的充分必要條件為

。(10)

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

， (11)

種范數。對上面鬆弛法的迭代格式可以得出一些有關收斂性的命題如下：① 若A為嚴格對角優勢矩陣（見對角優勢矩陣）或不可約弱對角優勢矩陣，為矩陣的元素取絕對值所成的矩陣，則JOR法和SOR法在

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

② 若A為埃爾米特矩陣，且均為正，則JOR法收斂的充分必要條件為A和正定；

③ SOR法收斂的必要條件為；

④ 若A為埃爾米特矩陣， 均為正，則SOR法收斂的充分必要條件為A正定和。

鬆弛因子的選取ω 的值選取得適當可使鬆弛法有較好的收斂性，然而如何選取最優的

ω,還是一個困難的問題。通常用五點差分格式解二維二階橢圓型方程得到的線性代數方程組的係數矩陣是塊三對角矩陣，主對角塊是三對角陣，非主對角塊為對角陣。對這種方程組若記簡單迭代和超鬆弛迭代的迭代矩陣為J和，則它們的特徵值和之間有關係

。 (12)

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

。 (13)

此時

， (14)

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

當取時，由(12)有。即對相容次序的矩陣來說，賽德爾迭代比簡單迭代斂速快一倍。在很多情況下，賽德爾迭代比簡單迭代收斂快。實際上，若，且、和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.)