ヤコビ法

ヤコビ法（ヤコビほう）とは $n$ 元の連立一次方程式 $A \vec{x} = \vec{b}$ を反復法で解く手法の1つである。ドイツの数学者カール・グスタフ・ヤコブ・ヤコビの名前にちなむ。

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

\begin{matrix} (L + D + U) \vec{x} & = & \vec{b} \\ D \vec{x} & = & \vec{b} - (L + U) \vec{x} \end{matrix}

この式を満たす $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_{i i}} (b_{i} - \sum_{j = 1}^{i - 1} a_{i j} x_{j}^{(k)} - \sum_{j = i + 1}^{n} a_{i j} x_{j}^{(k)}) = \frac{1}{a_{i i}} (b_{i} - \sum_{j \neq i}^{n} a_{i j} x_{j}^{(k)})

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

具体例

3元の連立一次方程式、すなわち、

$(\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \end{matrix})$

を解くことを考える。 $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, θ)$ による相似変換、すなわちギブンス回転を実行することにより、非対角要素 $a_{i j} (i \neq j)$ の最大値 $a_{p q}$ が0となるようにする。

B = G^{T} A G

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

{\begin{matrix} b_{p p} = a_{p p} \cos^{2} θ + a_{q q} \sin^{2} θ - 2 a_{p q} \sin θ \cos θ, \\ b_{q q} = a_{p p} \sin^{2} θ + a_{q q} \cos^{2} θ + 2 a_{p q} \sin θ \cos θ, \\ b_{p q} = b_{q p} = \frac{1}{2} (a_{p p} - a_{q q}) \sin 2 θ + a_{p q} \cos 2 θ, \\ b_{i j} = a_{i j}, \\ b_{p j} = a_{p j} \cos θ - a_{q j} \sin θ, \\ b_{q j} = a_{p j} \sin θ + a_{q j} \cos θ, \\ b_{i p} = a_{i p} \cos θ - a_{i q} \sin θ, \\ b_{i q} = a_{i p} \sin θ + a_{i q} \cos θ \end{matrix}

ここで、 $a_{p q} \neq 0$ のとき $b_{p q} = 0$ となる $θ$ は上式より

\tan 2 θ = \frac{- 2 a_{p q}}{(a_{p p} - a_{q q})}

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

A_{k} = G_{k}^{T} A_{k - 1} G_{k} = U_{k}^{T} A U_{k}

ここに、

U_{k} = G_{1} G_{2} G_{3} \dots G_{k - 1} G_{k}

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

なお上記のように、ヤコビの対角化法は実対称（あるいは複素エルミート）の場合が最も良く知られておりその場合だけしか適用できないものと考えられるかもしれない。しかし非対称な行列に対するヤコビ法もあって研究もされプログラムも公開されていたがQR法が登場した後では行列が非対称な場合にはほとんどQR法だけが使われているため今日では非対称な場合についてはほとんど認知されていないようである（複素エルミートの場合についてもその具体的な実装に言及している文献は稀であり，もっぱら実対称行列の場合だけがよく知られている）。

具体例

固有値問題

関連項目