ガウス＝ザイデル法

ガウス＝ザイデル法：連立一次方程式の数値解法

ガウス＝ザイデル法は、連立一次方程式を数値的に解くための反復解法の一種です。線形代数で扱うn元連立一次方程式 Ax = b を解くための効率的な手法として知られています。ヤコビ法と同様に反復計算によって近似解を求めますが、ガウス＝ザイデル法はヤコビ法よりも一般的に速い収束性を示します。

原理

ガウス＝ザイデル法は、係数行列Aを下三角行列L、対角行列D、上三角行列Uに分解することで導出されます。A = L + D + U と表せるとき、元の連立一次方程式は以下のように変形できます。

(L + D)x = b - Ux

この式を反復的に解くことで、解xの近似値を求めます。k回目の反復で得られた解をx^(k)とすると、(k+1)回目の反復における解x^(k+1)は以下のように計算されます。

x^(k+1) = D^-1(b - Lx^(k+1) - Ux^(k))

この式は、各成分ごとに以下のように表現できます。

x_i^(k+1) = (1/a_ii)(b_i - Σ_j=1^i-1a_ijx_j^(k+1) - Σ_j=i+1ⁿa_ijx_j^(k))

ここで、a_ijは係数行列Aの(i, j)成分、b_iはベクトルbのi番目の成分です。重要なのは、x_i^(k+1)を計算する際に、既に計算済みのx_j^(k+1) (j < i) を使用する点です。これがヤコビ法との大きな違いであり、収束性の向上に寄与します。

収束性

ガウス＝ザイデル法が収束する条件はいくつかあります。係数行列Aが正定値対称[[行列]]である場合、必ず収束します。また、Aが対角優位行列である場合も収束することが保証されています。対角優位とは、各行において対角成分の絶対値が非対角成分の絶対値の和よりも大きいことを意味します。


さらに、収束を加速させるために、SOR法（逐次過緩和法）などの改良手法も用いられます。

ヤコビ法との比較

ヤコビ法も連立一次方程式を解く反復法ですが、ガウス＝ザイデル法と大きく異なる点は、更新された値を直ちに使用しない点です。ヤコビ法では、k回目の反復で全てのx_i^(k)を計算し、それらを用いて次の反復でx_i^(k+1)を計算します。これに対し、ガウス＝ザイデル法は、計算済みの新しい値を直ちに次の計算に使用します。そのため、ガウス＝ザイデル法の方が一般的に収束が速いと言われています。しかし、ヤコビ法は並列計算に適しているのに対し、ガウス＝ザイデル法は逐次計算を行うため並列化が困難です。

具体例

3元連立一次方程式を例に、ガウス＝ザイデル法の計算手順を示します。


(a11 a12 a13)(x1) (b1)
(a21 a22 a23)(x2) = (b2)
(a31 a32 a33)(x3) (b3)


初期値x⁽⁰⁾を適当な値（例えばゼロベクトル）として、以下の式を繰り返し適用します。

x₁^(k+1) = (b₁ - a₁₂x₂^(k) - a₁₃x₃^(k))/a₁₁
x₂^(k+1) = (b₂ - a₂₁x₁^(k+1) - a₂₃x₃^(k))/a₂₂
x₃^(k+1) = (b₃ - a₃₁x₁^(k+1) - a₃₂x₂^(k+1))/a₃₃

この反復計算を収束するまで繰り返すことで、連立一次方程式の解の近似値を求めることができます。

まとめ

ガウス＝ザイデル法は、連立一次方程式を解くための効率的な反復法です。ヤコビ法よりも収束が速いという利点がありますが、並列計算には不向きです。係数行列の性質によって収束性が変わるため、適用する際には収束条件を確認する必要があります。

もう一度検索