ガウス＝ザイデル法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ガウス＝ザイデル法とは $n$ 元の連立一次方程式 $A\vec{x}=\vec{b}$ を反復法で解く手法の1つである。

[編集] 解説

$n$ 次正方行列 $A$ は、上三角行列 $U$ 、下三角行列 $L$ 、対角行列を $D$ とすると、A=L+D+Uと書ける。このようにすると、まず以下のような変形ができる。

$\begin{array}{ccc} (L+D+U) \vec{x} &=& \vec{b} \\ (L+D)\vec{x} &=& \vec{b}-U\vec{x} \\ \end{array}$

この式を満たすxを求める。初期値 $\vec{x}^{(0)}$ に対して、 $k$ 回目の反復で得られた $x 1$ の値を $x_1^{(k)}$ と書くと、以下のような反復法の漸化式ができる。

$(L+D)\vec{x}^{(k+1)} = \vec{b}-U\vec{x}^{(k)}$

この式は以下のように変形できる。

$\vec{x}^{(k+1)} = D^{-1}(\vec{b}-L\vec{x}^{(k+1)} - U\vec{x}^{(k)})$

もし、解が収束した場合、その場合は $x_1^{(k+1)}$ と $x_1^{(k)}$ は共通の値 $x_1^{(*)}$ を持つことになる。このとき、

$\vec{x}^{(*)} = D^{-1}(\vec{b}-L\vec{x}^{(*)} - U\vec{x}^{(*)})$

となり、変形していくと元の連立方程式の形に戻る。したがって、ガウス＝ザイデル法で解が収束した場合、その解は連立方程式の解となる。また、その収束の十分条件は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これはヤコビ法も同様である。

ガウス＝ザイデル法の式はベクトル $\vec{x}$ の各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。

$x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_{i} - \sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} \right)$

ガウス＝ザイデル法とヤコビ法を加速する方法としてはSOR法が知られている。

[編集] 具体例

3元の連立一次方程式、すなわち、

$\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)$

を解くことを考える。 $k$ 回目の反復で得られた $x 1$ の値を $x_1^{(k)}$ と書く。初期値 $\vec{x}^{(0)}$ は、適当な値、例えばゼロベクトルでもかまわない。

$x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}$

$x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k+1)} - a_{23} x_3^{(k)}) / a_{22}$

$x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k+1)} - a_{32} x_2^{(k+1)}) / a_{33}$

という反復を繰り返していく。ここで、2番目の式で $x_1^{(k+1)}$ が使われていることに注意する。次々に新しい $x_i^{(k+1)}$ を求めては、次の式で使われる。このために、ガウス＝ザイデル法は、このままでは並列計算できないので、上記の反復式の右辺の $x_i^{(k+1)}$ の代わりに $x_i^{(k)}$ を使う、すなわち、新しい $\vec{x}^{(k+1)}$ を別の場所に記憶しておいて、一斉に $\vec{x}$ を更新するヤコビ法を使用する。