修正リチャードソン反復法

修正リチャードソン反復法は、線形方程式系を解く反復法です。リチャードソン反復法は、ルイス・フライ・リチャードソンが1910 年の論文で提案しました。ヤコビ法やガウス・ザイデル法に似ています。

行列で表現される一連の線形方程式の解を求める。

${\displaystyle Ax=b.\,}$

リチャードソン反復は

${\displaystyle x^{(k+1)}=x^{(k)}+\omega \left(b-Ax^{(k)}\right),}$

ここで、はシーケンスが収束するように選択する必要があるスカラーパラメータです。 ${\displaystyle \omega}$${\displaystyle x^{(k)}}$

この方法が正しい固定点を持つことは容易に分かります。なぜなら、この方法が収束する場合、および はの解を近似する必要があるからです。 ${\displaystyle x^{(k+1)}\approx x^{(k)}}$${\displaystyle x^{(k)}}$${\displaystyle Ax=b}$

正確な解を減算し、誤差の表記を導入すると、誤差の等式が得られます。 ${\displaystyle x}$${\displaystyle e^{(k)}=x^{(k)}-x}$

${\displaystyle e^{(k+1)}=e^{(k)}-\omega Ae^{(k)}=(I-\omega A)e^{(k)}。}$

したがって、

${\displaystyle \|e^{(k+1)}\|=\|(I-\omega A)e^{(k)}\|\leq \|I-\omega A\|\|e^{(k)}\|,}$

任意のベクトルノルムとそれに対応する誘導行列ノルムに対して、 となります。したがって、 の場合、この方法は収束します。 ${\displaystyle \|I-\オメガ A\|<1}$

が対称正定値で、が の固有値であると仮定します。すべての固有値 に対して誤差は に収束します。たとえば、すべての固有値が正である場合、 が となるように選択されれば、これが保証されます。すべての を最小化する最適な選択は であり、これは最も単純なチェビシェフ反復を与えます。この最適な選択により、スペクトル半径 が得られます。 ${\displaystyle A}$${\displaystyle (\lambda _{j})_{j}}$${\displaystyle A}$${\displaystyle 0}$${\displaystyle |1-\omega \lambda _{j}|<1}$${\displaystyle \lambda_{j}}$${\displaystyle \omega}$${\displaystyle 0<\omega <\omega _{\text{max}}\,,\ \omega _{\text{max}}:=2/\lambda _{\text{max}}(A)}$${\displaystyle |1-\omega \lambda _{j}|}$${\displaystyle \omega _{\text{opt}}:=2/(\lambda _{\text{min}}(A)+\lambda _{\text{max}}(A))}$

${\displaystyle \min _{\omega \in (0,\omega _{\text{max}})}\rho (I-\omega A)=\rho (I-\omega _{\text{opt}}A)=1-{\frac {2}{\kappa (A)+1}}\,,}$

ここで は条件数です。 ${\displaystyle \kappa (A)}$

正の固有値と負の固有値の両方がある場合、初期誤差が対応する固有ベクトルにゼロ以外の成分を持つと、この方法は発散します。 ${\displaystyle \omega}$${\displaystyle e^{(0)}}$

関数 を最小化することを検討する。これは凸関数なので、最適性のための十分条件は勾配がゼロ（）であることであり、次の式が得られる。 ${\displaystyle F(x)={\frac {1}{2}}\|{\tilde {A}}x-{\tilde {b}}\|_{2}^{2}}$${\displaystyle \nabla F(x)=0}$

${\displaystyle {\tilde {A}}^{T}{\tilde {A}}x={\tilde {A}}^{T}{\tilde {b}}.}$

と を定義します。 Aの形式により、これは半正定値行列であり、負の固有値を持ちません。 ${\displaystyle A={\tilde {A}}^{T}{\tilde {A}}}$${\displaystyle b={\tilde {A}}^{T}{\tilde {b}}}$

勾配降下法のステップは

${\displaystyle x^{(k+1)}=x^{(k)}-t\nabla F(x^{(k)})=x^{(k)}-t(Ax^{(k)}-b)}$

これは、 を作成することにより、リチャードソン反復と同等になります。 ${\displaystyle t=\omega }$

• リチャードソン外挿

• リチャードソン、LF (1910)。「微分方程式を含む物理的問題の有限差分による近似算術解法、石造ダムの応力への応用」。王立協会哲学論文集 A。210 : 307–357。doi : 10.1098/rsta.1911.0009。JSTOR 90994  。
• レベデフ、ヴィアチェスラフ・イワノビッチ(2001) [1994]、「チェビシェフ反復法」、ミヒール・ハゼウィンケル(編)、数学百科事典、EMS プレス、ISBN 1-4020-0609-8、 2010年5月25日取得