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

Iterative method used to solve a linear system of equations

修正リチャードソン反復法は、連立一次方程式を解くための反復法です。リチャードソン反復法は、ルイス・フライ・リチャードソンが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)}=\left(I-\omega A\right)e^{(k)}.}$$

したがって、

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

任意のベクトルノルムとそれに対応する誘導行列ノルムに対して、 となる。したがって、 であれば、この方法は収束する。 ${\displaystyle \|I-\omega 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 \left(I-\omega A\right)=\rho \left(I-\omega _{\text{opt}}A\right)=1-{\frac {2}{\kappa (A)+1}}\,,}$$ ${\displaystyle \kappa (A)}$

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

同等性勾配降下法

関数 を最小化することを考えてみましょう。これは凸関数なので、最適性を得るための十分条件は勾配がゼロ（）であることであり、以下の式が得られます。 ${\textstyle F(x)={\frac {1}{2}}\left\|{\tilde {A}}x-{\tilde {b}}\right\|_{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\left(Ax^{(k)}-b\right)}$$ ${\displaystyle t=\omega }$

参照

• リチャードソン外挿

参考文献

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Modified_Richardson_iteration&oldid=1295336535"