ガウス＝ザイデル法

テンプレート:出典の明記 数値線形代数におけるガウス＝ザイデル法（ガウス＝ザイデルほう、テンプレート:Lang-en-short）とは$n$元の連立一次方程式$A\overrightarrow{x}=\overrightarrow{b}$を反復法で解く手法の1つである。

解説

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

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

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

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

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

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

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

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

となり、変形していくと元の連立方程式の形に戻る。 したがって、ガウス＝ザイデル法で解が収束した場合、その解は連立方程式の解となる。

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{j=i+1}^n{a}_{ij}{x}_j^{(k)})$

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

収束性

ガウス＝ザイデル法は、係数行列が正定値対称ならば収束する。

また、係数行列の各行で非対角要素の絶対値の和が対角要素の絶対値よりも小さい場合：

$\left|a_{ii}\right|>\sum _{i\ne j}\left|a_{ij}\right|.$

すなわち対角優位な行列ならば収束する（これはヤコビ法も同様である）。

係数行列が正定値対称ならばガウス＝ザイデル法が収束することを利用して、$A\overrightarrow{x}=\overrightarrow{b}$を解く代わりに、同値である$A^{T}A\overrightarrow{x}=A^T\overrightarrow{b}$を解く方法が考えられる。 この方法は$\overrightarrow{x}$の第i行要素$x_i$を更新するごとに確実に残差が減少する反面、条件数がもとの行列$A$の条件数の二乗になるため収束は遅くなる傾向となる。

上記のように$A\overrightarrow{x}=\overrightarrow{b}$の代わりに$A^{T}A\overrightarrow{x}=A^T\overrightarrow{b}$を解く方法は非対称、非正定値行列を共役勾配法で解く際のテクニックにも利用される。 しかしながらCG法においても条件数が増加することにより収束性は悪化する。

具体例

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)}$と書く。 初期値${\overrightarrow{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)}$を使う、 すなわち、新しい${\overrightarrow{x}}^{(k+1)}$を別の場所に記憶しておいて、 一斉に$\overrightarrow{x}$を更新するヤコビ法を使用する。

ヤコビ法は、直列計算ではガウス＝ザイデル法よりも遅いが、容易に並列計算できる。

関連項目

• 反復法 (数値計算) - ヤコビ法, SOR法