「ヤコビ法」の版間の差分
m カール・グスタフ・ヤコブ・ヤコビへリンク。 |
|||
(25人の利用者による、間の31版が非表示) | |||
1行目: | 1行目: | ||
{{出典の明記|date=2022年3月}} |
|||
⚫ | |||
{{distinguish|ヤコビ法 (固有値問題)}} |
|||
⚫ | |||
⚫ | |||
== 解説 == |
|||
⚫ | |||
<center><math> |
<center><math> |
||
11行目: | 12行目: | ||
</math></center> |
</math></center> |
||
この式を満たす''x''を求める。初期値<math>\vec{x}^{(0)}</math>に対して、 |
この式を満たす''<math>\ x</math>''を求める。初期値<math>\vec{x}^{(0)}</math>に対して、 |
||
<math>k</math>回目の反復で得られた<math>x_1</math>の値を<math>x_1^{(k)}</math>と書くと、 |
<math>\ k</math>回目の反復で得られた<math>x_1</math>の値を<math>x_1^{(k)}</math>と書くと、 |
||
以下のような反復法の[[漸化式]]ができる。 |
以下のような反復法の[[漸化式]]ができる。 |
||
<center><math> |
<center><math> |
||
29行目: | 30行目: | ||
また、その収束の[[十分条件]]は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これは[[ガウス=ザイデル法]]も同様である。 |
また、その収束の[[十分条件]]は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これは[[ガウス=ザイデル法]]も同様である。 |
||
ヤコビ法の式はベクトル<math>\vec{x}</math>の各成分ごとに次のような式で書くことができ、[[数値解析]]ではこの式が用いられる。 |
ヤコビ法の式は[[幾何ベクトル|ベクトル]]<math>\vec{x}</math>の各成分ごとに次のような式で書くことができ、[[数値解析]]ではこの式が用いられる。 |
||
<center><math> |
<center><math> |
||
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) |
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) |
||
46行目: | 47行目: | ||
<math>x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}</math> |
<math>x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}</math> |
||
<math>x_2^{(k+1)} = (b_2 - a_{ |
<math>x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k)} - a_{23} x_3^{(k)}) / a_{22}</math> |
||
<math>x_3^{(k+1)} = (b_3 - a_{ |
<math>x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k)} - a_{32} x_2^{(k)}) / a_{33}</math> |
||
という反復を繰り返していく。 |
という反復を繰り返していく。 |
||
ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、 |
ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、ガウス=ザイデル法と異なり各式が他の式に依存せず並列性があるため[[並列コンピューティング|並列計算]]でも用いられる。 |
||
== 固有値問題 == |
|||
実対称行列の固有値および固有ベクトルを求める繰り返し計算手法においても'''ヤコビ法'''と呼ばれる解法がある(紛らわしさを避けるためにはヤコビ対角化法という)。 |
|||
<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</math> の各要素は次のようになる。但し、 <math>\ i,j \ne p,q </math> である。 |
|||
:<math>\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}</math> |
|||
ここで、<math>\ a_{pq} \ne 0</math> のとき <math>\ b_{pq}=0</math> となる <math>\ \theta</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法だけが使われているため今日では非対称な場合についてはほとんど認知されていないようである(複素エルミートの場合についてもその具体的な実装に言及している文献は稀であり,もっぱら実対称行列の場合だけがよく知られている)。 |
|||
== 関連項目 == |
== 関連項目 == |
||
*[[数値解析]] |
|||
*[[ガウス=ザイデル法]] |
*[[ガウス=ザイデル法]] |
||
{{math-stub}} |
|||
⚫ | |||
⚫ | |||
{{Linear algebra}} |
|||
[[de:Jacobi-Verfahren]] |
|||
[[en:Jacobi method]] |
|||
{{デフォルトソート:やこひほう}} |
|||
[[it:Metodo di Jacobi]] |
|||
⚫ | |||
[[ru:Метод Якоби]] |
|||
[[Category:緩和法 (反復法)]] |
|||
⚫ | |||
[[Category:数学のエポニム]] |
2023年1月17日 (火) 12:05時点における最新版
![]() |
ヤコビ法(ヤコビほう)とは元の連立一次方程式を反復法で解く手法の1つである。ドイツの数学者カール・グスタフ・ヤコブ・ヤコビの名前にちなむ。
次正方行列は、上三角行列、下三角行列、対角行列をとすると、と書ける。このようにすると、まず以下のような変形ができる。
この式を満たすを求める。初期値に対して、 回目の反復で得られたの値をと書くと、 以下のような反復法の漸化式ができる。
この式は以下のように変形できる。
もし、解が収束した場合、その場合はとは共通の値を持つことになる。このとき、
となり、変形していくと元の連立方程式の形に戻る。 したがって、ヤコビ法で解が収束した場合、その解は連立方程式の解となる。 また、その収束の十分条件は、係数行列の対角要素の絶対値が非対角要素の絶対値よりも相対的に大きい場合、すなわち対角優位な行列である場合に収束する。これはガウス=ザイデル法も同様である。
ヤコビ法の式はベクトルの各成分ごとに次のような式で書くことができ、数値解析ではこの式が用いられる。
ガウス=ザイデル法とヤコビ法を加速する方法としてはSOR法が知られている。
具体例
[編集]3元の連立一次方程式、すなわち、
を解くことを考える。回目の反復で得られたの値をと書く。 初期値は、適当な値、例えばゼロベクトルでもかまわない。
という反復を繰り返していく。 ヤコビ法は、直列計算ではガウス=ザイデル法よりも遅いが、ガウス=ザイデル法と異なり各式が他の式に依存せず並列性があるため並列計算でも用いられる。
固有値問題
[編集]実対称行列の固有値および固有ベクトルを求める繰り返し計算手法においてもヤコビ法と呼ばれる解法がある(紛らわしさを避けるためにはヤコビ対角化法という)。 次の実対称行列について次のように による相似変換、すなわちギブンス回転を実行することにより、非対角要素 の最大値 が0となるようにする。
これによって行列 の各要素は次のようになる。但し、 である。
ここで、 のとき となる は上式より
から求められることがわかる。 ギブンス回転をすべての非対角要素がほぼ0になるまで繰り返せば、実対称行列 が対角化された形となるから、その対角要素が の固有値となる。また、 がk回変換された行列を 、k回目のギブンス回転を表す直交行列を と表せば、
- ここに、
となる。 のすべての非対角要素がほぼ0となったとき、 は固有ベクトルを並べた行列となっている。 なお、ギブンス回転の繰り返し過程において、一度は0になった要素がその後の変換により0でなくなることもあるが、変換の繰り返しによって非対角項は0に近づいてゆく。
なお上記のように、ヤコビの対角化法は実対称(あるいは複素エルミート)の場合が最も良く知られておりその場合だけしか適用できないものと考えられるかもしれない。しかし非対称な行列に対するヤコビ法もあって研究もされプログラムも公開されていたがQR法が登場した後では行列が非対称な場合にはほとんどQR法だけが使われているため今日では非対称な場合についてはほとんど認知されていないようである(複素エルミートの場合についてもその具体的な実装に言及している文献は稀であり,もっぱら実対称行列の場合だけがよく知られている)。