反復法

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

勾配降下法、山登り法、ニュートン法、またはBFGSのような準ニュートン法などの特定の反復法の終了基準を伴う特定の実装は、反復法または逐次近似法のアルゴリズムです。反復法は、対応するシーケンスが与えられた初期近似に対して収束する場合に収束すると呼ばれます。反復法の数学的に厳密な収束分析が通常実行されますが、ヒューリスティックベースの反復法も一般的です。

対照的に、直接法は有限の一連の演算によって問題を解こうとする。丸め誤差がない場合、直接法は正確な解をもたらす（例えば、ガウス消去法によって線形方程式を解く）。反復法は、非線形方程式の唯一の選択肢となることが多い。しかし、反復法は、多くの変数（時には数百万のオーダー）を含む線形問題でも有用であることが多い。そのような問題では、直接法は最高の計算能力をもってしても法外な費用がかかり（場合によっては不可能になる）^、${\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 + ₁番目_の 反復です。代わりに_、数値計算法では_、他の意味を持つ下付き文字と干渉しないように、括弧内の上付き文字がよく使用されます。(たとえば、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\rightarrow \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}+b\,,\quad k\geq 0\,.}$

このことから、反復行列は次のように与えられる。

${\displaystyle C=IM^{-1}A=M^{-1}N\,.}$

定常反復法の基本的な例としては、次のような 行列の分割が用いられる。${\displaystyle A}$

${\displaystyle A=D+L+U\,,\quad D:={\text{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 (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})}$

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

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

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

定常反復法に現れる近似演算子は、 GMRESなどのクリロフ部分空間法にも組み込むことができます(あるいは、前処理付きクリロフ法は定常反復法の加速法と見なすことができます)。この場合、近似演算子は元の演算子を、おそらくより条件の良い演算子に変換するものになります。前処理の構成は、大規模な研究分野です。

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

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

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

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

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

ウィキメディア・コモンズには、反復法に関連するメディアがあります。

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