数値的安定性

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数値的安定性(すうちてきあんていせい、: numerical stability)は、数値解析におけるアルゴリズムの望ましい属性の1つ。「安定性」の正確な定義は文脈に依存するが、基本的にはアルゴリズムの正確性に関連する。

ある計算を実施する方法がいくつか存在することがあり、それらは理想的な実数や複素数では代数学的に等価だが、デジタルコンピュータで実行すると結果に差異が生じる。ある計算方法は途中で生じる誤差を弱めるし、別の計算方法は誤差を拡大させる。誤差を拡大させない計算方法は「数値的に安定」であるという。数値解析では、堅牢なアルゴリズム、すなわち数値的安定性のよいアルゴリズムを選択することが重要である。

[編集]

不安定なアルゴリズムの例として、100個の数値の配列を加算するタスクを考える。話を単純化するため、使用するコンピュータは精度が2桁しかないとする(例えば、100以上の値を表すと、100、110、120 などと10単位でしか表せない)。

最も単純な方法は、次のような擬似コードになる。

 sum = 0
 for i = 1 to 100 do
   sum = sum + a[i]
 end

見たところ問題はなさそうだが、配列の最初の要素が 1.0 で、他の99個の要素は全て0.01だったとしよう。数学の問題として考えれば、答は1.99になるはずである。しかし、精度が2桁しかないコンピュータでは、まず 1.0 が sum に加算されると、それに 0.01 を加算しても精度未満なので何の影響も与えない。従って最終的に得られる答は 1.0 となる。これではあまりよい近似とは言えない。

安定なアルゴリズムは、まず配列を要素の絶対値の昇順になるようにソートし、それから上記のコードを実行すればよい。そうするとゼロに近い小さい値を先に加算することになる。このようにすると、0.01 が先に加算されるので、0.99 となり、それに 1.0 を加算するので、結果は丸められて 2.0 になるだろう。近似としてはこちらの方がよい。

前方安定性、後方安定性、混合安定性[編集]

安定性の定式化方法にはいくつかの種類がある。以下に述べる前方 (forward)、後方 (backward)、混合 (mixed) 安定性の定義は数値線形代数でよく使う。

前方誤差 Δy と後方誤差 Δx、正確な解の写像 f と数値解 f* の関係を示した図

数値アルゴリズムで解くべき問題を関数 f でデータ x から解 y への写像を得るという形にモデル化する。実際にアルゴリズムで得られる解を y* とすると、一般に真の解 y とは逸脱している。誤差の主な原因は丸め誤差や離散化誤差、モデルの誤差などである。アルゴリズムの「前方誤差」とは、結果と真の解の差、すなわち Δy = y* − y である。「後方誤差」とは、f(x + Δx) = y* となるような最小の Δx である。つまり後方誤差とは、我々が実際にはどういう問題を解いたのかを知らせてくれる値である。前方誤差と後方誤差は条件数で関連付けられている。前方誤差は、条件数のオーダーと後方誤差のオーダーを掛けたものを上限とする。

多くの場合、絶対誤差 Δx よりも、以下のような「相対誤差」を考慮するほうが自然である。

 \frac{|\Delta x|}{|x|}

アルゴリズムが「後方安定」であるとは、あらゆる入力 x について後方誤差が小さいことを意味する。もちろん「小さい」は相対的な言葉であり、その定義は文脈に依存する。多くの場合、マシンイプシロンと同程度か若干大きい程度の order of magnitude の誤差が望ましいとされる。

混合誤差は、前方誤差と後方誤差の概念を組み合わせたものである。

数値的安定性の定義としてより一般的に使われるのは「混合誤差」であり、前方誤差と後方誤差を組み合わせたものである。この場合、アルゴリズムが安定であるのは、近い問題の近似解を得るものである場合となる。すなわち、Δxf(x + Δx) − y* が共に小さいような Δx が存在する場合である。従って、後方安定なアルゴリズムは常に安定と言える。

アルゴリズムが「前方安定」であるとは、前方誤差をその問題の条件数で割った値が小さい場合である。つまり、何らかの後方安定アルゴリズムと同程度の大きさの前方誤差の場合を前方安定と呼ぶ。

数値微分方程式での安定性[編集]

上述の定義は、入力数値の離散化誤差を無視しても構わない状況に適したものである。微分方程式を数値的に解く場合はそうはいかず、数値的安定性の定義も異なる。

常微分方程式を数値的に解く場合、様々な数値的安定性の概念があるが、その1つがA-安定性である。それらはリアプノフ安定のような力学系の安定性の概念と関連している。硬い方程式を解く場合、特に安定な手法を使うことが重要となる。

偏微分方程式を数値的に解く場合は、安定性の定義はまた異なる。偏微分方程式を解くアルゴリズムは、ある時点の数値解がステップサイズをゼロに漸近させたときに大きく変化しないことを安定だという事もある。ラックスの等価定理によれば、アルゴリズムが一貫していて(ここでの意味で)安定していれば、そのアルゴリズムは収束する。安定性は数値拡散 (numerical diffusion) などで達成されることもある。数値的拡散とは、計算時の丸め誤差などが蓄積されない性質を言う。 また単純に解の任意のステップに対して、有界ならば、安定ともいう。

参考文献[編集]

  • Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society of Industrial and Applied Mathematics, Philadelphia, 1996. ISBN 0-89871-355-2.