查看“︁高斯-赛德尔迭代”︁的源代码

{{Incomplete}}
{{NoteTA
|T=zh-hans:高斯-赛德尔迭代;zh-hant:高斯-賽德爾疊代;
|1=zh-hans:迭代;zh-hant:疊代;
|G1 = Math
}}
{{unreferenced|time=2014-10-31T00:06:18+00:00}}
'''高斯－赛德尔迭代'''（'''{{lang|en|Gauss–Seidel method}}'''）是[[数值线性代数]]中的一个[[迭代法]]，可用来求出[[线性方程组]]解的近似值。该方法以[[卡爾·弗里德里希·高斯]]和{{link-en|路德维希·赛德尔|Philipp Ludwig von Seidel|路德维希·赛德尔}}命名。

== 算法 ==
对于一个含有n个未知量及n个等式的如下[[线性方程组]]

<math> \begin{align} 
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{align}</math>

为了求这个方程组的解<math>\vec{x}</math>，我们使用[[迭代法]]。k用来计量迭代步数。给定该方程组解的一个近似值<math>\vec{x}^{\,k}\in\mathbb{R}^{n}</math>。在求k+1步近似值时，我们利用第m个方程求解第m个未知量。在求解过程中，所有已解出的k+1步元素都被直接使用。这一点与[[雅可比法]]不同。对于每个元素可以使用如下公式

<math>
x^{k+1}_m = \frac{1}{a_{mm}}\left(b_m - \sum_{j=1}^{m-1} a_{mj}\cdot x^{k+1}_j - \sum_{j=m+1}^n a_{mj}\cdot x^{k}_j\right),
\quad 1\leq m\leq n.
</math>

重复上述的求解过程，可以得到一个线性方程组解的近似值数列：<math>\vec{x}^{0},\vec{x}^{1},\vec{x}^{2},\ldots</math>。在该方法收敛的前提下，此数列[[收敛]]于<math>\vec{x}</math>. 可以證明數列收斂若線性方程組係數矩陣為對稱[[正定矩陣]](symmetric positive definite matrix)或[[對角優勢矩陣]](diagonally dominant matrix)。

为了保证该方法可以进行，[[主对角线]]元素<math>a_{mm}</math>需非零。

== 矩阵分解 ==
线性方程组的系数<math>a_{ij}\, (i,j=1,2,\ldots,n)</math>可以被写成矩阵形式 <math> A\in \mathbb{R}^{n\times n}</math>, 该矩阵的第i行第j列元素满足 <math>(A)_{i,j}=a_{ij}</math>。方程组的右边项可以被写成向量形式 <math>\vec{b}\in\mathbb{R}^{n}:\, (\vec{b})_i=b_i</math>。 线性方程组因此可以被写成矩阵运算形式

<math> A\vec{x} = \vec{b}</math>

矩阵<math>A</math>可以分解成如下形式

<math>A=D+L+U</math>,

其中<math>D\in\mathbb{R}^{n\times n}</math>为一个[[对角矩阵]]满足<math>(D)_{i,i}=(A)_{i,i}</math>, <math>L,\,U</math>均为严格[[三角矩阵]]： <math>L</math>为严格下三角矩阵， <math>U</math> 为严格上三角矩阵。

<big>'''例子'''</big>

<math>A = \begin{pmatrix} 1 & 2 & 2 \\ 3 & 1 & 4 \\ 5 & 3 & 1 \end{pmatrix}</math>， <math>D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}</math>， <math>L = \begin{pmatrix} 0 & 0 & 0 \\ 3 & 0 & 0 \\ 5 & 3 & 0 \end{pmatrix}</math>， <math>U = \begin{pmatrix} 0 & 2 & 2 \\ 0 & 0 & 4 \\ 0 & 0 & 0 \end{pmatrix}</math>.

高斯－赛德尔迭代的每一步可以写成如下形式

<math>D\vec{x}^{\,k+1} = \vec{b} - L\vec{x}^{\,k+1} - U\vec{x}^{\,k} </math>.

:{| class="toccolours collapsible collapsed" width="50%" style="text-align:left"
!此形式的导出
|-
|
如上形式来自于高斯－赛德尔迭代的元素公式: 对于第m个未知量<math>(\vec{x}^{\,k+1})_m=x^{k+1}_m</math>, 我们可以得出

<math>(D\vec{x}^{\,k+1})_m = (\vec{b})_m - (L\vec{x}^{\,k+1})_m - (U\vec{x}^{\,k})_m\Rightarrow a_{mm}x^{k+1}_m = b_m -\sum_{j=1}^n (L)_{m,j}x^{k+1}_j - \sum_{j=1}^n (U)_{m,j}x^{k}_j</math>

已知<math>a_{mm}\neq 0</math>, <math>(L)_{m,j}=0\,(\forall j\geq m)</math> 以及 <math>(U)_{m,j}=0\,(\forall j\leq m)</math>，因此可以得出

<math> x^{\,k+1}_m = \frac{1}{a_{mm}}\left( b_m -\sum_{j=1}^{m-1} (L)_{m,j}x^{\,k+1}_j - \sum_{j=m+1}^n (U)_{m,j}x^{\,k}_j \right) = \frac{1}{a_{mm}}\left( b_m -\sum_{j=1}^{m-1} a_{mj}x^{\,k+1}_j - \sum_{j=m+1}^n a_{mj}x^{\,k}_j \right)</math>.
|}

== 算法 ==

因为元素可以被重新赋值为在这个算法中计算得到的新值，所以只需要保存一个向量，而向量索引被省略。该算法如下：

 输入: {{var|A}}, {{var|b}}
 输出: <math>\phi</math>
初始化一个的猜测结果<math>\phi</math>
 '''repeat''' until convergence（收敛）
     '''for''' {{var|i}} '''from''' 1 '''until''' {{var|n}} '''do'''
         <math>\sigma \leftarrow 0</math>
         '''for''' {{var|j}} '''from''' 1 '''until''' {{var|n}} '''do'''
             '''if''' {{var|j}} &ne; {{var|i}} '''then'''
                 <math> \sigma \leftarrow \sigma + a_{ij} \phi_j </math>
             '''end if'''
         '''end''' ({{var|j}} - loop)
         <math> \phi_i \leftarrow \frac 1 {a_{ii}} (b_i - \sigma)</math>
     '''end''' ({{var|i}}-loop)
     check if convergence is reached（检查是否已收敛）
 '''end''' (repeat)

== 參見 ==
*[[雅可比法]]

[[Category:線性代數]]
[[Category:带有伪代码示例的条目]]