条件、安定性、誤差解析

条件

まず問題の条件について見て行こう。ある問題の条件(condition)とはデータの摂動に対し問題がどう反応するかという感度(sensitivity)に関係したものである。データの小さな変動によって解が比較的大きく変化する場合には、問題はill-conditionedであると言う。そうでない場合はwell-conditionedであると言う。条件とは問題の感度に関する話であり、問題解法の手法とは無関係である点に注意する必要がある。ここではill-conditionedな問題の例をいくつか示すことにする。

Example 4.1 （3次方程式）

厳密解を持つ3次方程式 MATH について考える。今、 $x^{3}$ の係数をわずかに変化させ、 MATH とすると、その根はとなる。従って2つの根 $x_{2},x_{3}$ に対する変動は係数の変化よりもはるかに大きい。一方、3次方程式 MATH の解はとなり、重根は2つの共役複素数に分かれることになる（虚数部の値もそれなりに大きい）。

この場合、根 $x_{2},x_{3}$ はill-conditionedである。ただしこのデータからだけだと、 $x_{1}$ の条件について何かを演繹することはできない。図3はこれら3本の3次多項式をプロットしたものである。

図3 3次方程式の例

Example 4.2 （固有値問題）

行列 MATH は固有値を持つが、それにわずかな摂動を加えた行列 MATH の固有値はとなる。

Example 4.3 （積分）

MATH

であればであるが、のときには $I\approx-220$ となる。の場合の関数の形状を図4に示す。ただし縦軸のスケールファクタが $10^{4}$ である点に注意。このため関数式のわずかな変化によって定積分の値（曲線下の面積）は大きく変化することになる。

図4 積分の例

Example 4.4 （連立1次方程式）

で与えられる連立1次方程式

(5)

は $x_{1}=x_{2}=1$ という解を有するが、

の解は

となる。数式 (5)で表される2本の直線をプロットしたものが図5であるが、この解像度では2本を識別することはできない。

図5 連立1次方程式の例

問題がill-conditionedであるか否かを決定できるようにするためには、その条件に関し何らかの尺度があることが望ましい。そのような尺度が得られる2つの簡単なケースを紹介すると共に、3番目の例については結果を引用する。第1のケースについては1変数関数の評価に関する条件数(condition number)を導出する [Higham, 2002, Section 1.6]。

今、関数をとし、は2回微分可能で $f(x)\neq 0$ であるとする。またとする。このとき平均値の定理より MATH

これより MATH

このとき MATH はの条件数(condition number)と呼ばれる。なぜなら MATH だからである。従って $\kappa(x)$ が大きな値の場合には問題はill-conditionedとなる。すなわちのわずかな変動が解の大きな変動をもたらすことになる。

Example 4.5

$y=f(x)=\cos x$ とする。このとき MATH となるため、 $\cos x$ は $\tan x$ の漸近線に近い部分、例えばが $\pi/2$ (Note1)に近い部分で最も鋭敏に反応することがわかる。例えばとすると MATH となる。これはの非常に良い推定値であると言える。

第2の例として連立1次方程式の条件数について考えてみる。今、 $\QTR{bs}{\hat{x}}$ を摂動を加えた方程式 MATH の解とするとき、 MATH

これより

(6)

このとき MATH を方程式の解に関するの条件数、あるいは逆行列操作(matrix inversion)に関するの条件数と呼ぶ。 $I=AA^{-1}$ であるから、となるような任意のノルム(norm)に対して $1\leq\kappa(A)$ が言える。ここに等号は $1,2,\infty$ ノルムの場合に成り立つ。が特異(singular)である場合には $\kappa(A)=\infty$ となる。

Example 4.6 （行列の条件）

Example 4.4の行列の場合、 MATH 及び MATH より MATH

従っての精度が4桁程度である場合には解の精度が全く期待できないことがわかる。

条件数という用語は連立1次方程式との関連においてTuringによって初めて用いられた [Turing, 1948]。直交、またはユニタリ行列の場合には $\kappa_{2}(Q)=1$ となる点に注意。

第3の例としてここでは多項式の根の感度(sensitivity)に関する結果を引用することにする。今、多項式を MATH とし、 $\alpha$ をの単根であるとする。このとき $f(\alpha)=0$ であるが、である。次にを摂動を加えた多項式を MATH とし、その根をとする（ $p(\hat{\alpha})=0$ ）。このとき [Wilkinson, 1963, Section 7, Chapter 2] によれば MATH であることが示される。Wilkinsonはさらに $\alpha$ が重根である場合に MATH という式を導いている。

Example 4.7 （3次方程式の根の条件）

Example 4.1の3次方程式の根 $\alpha=x_{1}=1$ に対し、とすると MATH より MATH

従ってこの根は $x^{3}$ の係数値の摂動に対し大変well-conditionedであると言える。一方、重根 $\alpha=10$ については MATH より MATH

従って $\epsilon$ の摂動によって根に対してはかなり大きな摂動が加わることがわかる。 $\epsilon$ は特に小さいというわけではないので、 $\delta$ の推定値は特別に正確とは言えないが、ill-conditioningに関する警告としては十分である。

Higham [2002, Section 25.4] には一般的な非線形方程式の根の感度に関する結果が示されている。

スケーリングが適切でない（しばしば計測単位の選択のまずさから起る）というだけで問題がill-conditionedとなることがある。アルゴリズム、あるいはその実装によってはスケーリングの影響を受けない、あるいは自動スケーリングを試みるものもあるが、そうでない場合には、スケーリングの選択が良い結果を得る上で重要な要因となることがある。スケーリングが不適切な問題は容易に本質的にill-conditionedな問題に変貌し得る。

Example 4.8 （スケーリングが不適切な行列）

行列を MATH とするときとなるため、はill-conditionedである。しかしに対し次のようなスケーリングを施した場合、 MATH に対しては $\kappa_{2}(B)=3$ となるため、はwell-conditionedであると言える。一方を使い、として平面の回転を行うと MATH となる。ここでは直交行列であるため、従ってはと同様ill-conditionedとなる。しかしこの場合にはスケーリングによって事態は改善されない。は近似的に MATH と書けるが、これは特異行列である。従っては本質的にill-conditionedである。倍精度のIEEE arithmeticではこれがの浮動小数表現となる。

LAPACKルーチンの多くがスケーリングを行ったり、連立1次方程式の場合には行列を平衡化(equilibrate)させたり [Anderson et al., 1999, Sections 2.4.1 and 4.4.1], [Higham, 2002, Sections 7.3 and 9.8]、固有値問題の場合にはバランスさせたり [Anderson et al., 1999, Sections 4.8.1.2 and 4.11.1.2] するオプションを用意している。