ヤコビ法

ヤコビ法とは$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_{21} x_1^{(k)} - a_{23} x_3^{(k)}) / a_{22}$

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

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

固有値問題

実対称行列の固有値および固有ベクトルを求める繰り返し計算手法においてもヤコビ法と呼ばれる解法がある。 $\ n$次の実対称行列$\ A$について次のように $\ G(p, q, \theta)$ による相似変換、すなわちギブンス回転を実行することにより、非対角要素 $\ a_{ij}(i \ne j)$ の最大値 $\ a_{pq}$ が0となるようにする。

$\ B=G^TAG$

これによって行列 $\ B$ の各要素は次のようになる。但し、 $\ i,j \ne p,q$ である。

$\begin{cases} b_{pp} = a_{pp}\cos^2\theta + a_{qq}\sin^2\theta - 2a_{pq}\sin\theta\cos\theta ,\\ b_{qq} = a_{pp}\sin^2\theta + a_{qq}\cos^2\theta + 2a_{pq}\sin\theta\cos\theta ,\\ b_{pq} = b_{qp} = \frac{1}{2}(a_{pp}-a_{qq})\sin2\theta + a_{pq}\cos2\theta ,\\ b_{ij} = a_{ij} ,\\ b_{pj} = a_{pj}\cos\theta - a_{qj}\sin\theta ,\\ b_{qj} = a_{pj}\sin\theta + a_{qj}\cos\theta ,\\ b_{ip} = a_{ip}\cos\theta - a_{iq}\sin\theta ,\\ b_{iq} = a_{ip}\sin\theta + a_{iq}\cos\theta \end{cases}$

ここで、$\ a_{pq} \ne 0$ のとき $\ b_{pq}=0$ となる $\ \theta$ は上式より

$\tan 2\theta = \frac{-2a_{pq}}{(a_{pp}-a_{qq})}$

から求められることがわかる。 ギブンス回転をすべての非対角要素がほぼ0になるまで繰り返せば、実対称行列 $A\quad$ が対角化された形となるから、その対角要素が $A\quad$ の固有値となる。また、 $A\quad$ がk回変換された行列を $A_{k}\quad$ 、k回目のギブンス回転を表す直交行列を $G_{k}\quad$ と表せば、

$A_k = G_k^T A_{k-1} G_k = U_k^TAU_k$

ここに、 $U_k = G_1 G_2 G_3 \cdots G_{k-1} G_k$

となる。 $A_{k}\quad$ のすべての非対角要素がほぼ0となったとき、 $U_{k}\quad$ は固有ベクトルを並べた行列となっている。 なお、ギブンス回転の繰り返し過程において、一度は0になった要素がその後の変換により0でなくなることもあるが、変換の繰り返しによって非対角項は0に近づいてゆく。

関連項目

• 数値解析
• ガウス＝ザイデル法