ガウス・ザイデル法とは、ヤコビ法とともに、連立一次方程式を反復法で解く手法の１つです。
反復法
反復法とは、反復計算により解を求める手法の総称で、以下、連立一次方程式の解法について述べます。例として、以下の４元１次方程式について、
$$\left.\begin{array}{ll}
a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1 \\
a_{21}x_1+a_{22}x_2+a_{23}x_3+a_{24}x_4=b_2 \\
a_{31}x_1+a_{32}x_2+a_{33}x_3+a_{34}x_4=b_3 \\
a_{41}x_1+a_{42}x_2+a_{43}x_3+a_{44}x_4=b_4\end{array} \right\}①$$
この各方程式を上から順に $x_1\sim x_4$ について解くと、
$$\left.\begin{array}{ll}
x_1=(b_1-a_{12}x_2-a_{13}x_3-a_{14}x_4)/a_{11} \\
x_2=(b_2-a_{21}x_1-a_{23}x_3-a_{24}x_4)/a_{22} \\
x_3=(b_3-a_{31}x_1-a_{32}x_2-a_{34}x_4)/a_{33} \\
x_4=(b_4-a_{41}x_1-a_{42}x_2-a_{43}x_3)/a_{44}\end{array} \right\}②$$
反復法では、最初に $x_1\sim x_4$ について適当な初期値を定めておいて、②により左辺の $x_1\sim x_4$ を計算します。左辺の $x_1\sim x_4$ と右辺（一つ前）の $x_1\sim x_4$ の差分が無視できるレベルになったとき、連立一次方程式が近似的に解けたと考えます。
ヤコビ法
ヤコビ法では、②の右辺について、変数は全て一つ前の変数 $x_i^{(n)}$ を使用します。
$$\left.\begin{array}{ll}
x_1^{(n+1)}=(b_1-a_{12}x_2^{(n)}-a_{13}x_3^{(n)}-a_{14}x_4^{(n)})/a_{11} \\
x_2^{(n+1)}=(b_2-a_{21}x_1^{(n)}-a_{23}x_3^{(n)}-a_{24}x_4^{(n)})/a_{22} \\
x_3^{(n+1)}=(b_3-a_{31}x_1^{(n)}-a_{32}x_2^{(n)}-a_{34}x_4^{(n)})/a_{33} \\
x_4^{(n+1)}=(b_4-a_{41}x_1^{(n)}-a_{42}x_2^{(n)}-a_{43}x_3^{(n)})/a_{44}\end{array} \right\}③$$
ガウス・ザイデル法
ガウス・ザイデル法では、右辺について、新しく計算された変数 $x_i^{(n+1)}$ を逐次使います。これにより、ガウス・ザイデル法はヤコビ法より速く収束します。
$$\left.\begin{array}{ll}
x_1^{(n+1)}=(b_1-a_{12}x_2^{(n)}-a_{13}x_3^{(n)}-a_{14}x_4^{(n)})/a_{11} \\
x_2^{(n+1)}=(b_2-a_{21}x_1^{(n+1)}-a_{23}x_3^{(n)}-a_{24}x_4^{(n)})/a_{22} \\
x_3^{(n+1)}=(b_3-a_{31}x_1^{(n+1)}-a_{32}x_2^{(n+1)}-a_{34}x_4^{(n)})/a_{33} \\
x_4^{(n+1)}=(b_4-a_{41}x_1^{(n+1)}-a_{42}x_2^{(n+1)}-a_{43}x_3^{(n+1)})/a_{44}\end{array} \right\}④$$
収束の条件
①を行列で書き換えると、
$$A{\bf x}={\bf b} -⑤$$$$A\equiv\left(\begin{array}{ccc} a_{11} & \cdots & a_{14} \\
\vdots & \ddots & \vdots \\
a_{41} & \cdots & a_{44} \end{array}\right)$$$${\bf b}\equiv\left(\begin{array}{ccc} a_1 \\
\vdots\\
b_4 \end{array}\right) , {\bf x}\equiv\left(\begin{array}{ccc} x_1 \\
\vdots\\
x_4 \end{array}\right)$$
②を行列で書き換えると、
$${\bf x}=M{\bf x}+{\bf c} -⑥$$
⑥の反復式は以下のように書けます。
$${\bf x}^{(n)}=M{\bf x}^{(n-1)}+{\bf c} -⑦$$
この反復式を繰り返すと、${\bf x}^{(n)}$ は次第に解に近づき、$\epsilon$ を小さな整数として、以下の条件が成り立つまで繰返します。
$$|{\bf x}^{(n+1)}-{\bf x}^{(n)}|\lt\epsilon -⑧$$
⑧が収束する条件は、行列 $M$ の全ての固有値 $\lambda_i$ について、以下の関係が成り立つ場合です。
$$\lambda_i\lt 1 -⑨$$
⑨の導出
${\bf x}$ と ${\bf x}^{(n)}$ の差分を以下で定義し、
$${\bf e}^{(n)}\equiv{\bf x}-{\bf x}^{(n)}$$
⑥の⑦の差を取ると、
$${\bf e}^{(n)}=M{\bf e}^{(n-1)}$$
これを繰り返し使うと、
$${\bf e}^{(n)}=M\cdots M{\bf e}^{(0)}=M^n{\bf e}^{(0)} -(1)$$
$M$ の対角化行列を $\Lambda$ とすると、正則行列 $T$ により以下で表されます。
$$\Lambda=T^{-1}MT$$
これを(1)に代入すると、
$${\bf e}^{(n)}=(T\Lambda T^{-1})^n{\bf e}^{(0)}=T\Lambda^nT^{-1}{\bf e}^{(0)}$$
これより、$n\to\infty$ で $\Lambda^n\to0$（全ての固有値 $\lambda_i\lt1$ ）となれば、${\bf e}^{(n)}\to0$（⑧が収束）となることが分かります。
