桁落ち
この章の目標
桁落ちで相対誤差がどれだけ増幅されるかを式で理解し、具体的な数値例で桁落ちの影響を確認する。安全な代替公式の導出法を学ぶ。
前提知識
1. 定義
桁落ち（Catastrophic Cancellation）とは、ほぼ等しい2つの数を差し引いたとき（符号が逆でほぼ同じ大きさの数を足したときも同じ）に上位の桁が打ち消し合い、入力に含まれていた丸め誤差や近似誤差が、差の相対誤差として大きく現れる現象である。結果の信頼できる有効数字は大幅に減る。
桁落ちの本質
$x \approx y$ のとき $x - y$ を計算すると、$x$ と $y$ の上位の一致する桁がすべて相殺される。残った下位の桁は丸め誤差を含んでいるため、結果の相対誤差が入力に比べて大幅に増大する。
相対誤差の増幅
真値 $x$, $y$ の近似値を $\hat{x} = x(1 + \delta_x)$, $\hat{y} = y(1 + \delta_y)$ とし、減算 $\hat{x} - \hat{y}$ 自体は正確に行われるとする。このとき
$$\left|\frac{(\hat{x} - \hat{y}) - (x - y)}{x - y}\right| = \frac{|x\delta_x - y\delta_y|}{|x - y|} \le \frac{|x| + |y|}{|x - y|} \max(|\delta_x|, |\delta_y|)$$$x \approx y$ だと分母 $|x - y|$ が小さく、係数 $\dfrac{|x| + |y|}{|x - y|}$ が大きくなる。差が小さいほど、入力の相対誤差は大きく増幅される（§2 の例では係数は約 $2200$）。
桁落ちは減算そのものが誤差を「生む」のではなく、すでに存在していた丸め誤差を「顕在化」させる現象である。
2. 発生メカニズム
10進4桁の浮動小数点数で考える（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}$
真の差は $1.2345678\ldots - 1.2334567\ldots = 0.0011111\ldots$ なので、計算結果 $0.001$ の相対誤差は約 $10\%$ である。入力の相対誤差（$4.6 \times 10^{-4}$ と $3.7 \times 10^{-4}$）の 200 倍以上に増えた。元の $x$, $y$ は4桁の有効数字をもっていたが、減算結果は実質1桁しか信頼できない。正規化により $1.000 \times 10^{-3}$ と表示されるが、下位3桁の $000$ は情報を持たない「ゴミの桁」である。
3. 典型的な発生場面
二次方程式の解の公式
$ax^2 + bx + c = 0$（$a \ne 0$, $b^2 - 4ac \ge 0$）の解 $x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ において、$b^2 \gg |4ac|$ のとき $\sqrt{b^2 - 4ac} \approx |b|$ となり、$b > 0$ なら $-b + \sqrt{b^2-4ac}$、$b < 0$ なら $-b - \sqrt{b^2-4ac}$ で桁落ちが発生する。
数値微分
差分公式 $f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$ において、$h$ が非常に小さいと $f(x+h) \approx f(x)$ となり、分子で桁落ちが発生する。一方で $h$ を大きくすると打切り誤差が増えるので、$h$ には適切な大きさがある。
三角関数
$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. 回避技法
有理化（分子・分母の有理化）
$x \ge 0$ で、特に $x$ が大きいと $\sqrt{x+1}$ と $\sqrt{x}$ がほぼ等しくなり、$\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}$$と展開して計算する。これは $x$ が十分小さい範囲での近似で、打ち切った項 $x^4/24$ が誤差になる（相対誤差は約 $x^2/12$）。
代数的恒等式の利用
二次方程式（$b \ne 0$）では、$-b$ と同じ符号の項を足す方の根 $x_1 = \dfrac{-b - \operatorname{sgn}(b)\sqrt{b^2 - 4ac}}{2a}$ は桁落ちしないので先に求め、$x_1 \ne 0$ のときヴィエタの公式 $x_1 x_2 = c/a$ から $x_2 = \dfrac{c}{a x_1}$ と求める。
半角の公式の利用
$1 - \cos x = 2\sin^2(x/2)$（半角の公式）と変形すると、$1$ と $\cos x$ の直接の減算を避けられる。テイラー展開と違ってこれは恒等式なので、$x$ の大きさによらず使える。
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}$ とする。
倍精度（double）で実際に計算すると、不安定な計算では $x_2 = 7.450580596923828 \times 10^{-9}$（相対誤差約 $25\%$）、安定な計算では $x_2 = 1.0 \times 10^{-8}$（相対誤差 $10^{-16}$ 未満）になる。真値は $1.0000000000000001\ldots \times 10^{-8}$ である。
7. よくある質問
Q1. 桁落ちとは何か
ほぼ等しい2つの数を差し引いたとき（符号が逆でほぼ同じ大きさの数を足したときも同じ）に上位の桁が打ち消し合い、入力に含まれていた丸め誤差や近似誤差が、差の相対誤差として大きく現れる現象である。英語では Catastrophic Cancellation と呼ばれる。
Q2. 桁落ちと情報落ちの違いは何か
桁落ちは、ほぼ等しい値の実質的な減算（同符号の減算・異符号の加算）で上位の桁が打ち消し合い、相対誤差が増幅される現象である。情報落ちは、絶対値の大きく異なる数の加減算で、小さい方の下位の桁が失われる現象である。
Q3. 桁落ちを回避する方法は何か
主な方法は、(1) 有理化などの恒等変形で近い数の直接の減算を避ける、(2) テイラー展開による近似（$x$ が十分小さい範囲で使う）、(3) ヴィエタの公式などの代数的恒等式の利用、(4) より高精度の演算の使用、である。ただし (4) は桁落ちを先送りするだけで、式の不安定さそのものは残る。
8. 参考資料
- Wikipedia「桁落ち」（日本語版）
- Wikipedia「Catastrophic cancellation」（英語版）
- 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.