ヤコビ法

すると、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)}).}$

各行の要素ベースの数式${\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)}}$その値は残りの計算で必要となるため、保存しておく必要があります。最小限必要なストレージ容量は、サイズnのベクトル 2 つです。

次の形式の線形システム${\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}}.}$

私たちは方程式を使用します${\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\|}$は小さい）。25回の反復後の解は

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

次の線形システムが与えられたと仮定します。

${\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)を選択した場合、最初の近似解は次のように与えられます。$${\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}}}$$ 得られた近似値を用いて、所望の精度に達するまで反復手順を繰り返す。以下は、5回の反復後の近似解である。

このシステムの正確な解は(1,  2, − 1, 1)  です。

システム行列が${\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 }$は行列条件番号です。