反復法

定常反復法は、元の線形方程式を近似する演算子を用いて線形方程式系を解き、その結果の誤差（残差）に基づいて「補正方程式」を作成し、このプロセスを繰り返す。これらの方法は導出、実装、分析が容易であるが、収束が保証されるのは限られた種類の行列に限られる。

反復法は次のように定義される。 $${\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k}),\quad k\geq 0}$$ そして、与えられた線形システムに対して${\displaystyle A\mathbf {x} =\mathbf {b} }$正確な解$\displaystyle \mathbf {x} ^{*}}$エラー​​ $${\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*},\quad k\geq 0.}$$ 反復法は、行列が存在する場合に線形と呼ばれます。${\displaystyle C\in \mathbb {R} ^{n\times n}}$そのため $${\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall k\geq 0}$$ この行列は反復行列と呼ばれます。与えられた反復行列を用いた反復法${\displaystyle C}$以下の条件が満たされる場合、 収束すると呼ばれます。$${\displaystyle \lim _{k\to \infty }C^{k}=0.}$$

重要な定理によれば、与えられた反復法とその反復行列に対して、${\displaystyle C}$収束するのは、そのスペクトル半径が${\displaystyle \rho (C)}$ 1より小さい、つまり、 $${\displaystyle \rho (C)<1.}$$

基本的な反復法は、行列を分割することによって機能します。${\displaystyle A}$の中へ $${\displaystyle A=M-N}$$ そしてここに行列があります${\displaystyle M}$容易に逆変換できるはずである。反復法は次のように定義される。 $${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+\mathbf {b} ,\quad k\geq 0,}$$ または同等に、 $${\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}+M^{-1}\left(\mathbf {b} -A\mathbf {x} ^{k}\right),\quad k\geq 0.}$$ このことから、反復行列は次のように与えられることがわかる。 $${\displaystyle C=I-M^{-1}A=M^{-1}N.}$$

定常反復法の基本的な例では、行列の分割を使用します。${\displaystyle A}$のような $${\displaystyle A=D+L+U\,,\quad D:=\operatorname {diag} ((a_{ii})_{i})}$$ どこ${\displaystyle D}$は対角線部分のみである${\displaystyle A}$、 そして${\displaystyle L}$は、​${\displaystyle A}$。 それぞれ、${\displaystyle U}$は、${\displaystyle A}$。

• リチャードソン法：$${\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$$
• ヤコビ法：$${\displaystyle M:=D}$$
• 減衰ヤコビ法：$${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$$
• ガウス・ザイデル法：$${\displaystyle M:=D+L}$$
• 連続過弛緩法（SOR）：$${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$$
• 対称的逐次過弛緩法（SSOR）：$${\displaystyle M:={\frac {1}{\omega \left(2-\omega \right)}}\left(D+\omega L\right)D^{-1}\left(D+\omega U\right)\quad (\omega \not \in \{0,2\})}$$

線形定常反復法は緩和法とも呼ばれる。

これらの手法は基礎を形成するため、システムサイズをNとした場合、N回の反復で収束することは明らかです。しかし、丸め誤差が存在する場合、この記述は成り立ちません。さらに、実際にはNは非常に大きくなる可能性があり、反復プロセスははるかに早く十分な精度に達します。これらの手法の解析は、演算子のスペクトルの複雑な関数に依存するため困難です。