此條目
不完整 。
請幫忙改善本條目,或到討論頁 去討論该條目的問題。
高斯-赛德尔迭代 (Gauss–Seidel method )是数值线性代数 中的一个迭代法 ,可用来求出线性方程组 解的近似值。该方法以卡爾·弗里德里希·高斯 和路德维希·赛德尔 命名。
对于一个含有n个未知量及n个等式的如下线性方程组
a 11 ⋅ x 1 + a 12 ⋅ x 2 + … + a 1 n ⋅ x n = b 1 , a 21 ⋅ x 1 + a 22 ⋅ x 2 + … + a 2 n ⋅ x n = b 2 , ⋮ = ⋮ a n 1 ⋅ x 1 + a n 2 ⋅ x 2 + … + a n n ⋅ x n = b n . {\displaystyle {\begin{aligned}a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+\ldots +a_{1n}\cdot x_{n}&=b_{1},\\a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+\ldots +a_{2n}\cdot x_{n}&=b_{2},\\\vdots \qquad \qquad \qquad &=\vdots \\a_{n1}\cdot x_{1}+a_{n2}\cdot x_{2}+\ldots +a_{nn}\cdot x_{n}&=b_{n}.\end{aligned}}}
为了求这个方程组的解 x → {\displaystyle {\vec {x}}} ,我们使用迭代法 。k用来计量迭代步数。给定该方程组解的一个近似值 x → k ∈ R n {\displaystyle {\vec {x}}^{\,k}\in \mathbb {R} ^{n}} 。在求k+1步近似值时,我们利用第m个方程求解第m个未知量。在求解过程中,所有已解出的k+1步元素都被直接使用。这一点与雅可比法 不同。对于每个元素可以使用如下公式
x m k + 1 = 1 a m m ( b m − ∑ j = 1 m − 1 a m j ⋅ x j k + 1 − ∑ j = m + 1 n a m j ⋅ x j k ) , 1 ≤ m ≤ n . {\displaystyle x_{m}^{k+1}={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}a_{mj}\cdot x_{j}^{k+1}-\sum _{j=m+1}^{n}a_{mj}\cdot x_{j}^{k}\right),\quad 1\leq m\leq n.}
重复上述的求解过程,可以得到一个线性方程组解的近似值数列: x → 0 , x → 1 , x → 2 , … {\displaystyle {\vec {x}}^{0},{\vec {x}}^{1},{\vec {x}}^{2},\ldots } 。在该方法收敛的前提下,此数列收敛 于 x → {\displaystyle {\vec {x}}} . 可以證明數列收斂若線性方程組係數矩陣為對稱正定矩陣 (symmetric positive definite matrix)或對角優勢矩陣 (diagonally dominant matrix)。
为了保证该方法可以进行,主对角线 元素 a m m {\displaystyle a_{mm}} 需非零。
线性方程组的系数 a i j ( i , j = 1 , 2 , … , n ) {\displaystyle a_{ij}\,(i,j=1,2,\ldots ,n)} 可以被写成矩阵形式 A ∈ R n × n {\displaystyle A\in \mathbb {R} ^{n\times n}} , 该矩阵的第i行第j列元素满足 ( A ) i , j = a i j {\displaystyle (A)_{i,j}=a_{ij}} 。方程组的右边项可以被写成向量形式 b → ∈ R n : ( b → ) i = b i {\displaystyle {\vec {b}}\in \mathbb {R} ^{n}:\,({\vec {b}})_{i}=b_{i}} 。 线性方程组因此可以被写成矩阵运算形式
A x → = b → {\displaystyle A{\vec {x}}={\vec {b}}}
矩阵 A {\displaystyle A} 可以分解成如下形式
A = D + L + U {\displaystyle A=D+L+U} ,
其中 D ∈ R n × n {\displaystyle D\in \mathbb {R} ^{n\times n}} 为一个对角矩阵 满足 ( D ) i , i = ( A ) i , i {\displaystyle (D)_{i,i}=(A)_{i,i}} , L , U {\displaystyle L,\,U} 均为严格三角矩阵 : L {\displaystyle L} 为严格下三角矩阵, U {\displaystyle U} 为严格上三角矩阵。
例子
A = ( 1 2 2 3 1 4 5 3 1 ) {\displaystyle A={\begin{pmatrix}1&2&2\\3&1&4\\5&3&1\end{pmatrix}}} , D = ( 1 0 0 0 1 0 0 0 1 ) {\displaystyle D={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}} , L = ( 0 0 0 3 0 0 5 3 0 ) {\displaystyle L={\begin{pmatrix}0&0&0\\3&0&0\\5&3&0\end{pmatrix}}} , U = ( 0 2 2 0 0 4 0 0 0 ) {\displaystyle U={\begin{pmatrix}0&2&2\\0&0&4\\0&0&0\end{pmatrix}}} .
高斯-赛德尔迭代的每一步可以写成如下形式
D x → k + 1 = b → − L x → k + 1 − U x → k {\displaystyle D{\vec {x}}^{\,k+1}={\vec {b}}-L{\vec {x}}^{\,k+1}-U{\vec {x}}^{\,k}} .
此形式的导出 如上形式来自于高斯-赛德尔迭代的元素公式: 对于第m个未知量 ( x → k + 1 ) m = x m k + 1 {\displaystyle ({\vec {x}}^{\,k+1})_{m}=x_{m}^{k+1}} , 我们可以得出
( D x → k + 1 ) m = ( b → ) m − ( L x → k + 1 ) m − ( U x → k ) m ⇒ a m m x m k + 1 = b m − ∑ j = 1 n ( L ) m , j x j k + 1 − ∑ j = 1 n ( U ) m , j x j k {\displaystyle (D{\vec {x}}^{\,k+1})_{m}=({\vec {b}})_{m}-(L{\vec {x}}^{\,k+1})_{m}-(U{\vec {x}}^{\,k})_{m}\Rightarrow a_{mm}x_{m}^{k+1}=b_{m}-\sum _{j=1}^{n}(L)_{m,j}x_{j}^{k+1}-\sum _{j=1}^{n}(U)_{m,j}x_{j}^{k}}
已知 a m m ≠ 0 {\displaystyle a_{mm}\neq 0} , ( L ) m , j = 0 ( ∀ j ≥ m ) {\displaystyle (L)_{m,j}=0\,(\forall j\geq m)} 以及 ( U ) m , j = 0 ( ∀ j ≤ m ) {\displaystyle (U)_{m,j}=0\,(\forall j\leq m)} ,因此可以得出
x m k + 1 = 1 a m m ( b m − ∑ j = 1 m − 1 ( L ) m , j x j k + 1 − ∑ j = m + 1 n ( U ) m , j x j k ) = 1 a m m ( b m − ∑ j = 1 m − 1 a m j x j k + 1 − ∑ j = m + 1 n a m j x j k ) {\displaystyle x_{m}^{\,k+1}={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}(L)_{m,j}x_{j}^{\,k+1}-\sum _{j=m+1}^{n}(U)_{m,j}x_{j}^{\,k}\right)={\frac {1}{a_{mm}}}\left(b_{m}-\sum _{j=1}^{m-1}a_{mj}x_{j}^{\,k+1}-\sum _{j=m+1}^{n}a_{mj}x_{j}^{\,k}\right)} .
因为元素可以被重新赋值为在这个算法中计算得到的新值,所以只需要保存一个向量,而向量索引被省略。该算法如下:
输入: A , b 输出: ϕ {\displaystyle \phi } 初始化一个的猜测结果 ϕ {\displaystyle \phi }
repeat until convergence(收敛) for i from 1 until n do σ ← 0 {\displaystyle \sigma \leftarrow 0} for j from 1 until n do if j ≠ i then σ ← σ + a i j ϕ j {\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}} end if end (j - loop) ϕ i ← 1 a i i ( b i − σ ) {\displaystyle \phi _{i}\leftarrow {\frac {1}{a_{ii}}}(b_{i}-\sigma )} end (i -loop) check if convergence is reached(检查是否已收敛) end (repeat)