ヤコビ法

Iterative method used to solve a linear system of equations

数値線形代数において、ヤコビ法（別名ヤコビ反復法）は、厳密に対角優位な 線形方程式系の解を求める反復アルゴリズムです。各対角要素を解き、近似値を代入します。この処理は収束するまで反復されます。このアルゴリズムは、行列対角化におけるヤコビ変換法の簡略版です。この法は、カール・グスタフ・ヤコブ・ヤコビにちなんで名付けられました。

説明

をn個の線形方程式の正方連立方程式とします。 ${\displaystyle A\mathbf {x} =\mathbf {b} }$ $${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.}$$

と が既知で が未知の場合、ヤコビ法を用いて を近似することができます。ベクトル は（多くの場合 ）の初期推定値を表します。を のk回目の近似値または反復と表し、を の次の（またはk +1 回目の）反復と表します。 ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(0)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} _{i}^{(0)}=0}$ ${\displaystyle i=1,2,...,n}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle \mathbf {x} }$

行列ベースの式

そして、Aは対角成分D、下三角部分L、上三角部分Uに分解できる。そして、解は次のように反復的に得られる。 $${\displaystyle A=D+L+U\qquad {\text{where}}\qquad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}{\text{ and }}L+U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\a_{21}&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}}.}$$

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

要素ベースの式

各行の要素に基づく式は次のようになります。の計算には、自身を除く各要素が必要です。ガウス・ザイデル法とは異なり、を で上書きすることはできません。その値は残りの計算で必要になるからです。必要な記憶領域の最小量は、サイズnのベクトル2つです。 ${\displaystyle i}$ $${\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}$$ ${\displaystyle x_{i}^{(k+1)}}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle x_{i}^{(k)}}$ ${\displaystyle x_{i}^{(k+1)}}$

アルゴリズム

入力: 解の初期推定値x (0)、（対角優勢）行列A、右辺ベクトルb、収束基準出力: 収束に達したときの解コメント:上記の要素ベースの式に基づく擬似コードk = 0収束に達していない間i  := 1ステップnまで実行 σ = 0の場合j  := 1ステップnまで実行j ≠ iの場合σ = σ + a ij x j ( k ) end end x i ( k +1) = ( b i − σ ) / a ii end k を増分end             

収束

標準的な収束条件（あらゆる反復法の場合）は、反復行列のスペクトル半径が1未満であるときです。

${\displaystyle \rho (D^{-1}(L+U))<1.}$

この方法が収束するための十分条件（ただし必要条件ではない）は、行列Aが厳密または既約に対角優位であることです。厳密な行対角優位とは、各行において対角項の絶対値が他の項の絶対値の合計よりも大きいことを意味します。

${\displaystyle \left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.}$

ヤコビ法は、これらの条件が満たされなくても収束することがあります。

ヤコビ法はすべての対称正定値行列に対して収束するわけではないことに注意する。例えば、 $${\displaystyle A={\begin{pmatrix}29&2&1\\2&6&1\\1&1&{\frac {1}{5}}\end{pmatrix}}\quad \Rightarrow \quad D^{-1}(L+U)={\begin{pmatrix}0&{\frac {2}{29}}&{\frac {1}{29}}\\{\frac {1}{3}}&0&{\frac {1}{6}}\\5&5&0\end{pmatrix}}\quad \Rightarrow \quad \rho (D^{-1}(L+U))\approx 1.0661\,.}$$

例

例題

初期推定値を持つ形式の線形システムは次のように与えられる。 ${\displaystyle Ax=b}$ ${\displaystyle x^{(0)}}$

${\displaystyle A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}}\quad {\text{and}}\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.}$

を推定するために、上で述べた方程式 を使います。まず、より便利な形 に方程式を書き直します。ここで、 と です。既知の値から、が求められます。さらに 、はと求められます 。 と を計算して、を推定します。次の反復では が得られます 。このプロセスは収束するまで（つまり、が小さくなるまで）繰り返されます。25回の反復後の解は ${\displaystyle x^{(k+1)}=D^{-1}(b-(L+U)x^{(k)})}$ ${\displaystyle x}$ ${\displaystyle D^{-1}(b-(L+U)x^{(k)})=Tx^{(k)}+C}$ ${\displaystyle T=-D^{-1}(L+U)}$ ${\displaystyle C=D^{-1}b}$ $${\displaystyle D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}}\quad {\text{and}}\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.}$$ ${\displaystyle T=-D^{-1}(L+U)}$ $${\displaystyle T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}.}$$ ${\displaystyle C}$ $${\displaystyle C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}.}$$ ${\displaystyle T}$ ${\displaystyle C}$ ${\displaystyle x}$ ${\displaystyle x^{(1)}=Tx^{(0)}+C}$ $${\displaystyle x^{(1)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}\approx {\begin{bmatrix}5\\1.143\\\end{bmatrix}}.}$$ $${\displaystyle x^{(2)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}69/14\\-12/7\\\end{bmatrix}}\approx {\begin{bmatrix}4.929\\-1.714\\\end{bmatrix}}.}$$ ${\displaystyle \|Ax^{(n)}-b\|}$

${\displaystyle x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.}$

例題2

次のような線形システムが与えられているとします。

${\displaystyle {\begin{aligned}10x_{1}-x_{2}+2x_{3}&=6,\\-x_{1}+11x_{2}-x_{3}+3x_{4}&=25,\\2x_{1}-x_{2}+10x_{3}-x_{4}&=-11,\\3x_{2}-x_{3}+8x_{4}&=15.\end{aligned}}}$

