ガウス＝ザイデル法

数値線形代数におけるガウス＝ザイデル法（ガウス＝ザイデルほう、）とはformula_1元の連立一次方程式formula_2を反復法で解く手法の1つである。
解説.
formula_1次正方行列formula_4は、上三角行列formula_5、下三角行列formula_6、対角行列をformula_7とすると、"A=L+D+U"と書ける。このようにすると、まず以下のような変形ができる。
formula_8
この式を満たす"x"を求める。初期値formula_9に対して、
formula_10回目の反復で得られたformula_11の値をformula_12と書くと、
以下のような反復法の漸化式ができる。
formula_13
この式は以下のように変形できる。
formula_14
もし、解が収束した場合、その場合はformula_15とformula_12は共通の値formula_17を持つことになる。このとき、
formula_18
となり、変形していくと元の連立方程式の形に戻る。
したがって、ガウス＝ザイデル法で解が収束した場合、その解は連立方程式の解となる。
ガウス＝ザイデル法の式はベクトルformula_19の各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。
formula_20
ガウス＝ザイデル法とヤコビ法を加速する方法としてはSOR法が知られている。
収束性.
ガウス＝ザイデル法は、係数行列が正定値対称ならば収束する。
また、係数行列の各行で非対角要素の絶対値の和が対角要素の絶対値よりも小さい場合：
すなわち対角優位な行列ならば収束する（これはヤコビ法も同様である）。
係数行列が正定値対称ならばガウス＝ザイデル法が収束することを利用して、formula_2を解く代わりに、同値であるformula_23を解く方法が考えられる。
この方法はformula_19の第i行要素formula_25を更新するごとに確実に残差が減少する反面、条件数がもとの行列formula_4の条件数の二乗になるため収束は遅くなる傾向となる。
上記のようにformula_2の代わりにformula_23を解く方法は非対称、非正定値行列を共役勾配法で解く際のテクニックにも利用される。
しかしながらCG法においても条件数が増加することにより収束性は悪化する。
具体例.
3元の連立一次方程式、すなわち、
formula_29
を解くことを考える。formula_10回目の反復で得られたformula_11の値をformula_12と書く。
初期値formula_9は、適当な値、例えばゼロベクトルでもかまわない。
formula_34
formula_35
formula_36
という反復を繰り返していく。
ここで、2番目の式でformula_15が使われていることに注意する。
次々に新しいformula_38を求めては、次の式で使われる。
このために、ガウス＝ザイデル法は、このままでは並列計算できないので、
上記の反復式の右辺のformula_38の代わりにformula_40を使う、
すなわち、新しいformula_41を別の場所に記憶しておいて、
一斉にformula_19を更新するヤコビ法を使用する。
ヤコビ法は、直列計算ではガウス＝ザイデル法よりも遅いが、容易に並列計算できる。