数値安定性

アルゴリズムが誤差をどれだけ増幅するか。

条件数が問題の性質であるのに対し、 安定性はアルゴリズムの性質。両者は独立に議論される。

後退安定性#

計算結果 $\hat{y}$ が、 わずかに摂動した入力に対する厳密解になっていること。

$$\hat{y}=f(x+\delta x),\frac{\Vert \delta x\Vert }{\Vert x\Vert }=𝒪(\epsilon )$$

「入力がほんの少し違っていたら、これが正解だった」と言える状態。 数値線形代数で最も重要な品質基準。

誤差の全体像#

$$\text{結果の誤差}\lesssim \underset{\text{問題}}{\underbrace{\kappa }}\times \underset{\text{手法}}{\underbrace{{\epsilon }_{\text{アルゴリズム}}}}$$

• 悪条件な問題は、安定なアルゴリズムでも精度が出ない
• 良条件な問題でも、不安定なアルゴリズムなら壊れる

両方を確かめる必要がある。

安定・不安定の例#

不安定	安定な代替
ピボットなし LU 分解	部分ピボット選択つき LU
古典グラム・シュミット	修正グラム・シュミット、Householder QR
特性方程式で固有値	QR 法
$𝔼[X^2]-{\mu }^2$ で分散	Welford の逐次法

直交変換は条件数が 1 なので誤差を増幅しない。 安定なアルゴリズムが直交変換で組まれているのはこの理由。

参考文献#

• Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms, 2nd ed. SIAM, 2002. https://doi.org/10.1137/1.9780898718027
• Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574