桁落ち
この章の目標
壊滅的桁落ちの定量的な分析方法を理解し、具体的な数値例で桁落ちの影響を確認する。安全な代替公式の導出法を学ぶ。
前提知識
1. 定義
桁落ち（Catastrophic Cancellation）とは、ほぼ等しい2つの浮動小数点数を減算した際に、上位の有効数字が打ち消し合い、結果の有効数字が大幅に減少する現象である。
桁落ちの本質
$x \approx y$ のとき $x - y$ を計算すると、$x$ と $y$ の上位の一致する桁がすべて相殺される。残った下位の桁は丸め誤差を含んでいるため、結果の相対誤差が入力に比べて大幅に増大する。
桁落ちは減算そのものが誤差を「生む」のではなく、すでに存在していた丸め誤差を「顕在化」させる現象である。
2. 発生メカニズム
10進4桁の浮動小数点数で考える。
$x = 1.234 \times 10^0$（真値は $1.2345678\ldots$）
$y = 1.233 \times 10^0$（真値は $1.2334567\ldots$）
$x - y = 0.001 \times 10^0 = 1.000 \times 10^{-3}$
元の $x$, $y$ は4桁の有効数字をもっていたが、減算結果は実質1桁しか信頼できない。正規化により $1.000 \times 10^{-3}$ と表示されるが、下位3桁の $000$ は情報を持たない「ゴミの桁」である。
3. 典型的な発生場面
二次方程式の解の公式
$ax^2 + bx + c = 0$ の解 $x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ において、$b^2 \gg 4ac$ のとき $\sqrt{b^2 - 4ac} \approx |b|$ となり、$-b + \sqrt{b^2-4ac}$ または $-b - \sqrt{b^2-4ac}$ の一方で桁落ちが発生する。
数値微分
差分公式 $f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$ において、$h$ が非常に小さいと $f(x+h) \approx f(x)$ となり、分子で桁落ちが発生する。
三角関数
$1 - \cos x$ を $x \approx 0$ で計算すると桁落ちが起こる。$\cos x \approx 1 - x^2/2$ であるため、$1 - \cos x \approx x^2/2$ は非常に小さい。
指数関数
$e^x - 1$ を $x \approx 0$ で計算すると、$e^x \approx 1$ であるため桁落ちが発生する。多くの言語では expm1(x) という組み込み関数が用意されており、$e^x - 1$ を精度良く計算できる。同様に $\log(1+x)$ には log1p(x) が有効である。
4. 回避技法
有理化（分子・分母の有理化）
$\sqrt{x+1} - \sqrt{x}$ の桁落ちを回避するには、分子を有理化する。
$$\sqrt{x+1} - \sqrt{x} = \dfrac{(\sqrt{x+1} - \sqrt{x})(\sqrt{x+1} + \sqrt{x})}{\sqrt{x+1} + \sqrt{x}} = \dfrac{1}{\sqrt{x+1} + \sqrt{x}}$$右辺には減算がなく、桁落ちは発生しない。
テイラー展開の利用
$1 - \cos x$ を $x \approx 0$ で計算する代わりに、
$$1 - \cos x = \dfrac{x^2}{2} - \dfrac{x^4}{24} + \cdots \approx \dfrac{x^2}{2}$$と展開して計算する。多くのプログラミング言語には expm1(x)（$e^x - 1$）や log1p(x)（$\log(1+x)$）が組み込み関数として用意されている。
代数的恒等式の利用
二次方程式では、桁落ちしない方の根 $x_1$ を先に求め、ヴィエタの公式 $x_1 x_2 = c/a$ からもう一方を求める。
加法定理の利用
$1 - \cos x = 2\sin^2(x/2)$ と変形すると桁落ちを回避できる。
5. 情報落ちとの違い
| 性質 | 桁落ち | 情報落ち |
|---|---|---|
| 原因 | ほぼ等しい値の減算 | 絶対値の大きく異なる数の加減算 |
| 失われるもの | 上位の有効数字 | 小さい方の下位桁 |
| 演算 | 減算のみ | 加算でも発生 |
| 結果 | 相対誤差の増大 | 小さい値の情報の消失 |
| 回避法 | 数式変形、展開 | 演算順序の工夫、補償加算 |
6. 計算例
例: 二次方程式 $x^2 - 10^8 x + 1 = 0$
解の公式では $b^2 - 4ac = 10^{16} - 4 \approx 10^{16}$ であるから $\sqrt{b^2 - 4ac} \approx 10^8$ となる。
不安定な計算: $x_2 = \dfrac{10^8 - \sqrt{10^{16} - 4}}{2}$ で桁落ちが発生し、有効数字が激減する。
安定な計算: まず $x_1 = \dfrac{10^8 + \sqrt{10^{16} - 4}}{2} \approx 10^8$ を求め、ヴィエタの公式 $x_2 = 1/x_1 \approx 10^{-8}$ とする。
7. よくある質問
Q1. 桁落ちとは何ですか？
ほぼ等しい2つの浮動小数点数を減算した際に、上位の有効数字が打ち消し合い、結果の有効数字が大幅に減少する現象である。
Q2. 桁落ちと情報落ちの違いは何ですか？
桁落ちはほぼ等しい値の減算で有効数字が失われる現象であり、情報落ちは絶対値の大きく異なる数の加減算で小さい方の情報が失われる現象である。
Q3. 桁落ちを回避する方法は何ですか？
有理化による数式変形、テイラー展開による近似、ヴィエタの公式などの代数的恒等式の利用、より高精度の演算の使用などがある。
8. 参考資料
- Wikipedia「桁落ち」（日本語版）
- Wikipedia「Catastrophic cancellation」（英語版）
- Wikipedia「Loss of significance」（英語版）
- D. Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic," ACM Computing Surveys, vol. 23, no. 1, pp. 5--48, 1991.
- N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002.