ヤコビ法

ヤコビ法とは$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}}\\D{\vec {x}}&=&{\vec {b}}-(L+U){\vec {x}}\\\end{array}}$

この式を満たすxを求める。初期値${\vec {x}}^{(0)}$に対して、 $k$回目の反復で得られた$x_{1}$の値を$x_{1}^{(k)}$と書くと、 以下のような反復法の漸化式ができる。

$D{\vec {x}}^{(k+1)}={\vec {b}}-(L+U){\vec {x}}^{(k)}$

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

${\vec {x}}^{(k+1)}=D^{-1}\{{\vec {b}}-(L+U){\vec {x}}^{(k)}\}$

もし、解が収束した場合、その場合は$x_{1}^{(k+1)}$と$x_{1}^{(k)}$は共通の値$x_{1}^{(*)}$を持つことになる。このとき、

${\vec {x}}^{(*)}=D^{-1}\{{\vec {b}}-(L+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)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right)={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}^{n}a_{ij}x_{j}^{(k)}\right)$

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

具体例

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_{11}x_{1}^{(k)}-a_{13}x_{3}^{(k)})/a_{22}$

$x_{3}^{(k+1)}=(b_{3}-a_{11}x_{1}^{(k)}-a_{12}x_{2}^{(k)})/a_{33}$

という反復を繰り返していく。 ヤコビ法は、直列計算ではガウス＝ザイデル法よりも遅いが、アルゴリズムが比較的簡単なため並列計算でも用いられる。

関連項目

• ガウス＝ザイデル法