ヤコビ法

「ヤコビ法 (固有値問題)」とは異なります。

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

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

${\displaystyle {\begin{array}{ccc}(L+D+U){\vec {x}}&=&{\vec {b}}\\D{\vec {x}}&=&{\vec {b}}-(L+U){\vec {x}}\\\end{array}}}$

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

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

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

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

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

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

となり、変形していくと元の連立方程式の形に戻る。 したがって、ヤコビ法で解が収束した場合、その解は連立方程式の解となる。 また、その収束の十分条件は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これはガウス＝ザイデル法も同様である。

ヤコビ法の式はベクトル${\displaystyle {\vec {x}}}$の各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。

${\displaystyle 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元の連立一次方程式、すなわち、

${\displaystyle \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)}$

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

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

${\displaystyle x_{2}^{(k+1)}=(b_{2}-a_{21}x_{1}^{(k)}-a_{23}x_{3}^{(k)})/a_{22}}$

${\displaystyle x_{3}^{(k+1)}=(b_{3}-a_{31}x_{1}^{(k)}-a_{32}x_{2}^{(k)})/a_{33}}$

という反復を繰り返していく。 ヤコビ法は、直列計算ではガウス＝ザイデル法よりも遅いが、ガウス＝ザイデル法と異なり各式が他の式に依存せず並列性があるため並列計算でも用いられる。

固有値問題

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

${\displaystyle \ B=G^{T}AG}$

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

${\displaystyle {\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})\sin 2\theta +a_{pq}\cos 2\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}}}$

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

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

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

${\displaystyle A_{k}=G_{k}^{T}A_{k-1}G_{k}=U_{k}^{T}AU_{k}}$

ここに、 ${\displaystyle U_{k}=G_{1}G_{2}G_{3}\cdots G_{k-1}G_{k}}$

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

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

関連項目

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

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