ストーン法

数値解析において、ストーン法（SIP法とも呼ばれる）は、疎な線形方程式系を解くアルゴリズムです。この法では、正確なLU分解を近似する不完全LU分解を用いて、問題の反復解を得ます。この法は、1968年に提案したハロルド・S・ストーンにちなんで名付けられました。

LU分解は、汎用的な線形方程式ソルバーとして優れています。最大の欠点は、係数行列が疎行列であるという利点を活かせないことです。疎行列のLU分解は通常は疎行列ではないため、大規模な連立方程式の場合、LU分解には膨大な量のメモリと演算処理が必要になることがあります。

前処理付き反復法では、前処理行列Mが係数行列Aの良い近似値であれば収束が速くなります。このことから、反復行列MとしてAの近似LU分解を用いるという考えが生まれます。

不完全下上分解法の一種は、1968年にストーンによって提案された。この方法は偏微分方程式の離散化から生じる方程式系のために設計されており、 2次元空間における楕円型偏微分方程式を有限差分法で解く際に得られる五角形方程式系に初めて用いられた。LU^{近似分解は、元}の行列と同じ五角形形式（Lに3つの対角要素、 Uに3つの対角要素）において、行列の各行の5つの未知数に対する7つの可能な方程式のうち最も一致^するものとして検討された[説明が必要]。

アルゴリズム

ストーン法は、
    線形システムA x = bに対して、行列 A の
    不完全LU分解を計算するものです。A 
       x = ( M - N )x = ( LU - N )x = b 
       M x (k+1) = N x (k) + b 、|| M || >> || N || 
       M x (k+1) = LU x (k+1) = c (k) 
       LU x (k) = L ( U x (k+1) ) = L y (k) = c (k)
    推測する
       k = 0, x (k) 
       r (k) =b - A x (k)
    であるが、 ( ||r (k) || 2 ≥ ε )となる。
       新しい右側を評価する
          c (k) = N x (k) + b前進代入により
          L y (k) = c (k)
       を解きますy (k) = L −1 c (k)後退代入によりU x (k+1) = y (k)
       を解きますx
           ( k+1) = U −1 y (k)
    終了

脚注

参考文献

• ストーン, HL (1968). 「多次元偏微分方程式の暗黙近似の反復解法」. SIAM Journal on Numerical Analysis . 5 (3): 530– 538. Bibcode :1968SJNA....5..530S. doi :10.1137/0705044. hdl : 10338.dmlcz/104038 .-原文記事
• Ferziger, JHおよび Peric, M. (2001).流体力学の計算手法. Springer-Verlag, ベルリン. ISBN 3-540-42074-6。
• Acosta, JM (2001).三次元数値流体力学問題のための数値アルゴリズム.カタルーニャ工科大学博士論文.
• この記事には、 GFDLライセンスの下にある CFD-Wiki の記事「Stone's_method」のテキストが組み込まれています。