📂アルゴリズム

数値アルゴリズムにおける安定性

定義 ¹

相対誤差と近さ

1. 与えられた浮動小数点体系で動作するアルゴリズムがデータ$a$を入力として受け取り、計算された解^{computed solution}$\bar{w}$を出力するとしよう。このとき、正確な解^{exact solution}$w$に対して$\left| w - \bar{w} \right| / \left| w \right|$を相対誤差^{relative error}という。
2. マシンイプシロン$\epsilon$に対して、相対誤差が次のようにそれほど大きくない定数$c$と$\epsilon$の積である$c \epsilon$より小さいか等しければ、$\bar{w}$は$w$に近い^closeという。
   $$ {\frac{ \left| w - \bar{w} \right| }{ \left| w \right| }} \le c \epsilon $$

前方安定性

3. 計算された解が正確な解に近ければ、アルゴリズムが前方安定的^{forward stable}であるという。

後方安定性

4. データ$a$の計算された解$\bar{w}$が、$a$に近い$\tilde{a}$に対する正確な解であれば、アルゴリズムが後方安定的^{backward stable}であるという。

数値行列代数における後方安定性

5. ある行列のクラスを$\mathcal{A}$としよう。各々の$A \in \mathcal{A}$とベクトル$\mathbf{b}$に対する線形システム$A \mathbf{x} = \mathbf{b}$を解くための数値的アルゴリズムは、$\bar{A} \in \mathcal{A}$と$\bar{\mathbf{b}}$が$A \in \mathcal{A}$と$\mathbf{b}$に近いとするとき$A \mathbf{x} = \mathbf{b}$の計算された解である$\bar{\mathbf{x}}$が$\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$を満たせば後方安定的であるという。

説明

いわゆる$\tilde{a}$は少し摂動が加えられた^{slightly perturbed}といい、アルゴリズムが後方安定的であるという言葉はすなわちデータに少しの変化があっても安定的に解を求めることができるという意味になる。この説明が少し難しければ、むしろ数値行列代数の後方安定性として理解するのがよく、$\bar{\mathbf{x}}$は$A$と$\mathbf{b}$から計算されたにもかかわらず$\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$の正確な解となっている。ここで後方^backwardという表現は単に解が似ているかではなく、後ろに戻って元の問題の解として正しく機能するかまで考慮したという意味になる。

普遍的な後方安定性と数値線形代数の後方安定性で異なる点は$A \in \mathcal{A}$のように行列のクラスを考えるということである。言葉は少し難しいが、数値行列代数的なアルゴリズムが可逆行列に対するものなのか、正定値行列に対するものなのかなどについての条件は一貫して守らなければならないという程度にだけ受け取ればよい。このようにクラスに対する制限を置かなければ、そもそもアルゴリズムが要求する条件を破っておきながら後方安定的ではないと言い張ることができる。