📂アルゴリズム

数値アルゴリズムにおける条件数と好条件・悪条件

定義

条件数 ¹

与えられた入力^inputとしての問題^problem $a$に対して、アルゴリズムが計算結果として解^solution $w$を出力^outputするとしよう。データと解はノルム $\left\| \cdot \right\|$に対して大きさを測ることができ、$\hat{a}$はある $\varepsilon > 0$に対して $\left| \hat{a} - a \right| \le \varepsilon \left| a \right|$を満たす $a$の近似値^{approximation}であるとしよう。$\hat{a}$に対する解が $\hat{w}$であるとき、次のように相対誤差と $\varepsilon$の比にリミット・スープリマムを取った値を条件数^{condition number} $\kappa = \kappa (a)$という。 $$ \kappa(a) = \limsup_{\varepsilon \to 0} \left\{ \frac{\left\| \hat{w} - w \right\|}{\varepsilon \left\| w \right\|} : \left\| \hat{a} - a \right\| \le \varepsilon \left\| a \right\| \right\} $$

好条件と悪条件

条件数 $\kappa$が大きければ悪条件^{ill-conditioned}といい、大きくなければ好条件^{well-conditioned}という。

説明

厳密な意味において、条件数は簡単に言えばデータが真値に近づくにつれて誤差もうまく減っていくかどうかに対する尺度であるといえる。条件数が大きいということは、入力の誤差 $\varepsilon$が減るのに比べて誤差があまり減らないという意味になる。

一方で数学徒であれば、では条件数が大きい小さいという基準は何なのかが気になるだろうが、定義で明示していないことからわかるように、あえて具体的な数値の基準を提示したりはせず、問題ごとに異なるものとして考えなければならない。ある臨界点があって、ぎりぎり悪条件だとかいったことを扱うことはなく、悪条件であればまったく明確な悪条件を扱うのが一般的だからである。統計学では15を基準とすることもあるが、やはり広く使われているわけではない。

関連リンク

• 数値行列代数における条件数