コンテンツにスキップ

ガウス=ザイデル法

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

数値線形代数におけるガウス=ザイデル法(ガウス=ザイデルほう、: Gauss-Seidel method)とは元の連立一次方程式反復法で解く手法の1つである。

解説

[編集]

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

この式を満たすxを求める。初期値に対して、 回目の反復で得られたの値をと書くと、 以下のような反復法の漸化式ができる。

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

もし、解が収束した場合、その場合はは共通の値を持つことになる。このとき、

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

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

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

収束性

[編集]

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

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

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

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

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

具体例

[編集]

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

を解くことを考える。回目の反復で得られたの値をと書く。 初期値は、適当な値、例えばゼロベクトルでもかまわない。

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

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

関連項目

[編集]