反復のスキーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/21 15:59 UTC 版)
n {\displaystyle n} 次正方行列 A {\displaystyle A} は、上三角行列 U {\displaystyle U} 、下三角行列 L {\displaystyle L} 、対角行列 D {\displaystyle D} の和に分離すると、 A = L + D + U {\displaystyle A=L+D+U} と書ける。 非対角成分に相当する項をすべて右辺に移項し、すべての量 x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} に各段階で得られている最新のデータを代入するようにする(ガウス＝ザイデル法)。こうして計算された値を x ~ ( k + 1 ) {\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}} とすると、 x ~ i ( k + 1 ) {\displaystyle {\tilde {x}}_{i}^{(k+1)}} は次の形となる。 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 ) ) {\displaystyle {\tilde {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)} この値を次段でそのまま採用せずに、ガウス＝ザイデル法で本来修正される量 x ~ i ( k + 1 ) − x i ( k ) {\displaystyle {\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}} に1より大きい加速パラメータ（では緩和因子、緩和係数と呼ばれている） ω {\displaystyle \omega } を乗じてこの修正量を拡大し、これを前段の近似値 x i ( k ) {\displaystyle x_{i}^{(k)}} に加えることで、新たな値は x i ( k + 1 ) = x i ( k ) + ω ( x ~ i ( k + 1 ) − x i ( k ) ) {\displaystyle x_{i}^{(k+1)}=x_{i}^{(k)}+\omega \left({\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}\right)} とできる。ただし、桁落ちを防ぐ観点からこの式の通り計算するのではなく、 x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω x ~ i ( k + 1 ) {\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+\omega {\tilde {x}}_{i}^{(k+1)}} として計算するか、または本節の最後に書かれた式を用いるのがよい。 この漸化式を、上の A = L + D + U {\displaystyle A=L+D+U} を用いて行列で表現すると、 { x ~ ( k + 1 ) = D − 1 ( b − L x ( k + 1 ) − U x ( k ) ) x ( k + 1 ) = x ( k ) + ω ( x ~ ( k + 1 ) − x ( k ) ) {\displaystyle {\Biggl \{}{\begin{matrix}{\boldsymbol {\tilde {x}}}^{(k+1)}&=&D^{-1}\left({\boldsymbol {b}}-L{\boldsymbol {x}}^{(k+1)}-U{\boldsymbol {x}}^{(k)}\right)\\{\boldsymbol {x}}^{(k+1)}&=&{\boldsymbol {x}}^{(k)}+\omega \left({\boldsymbol {\tilde {x}}}^{(k+1)}-{\boldsymbol {x}}^{(k)}\right)\end{matrix}}} となり、この2式から x ~ ( k + 1 ) {\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}} を消去することで、次式が得られる。 x ( k + 1 ) = ( I + ω D − 1 L ) − 1 { ( 1 − ω ) I − ω D − 1 U } x ( k ) + ω ( D + ω L ) − 1 b {\displaystyle {\boldsymbol {x}}^{(k+1)}=\left(I+\omega D^{-1}L\right)^{-1}\left\{\left(1-\omega \right)I-\omega D^{-1}U\right\}{\boldsymbol {x}}^{(k)}+\omega \left(D+\omega L\right)^{-1}{\boldsymbol {b}}} 上式における x ( k ) {\displaystyle {\boldsymbol {x}}^{(k)}} の係数 M ω = ( I + ω D − 1 L ) − 1 { ( 1 − ω ) I − ω D − 1 U } {\displaystyle M_{\omega }=\left(I+\omega D^{-1}L\right)^{-1}\left\{\left(1-\omega \right)I-\omega D^{-1}U\right\}} を反復行列という。 実際の数値計算においては、これを各成分について表した下の式が用いられる。 x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j ( k + 1 ) − ∑ j = i n a i j x j ( k ) ) {\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+\omega {\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i}^{n}a_{ij}x_{j}^{(k)}\right)}
※この「反復のスキーム」の解説は、「SOR法」の解説の一部です。
「反復のスキーム」を含む「SOR法」の記事については、「SOR法」の概要を参照ください。
- 反復のスキームのページへのリンク
