数値解の品質トップへ

浮動小数誤差解析

浮動小数誤差解析(floating point error analysis)とは浮動小数演算機構を前提にした誤差解析のことを言う。それは個々の基本演算の結果として生じる相対誤差をベースにしている。ここではその考え方を紹介する意味で、浮動小数誤差解析に関する簡単な説明を行う。

を実数とするとき、の浮動小数値を表す記号として $\func{fl}(x)$ を用いることにする。基本的な仮定としては次がある。

(16)

ここには(1)に示される相対精度(unit roundoff)を意味する。もちろん

である。役に立つ別の表現としては次がある。

(17)

Example 5.1 （浮動小数）

ここでは10進4桁の演算を考える。このとき MATH である。今、とすると $\func{fl}(x)=1.414$ であり MATH となる。 $x=1.000499\ldots$ とすると $\func{fl}(x)=1.000$ であり MATH となる。 $x=1000.499\ldots$ とすると $\func{fl}(x)=1000$ であり、このときも MATH となる。

今、を浮動小数とすると、Wilkinson [1960] によって紹介された浮動小数演算の標準モデルは(16)に基づき

(18)

で与えられる。ただし演算 $x\otimes y$ は表現可能な浮動小数値を生成するものとする。(17)に対応する形で次の関係式が導かれる。 MATH

一連の浮動小数演算について考えるとき、誤差項の積としてしばしば次の形のものが得られる。 MATH

それ故、 MATH

今、2次の項を無視することにすれば

(19)

という妥当な仮定が導かれる。(Note1)

次に3つの例を示す。いずれにおいても $x_{i}$ は浮動小数値とする。すなわちそれらはコンピュータ上で既に表現されている値とする。これは計算に際しての誤差を分析する上において自然な仮定である。

Example 5.2 （値の積）

とする。個の積を構成する必要があり、それぞれがを上限とする誤差を生むことになる。(18)から

(20)

一方、(19)から

(21)

であることがわかる。ここに MATH

である。(21)より結果は厳密解に近いため、この計算は前向きに安定であることがわかる。一方、(20)より結果はわずかな摂動に対して厳密である、すなわち結果はデータ

に対して厳密であるため、この計算は後向きにも安定であると言える。

Example 5.3 （値の和）

とする。 MATH と書けることを考慮すると次が容易に導ける。 MATH

これより和は後向きには安定であるが、前向きには安定とは限らないことがわかる。Example 3.1は和が前向きに安定でないケースを示すものである。 $\hfill\square$

$x_{i}$ がすべて同じ符合を持つ場合には MATH より MATH となるため、和は前向きに安定となる。

Example 5.4 （2平方の差）

次の計算について考える。

(22)

もちろんは次のようにも表現できる。

(23)

(22)をベースにの計算を行うと MATH となるため、後向きには安定であるが、前向きには安定ではない。一方、(23) をベースにの計算を行った場合には MATH となるため、後向きにも前向きにも安定となる。具体的に MATH としたとき、有効桁数4桁での計算を行うと MATH という結果が得られる。 $\tilde{z}$ の場合には桁落ちが生じているが、 $\hat{z}$ の場合には問題なく計算が行えている。

今度は線形代数の問題に関するいくつかの結果を紹介する。ただし証明は抜きにし、結果の引用のみに留める。基本的に個の連立1次方程式

(24)

をガウス消去法(Gaussian elimination)で解くことを考える。ただし、読者はガウス消去法に精通しておられることを仮定する。ガウス消去法の

番目のステップは

(25)

と表現される。ここに $P_{k}$ と $Q_{k}$ は置換行列(permutation matrices)で、枢軸選択法(pivoting strategy)に合せて選択される（単位行列であっても良い）。また $M_{k}$ は乗算行列(multiplier matrix)で、 $A_{k-1}$ の

番目の対角要素より下にある要素を消去すべく選択される。因子分解(factorization)の結果は次のようになる。 MATH

