条件数
条件数（じょうけんすう、英: condition number）は、問題のコンピュータでの数値解析しやすさの尺度であり、その問題がどれだけ数値解析に適しているかを表す。条件数が小さい問題は「良条件 (well-conditioned)」であり、条件数が大きい問題は「悪条件 (ill-conditioned)」である。
Contents
行列の条件数
たとえば [math]Ax = b[/math] という方程式の条件数は、[math]x[/math] を近似的に求める際の不正確さの上限を与える。なお、これには丸め誤差の影響は考慮しない。条件数は行列の属性であって、計算に使うシステムの浮動小数点数の精度やアルゴリズムとは無関係である。この場合（非常に大まかに言って）、[math]b[/math] の変化によって解である [math]x[/math] が変化する率が条件数である。従って、条件数が大きければ [math]b[/math] の小さな誤差も [math]x[/math] の大きな誤差となって現れる。一方、条件数が小さければ、[math]x[/math] における誤差は [math]b[/math] における誤差より大きくなることはない。
より正確に条件数を定義すると、[math]x[/math] の相対誤差を [math]b[/math] の相対誤差で割った最大比率である。
[math]b[/math] の誤差を [math]e[/math] とする。すると解 [math] A^{-1} b[/math] の誤差は [math]A^{-1} e[/math] となる。解の相対誤差と [math]b[/math] の相対誤差の比率は、次のようになる。
[math]\frac{\Vert A^{-1} e\Vert / \Vert A^{-1} b\Vert}{\Vert e\Vert / \Vert b\Vert}[/math]
これは容易に次のように書き換えられる。
[math](\Vert A^{-1} e\Vert / \Vert e\Vert) \cdot (\Vert b\Vert / \Vert A^{-1} b\Vert)[/math]
（[math]b[/math] と [math]e[/math] がゼロでないとき）その最大値は明らかに2つの作用素ノルムの積となる。
[math]\kappa (A) = \Vert A^{-1}\Vert \cdot \Vert A\Vert[/math]
同様の定義は、任意の行列ノルムに当てはまる。この数は数値線型代数学にはよく使われるので、行列の条件数 (condition number of a matrix) と名づけられている。
もちろん、この定義はノルムの選択に依存している。
- [math]\|\cdot\|[/math] が [math] l_2[/math] ノルムなら、
[math]\kappa(A) = \frac{\sigma_\mathrm{max} (A)}{\sigma_\mathrm{min}(A)}[/math] であり、ここで [math]\sigma_\mathrm{max}(A)[/math] は [math]A[/math] の最大特異値、[math]\sigma_\mathrm{min}(A)[/math] は最小特異値である。したがって、 - [math]\|\cdot\|[/math] が [math] l_{\infty}[/math] ノルムで、[math]A[/math] が三角行列で特異値を持たない（すなわち、[math] a_{ii} \ne 0 \; \forall i[/math]）なら
[math]\kappa(A) \geq \frac{\max_i(|a_{ii}|)}{\min_i(|a_{ii}|)}[/math]
それ以外の条件数
特異値分解の条件数、多項式の解を求める際の条件数、固有値の条件数など、様々な問題について条件数を定義できる。
一般に数値問題が良設定なら、それを関数 [math]f[/math] で表すことができ、[math]m[/math]-タプルの実数 [math]x[/math] から [math]n[/math]-タプルの実数 [math]f(x)[/math] への写像となる。
するとその条件数は、問題の定義域における解の相対誤差とデータの相対誤差の比の最大値と定義される。
[math]\max \left\{ \left| \frac{f(x) - f(x^*)}{f(x)} \right| \left/ \left| \frac{x - x^*}{x} \right| \right. : |x - x^*| \lt \epsilon \right\}[/math]
ここで [math]\epsilon[/math] は問題のデータの変化における何らかの適度に小さい値である。
[math]f[/math] が可微分であれば、次のように近似できる。
[math]\left| \frac{ f'(x) }{ f(x) } \right| \cdot \left| x \right| [/math]
関連項目
外部リンク
- Condition Number of a Matrix at Holistic Numerical Methods Institute
- Matrix condition number on PlanetMath