丸め誤差

1. 丸め誤差の位置づけ

丸め誤差（Round-off Error）とは、実数や演算の結果を有限桁の浮動小数点数に丸める際に生じる誤差である。1回の丸めの相対誤差は、既定の最近接丸めでは丸めの単位 $u = \varepsilon_{\text{mach}}/2$ 以下（$\varepsilon_{\text{mach}}$ は計算機イプシロン）と微小であるが、多数の演算を繰り返すと蓄積して無視できない大きさになりうる。

丸め誤差の定義・発生メカニズム・丸めモードについては前の章（第1章「浮動小数点数」など）を参照されたい。本章では蓄積の定量的分析と低減手法に焦点を当てる。

以下、誤差のオーダーを表す式では $\varepsilon_{\text{mach}}$ を単に $\varepsilon$ と書く（$O(\cdot)$ の中では $u$ との 2 倍の違いは定数に吸収される）。

2. 蓄積モデル

ランダムウォークモデル

$n$ 回の演算で各回の丸め誤差がランダムかつ独立であると仮定すると、累積誤差は

と増大する（ランダムウォーク）。実際の浮動小数点演算では誤差の符号がある程度ランダムに振れるため、多くの場合このモデルに近い振る舞いを示す。

ここで $E$ は、$n$ 個の数の総和 $S = \sum_i a_i$ を計算したときの誤差 $|\hat{S} - S|$ を $\sum_i |a_i|$ で割った相対誤差である。$|S|$ で割った相対誤差は、正負の項が打ち消し合う（桁落ちが起きる）とこれよりずっと大きくなりうる（§3 の桁落ちの回避を参照）。

最悪ケース

丸め誤差が常に同じ方向に蓄積する最悪の場合は

となる。単純な逐次加算の誤差の上界はこの最悪ケースで与えられる。ただし実際のデータでは誤差の符号が振れるため、多くの場合は上のランダムウォークに近く、$n$ に比例して増えるのは丸めが同じ向きにそろうように作ったデータに限られる。

3. 総和アルゴリズムの比較

$n$ 個の浮動小数点数 $a_1, a_2, \ldots, a_n$ の総和 $\displaystyle S = \displaystyle\sum_{i=1}^{n} a_i$ を求める場合、アルゴリズムの選択で蓄積誤差が大きく変わる。

Kahan の補償加算

丸めで失われた端数を補償項に蓄積し、次のステップで補正する手法。情報落ちの章に疑似コードと詳細がある。誤差上界の証明・Neumaier 改良・誤差なし変換 (2Sum/Fast2Sum) との関係は中級「補償付き加算」を参照。

ペアワイズ加算

配列を再帰的に半分に分割し、各半分の和を加算する。$\log_2 n$ 段の加算で済むため、蓄積誤差が $O(\log n \cdot \varepsilon)$ に抑えられる。

function pairwiseSum(a[], lo, hi):
    if hi - lo < 16:          // ベースケース: 逐次加算
        s = 0.0
        for i = lo to hi-1: s += a[i]
        return s
    mid = (lo + hi) / 2
    return pairwiseSum(a, lo, mid)
         + pairwiseSum(a, mid, hi)

その他の低減手法

• 桁落ちの回避: 数式を等価変形して、ほぼ等しい値の減算を避ける。
• 高精度演算: 倍精度で不足する場合、四倍精度や任意精度演算を利用する。
• 安定なアルゴリズムの選択: 後退安定なアルゴリズムを選ぶ。

4. 打ち切り誤差とのトレードオフ

アルゴリズムに由来する誤差の主な 2 つが 丸め誤差 と 打ち切り誤差 であり（入力データの誤差やモデル化の誤差は別に考える）、全体の誤差はおおむね両者の和で見積もられる。多くの場面で、精度を上げようとすると丸め誤差が増大し、最適なパラメータが存在する。

数値微分の例

前進差分 $f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$ を考える。

• 打ち切り誤差（Taylor 展開の剰余項）: $\dfrac{h}{2}|f''(\xi)| = O(h)$ — $h$ が小さいほど小さい。
• 丸め誤差: $f(x+h)$ と $f(x)$ はそれぞれ関数値の大きさに比例した $O(\varepsilon |f(x)|)$ の丸め誤差をもつ。差分 $f(x+h) - f(x)$ にもこの大きさの誤差が残り、それを $h$ で割るため $O(\varepsilon |f(x)| / h)$ に増幅される。

全誤差 $E(h) \sim C_1 h + C_2 \varepsilon / h$ を最小化すると、最適刻み幅は $h^* = \sqrt{C_2 \varepsilon / C_1}$ であり、これより小さい $h$ ではかえって精度が悪化する。ここで $C_1 = |f''(\xi)|/2$, $C_2 \approx 2|f(x)|$（$f(x+h)$ と $f(x)$ の丸め誤差がそれぞれ $\varepsilon|f(x)|$ 程度であることから。定数は関数の計算法でも変わるので目安）であるから、$h^*$ の値は対象の関数に依存する。$|f(x)|$ と $|f''(x)|$ が同程度なら $h^* \approx 2\sqrt{\varepsilon} \approx 3 \times 10^{-8}$（倍精度）で、おおまかには $h^* \sim \sqrt{\varepsilon} \approx 10^{-8}$ の桁である。

下図は $E_{\text{trunc}} = C_1 h$（青）、$E_{\text{round}} = C_2 \varepsilon / h$（赤）、全誤差（緑）を対数-対数スケールで描いたものである。2直線の交点が最適 $h^*$ に対応し、全誤差は交点で最小値をとる。

級数の打ち切り

Taylor 展開を有限和 $e^x \approx \displaystyle\sum_{k=0}^{N} x^k / k!$ で打ち切る場合にもトレードオフが生じる。

• 打ち切り誤差: $O(|x|^{N+1}/(N+1)!)$ — 項数 $N$ を増やすと急速に減少。
• 丸め誤差: $N$ 回の加算 → $O(N \varepsilon)$ で蓄積（§2 のモデル）。

ただし、$|x|$ が大きくなければ $e^x$ の級数の項は急速に小さくなる（$|x|^k / k!$ は $k$ が $|x|$ を超えると減少に転じる）ので、実用上の $N$（数十項程度）で丸め誤差の蓄積は通常問題にならない。より深刻なのは、交互級数で $e^{-x}$（$x > 0$）を $\displaystyle\sum (-x)^k / k!$ と計算する場合の桁落ちであり、$e^{-x} = 1/e^x$ と変形するなどの対策が必要となる（ただし $x$ が非常に大きい場合は $e^x$ 自体がオーバーフローするため、別の近似が必要になる）。

5. よくある質問

6. 参考資料

• Wikipedia「丸め誤差」（日本語版）
• Wikipedia「Round-off error」（英語版）
• Wikipedia「Kahan summation algorithm」（英語版）
• Wikipedia「Pairwise summation」（英語版）
• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Chapter 4 (Summation).
• D. Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic," ACM Computing Surveys, vol. 23, no. 1, pp. 5--48, 1991.