跳至內容

高斯-賽德爾疊代

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

高斯-賽德爾疊代Gauss–Seidel method)是數值線性代數中的一個疊代法,可用來求出線性方程組解的近似值。該方法以卡爾·弗里德里希·高斯路德維希·賽德爾英語Philipp Ludwig von Seidel命名。

算法

[編輯]

對於一個含有n個未知量及n個等式的如下線性方程組

為了求這個方程組的解,我們使用疊代法。k用來計量疊代步數。給定該方程組解的一個近似值。在求k+1步近似值時,我們利用第m個方程式求解第m個未知量。在求解過程中,所有已解出的k+1步元素都被直接使用。這一點與雅可比法不同。對於每個元素可以使用如下公式

重複上述的求解過程,可以得到一個線性方程組解的近似值數列:。在該方法收斂的前提下,此數列收斂. 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣(symmetric positive definite matrix)或對角優勢矩陣(diagonally dominant matrix)。

為了保證該方法可以進行,主對角線元素需非零。

矩陣分解

[編輯]

線性方程組的係數可以被寫成矩陣形式 , 該矩陣的第i行第j列元素滿足 。方程組的右邊項可以被寫成向量形式 。 線性方程組因此可以被寫成矩陣運算形式

矩陣可以分解成如下形式

,

其中為一個對角矩陣滿足, 均為嚴格三角矩陣為嚴格下三角矩陣, 為嚴格上三角矩陣。

例子

.

高斯-賽德爾疊代的每一步可以寫成如下形式

.

算法

[編輯]

因為元素可以被重新賦值為在這個算法中計算得到的新值,所以只需要保存一個向量,而向量索引被省略。該算法如下:

输入: A, b
输出: 

初始化一個的猜測結果

repeat until convergence(收敛)
    for i from 1 until n do
        
        for j from 1 until n do
            if ji then
                
            end if
        end (j - loop)
        
    end (i-loop)
    check if convergence is reached(检查是否已收敛)
end (repeat)

參見

[編輯]