丸め誤差
この章の目標
丸め誤差が多数の演算を通じてどのように蓄積するかを定量的に理解し、打ち切り誤差との関係および低減手法を学ぶ。
前提知識
1. 丸め誤差の位置づけ
丸め誤差（Round-off Error）とは、実数を有限桁の浮動小数点数で表現する際に生じる誤差である。1回の丸めの相対誤差は計算機イプシロン $\varepsilon_{\text{mach}}$ 以下と微小であるが、多数の演算を繰り返すと蓄積して無視できない大きさになりうる。
丸め誤差の定義・発生メカニズム・丸めモードについては前章を参照されたい。本章では蓄積の定量的分析と低減手法に焦点を当てる。
2. 蓄積モデル
ランダムウォークモデル
$n$ 回の演算で各回の丸め誤差がランダムかつ独立であると仮定すると、累積誤差は
$$E \sim \sqrt{n} \cdot \varepsilon_{\text{mach}}$$と増大する（ランダムウォーク）。実際の浮動小数点演算では誤差の符号がある程度ランダムに振れるため、多くの場合このモデルに近い振る舞いを示す。
最悪ケース
丸め誤差が常に同じ方向に蓄積する最悪の場合は
$$E \sim n \cdot \varepsilon_{\text{mach}}$$となる。単純な逐次加算アルゴリズムはこの最悪ケースに近い振る舞いを示す。
3. 総和アルゴリズムの比較
$n$ 個の浮動小数点数 $a_1, a_2, \ldots, a_n$ の総和 $\displaystyle S = \sum_{i=1}^{n} a_i$ を求める場合、アルゴリズムの選択で蓄積誤差が大きく変わる。
| アルゴリズム | 誤差上界 | 追加メモリ | 特徴 |
|---|---|---|---|
| 逐次加算 | $O(n \varepsilon)$ | $O(1)$ | 最も単純。最悪ケース。 |
| ソート加算 | $O(n \varepsilon)$ | $O(1)$ | 小さい値から順に加算。定数改善。$O(n \log n)$ のソートが必要。 |
| ペアワイズ加算 | $O(\log n \cdot \varepsilon)$ | $O(\log n)$ | 再帰的に半分ずつ加算。NumPy の np.sum が採用。 |
| Kahan補償加算 | $O(\varepsilon)$ | $O(1)$ | 補償項で誤差を追跡。$n$ に依存しない。 |
Kahan の補償加算
丸めで失われた端数を補償項に蓄積し、次のステップで補正する手法。情報落ちの章に疑似コードと詳細がある。
ペアワイズ加算
配列を再帰的に半分に分割し、各半分の和を加算する。$\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. 打ち切り誤差とのトレードオフ
数値計算の全誤差は 丸め誤差 と 打ち切り誤差 の和である。多くの場面で、精度を上げようとすると丸め誤差が増大し、最適なパラメータが存在する。
数値微分の例
前進差分 $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+h) - f(x)$ 自体の丸め誤差も $O(\varepsilon)$ だが、それを $h$ で割るため $O(\varepsilon / h)$ に増幅される。
全誤差 $E(h) \sim C_1 h + C_2 \varepsilon / h$ を最小化すると、最適刻み幅は $h^* = \sqrt{C_2 \varepsilon / C_1} \sim \sqrt{\varepsilon} \approx 10^{-8}$（倍精度）であり、これより小さい $h$ ではかえって精度が悪化する。ここで $C_1 = |f''(\xi)|/2$, $C_2 \approx 2|f(x)|/|f'(x)|$ であるから、$h^*$ の正確な値は対象の関数に依存する。
下図は $E_{\text{trunc}} = C_1 h$（青）、$E_{\text{round}} = C_2 \varepsilon / h$（赤）、全誤差（緑）を対数-対数スケールで描いたものである。2直線の交点が最適 $h^*$ に対応し、全誤差は交点で最小値をとる。
丸め誤差増大の2つのメカニズム
数値微分では、$h$ を小さくしても演算回数は変わらない。丸め誤差が増大するのは、分子 $f(x+h) - f(x)$ の $O(\varepsilon)$ の丸め誤差を小さな $h$ で割ることで誤差が増幅されるためである（§2 の蓄積モデルとは異なるメカニズム）。一方、数値積分では刻み幅を小さくすると分割数 $n = 1/h$ が増えて丸め誤差が蓄積するため、§2 の蓄積モデルが直接適用される。
級数の打ち切り
Taylor 展開 $e^x = \sum_{k=0}^{N} x^k / k!$ を $N$ 項で打ち切る場合にもトレードオフが生じる。
- 打ち切り誤差: $O(|x|^{N+1}/(N+1)!)$ — 項数 $N$ を増やすと急速に減少。
- 丸め誤差: $N$ 回の加算 → $O(N \varepsilon)$ で蓄積（§2 のモデル）。
ただし、$e^x$ のように各項が急減する級数では、実用上の $N$（数十項程度）で丸め誤差の蓄積は通常問題にならない。より深刻なのは、交互級数で $e^{-x}$（$x > 0$）を $\sum (-x)^k / k!$ と計算する場合の桁落ちであり、$e^{-x} = 1/e^x$ と変形するなどの対策が必要となる（ただし $x$ が非常に大きい場合は $e^x$ 自体がオーバーフローするため、別の近似が必要になる）。
5. よくある質問
Q1. 丸め誤差はどのように蓄積しますか？
$n$ 回の演算で各回の誤差がランダムなら累積誤差は $O(\sqrt{n} \cdot \varepsilon)$、最悪ケース（同方向蓄積）なら $O(n \cdot \varepsilon)$ である。Kahan の補償加算を用いると $O(\varepsilon)$ で抑えられる。
Q2. 丸め誤差と打ち切り誤差の違いは何ですか？
丸め誤差は有限桁の浮動小数点演算に由来し、打ち切り誤差は無限の数学的過程を有限の近似で置き換えた際に生じる。数値計算の全誤差はこの2つの和であり、刻み幅を小さくすると打ち切り誤差は減るが丸め誤差は増大する。
Q3. 総和アルゴリズムごとの誤差オーダーは？
逐次加算は $O(n \varepsilon)$、ソート加算も $O(n \varepsilon)$ だが定数が改善、ペアワイズ加算は $O(\log n \cdot \varepsilon)$、Kahan の補償加算は $O(\varepsilon)$ である。
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.