数値的安定性

数値的安定性（すうちてきあんていせい、英: 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 の誤差が望ましいとされる。

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

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

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

この区別は、問題そのものの感度とアルゴリズムの安定性を分けて考えるために重要であり、条件数は入力データの小さな相対変化が厳密解にどの程度増幅されるかを表す問題側の量であって、丸め誤差を含む計算手順の良し悪しとは別に定まる。したがって、後方安定なアルゴリズムであっても、対象問題の条件数が大きければ得られる解の前方誤差は大きくなりうる一方、条件数が小さい問題では、後方誤差を機械精度程度に抑えるアルゴリズムは前方誤差の面でもよい結果を与えると期待される。

この観点からは、「安定な方法」と「よく条件づけられた問題」は同義ではない。数値線形代数では、ガウスの消去法、QR分解、特異値分解などの各手法について、丸め誤差をどのような近い問題の厳密解として解釈できるかを調べる後方誤差解析が用いられる。また、同じ数学的問題を解く式でも、桁落ちやオーバーフローを避けるように変形した実装は、浮動小数点演算上の誤差増幅を抑えられる場合があるため、数値的安定性は単なる収束性や計算量とは異なる評価軸である。

実際の算法選択では、まず問題の条件のよさを見積もり、そのうえで安定性が解析されている方法を選ぶ、という二段階の見方が用いられる。たとえば線形方程式の解法では、入力行列が悪条件であることによる精度低下と、消去過程や直交化過程で発生する丸め誤差の増幅とは区別して評価される。このため、数値的安定性の記述では、抽象的な「誤差が小さい」という説明だけでなく、前方誤差、後方誤差、条件数、機械精度の関係を明示することが、どの不正確さが問題由来で、どの不正確さがアルゴリズム由来であるかを理解する手掛かりになる。

この区別は、計算結果を診断する際にも役立つ。残差や後方誤差が小さいのに前方誤差が大きい場合は、算法だけでなく問題の条件の悪さが主因である可能性がある一方、よく条件づけられた問題で後方誤差が大きい場合は、計算過程での丸め誤差の増幅や実装上の不安定性を疑う根拠になる。そのため、数値的安定性は「正しい答に近いか」だけでなく、「近い入力データに対する厳密解として説明できるか」という形で評価され、実際の計算結果の信頼性を条件数と合わせて判断する枠組みを与える。これにより、精度低下を入力データの性質、問題設定、計算手順のいずれに帰すべきかを整理しやすくなる。

数値微分方程式での安定性

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

常微分方程式を数値的に解く場合、様々な数値的安定性の概念があるが、その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.
• Wolfgang Hackbusch: The Concept of Stability in Numerical Mathematics, Springer (2017).