桁落ち

近い値どうしを引き算すると、有効桁数が激減する現象。 catastrophic cancellation。

例#

$1.23456789$ と $1.23456700$（有効 9 桁）を引くと $0.00000089$。 有効桁は 2 桁しか残らない。 上位の一致していた桁が消え、下位の誤差だけが残る。

二次方程式での典型例#

$$x=\frac{-b+\sqrt{b^2-4ac}}{2a}$$

$b>0$ で $4ac\ll b^2$ のとき、$-b$ と $\sqrt{b^2-4ac}$ が近くなり桁落ちする。

対処は式を変形すること。

$$x=\frac{2c}{-b-\sqrt{b^2-4ac}}$$

数学的に同じ式でも、数値的には別物。

数値微分での桁落ち#

$$f^{\prime }(x)\approx \frac{f(x+h)-f(x)}{h}$$

$h$ を小さくすると分子で桁落ちが起きる。 打ち切り誤差と丸め誤差の綱引きの正体がこれ。

対策#

• 式を変形して引き算を避ける
• $\log (1+x)$ には log1p、$e^x-1$ には expm1 を使う
• 分散の計算に $𝔼[X^2]-{\mu }^2$ ではなく Welford の逐次法を使う

参考文献#

• David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys 23(1), 1991. https://doi.org/10.1145/103162.103163
• Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms, 2nd ed. SIAM, 2002. https://doi.org/10.1137/1.9780898718027