条件数

入力の誤差が、出力の誤差にどれだけ拡大されるか。

$$\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert =\frac{{\sigma }_{\max }}{{\sigma }_{\min }}$$

（2-ノルムの場合。$\sigma$ は特異値。）

何を教えるか#

$Ax=b$ を解くとき、$b$ の相対誤差 $\delta$ は 解の相対誤差 $\kappa \delta$ に拡大されうる。

$\kappa ={10}^k$ なら、有効桁が $k$ 桁失われると考えてよい。 float64（16 桁）で $\kappa ={10}^{12}$ なら、 残る有効桁は 4 桁程度。

問題の性質であって手法の性質ではない#

条件数が大きい（悪条件）とき、 どんなに優れたアルゴリズムを使っても精度は出ない。 問題そのものが誤差に敏感だから。

これに対し安定性は アルゴリズム側の性質で、両者は独立。

最適化との関係#

ヘッセ行列の条件数が大きいと、 等高線が細長い楕円になる。

• 勾配降下法がジグザグして進まない
• 収束速度が $\kappa$ に依存する

Newton 法や CMA-ES が強いのは、 実質的に座標変換して条件数を 1 に近づけているから。

参考文献#

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