|
|
(16人の利用者による、間の20版が非表示) |
1行目: |
1行目: |
|
|
{{出典の明記|date=2022年3月}} |
⚫ |
'''ヤコビ法'''とは<math>n</math>元の[[連立一次方程式]]<math>A\vec{x}=\vec{b}</math>を[[反復法_(数値計算)|反復法]]で解く手法の1つである。[[ドイツ]]の[[数学者]][[カール・グスタフ・ヤコブ・ヤコビ]]の名前にちなむ。 |
|
|
|
{{distinguish|ヤコビ法 (固有値問題)}} |
|
⚫ |
'''ヤコビ法''' (ヤコビほう)とは<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>とすると、''<math>A=L+D+U</math>''と書ける。このようにすると、まず以下のような変形ができる。 |
|
<math>n</math>次[[正方行列]]<math>A</math>は、上[[三角行列]]<math>U</math>、下三角行列<math>L</math>、[[対角行列]]を<math>D</math>とすると、''<math>A=L+D+U</math>''と書ける。このようにすると、まず以下のような変形ができる。 |
50行目: |
52行目: |
|
|
|
|
|
という反復を繰り返していく。 |
|
という反復を繰り返していく。 |
|
ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、アルゴリズムが比較的簡単なため[[並列コンピューティング|並列計算]]でも用いられる。 |
|
ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、ガウス=ザイデル法と異なり各式が他の式に依存せず並列性があるため[[並列コンピューティング|並列計算]]でも用いられる。 |
|
|
|
|
|
== [[固有値問題]] == |
|
== 固有値問題 == |
|
実対称行列の固有値および固有ベクトルを求める反復計算手法においても'''ヤコビ法'''と呼ばれる解法がある。 |
|
実対称行列の固有値および固有ベクトルを求める繰り返し計算手法においても'''ヤコビ法'''と呼ばれる解法がある(紛らわしさを避けるためにはヤコビ対角化法という)。 |
|
<math>\ n</math>次の実[[対称行列]]<math>\ A</math>について次のように <math>\ G(p, q, \theta)</math> により[[ギブンス回転]]を実行することにより、非対角要素 <math>\ a_{ij}</math> の最大値 <math>\ a_{pq}</math> が0となるようにする。 |
|
<math>\ n</math>次の実[[対称行列]]<math>\ A</math>について次のように <math>\ G(p, q, \theta)</math> による相似変換、すなわち[[ギブンス回転]]を実行することにより、非対角要素 <math>\ a_{ij}(i \ne j)</math> の最大値 <math>\ a_{pq}</math> が0となるようにする。 |
|
|
|
|
|
:<math>\ B=G^TAG</math> |
|
:<math>\ B=G^TAG</math> |
70行目: |
72行目: |
|
\end{cases}</math> |
|
\end{cases}</math> |
|
|
|
|
|
ここで、<math>\ a_{pq} \ne 0</math> のとき <math>\ b_{pq}=0</math> となる<math>\theta</math> は上式より |
|
ここで、<math>\ a_{pq} \ne 0</math> のとき <math>\ b_{pq}=0</math> となる <math>\ \theta</math> は上式より |
|
|
|
|
|
:<math> \tan 2\theta = \frac{-a_{pq}}{(a_{pp}-a_{qq})/2}</math> |
|
:<math> \tan 2\theta = \frac{-2a_{pq}}{(a_{pp}-a_{qq})}</math> |
|
|
|
|
|
から求められることがわかる。 |
|
から求められることがわかる。 |
|
|
ギブンス回転をすべての非対角要素がほぼ0になるまで繰り返せば、実対称行列 <math>A\quad</math> が対角化された形となるから、その対角要素が <math>A\quad</math> の固有値となる。また、 <math>A\quad</math> がk回変換された行列を <math>A_{k}\quad</math> 、k回目のギブンス回転を表す直交行列を <math>G_{k}\quad</math> と表せば、 |
|
|
|
|
|
:<math> A_k = G_k^T A_{k-1} G_k = U_k^TAU_k</math> |
|
|
:ここに、 <math> U_k = G_1 G_2 G_3 \cdots G_{k-1} G_k</math> |
|
|
|
|
|
となる。 <math>A_{k}\quad</math> のすべての非対角要素がほぼ0となったとき、 <math>U_{k}\quad</math> は固有ベクトルを並べた行列となっている。 |
|
|
なお、ギブンス回転の繰り返し過程において、一度は0になった要素がその後の変換により0でなくなることもあるが、変換の繰り返しによって非対角項は0に近づいてゆく。 |
|
|
|
|
|
なお上記のように、ヤコビの対角化法は実対称(あるいは複素エルミート)の場合が最も良く知られておりその場合だけしか適用できないものと考えられるかもしれない。しかし非対称な行列に対するヤコビ法もあって研究もされプログラムも公開されていたがQR法が登場した後では行列が非対称な場合にはほとんどQR法だけが使われているため今日では非対称な場合についてはほとんど認知されていないようである(複素エルミートの場合についてもその具体的な実装に言及している文献は稀であり,もっぱら実対称行列の場合だけがよく知られている)。 |
|
|
|
|
|
== 関連項目 == |
|
== 関連項目 == |
80行目: |
91行目: |
|
*[[ガウス=ザイデル法]] |
|
*[[ガウス=ザイデル法]] |
|
|
|
|
|
|
{{Linear algebra}} |
⚫ |
[[Category:数値線形代数 |やこひほう]] |
|
⚫ |
[[Category:数学に関する記事 |やこひほう]] |
|
|
|
|
|
|
|
{{デフォルトソート:やこひほう}} |
|
[[de:Jacobi-Verfahren]] |
|
|
⚫ |
|
|
[[en:Jacobi method]] |
|
|
|
[[Category:緩和法 (反復法)]] |
|
[[es:Método de Jacobi]] |
|
|
⚫ |
|
|
[[fr:Méthode de Jacobi]] |
|
|
|
[[Category:数学のエポニム]] |
|
[[id:Metode Jacobi]] |
|
|
[[it:Metodo di Jacobi]] |
|
|
[[nl:Methode van Jacobi]] |
|
|
[[ru:Метод Якоби]] |
|
|
[[ur:جیکبی طریقہ]] |
|
| この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "ヤコビ法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2022年3月) |
ヤコビ法(ヤコビほう)とは
元の連立一次方程式
を反復法で解く手法の1つである。ドイツの数学者カール・グスタフ・ヤコブ・ヤコビの名前にちなむ。
次正方行列
は、上三角行列
、下三角行列
、対角行列を
とすると、
と書ける。このようにすると、まず以下のような変形ができる。
この式を満たす
を求める。初期値
に対して、
回目の反復で得られた
の値を
と書くと、
以下のような反復法の漸化式ができる。
この式は以下のように変形できる。
もし、解が収束した場合、その場合は
と
は共通の値
を持つことになる。このとき、
となり、変形していくと元の連立方程式の形に戻る。
したがって、ヤコビ法で解が収束した場合、その解は連立方程式の解となる。
また、その収束の十分条件は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これはガウス=ザイデル法も同様である。
ヤコビ法の式はベクトル
の各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。
ガウス=ザイデル法とヤコビ法を加速する方法としてはSOR法が知られている。
3元の連立一次方程式、すなわち、
を解くことを考える。
回目の反復で得られた
の値を
と書く。
初期値
は、適当な値、例えばゼロベクトルでもかまわない。
という反復を繰り返していく。
ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、ガウス=ザイデル法と異なり各式が他の式に依存せず並列性があるため並列計算でも用いられる。
実対称行列の固有値および固有ベクトルを求める繰り返し計算手法においてもヤコビ法と呼ばれる解法がある(紛らわしさを避けるためにはヤコビ対角化法という)。
次の実対称行列
について次のように
による相似変換、すなわちギブンス回転を実行することにより、非対角要素
の最大値
が0となるようにする。
![{\displaystyle \ B=G^{T}AG}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d0f26ad0d0a9b2781924f861487cf155040e82a)
これによって行列
の各要素は次のようになる。但し、
である。
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dc3b7b8d3774f3edc9f9d08144848841ccf6be1)
ここで、
のとき
となる
は上式より
![{\displaystyle \tan 2\theta ={\frac {-2a_{pq}}{(a_{pp}-a_{qq})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfe05de787f1474c247fbb57bc7d352a805f27b8)
から求められることがわかる。
ギブンス回転をすべての非対角要素がほぼ0になるまで繰り返せば、実対称行列
が対角化された形となるから、その対角要素が
の固有値となる。また、
がk回変換された行列を
、k回目のギブンス回転を表す直交行列を
と表せば、
![{\displaystyle A_{k}=G_{k}^{T}A_{k-1}G_{k}=U_{k}^{T}AU_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bffdabd27438ad6d35a7dedcc9e13a70a24990b)
- ここに、
![{\displaystyle U_{k}=G_{1}G_{2}G_{3}\cdots G_{k-1}G_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/145a4746e2d7a4c6797e555f9d397c4c51f206ce)
となる。
のすべての非対角要素がほぼ0となったとき、
は固有ベクトルを並べた行列となっている。
なお、ギブンス回転の繰り返し過程において、一度は0になった要素がその後の変換により0でなくなることもあるが、変換の繰り返しによって非対角項は0に近づいてゆく。
なお上記のように、ヤコビの対角化法は実対称(あるいは複素エルミート)の場合が最も良く知られておりその場合だけしか適用できないものと考えられるかもしれない。しかし非対称な行列に対するヤコビ法もあって研究もされプログラムも公開されていたがQR法が登場した後では行列が非対称な場合にはほとんどQR法だけが使われているため今日では非対称な場合についてはほとんど認知されていないようである(複素エルミートの場合についてもその具体的な実装に言及している文献は稀であり,もっぱら実対称行列の場合だけがよく知られている)。