反復法

計算数学において、反復法とは、初期値を使用して、一連の問題に対する改善される近似解を生成する数学的手順であり、i番目の近似値 (「反復」と呼ばれる) は、前の近似値から導出されます。

勾配降下法、山登り法、ニュートン法、あるいはBFGSのような準ニュートン法といった反復法の終了条件付き実装は、反復法アルゴリズム、あるいは逐次近似法と呼ばれます。反復法は、対応するシーケンスが与えられた初期近似値に対して収束する場合、収束性があると呼ばれます。反復法の収束性解析は通常、数学的に厳密な解析が行われますが、ヒューリスティックに基づく反復法も一般的です。

対照的に、直接法は有限の演算シーケンスによって問題を解こうとする。丸め誤差がない場合、直接法は正確な解を与える（例えば、ガウス消去法によって線形連立方程式を解く）。反復法は、非線形方程式の場合、しばしば唯一の選択肢となる。しかし、反復法は、多数の変数（時には数百万のオーダー）を含む線形問題にも有用であることが多い。そのような問題では、直接法は利用可能な最高の計算能力をもってしても、法外なコストがかかる（場合によっては不可能になる）可能性がある。^[1]${\displaystyle A\mathbf {x} =\mathbf {b} }$

魅力的な固定点

方程式をf ( x ) = xの形にすることができ、解x が関数fの吸引不動点である場合、 xの吸引域内の点x ₁から始めて、 n ≥ 1に対してx _{n +1} = f ( x _n )とすると 、シーケンス { x _n } _{n  ≥ 1が解}xに収束します。ここで、 x _nはxの n 番目の近似または反復であり、 x _{n +1は}xの次の反復またはn + 1 番目の反復です。代わりに、数値計算法では、他の意味を持つ下付き文字と干渉しないように、括弧内の上付き文字がよく使用されます (たとえば、x ^{( n +1)} = f ( x ^{( n )} )。) 関数fが連続的に微分可能である場合、収束するための十分な条件は、導関数のスペクトル半径が固定点の近傍で厳密に 1 によって制限されることです。この条件が固定点で成り立つ場合、十分に小さい近傍（吸引域）が存在する必要があります。^[要出典]

線形システム

線形方程式のシステムの場合、反復法の 2 つの主なクラスは、定常反復法と、より一般的なクリロフ部分空間法です。

定常反復法

導入

定常反復法は、元の演算子を近似する演算子を用いて線形システムを解き、結果（残差）の誤差の測定値に基づいて「補正方程式」を作成し、このプロセスを繰り返します。これらの手法は導出、実装、解析が簡単ですが、収束が保証されるのは限られた行列のクラスのみです。

意味

反復法は によって定義され 、与えられた線形システムに対して正確な解が によって誤差が定義 される。反復法はと なる 行列が存在するとき線形と呼ばれ 、この行列は反復行列と呼ばれる。与えられた反復行列を持つ反復法は、以下が成り立つとき 収束的と呼ばれる。$${\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.}$$

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

基本的な反復法は、行列を に 分割することで機能します。 ここで、行列は簡単に逆行列となるはずです。反復法は次のように定義されます。 または、これは等価です。 このことから、反復行列は次のように与えられます。 ${\displaystyle A}$ $${\displaystyle A=MN}$$ ${\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=IM^{-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\})}$$

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

クリロフ部分空間法

クリロフ部分空間法^[2]は、連続する行列のべき乗の列と初期残差の積（クリロフ列）を基底として用いる。解の近似値は、形成された部分空間上で残差を最小化することで形成される。このクラスの典型的な手法は共役勾配法（CG）であり、これはシステム行列が対称正定値行列であると仮定する。対称行列（および場合によっては不定値行列）の場合、最小残差法（MINRES）が用いられる。非対称行列の場合、一般化最小残差法（GMRES）や共役勾配法（BiCG）などの手法が導出されている。 ${\displaystyle A}$ ${\displaystyle A}$

クリロフ部分空間法の収束

これらの手法は基底となるため、N回の反復で収束することは明らかである。ここでNはシステムサイズである。しかし、丸め誤差が存在する場合、この記述は成り立たない。さらに、実際にはNは非常に大きくなる可能性があり、反復プロセスははるかに早く十分な精度に達する。これらの手法の解析は困難であり、作用素のスペクトルの複雑な関数に依存する。 ^[要出典]

前処理

定常反復法に現れる近似演算子は、GMRESなどのクリロフ部分空間法にも組み込むことができます（あるいは、前処理付きクリロフ法は定常反復法の加速法と考えることもできます）。この場合、前処理付きクリロフ法は元の演算子を、おそらくより条件の良い演算子に変換するものとなります。前処理演算子の構築は、広範な研究分野です。^[要出典]

逐次近似法

逐次近似に関連する数学的手法には以下のものがあります。

• バビロニア法、数値の平方根を求める方法^[3]
• 固定小数点反復法^[4]
• 関数の零点を見つける手段:
  • ハレー法
  • ニュートン法
• 微分方程式は重要です:
  • ピカール・リンデレフの定理、微分方程式の解の存在に関する定理
  • ルンゲ・クッタ法、微分方程式の数値解法

歴史

ジャムシード・アル＝カーシーは『弦と正弦論』の中で、反復法を用いて1°とπの正弦を高精度に計算しました。線形連立方程式を解くための初期の反復法は、ガウスが弟子に宛てた手紙の中に見受けられます。彼は、残差が最大となる成分を繰り返し解くことで、4行4列の連立方程式を解くことを提案しました^[要出典]。

定常反復法の理論は、1950年代に始まったDM Youngの研究によって確固たる地位を築きました。共役勾配法も1950年代に発明され、Cornelius Lanczos、Magnus Hestenes、Eduard Stiefelによってそれぞれ独立に発展しましたが、その性質と適用性は当時誤解されていました。共役性に基づく手法が偏微分方程式、特に楕円型方程式に非常に有効であることが認識されたのは、1970年代になってからでした。 ^[要出典]

参照

• 数学ポータル

• 閉じた形式の表現
• 反復的な改良
• カツマルツ法
• 非線形最小二乗法
• 数値解析
• 根探索アルゴリズム

参考文献

1. Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). 「CFDアプリケーションのためのKrylov部分空間のリサイクルと新しいハイブリッドリサイクルソルバー」. Journal of Computational Physics . 303 : 222. arXiv : 1501.03358 . Bibcode :2015JCoPh.303..222A. doi :10.1016/j.jcp.2015.09.040.
2. Charles George BroydenとMaria Terasa Vespucci：線形代数システムのためのKrylovソルバー：Krylovソルバー、Elsevier、ISBN 0-444-51474-0、（2004年）。
3. 「バビロニア数学」バビロニア数学. 2000年12月1日.
4. day, Mahlon (1960年11月2日).コンパクト凸集合の不動点定理. Mahlon M day.

外部リンク

• 線形システムの解法テンプレート
• Y. Saad: 疎線形システムのための反復法、第 1 版、PWS 1996