誤差（数値解析）
概要
誤差（error）とは、数値計算で真値と近似値の間に生じるずれである。絶対誤差・相対誤差はずれの尺度を、前進誤差・後退誤差は出力側と入力側の見方を区別する。丸め誤差は有限精度表現から、打ち切り誤差は無限過程を有限操作へ置き換えることから生じる。条件数は問題による誤差増幅を、安定性はアルゴリズムによる増幅を測る。
前提知識: 実数、絶対値、微分、Taylor展開
近似値と誤差
数値計算では、入力、途中の演算、出力のいずれも真の実数値そのものではなく、有限桁で表された近似値になることが多い。そこで単に「答えが近いか」を見るだけでなく、何を真値とし、どの尺度でずれを測り、そのずれがどこで生じ、問題とアルゴリズムのどちらに由来するかを区別する必要がある。
誤差（error）は真値と近似値の差であり、数値解析では絶対誤差・相対誤差、前進誤差・後退誤差、丸め誤差・打ち切り誤差などの形で測る。以下では主に実数と有限次元ベクトルを扱う。無限次元の場合も、適切なノルムを選べば同じ考え方が使える（Hig02、TB97）。
絶対誤差と相対誤差
真値を $x\in\mathbb R$、その近似値を $\widehat{x}\in\mathbb R$ とする。
- 符号付き誤差は $e=\widehat{x}-x$ である。
- 絶対誤差は $|\widehat{x}-x|$ である。
- $x\ne0$ のとき、相対誤差は
$$ \frac{|\widehat{x}-x|}{|x|} $$
である。
ベクトル $x,\widehat{x}$ については、選んだノルムにより絶対誤差を $\|\widehat{x}-x\|$、$x\ne0$ のときの相対誤差を $\|\widehat{x}-x\|/\|x\|$ と定める。
絶対誤差は量の単位をもち、相対誤差は無次元である。たとえば $1000$ m の長さを $1$ mm 間違えることと、$2$ mm の長さを $1$ mm 間違えることは絶対誤差が同じでも意味が異なる。相対誤差はこの尺度差を表す。
$x=1000$、$\widehat{x}=1000.001$ なら絶対誤差は $0.001$、相対誤差は $10^{-6}$ である。一方、$x=0.002$、$\widehat{x}=0.003$ なら絶対誤差は同じ $0.001$ だが、相対誤差は $1/2$ である。
$x=0$ では相対誤差を定義できない。小さい真値の近くでも相対誤差は大きくなりやすい。その場合は、絶対誤差、問題固有の基準量で正規化した誤差、または絶対誤差と相対誤差を組み合わせた許容条件を用いる。
前進誤差と後退誤差
問題を写像 $f:X\to Y$ として、入力 $x$ に対する真の出力を $y=f(x)$、計算結果を $\widehat{y}$ とする。
出力空間の距離を $d_Y$ とすると、$d_Y(\widehat y,f(x))$ を 前進誤差（forward error）という。
入力空間の距離を $d_X$ とすると、
$$
\inf\{d_X(x,\widetilde x)\mid f(\widetilde x)=\widehat y\}
$$
を 後退誤差（backward error）という。集合が空なら後退誤差は $+\infty$ とする。
後退誤差が小さいとは、計算結果が「わずかに摂動した入力に対する厳密解」になっていることを意味する。後退安定性は強い性質だが、問題そのものが悪条件なら、小さな後退誤差から小さな前進誤差は従わない。
$\varepsilon>0$ に対する方程式 $\varepsilon z=\varepsilon$ の真の解は $z=1$ である。近似解 $\widehat z=0$ の残差は
$$
|\varepsilon\widehat z-\varepsilon|=\varepsilon
$$
であり、$\varepsilon$ を小さくすればいくらでも小さくなる。しかし前進誤差 $|\widehat z-z|$ は常に $1$ である。残差を解の誤差へ変換するには、係数の逆数、一般には条件数を考慮しなければならない。
条件数
条件数は、入力の小さな相対変化が出力へどれだけ増幅されうるかを測る。これは問題 $f$ の性質であって、計算手順の性質ではない。
$f$ が $x\ne0$ の近傍で微分可能で $f(x)\ne0$ とする。点 $x$ における相対条件数を
$$
\kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|
$$
と定める。
上の仮定のもとで $h\to0$ とすると、
$$
\frac{|f(x+h)-f(x)|}{|f(x)|}
=\kappa_f(x)\frac{|h|}{|x|}+o\!\left(\frac{|h|}{|x|}\right).
$$
微分可能性から
$$
f(x+h)-f(x)=f'(x)h+o(|h|)
$$
である。両辺の絶対値をとって $|f(x)|$ で割り、
$$
\frac{|f'(x)h|}{|f(x)|}
=\left|\frac{x f'(x)}{f(x)}\right|\frac{|h|}{|x|}
$$
を用いればよい。
$f(x)=x^2$ では $x\ne0$ に対し $\kappa_f(x)=2$ である。一方、$f(x)=1/(1-x)$ では
$$
\kappa_f(x)=\left|\frac{x}{1-x}\right|
$$
なので、$x$ が $1$ に近づくと悪条件になる。後者では入力の小さな相対誤差が出力で大きく増幅されうる。
丸め誤差
浮動小数点演算では、厳密な実数演算の結果を表現可能な数へ丸める。IEEE 754 の最近接丸めを含む標準的な解析では、正規化数の範囲にあり、オーバーフローや段階的アンダーフローの影響を受けない演算について次のモデルを用いる。
$\operatorname{fl}$ を丸められた演算結果とする。基本演算 $\circ\in\{+,-,\times,/\}$ に対し
$$
\operatorname{fl}(x\circ y)=(x\circ y)(1+\delta),
\qquad |\delta|\le u
$$
と書けるとき、$u$ を 単位丸め誤差（unit roundoff）という。
「$1+u$ が浮動小数点数として $1$ より大きくなる最小の $u$」をマシンイプシロンと呼ぶ流儀では、二進最近接丸めの単位丸め誤差はその半分になる。文献や処理系により用語の規約が異なるため、数値だけでなく定義を確認する必要がある。
$|\delta_i|\le u$（$1\le i\le n$）かつ $nu<1$ とする。このとき、ある $\theta_n$ が存在して
$$
\prod_{i=1}^n(1+\delta_i)=1+\theta_n,
\qquad
|\theta_n|\le\gamma_n:=\frac{nu}{1-nu}
$$
となる。
上側について $1+t\le e^t$ を用いると
$$
\prod_{i=1}^n(1+\delta_i)\le(1+u)^n\le e^{nu}.
$$
$0\le t<1$ に対して $e^t\le1/(1-t)$ だから、
$$
\prod_{i=1}^n(1+\delta_i)-1\le\frac{nu}{1-nu}=\gamma_n.
$$
下側は
$$
\prod_{i=1}^n(1+\delta_i)\ge(1-u)^n\ge1-nu
$$
である。したがって
$$
1-\prod_{i=1}^n(1+\delta_i)\le nu\le\gamma_n.
$$
両側を合わせれば主張を得る。
この評価は、多数の浮動小数点演算で生じた相対誤差を一つの係数 $1+\theta_n$ にまとめる際に使われる（Hig02）。
桁落ち
近い二数を引くと、結果に残る有効数字が少なくなることがある。これは 桁落ち（catastrophic cancellation）と呼ばれる。減算が浮動小数点モデルに反するのではなく、入力にすでに含まれる誤差が小さな差に対して大きな相対誤差になる現象である。
$h>0$ が非常に小さいとき、$\sqrt{1+h}-1$ は近い二数の差である。恒等式
$$
\sqrt{1+h}-1=\frac{h}{\sqrt{1+h}+1}
$$
を使えば、分子で近い数を差し引かずに計算できる。たとえば $h=10^{-16}$ では左辺を素朴に計算すると0へ丸められる処理系があるが、右辺は約 $5\times10^{-17}$ を与える。
情報落ちと和の順序
大きさが大きく異なる浮動小数点数を加えると、小さい項が丸めで消えることがある。この 情報落ち は、絶対値の小さい項から加える、二分木状に加える、または補償和を使うことで軽減できる。
$\sum_{k=1}^n k^{-2}$ を有限精度で計算するとき、$1$ から順に加えると後半の小さい項が現在の和へ反映されないことがある。$n^{-2}$ から逆順に加えれば、まず同程度に小さい項どうしを加えるため、通常は誤差が小さくなる。ただし「逆順なら常に最適」という一般定理ではなく、符号の混在する和では別の解析が必要である。
打ち切り誤差
無限級数、極限、微分方程式などを有限の操作で置き換えることにより生じるずれを 打ち切り誤差（truncation error）という。これは数の表現による丸め誤差とは区別される。
$x\in\mathbb R$ と $n\ge0$ に対し
$$
p_n(x)=\sum_{k=0}^n\frac{x^k}{k!}
$$
とおく。このとき $0$ と $x$ の間の点 $\xi$ が存在して
$$
e^x-p_n(x)=\frac{e^\xi x^{n+1}}{(n+1)!}
$$
となる。したがって
$$
|e^x-p_n(x)|\le
\frac{e^{|x|}|x|^{n+1}}{(n+1)!}.
$$
$f(t)=e^t$ に $0$ を中心とする Taylor の定理を適用する。$f^{(k)}(t)=e^t$ なので、Lagrange形剰余項により、$0$ と $x$ の間の $\xi$ が存在して
$$
e^x=\sum_{k=0}^n\frac{x^k}{k!}+\frac{e^\xi x^{n+1}}{(n+1)!}
$$
となる。$|\xi|\le|x|$ から $e^\xi\le e^{|x|}$ であり、絶対値をとれば評価を得る。
刻み幅を小さくすれば打ち切り誤差が減っても、演算回数の増加や差商の桁落ちにより丸め誤差が増えることがある。したがって、二種類の誤差を別々に小さくするだけでなく、全誤差の釣り合いを見る必要がある。
安定性と精度保証
安定なアルゴリズムとは、丸めなどの小さな局所誤差を不必要に増幅しない計算法である。特に、計算結果が少し摂動した入力に対する厳密解とみなせるとき、後退安定であるという。最終的な前進誤差は概念的には
$$
\text{前進誤差}
\lesssim
\text{問題の条件数}\times\text{後退誤差}
$$
と理解できる。条件数は問題を、安定性はアルゴリズムを評価するため、両者を混同してはいけない。
丸め方向を制御する区間演算などにより、真値を必ず含む区間を計算する方法を 精度保証付き数値計算という。通常の誤差解析が理論上の上界を与えるのに対し、精度保証では実際の計算結果に対する包含を機械的に確認することを目指す。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
