Iterative method used to solve a linear system of equations
数値線形代数 において 、 ガウス・ザイデル法は リープマン法 あるいは 逐次変位法 とも呼ばれ 、 線形方程式系 を解く 反復法である。 ドイツの 数学者 カール・フリードリヒ・ガウス と フィリップ・ルートヴィヒ・フォン・ザイデル にちなんで名付けられた 。対角成分がゼロでない任意の行列に適用できるが、収束が保証されるのは、行列が 厳密に対角優勢 な場合、 [1] あるいは 対称 かつ 正定値行列 である場合のみである。この法則は、ガウスが1823年に弟子の ゲルリング に宛てた私信の中でのみ言及されている。 [2] ザイデルによる出版物は1874年より前には発表されていなかった。 [3]
説明 をn個の 線形方程式の正方連立方程式とし ます 。 A x = b {\textstyle \mathbf {A} \mathbf {x} =\mathbf {b} }
A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] , x = [ x 1 x 2 ⋮ x n ] , b = [ b 1 b 2 ⋮ b n ] . {\displaystyle \mathbf {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}}.}
と が 既知で が未知の 場合 、ガウス・ザイデル法を用いて を反復的に近似することができます 。ベクトル は の初期推定値 （多くの場合 ）を表します。 を の - 回目の近似値または反復 で表し 、 を次の（または - 回目の）反復 における の近似値で表します。 A {\displaystyle \mathbf {A} } b {\displaystyle \mathbf {b} } x {\displaystyle \mathbf {x} } x {\displaystyle \mathbf {x} } x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} x {\displaystyle \mathbf {x} } x i ( 0 ) = 0 {\displaystyle \mathbf {x} _{i}^{(0)}=0} i = 1 , 2 , . . . , n {\displaystyle i=1,2,...,n} x ( k ) {\displaystyle \mathbf {x} ^{(k)}} k {\displaystyle k} x {\displaystyle \mathbf {x} } x ( k + 1 ) {\displaystyle \mathbf {x} ^{(k+1)}} x {\displaystyle \mathbf {x} } k + 1 {\displaystyle k+1}
解は、 によって反復的に得られます。 ここで、行列は 下三角 成分 と、 となる 厳密に上三角 成分 に分解されます 。 [4] 具体的には、をと に 分解すると 、 次の式で与えられます。 L x ( k + 1 ) = b − U x ( k ) , {\displaystyle \mathbf {L} \mathbf {x} ^{(k+1)}=\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)},} A {\displaystyle \mathbf {A} } L {\displaystyle \mathbf {L} } U {\displaystyle \mathbf {U} } A = L + U {\displaystyle \mathbf {A} =\mathbf {L} +\mathbf {U} } A {\displaystyle \mathbf {A} } L {\displaystyle \mathbf {L} } U {\displaystyle \mathbf {U} }
A = [ a 11 0 ⋯ 0 a 21 a 22 ⋯ 0 ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] ⏟ L + [ 0 a 12 ⋯ a 1 n 0 0 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 0 ] ⏟ U . {\displaystyle \mathbf {A} =\underbrace {\begin{bmatrix}a_{11}&0&\cdots &0\\a_{21}&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}} _{\textstyle \mathbf {L} }+\underbrace {\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}} _{\textstyle \mathbf {U} }.}
線形方程式系は次のように書き直すことができます。
A x = b ( L + U ) x = b L x + U x = b L x = b − U x {\displaystyle {\begin{alignedat}{1}\mathbf {A} \mathbf {x} &=\mathbf {b} \\(\mathbf {L} +\mathbf {U} )\mathbf {x} &=\mathbf {b} \\\mathbf {L} \mathbf {x} +\mathbf {U} \mathbf {x} &=\mathbf {b} \\\mathbf {L} \mathbf {x} &=\mathbf {b} -\mathbf {U} \mathbf {x} \end{alignedat}}} ガウス・ザイデル法では 、右辺の の値を として、この式の左辺を について解きます 。解析的には、これは次のように書けます。 x {\displaystyle \mathbf {x} } x {\displaystyle \mathbf {x} } x ( k + 1 ) = L − 1 ( b − U x ( k ) ) . {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}\left(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)}\right).}
しかし、の三角形状を利用することで 、の要素は 前方置換 を用いて 各行ごとに順番に計算することができる ： [5] L {\displaystyle \mathbf {L} } x ( k + 1 ) {\displaystyle \mathbf {x} ^{(k+1)}} i {\displaystyle i} x i ( k + 1 ) = 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j ( k + 1 ) − ∑ j = i + 1 n a i j x j ( k ) ) , i = 1 , 2 , … , n . {\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\dots ,n.}
この式では、反復ごとに2つの合計が用いられますが、これは最後に計算された反復 を用いた 1つの合計として表すことができます。この手順は通常、反復による変化が、例えば 残差 が 十分に小さいなど、ある許容範囲を下回るまで続けられます 。 ∑ j ≠ i a i j x j {\displaystyle \sum _{j\neq i}a_{ij}x_{j}} x j {\displaystyle x_{j}}
議論 ガウス・ザイデル法の要素ごとの式は、（反復） ヤコビ法 の式と関連していますが、重要な違いがあります。
ガウス・ザイデル法では、 の計算には 、既に計算済みの の要素と、 回目の反復 で計算されていないの要素のみが使用されます 。これは、ヤコビ法とは異なり、要素は計算中に上書きできるため、必要な記憶ベクトルは1つだけであることを意味します。これは、非常に大規模な問題の場合に有利です。 x ( k + 1 ) {\displaystyle \mathbf {x} ^{(k+1)}} x ( k + 1 ) {\displaystyle \mathbf {x} ^{(k+1)}} x ( k ) {\displaystyle \mathbf {x} ^{(k)}} ( k + 1 ) {\displaystyle (k+1)}
しかし、ヤコビ法とは異なり、各要素の計算は クリティカルパスが 非常に長くなる可能性があるため、 並列実装が 一般的に非常に困難であり、 疎行列 で最も実現可能です。さらに、各反復における値は元の方程式の順序に依存します。
ガウス・ザイデルは、による 逐次過剰緩和 と同じです 。 ω = 1 {\displaystyle \omega =1}
収束 ガウス・ザイデル法の収束特性は行列に依存します 。つまり、この法は次のいずれかの条件を満たす場合に収束することが知られています。 A {\displaystyle \mathbf {A} }
A {\displaystyle \mathbf {A} } 対称 正定値で ある[ 6] または A {\displaystyle \mathbf {A} } は厳密または不可約的に 対角優勢 である。 [7] ガウス・ザイデル法は、これらの条件が満たされていなくても収束する可能性があります。
ゴルブとヴァン・ローンは、2つの部分に 分割できるアルゴリズムの定理を与えている。 が非特異であるとする。 を の スペクトル半径 とする。すると、 が非特異で の とき 、 で定義される 反復は 任意の開始ベクトル に対して に収束する 。 [8] A {\displaystyle \mathbf {A} } A = M − N {\displaystyle \mathbf {A} =\mathbf {M} -\mathbf {N} } r = ρ ( M − 1 N ) {\displaystyle r=\rho (\mathbf {M} ^{-1}\mathbf {N} )} M − 1 N {\displaystyle \mathbf {M} ^{-1}\mathbf {N} } x ( k ) {\displaystyle \mathbf {x} ^{(k)}} M x ( k + 1 ) = N x ( k ) + b {\displaystyle \mathbf {M} \mathbf {x} ^{(k+1)}=\mathbf {N} \mathbf {x} ^{(k)}+\mathbf {b} } x = A − 1 b {\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} } x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} M {\displaystyle \mathbf {M} } r < 1 {\displaystyle r<1}
アルゴリズム このアルゴリズムでは、要素は計算時に上書きできるため、必要な記憶ベクトルは1つだけで、ベクトルのインデックス付けは省略されます。アルゴリズムは以下のようになります。
アルゴリズム ガウス・ザイデル法 は 入力: A , b 出力: φ 解の 初期推定値 φ を選択し、収束する まで 繰り返します。 i に対して 1 から n まで σ ← 0 を 実行します 。 j に対して 1 から n まで j ≠ i の場合 σ ← σ + a ij φ j end if end ( j -loop) φ i ← ( b i − σ ) / a ii end ( i -loop) 収束に達したかどうかを確認する 終了 （繰り返し）
例
マトリックスバージョンの例 次のように表される線形システムは 次のようになります。 A x = b {\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} } A = [ 16 3 7 − 11 ] and b = [ 11 13 ] . {\displaystyle \mathbf {A} ={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {b} ={\begin{bmatrix}11\\13\end{bmatrix}}.}
次の形式の 方程式を使用します 。 x ( k + 1 ) = L − 1 ( b − U x ( k ) ) {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)})} x ( k + 1 ) = T x ( k ) + c {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {T} \mathbf {x} ^{(k)}+\mathbf {c} }
T = − L − 1 U and c = L − 1 b . {\displaystyle \mathbf {T} =-\mathbf {L} ^{-1}\mathbf {U} \quad {\text{and}}\quad \mathbf {c} =\mathbf {L} ^{-1}\mathbf {b} .} 下三角成分と厳密な上三角成分 の和に 分解します 。 A {\displaystyle \mathbf {A} } L {\displaystyle \mathbf {L} } U {\displaystyle U} L = [ 16 0 7 − 11 ] and U = [ 0 3 0 0 ] . {\displaystyle \mathbf {L} ={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {U} ={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.}
の逆は次の ようになります。 L {\displaystyle \mathbf {L} } L − 1 = [ 16 0 7 − 11 ] − 1 = [ 0.0625 0.0000 0.0398 − 0.0909 ] . {\displaystyle \mathbf {L} ^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}.}
次に以下を見つけます: T = − [ 0.0625 0.0000 0.0398 − 0.0909 ] [ 0 3 0 0 ] = [ 0.000 − 0.1875 0.000 − 0.1194 ] , c = [ 0.0625 0.0000 0.0398 − 0.0909 ] [ 11 13 ] = [ 0.6875 − 0.7439 ] . {\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\end{bmatrix}}={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1194\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}11\\13\end{bmatrix}}={\begin{bmatrix}0.6875\\-0.7439\end{bmatrix}}.\end{aligned}}}
とを使用する と、 ベクトルを 反復的に取得できます。 T {\displaystyle \mathbf {T} } c {\displaystyle \mathbf {c} } x {\displaystyle \mathbf {x} }
まず、 たとえば を選択します。 推測が最終解に近いほど、アルゴリズムに必要な反復回数は少なくなります。 x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} x ( 0 ) = [ 1.0 1.0 ] . {\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1.0\\1.0\end{bmatrix}}.}
次に計算します。 x ( 1 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 1.0 1.0 ] + [ 0.6875 − 0.7443 ] = [ 0.5000 − 0.8636 ] . x ( 2 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.5000 − 0.8636 ] + [ 0.6875 − 0.7443 ] = [ 0.8494 − 0.6413 ] . x ( 3 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.8494 − 0.6413 ] + [ 0.6875 − 0.7443 ] = [ 0.8077 − 0.6678 ] . x ( 4 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.8077 − 0.6678 ] + [ 0.6875 − 0.7443 ] = [ 0.8127 − 0.6646 ] . x ( 5 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.8127 − 0.6646 ] + [ 0.6875 − 0.7443 ] = [ 0.8121 − 0.6650 ] . x ( 6 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.8121 − 0.6650 ] + [ 0.6875 − 0.7443 ] = [ 0.8122 − 0.6650 ] . x ( 7 ) = [ 0.000 − 0.1875 0.000 − 0.1193 ] [ 0.8122 − 0.6650 ] + [ 0.6875 − 0.7443 ] = [ 0.8122 − 0.6650 ] . {\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}1.0\\1.0\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8494\\-0.6413\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8494\\-0.6413\\\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(4)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(5)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(6)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(7)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\end{aligned}}}
予想どおり、アルゴリズムは次の解に収束します 。 x = A − 1 b ≈ [ 0.8122 − 0.6650 ] {\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} \approx {\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}}
実際、行列 A は厳密に対角優勢ですが、正定値ではありません。
マトリックス版の別の例 として示される別の線形システムは 次のとおりです。 A x = b {\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }
A = [ 2 3 5 7 ] and b = [ 11 13 ] . {\displaystyle \mathbf {A} ={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {b} ={\begin{bmatrix}11\\13\\\end{bmatrix}}.}
次の形式の 方程式を使用します 。 x ( k + 1 ) = L − 1 ( b − U x ( k ) ) {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {L} ^{-1}(\mathbf {b} -\mathbf {U} \mathbf {x} ^{(k)})} x ( k + 1 ) = T x ( k ) + c {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {T} \mathbf {x} ^{(k)}+\mathbf {c} }
T = − L − 1 U and c = L − 1 b . {\displaystyle \mathbf {T} =-\mathbf {L} ^{-1}\mathbf {U} \quad {\text{and}}\quad \mathbf {c} =\mathbf {L} ^{-1}\mathbf {b} .} 下三角成分と厳密な上三角成分 の和に 分解します 。 A {\displaystyle \mathbf {A} } L {\displaystyle \mathbf {L} } U {\displaystyle \mathbf {U} } L = [ 2 0 5 7 ] and U = [ 0 3 0 0 ] . {\displaystyle \mathbf {L} ={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}\quad {\text{and}}\quad \mathbf {U} ={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.}
の逆は次の ようになります。 L {\displaystyle \mathbf {L} } L − 1 = [ 2 0 5 7 ] − 1 = [ 0.500 0.000 − 0.357 0.143 ] . {\displaystyle \mathbf {L} ^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}.}
次に以下を見つけます: T = − [ 0.500 0.000 − 0.357 0.143 ] [ 0 3 0 0 ] = [ 0.000 − 1.500 0.000 1.071 ] , c = [ 0.500 0.000 − 0.357 0.143 ] [ 11 13 ] = [ 5.500 − 2.071 ] . {\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}={\begin{bmatrix}0.000&-1.500\\0.000&1.071\\\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}.\end{aligned}}}
とを使用する と、 ベクトルを 反復的に取得できます。 T {\displaystyle \mathbf {T} } c {\displaystyle \mathbf {c} } x {\displaystyle \mathbf {x} }
まず、 例えばを選択しなければなりません x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} x ( 0 ) = [ 1.1 2.3 ] {\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1.1\\2.3\end{bmatrix}}}
次に計算します。 x ( 1 ) = [ 0 − 1.500 0 1.071 ] [ 1.1 2.3 ] + [ 5.500 − 2.071 ] = [ 2.050 0.393 ] . x ( 2 ) = [ 0 − 1.500 0 1.071 ] [ 2.050 0.393 ] + [ 5.500 − 2.071 ] = [ 4.911 − 1.651 ] . x ( 3 ) = ⋯ . {\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}1.1\\2.3\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}4.911\\-1.651\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&=\cdots .\end{aligned}}}
収束性検定において、アルゴリズムが発散することが判明しました。実際、行列は 対角優勢行列でも正定値行列でもありません。したがって、厳密解への収束は 保証されておらず、この場合は収束しません。 A {\displaystyle \mathbf {A} } x = A − 1 b = [ − 38 29 ] {\displaystyle \mathbf {x} =\mathbf {A} ^{-1}\mathbf {b} ={\begin{bmatrix}-38\\29\end{bmatrix}}}
方程式バージョンの例 与えられた方程式 と開始点 を仮定します 。ガウス・ザイデル反復法の任意のステップにおいて、最初の方程式 を について で解き 、次に2番目の方程式 を、 先ほど求めた と残りの について で解き 、 まで続けます 。そして、収束に達するまで反復を繰り返すか、解の発散が定義済みのレベルを超え始めた場合は反復を中断します。 n {\displaystyle n} x 0 {\displaystyle \mathbf {x} _{0}} x 1 {\displaystyle x_{1}} x 2 , … , x n {\displaystyle x_{2},\dots ,x_{n}} x 2 {\displaystyle x_{2}} x 1 {\displaystyle x_{1}} x 3 , … , x n {\displaystyle x_{3},\dots ,x_{n}} x n {\displaystyle x_{n}}
例を考えてみましょう: 10 x 1 − x 2 + 2 x 3 = 6 , − x 1 + 11 x 2 − x 3 + 3 x 4 = 25 , 2 x 1 − x 2 + 10 x 3 − x 4 = − 11 , 3 x 2 − x 3 + 8 x 4 = 15. {\displaystyle {\begin{array}{rrrrl}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{array}}}
を解く と 次のようになります。 x 1 , x 2 , x 3 {\displaystyle x_{1},x_{2},x_{3}} x 4 {\displaystyle x_{4}} x 1 = x 2 / 10 − x 3 / 5 + 3 / 5 , x 2 = x 1 / 11 + x 3 / 11 − 3 x 4 / 11 + 25 / 11 , x 3 = − x 1 / 5 + x 2 / 10 + x 4 / 10 − 11 / 10 , x 4 = − 3 x 2 / 8 + x 3 / 8 + 15 / 8. {\displaystyle {\begin{aligned}x_{1}&=x_{2}/10-x_{3}/5+3/5,\\x_{2}&=x_{1}/11+x_{3}/11-3x_{4}/11+25/11,\\x_{3}&=-x_{1}/5+x_{2}/10+x_{4}/10-11/10,\\x_{4}&=-3x_{2}/8+x_{3}/8+15/8.\end{aligned}}}
(0, 0, 0, 0) が初期近似値である とすると、最初の近似解は次のようになります。 x 1 = 3 / 5 = 0.6 , x 2 = ( 3 / 5 ) / 11 + 25 / 11 = 3 / 55 + 25 / 11 = 2.3272 , x 3 = − ( 3 / 5 ) / 5 + ( 2.3272 ) / 10 − 11 / 10 = − 3 / 25 + 0.23272 − 1.1 = − 0.9873 , x 4 = − 3 ( 2.3272 ) / 8 + ( − 0.9873 ) / 8 + 15 / 8 = 0.8789. {\displaystyle {\begin{aligned}x_{1}&=3/5=0.6,\\x_{2}&=(3/5)/11+25/11=3/55+25/11=2.3272,\\x_{3}&=-(3/5)/5+(2.3272)/10-11/10=-3/25+0.23272-1.1=-0.9873,\\x_{4}&=-3(2.3272)/8+(-0.9873)/8+15/8=0.8789.\end{aligned}}}
得られた近似値を用いて、所望の精度に達するまで反復手順を繰り返します。以下は4回の反復後の近似解です。
x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} x 4 {\displaystyle x_{4}} 0.6 2.32727 −0.987273 0.878864 1.03018 2.03694 −1.01446 0.984341 1.00659 2.00356 −1.00253 0.998351 1.00086 2.0003 −1.00031 0.99985
この系の正確な解は (1, 2, −1, 1) である。
PythonとNumPyを使った例 次の反復手順により、線形方程式の解ベクトルが生成されます。
numpyを np として インポートする 反復制限 = 1000 # 行列を初期化します A = np . array ( [ [ 10.0 , - 1.0 , 2.0 , 0.0 ], [ - 1.0 , 11.0 , - 1.0 , 3.0 ], [ 2.0 , - 1.0 , 10.0 , - 1.0 ], [ 0.0 , 3.0 , - 1.0 , 8.0 ], ] ) # 右辺ベクトルを初期化します b = np . array ([ 6.0 , 25.0 , - 11.0 , 15.0 ]) print ( "方程式系:" ) for i in range ( A . shape [ 0 ]): row = [ f " { A [ i , j ] : 3g } *x { j + 1 } " for j in range ( A . shape [ 1 ])] print ( "[ {0} ] = [ {1:3g} ]" . format ( " + " . join ( row ), b [ i ])) x = np . zeros_like ( b , np . float_ ) で it_count が range ( 1 , ITERATION_LIMIT ) の場合: x_new = np . zeros_like ( x , dtype = np . float_ ) で print ( f "反復 { it_count } : { x } " ) で i が range ( A . shape [ 0 ] ) の場合: s1 = np . dot ( A [ i , : i ], x_new [: i ]) s2 = np . dot ( A [ i , i + 1 :], x [ i + 1 :]) x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i , i ]で np . allclose ( x , x_new , rtol = 1e-8 ) の場合 : break x = x_new print ( f "解: { x } " ) error = np . dot ( A , x ) - b print ( f "エラー: { error } " ) 次の出力を生成します:
System of equations: [ 10*x1 + -1*x2 + 2*x3 + 0*x4] = [ 6] [ -1*x1 + 11*x2 + -1*x3 + 3*x4] = [ 25] [ 2*x1 + -1*x2 + 10*x3 + -1*x4] = [-11] [ 0*x1 + 3*x2 + -1*x3 + 8*x4] = [ 15] Iteration 1: [ 0. 0. 0. 0.] Iteration 2: [ 0.6 2.32727273 -0.98727273 0.87886364] Iteration 3: [ 1.03018182 2.03693802 -1.0144562 0.98434122] Iteration 4: [ 1.00658504 2.00355502 -1.00252738 0.99835095] Iteration 5: [ 1.00086098 2.00029825 -1.00030728 0.99984975] Iteration 6: [ 1.00009128 2.00002134 -1.00003115 0.9999881 ] Iteration 7: [ 1.00000836 2.00000117 -1.00000275 0.99999922] Iteration 8: [ 1.00000067 2.00000002 -1.00000021 0.99999996] 反復9: [ 1.00000004 1.99999999 -1.00000001 1. ] 反復10: [ 1. 2. -1. 1.] 解答: [ 1. 2. -1. 1.] エラー: [ 2.06480930e-08 -1.25551054e-08 3.61417563e-11 0.00000000e+00]
Matlabを使用して任意の数の方程式を解くプログラム 次のコードでは次の式を使用しています x i ( k + 1 ) = 1 a i i ( b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) ) , i = 1 , 2 , … , n k = 0 , 1 , 2 , … {\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad {\begin{array}{l}i=1,2,\ldots ,n\\k=0,1,2,\ldots \end{array}}}
function x = gauss_seidel ( A, b, x, iters ) for i = 1 : iters for j = 1 : size ( A , 1 ) x ( j ) = ( b ( j ) - sum ( A ( j ,:) '.* x ) + A ( j , j ) * x ( j )) / A ( j , j ); 終わり、 終わり、 終わり
参照
注記 ^ ザウアー、ティモシー (2006). 数値解析 （第2版）. ピアソン・エデュケーション社. p. 109. ISBN 978-0-321-78367-7 。 ^
Gauss 1903、p. 279; 直接リンク。 ^ ザイデル、ルートヴィヒ (1874)。 「Über ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate füult, sowie lineäre Gleichungen überhaupt, durch successive Annäherung aufzulösen」 [最小二乗法が導く方程式および一般的な線形方程式を逐次近似によって解くプロセスについて]。 Abhandlungen der Mathematisch-Physikalischen Klasse der Königlich Bayerischen Akademie der Wissenschaften (ドイツ語)。 11 (3): 81–108 . ^ ゴラブとヴァン・ローン、1996年、p. 511。 ^ Golub & Van Loan 1996、式（10.1.3） ^ Golub & Van Loan 1996、Thm 10.1.2。 ^ Bagnara, Roberto (1995年3月). 「ヤコビ法とガウス・ザイデル法の収束性に関する統一的証明」. SIAM Review . 37 (1): 93– 97. CiteSeerX 10.1.1.26.5207 . doi :10.1137/1037008. JSTOR 2132758. ^ ゴルブ＆ヴァン・ローン 1996、Thm 10.1.2
参考文献 この記事には、 GFDL ライセンスの下にある CFD-Wiki の記事「Gauss-Seidel_method」のテキストが組み込まれています 。
外部リンク 「ザイデル法」、 数学百科事典 、 EMSプレス 、2001 [1994] www.math-linux.com の Gauss–Seidel ガウス・ザイデル（ホリスティック数値解析研究所より） www.geocities.com のガウス ジーデル反復 ガウス・ザイデル法 ビックソン Matlabコード Cコードの例
![{\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\end{bmatrix}}={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1194\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}11\\13\end{bmatrix}}={\begin{bmatrix}0.6875\\-0.7439\end{bmatrix}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df785dc59c5da4829f3c23cc74e632ecf88f0c63)
![{\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}1.0\\1.0\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.5000\\-0.8636\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8494\\-0.6413\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8494\\-0.6413\\\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(4)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8077\\-0.6678\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(5)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8127\\-0.6646\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(6)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8121\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(7)}&={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1193\end{bmatrix}}{\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}+{\begin{bmatrix}0.6875\\-0.7443\end{bmatrix}}={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97ae0b62d9839ae8a03a54f02be3a54a31021d17)
![{\displaystyle {\begin{aligned}\mathbf {T} &=-{\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}={\begin{bmatrix}0.000&-1.500\\0.000&1.071\\\end{bmatrix}},\\[1ex]\mathbf {c} &={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0300036d45f867e4c257d76f77af4543680b6249)
![{\displaystyle {\begin{aligned}\mathbf {x} ^{(1)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}1.1\\2.3\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(2)}&={\begin{bmatrix}0&-1.500\\0&1.071\\\end{bmatrix}}{\begin{bmatrix}2.050\\0.393\\\end{bmatrix}}+{\begin{bmatrix}5.500\\-2.071\\\end{bmatrix}}={\begin{bmatrix}4.911\\-1.651\end{bmatrix}}.\\[1ex]\mathbf {x} ^{(3)}&=\cdots .\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56495bb13fbd1d9aae010837343c0758eb87e57f)