初期近似値として(0, 0, 0, 0)を選択した場合、最初の近似解は次のように与えられます。得られた近似値を用いて、所望の精度に達するまで反復手順を繰り返します。以下は、5回の反復後の近似解です。 $${\displaystyle {\begin{aligned}x_{1}&=(6+0-(2*0))/10=0.6,\\x_{2}&=(25+0+0-(3*0))/11=25/11=2.2727,\\x_{3}&=(-11-(2*0)+0+0)/10=-1.1,\\x_{4}&=(15-(3*0)+0)/8=1.875.\end{aligned}}}$$

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0.93263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

この系の正確な解は(1, 2, −1, 1)である。

Pythonの例

numpyをnpとしてインポートする   反復制限 =  1000# 行列を初期化するA  =  np .配列([[ 10. ,  - 1. ,  2. ,  0. ], [ - 1. ,  11. ,  - 1. ,  3. ], [ 2. ,  - 1. ,  10. ,  - 1. ], [ 0.0 ,  3. ,  - 1. ,  8. ]])# RHSベクトルを初期化するb  =  np .配列([ 6. ,  25. ,  - 11. ,  15. ])# システムを印刷するprint ( "システム:" ) i が 範囲内 ( A .形状[ 0 ] )の場合: row  =  [ f " { A [ i , j ] } *x { j + 1 } " （jは範囲（A . shape [ 1 ] ））]        print ( f ' { " + " . join ( row ) } = { b [ i ] } ' )印刷（）x  =  np . zeros_like ( b ) it_countが 範囲内の 場合( ITERATION_LIMIT ):  it_count  !=  0 の場合: print ( f "反復{ it_count } : { x } " ) x_new  =  np . zeros_like ( x )  i が 範囲内 ( A .形状[ 0 ] )の場合: s1  =  np . dot ( A [ i ,  : i ],  x [: i ]) s2  =  np . dot ( A [ i ,  i  +  1 :],  x [ i  +  1 :]) x_new [ i ]  =  ( b [ i ]  -  s1  -  s2 )  /  A [ i ,  i ]  x_new [ i ]  ==  x_new [ i - 1 ]の場合: 壊す  np . allclose ( x 、 x_new 、 atol = 1e-10 、 rtol = 0 )の場合: 壊す x  =  x_newprint ( "解決策: " )印刷( x )誤差 =  np . dot ( A ,  x )  -  bprint ( "エラー:" )印刷(エラー)

重み付きヤコビ法

重み付きヤコビ反復法は、パラメータを使用して反復を計算します。 ${\displaystyle \omega }$

${\displaystyle \mathbf {x} ^{(k+1)}=\omega D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)})+\left(1-\omega \right)\mathbf {x} ^{(k)}}$

が通常の選択肢となる。 ^[1]の関係から、これは次のようにも表される。 ${\displaystyle \omega =2/3}$ ${\displaystyle L+U=A-D}$

${\displaystyle {\begin{aligned}\mathbf {x} ^{(k+1)}&=\omega D^{-1}\mathbf {b} +\left(I-\omega D^{-1}A\right)\mathbf {x} ^{(k)}\\&=\mathbf {x} ^{(k)}+\omega D^{-1}\mathbf {r} ^{(k)},\end{aligned}}}$

ここで、 は反復における代数残差です。 ${\displaystyle \mathbf {r} ^{(k)}=\mathbf {b} -A\mathbf {x} ^{(k)}}$ ${\displaystyle k}$

対称正定値の場合の収束

システム行列が対称正定値である場合、収束を示すことができます。 ${\displaystyle A}$

を反復行列とする。すると、収束は保証される。 ${\displaystyle C=C_{\omega }=I-\omega D^{-1}A}$

${\displaystyle \rho (C_{\omega })<1\quad \Longleftrightarrow \quad 0<\omega <{\frac {2}{\lambda _{\text{max}}(D^{-1}A)}}\,,}$

ここで最大固有値です。 ${\displaystyle \lambda _{\text{max}}}$

スペクトル半径は、 の特定の選択に対して次のように 最小化できます。ここで、は行列条件数です。 ${\displaystyle \omega =\omega _{\text{opt}}}$ $${\displaystyle \min _{\omega }\rho (C_{\omega })=\rho (C_{\omega _{\text{opt}}})=1-{\frac {2}{\kappa (D^{-1}A)+1}}\quad {\text{for}}\quad \omega _{\text{opt}}:={\frac {2}{\lambda _{\text{min}}(D^{-1}A)+\lambda _{\text{max}}(D^{-1}A)}}\,,}$$ ${\displaystyle \kappa }$

参照

• ガウス・ザイデル法
• 連続的な過剰緩和
• 反復法 § 線形システム
• ガウス確率伝播
• 行列分割

参考文献

1. Saad, Yousef (2003). 疎線形システムのための反復法（第2版）. SIAM . p. 414. ISBN 0898715342。

外部リンク

• この記事には、 GFDLライセンスの下にある CFD-Wiki の記事 Jacobi_method のテキストが組み込まれています。

• ブラック、ノエル、ムーア、シャーリー、ワイスタイン、エリック・W.「ヤコビ法」。MathWorld。
• www.math-linux.com の Jacobi 法

Retrieved from "https://en.wikipedia.org/w/index.php?title=Jacobi_method&oldid=1309522917"