ここには置換行列、は単位下三角行列(unit lower triangular matrix)、は上三角行列(upper triangular matrix)である。解析を簡単化するために、慣行に従ってはのように既に並べ替え(permute)られているとする。この場合、(25) は MATH のようになる。ただし $M_{k}$ と $A_{k-1}$ は MATH のような形を持つ。 $m_{k}$ は $a_{k-1}$ を消去できるように選択されるため、 MATH という関係にある。 $\hat{A}_{k-1}$ は MATH のように更新される。このとき MATH となる。 MATH であるため MATH と表現される。このとき計算結果である因子は MATH を満たすことが示される。ただしに関する種々の上限があり得る。例えば $1,\infty$ またはノルムに関して言えば MATH が成立する。ここでは成長因子(growth factor)と呼ばれる。同様に(24) の計算解が MATH を満たすことが示される。この場合の典型的な上限は MATH で与えられる。この不等式はが大きな値でない限り順当なものと言えるので、のサイズを抑えられるようにを選択することが大切である。これが本質的に Wilkinson [1961], Wilkinson [1963, Section 25] の結果である。ただしそこでは $\infty$ ノルムとpartial pivotingが仮定されている。Higham [2002, Theorem 9.5] についても参照されたい。

次はpivotingの必要性を示す簡単な例である。

Example 5.5 （Pivotingの必要性）

行列を MATH とし、有効桁数4桁の計算を行うものとする。は単なる $2\times 2$ 行列のため、となる。算出された行列を $\tilde{X}$ と書くことにすれば、計算の結果は次のようになる。 MATH

これより MATH 従って MATH となる。はに比べると小さいながら、の大きな相対摂動(relative perturbation)に対応する。一方、の行を入れ替え、 MATH とすると MATH

これより MATH 従って MATH となる。今回の場合、は双方に比べて小さな値となっている。

今、とすると MATH であることを示すことができる。Partial pivotingを使えば MATH とすることができる。しかし極めて特殊な場合にはこれに近づけることができない。Wilkinsonが示した例で言うと MATH であり、このとき MATH となる。このような特殊な例はあるものの、現実問題としてはpartial pivotingは最も良く使用される手法である。しかし慎重なソフトウェアであれば少なくとも成長因子をモニタできるオプションを用意すべきである。

の成長を制御する上でpivotingを必要としない行列のクラスもある [Higham, 2002, Table 9.1]。最も重要なのは対称正定値行列(symmetric positive definite matrices)のケースであり、その場合には成長が起り得ないことが最初から知られている。従って係数行列が対称正定値である連立1次方程式にガウス消去法を適用した場合には、計算は安定したものとなる。(Note2)

Pivotsの選択はスケーリングと平衡化(equilibration)によって左右される。スケーリングの選択がまずいとpivotsの選択も望ましいものとはならない可能性がある。Pivoting戦略、平衡化、スケーリング、及びそれらに関する助言については Higham [2002] に記載されている。

直交変換(orthogonal transformations)を用いる手法に対しては誤差の上限として似たような結果を通常得ることができるが、直交変換はノルムとノルムを維持するために、その中には成長因子は含まれない。例えば最小2乗問題 $\min_{x}$ の解法におけるに対し因子分解を行うためにHouseholder変換を用いるとする。ただしは $m\times n(m\geq n)$ 行列で階数(rank)はとする [Golub, 1965]。このとき数値解は MATH を満足する。ただし $c_{1},c_{2}$ を小さな整定数とするとき、 $\QTR{bs}{f},E$ に対しては次の不等式が成り立つ [Lawson and Hanson, 1995, page 90]。 MATH

を $n\times n$ 行列としたとき、固有値問題の解法に際して、まずHouseholder変換を用いてを上(upper)Hessenberg形式に変換した後、アルゴリズムを用いてHessenberg形式を上三角Schur形式に変換するものとする。このときの数値解は MATH を満たす。ただしをの漸増関数としたとき MATH が成り立つ [Wilkinson, 1965; Anderson et al., 1999]。

なお、これまで議論してきた上限はnormwise boundsと呼ばれるが、多くの場合においてこれらはcomponentwise boundsで置き換え得る。後者は個々の要素の絶対値に関する上限であり、より都合の良いものである。例えばが疎行列である場合、我々は構造的にである要素に対して摂動を加えることは好まないであろう。簡単な例として方程式 MATH について考える。ただしは $n\times n$ の三角行列とする。今、を前進代入(forward substitution)、あるいは後退代入(backward substitution)によって得られた数値解とするとき（前進/後退のいずれを用いるかはが下三角か上三角かによる）、は次の条件を満たす。 MATH

これは後向きの安定性を示す強力なcomponentwiseの結果である [Higham, 2002, Theorem 8.5]。

Componentwiseの誤差上限値に付随してcomponentwiseの条件数(condition numbers)がある。詳細については Higham [2002] を参照されたい。