ガウス＝ザイデル法のソースを表示

{{出典の明記|date=2023年9月}}
[[数値線形代数]]における'''ガウス＝ザイデル法'''（ガウス＝ザイデルほう、{{lang-en-short|Gauss-Seidel method}}）とは<math>n</math>元の[[連立一次方程式]]<math>A\vec{x}=\vec{b}</math>を[[反復法_(数値計算)|反復法]]で解く手法の1つである。

== 解説 ==
<math>n</math>次[[正方行列]]<math>A</math>は、上[[三角行列]]<math>U</math>、下三角行列<math>L</math>、[[対角行列]]を<math>D</math>とすると、''A=L+D+U''と書ける。このようにすると、まず以下のような変形ができる。

<center><math>
\begin{array}{ccc}
(L+D+U) \vec{x} &=& \vec{b} \\
(L+D)\vec{x} &=& \vec{b}-U\vec{x} \\
\end{array}
</math></center>

この式を満たす''x''を求める。初期値<math>\vec{x}^{(0)}</math>に対して、
<math>k</math>回目の反復で得られた<math>x_1</math>の値を<math>x_1^{(k)}</math>と書くと、
以下のような反復法の[[漸化式]]ができる。
<center><math>
(L+D)\vec{x}^{(k+1)} = \vec{b}-U\vec{x}^{(k)}
</math></center>
この式は以下のように変形できる。
<center><math>
\vec{x}^{(k+1)} = D^{-1}(\vec{b}-L\vec{x}^{(k+1)} - U\vec{x}^{(k)})
</math></center>
もし、解が収束した場合、その場合は<math>x_1^{(k+1)}</math>と<math>x_1^{(k)}</math>は共通の値<math>x_1^{(*)}</math>を持つことになる。このとき、
<center><math>
\vec{x}^{(*)} = D^{-1}(\vec{b}-L\vec{x}^{(*)} - U\vec{x}^{(*)})
</math></center>
となり、変形していくと元の連立方程式の形に戻る。
したがって、ガウス＝ザイデル法で解が収束した場合、その解は連立方程式の解となる。

ガウス＝ザイデル法の式はベクトル<math>\vec{x}</math>の各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。
<center><math>
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)
</math></center>

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

== 収束性 ==

ガウス＝ザイデル法は、係数行列が[[対称行列#対称行列に関連する行列の各種分解|正定値対称]]ならば収束する。

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

:<math>\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}. </math>

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

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

上記のように<math>A\vec{x}=\vec{b}</math>の代わりに<math>A^TA\vec{x}=A^T \vec{b}</math>を解く方法は非対称、非正定値行列を[[共役勾配法]]で解く際のテクニックにも利用される。
しかしながらCG法においても条件数が増加することにより収束性は悪化する。

== 具体例 ==
3元の連立一次方程式、すなわち、

<math>\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)</math>

を解くことを考える。<math>k</math>回目の反復で得られた<math>x_1</math>の値を<math>x_1^{(k)}</math>と書く。
初期値<math>\vec{x}^{(0)}</math>は、適当な値、例えばゼロベクトルでもかまわない。

<math>x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}</math>

<math>x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k+1)} - a_{23} x_3^{(k)}) / a_{22}</math>

<math>x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k+1)} - a_{32} x_2^{(k+1)}) / a_{33}</math>

という反復を繰り返していく。
ここで、2番目の式で<math>x_1^{(k+1)}</math>が使われていることに注意する。
次々に新しい<math>x_i^{(k+1)}</math>を求めては、次の式で使われる。
このために、ガウス＝ザイデル法は、このままでは並列計算できないので、
上記の反復式の右辺の<math>x_i^{(k+1)}</math>の代わりに<math>x_i^{(k)}</math>を使う、
すなわち、新しい<math>\vec{x}^{(k+1)}</math>を別の場所に記憶しておいて、
一斉に<math>\vec{x}</math>を更新する[[ヤコビ法]]を使用する。

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

== 関連項目 ==
* [[反復法 (数値計算)]] - [[ヤコビ法]], [[SOR法]]

{{Linear algebra}}

{{DEFAULTSORT:かうすさいてるほう}}
[[Category:緩和法 (反復法)]]
[[Category:数値線形代数]]
[[Category:カール・フリードリヒ・ガウス|さいてるほう]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]