ガウス=ザイデル法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数値線形代数におけるガウス=ザイデル法(〜ほう、: Gauss-Seidel method)とは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法が知られている。

収束性[編集]

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

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

\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}.

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

具体例[編集]

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}を更新するヤコビ法を使用する。

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

関連項目[編集]