壊滅的なキャンセル

数値解析において、破滅的相殺^{[1] [2]}とは、2つの近い数値の良い近似値を減算すると、元の数値の差の非常に悪い近似値が得られるという現象である。

たとえば、 と の 2 つのスタッドがあり、一方が で他方がである場合、センチメートルまでしか測定できない定規で測定すると、近似値はおよびになる可能性があります。これらは、相対誤差では、実際の長さに対して良好な近似値である可能性があります。近似値の誤差は、実際の長さの 2% 未満です。 ${\displaystyle L_{1}=253.51\,{\text{cm}}}$${\displaystyle L_{2}=252.49\,{\text{cm}}}$${\displaystyle {\tilde {L}}_{1}=254\,{\text{cm}}}$${\displaystyle {\tilde {L}}_{2}=252\,{\text{cm}}}$${\displaystyle |L_{1}-{\チルダ {L}}_{1}|/|L_{1}|<2\%}$

しかし、近似値の長さを減算すると、長さの真の違いが であっても、その差は になります。近似値の差 は、真の値の差 の大きさのほぼ 100% の誤差があります。 ${\displaystyle {\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}}$${\displaystyle L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}}$${\displaystyle 2\,{\text{cm}}}$${\displaystyle 1.02\,{\text{cm}}}$

壊滅的なキャンセルは入力の大きさには影響されません。入力が大きい場合も小さい場合も同様に適用されます。これは、差の大きさと入力の誤差にのみ依存します。から をおよびの近似値として減算した場合、またはから をおよびの近似値として減算した場合、まったく同じ誤差が発生します。 ${\displaystyle 52\,{\text{cm}}}$${\displaystyle 54\,{\text{cm}}}$${\displaystyle 52.49\,{\text{cm}}}$${\displaystyle 53.51\,{\text{cm}}}$${\displaystyle 2.00052\,{\text{km}}}$${\displaystyle 2.00054\,{\text{km}}}$${\displaystyle 2.0005249\,{\text{km}}}$${\displaystyle 2.0005351\,{\text{km}}}$

上記の例のように、差が正確に計算された場合でも、壊滅的な相殺が発生する可能性があります。これは、浮動小数点演算のような特定の種類の演算の特性ではなく、入力自体が近似値である場合の減算に固有のものです。実際、浮動小数点演算では、入力が十分に近い場合、ステルベンツの補題により、浮動小数点差は正確に計算されます。つまり、浮動小数点減算演算によって丸め誤差は発生しません。

正式には、破滅的な相殺は、減算が近くの入力で悪条件であるために発生します。つまり、近似値と がそれぞれ真の値とから小さな相対誤差とを持つ場合でも、近似値の差と真の値の差の相対誤差は、真の値の差に反比例します。 ${\displaystyle {\tilde {x}}=x(1+\delta _{x})}$${\displaystyle {\チルダ {y}}=y(1+\delta _{y})}$ ${\displaystyle |\delta _{x}|=|x-{\tilde {x}}|/|x|}$${\displaystyle |\delta _{y}|=|y-{\チルダ {y}}|/|y|}$${\displaystyle x}$${\displaystyle y}$${\displaystyle {\チルダ {x}}-{\チルダ {y}}}$${\displaystyle xy}$

$${\displaystyle {\begin{aligned}{\tilde {x}}-{\tilde {y}}&=x(1+\delta _{x})-y(1+\delta _{y})= x-y+x\delta _{x}-y\delta _{y}\\&=x-y+(xy){\frac {x\delta _{x}-y\delta _{y}}{xy}}\\&=(xy){\biggr (}1+{\frac {x\delta _{x}-y\delta _{y}}{xy}}{\biggr )}.\end{整列}}}$$

したがって、近似値の正確な差と真の値の 差の相対誤差は${\displaystyle {\チルダ {x}}-{\チルダ {y}}}$${\displaystyle xy}$

$${\displaystyle \left|{\frac {x\delta _{x}-y\delta _{y}}{xy}}\right|.}$$

真の値とが近い場合、これは任意に大きくなる可能性があります。 ${\displaystyle x}$${\displaystyle y}$

浮動小数点演算で近い数値を減算しても、必ずしも壊滅的な相殺やエラーが発生するわけではありません。ステルベンツの補題によれば、数値が十分に近い場合、浮動小数点の差は正確です。ただし、相殺によって、他の浮動小数点演算での丸めによって発生した入力のエラー が増幅される可能性があります。

数とが与えられた場合、との大きさが近い ときに、 浮動小数点演算によって 数学関数を計算する単純な試みは 、減算によって二乗の丸め誤差が明らかになる可能性があるため、壊滅的な相殺の影響を受けます。 浮動小数点演算 によって評価される 代替因数分解は、減算につながる丸め誤差の導入を回避するため、壊滅的な相殺を回避します。^[2]${\displaystyle x}$${\displaystyle y}$${\displaystyle x^{2}-y^{2}}$${\displaystyle \operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x+y)(xy)}$${\displaystyle \operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (xy))}$

たとえば、 および の場合、差の真の値 は です 。IEEE 754 バイナリ 64演算では、代替因数分解を評価すると、 （丸めなしで）正しい結果が正確に得られますが、単純な式を評価すると、 浮動小数点数 が得られ 、その桁の半分以下が正しく、他の（下線付きの）桁は、中間の二乗値を計算するときに丸めによって失われた、 欠落した項 を反映します。${\displaystyle x=1+2^{-29}\approx 1.0000000018626451}$${\displaystyle y=1+2^{-30}\approx 1.0000000009313226}$${\displaystyle x^{2}-y^{2}}$${\displaystyle 2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}}$${\displaystyle (x+y)(xy)}$${\displaystyle x^{2}-y^{2}}$${\displaystyle 2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}}$${\displaystyle 2^{-59}+2^{-60}}$

複素逆正弦関数を計算する場合、対数式を直接使用したくなるかもしれません。

$${\displaystyle \arcsin(z)=i\log {\bigl (}{\sqrt {1-z^{2}}}-iz{\bigr )}.}$$

しかし、 について と仮定します。そしてとを呼び出します。それらの差は非常に小さく、ほぼゼロです。 を浮動小数点演算で評価する と、${\displaystyle z=iy}$${\displaystyle y\ll 0}$${\displaystyle {\sqrt {1-z^{2}}}\approx -y}$${\displaystyle iz=-y}$${\displaystyle \varepsilon }$${\displaystyle {\sqrt {1-z^{2}}}}$

$${\displaystyle \operatorname {fl} {\Bigl (}{\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}{\Bigr )}={\sqrt {1-z^{2}}}(1+\delta )}$$

誤差は （ただし は浮動小数点の丸めを表す）で、差を計算すると ${\displaystyle \delta \neq 0}$${\displaystyle \operatorname {fl} (\cdots )}$

$${\displaystyle {\sqrt {1-z^{2}}}(1+\delta )-iz}$$

2 つの近い数値がどちらも に非常に近い場合、1 つの入力の誤差が倍に増幅される可能性があります。これは がほぼゼロであるため、非常に大きな倍数です。たとえば、 の場合、 の真の値はおよそ ですが、 IEEE 754 バイナリ 64演算の単純な対数式を使​​用するととなり、16 桁のうち 5 桁のみが正しく、残り (下線部) はすべて正しくありません。 ${\displaystyle -y}$${\displaystyle \delta }$${\displaystyle 1/\varepsilon }$${\displaystyle \varepsilon }$${\displaystyle z=-1234567i}$${\displaystyle \arcsin(z)}$${\displaystyle -14.71937803983977i}$${\displaystyle -14.719{\underline {644263563968}}i}$

の場合、ではなく であるため、恒等式を使用すると相殺を回避できます。したがって、減算は実質的に同じ符号の加算となり、相殺されません。 ${\displaystyle z=iy}$${\displaystyle y<0}$${\displaystyle \arcsin(z)=-\arcsin(-z)}$${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$${\displaystyle i(-z)=-iz=y}$

ソフトウェア プログラム内の数値定数は、多くの場合、10 進数で記述されます。たとえば、という IEEE 754 binary64 変数を宣言して初期化するC フラグメントでは、 がこれに該当します。ただし、は binary64 浮動小数点数ではありません。このフラグメントで に初期化される最も近い値は です。10 進浮動小数点から 2 進浮動小数点への基数変換では相対誤差はわずかしか発生しませんが、壊滅的なキャンセルによって誤差がさらに大きくなる可能性があります。 double x = 1.000000000000001;x${\displaystyle 1.000000000000001}$x${\displaystyle 1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}}$

double x = 1.0000000000000001 ; // 1 + 5*2^{-52} に丸められますdouble y = 1.0000000000000002 ; // 1 + 9*2^{-52} に丸められますdouble z = y - x ; // 差はちょうど 4*2^{-52} です     
     
                   

差は です。からの の相対誤差とからの の相対誤差は両方とも より小さく、浮動小数点減算はシュテルベンツの補題によって正確に計算されます。 ${\displaystyle 1.000000000000002-1.000000000000001}$${\displaystyle 0.000000000000001=1.0\times 10^{-15}}$x${\displaystyle 1.000000000000001}$y${\displaystyle 1.000000000000002}$${\displaystyle 10^{-15}=0.0000000000001\%}$y - x

しかし、入力が良好な近似値であり、減算が正確に計算されたとしても、近似値 の差は、10 進数で記述された元の値の差を超える相対誤差を持ちます。つまり、壊滅的なキャンセルにより、基数変換の小さな誤差が出力の大きな誤差に増幅されたのです。 ${\displaystyle {\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}}$${\displaystyle 11\%}$${\displaystyle 1.0\times 10^{-15}}$

キャンセルは、数値アルゴリズムでは便利で望ましい場合があります。たとえば、2Sum アルゴリズムと Fast2Sumアルゴリズムはどちらも、浮動小数点数自体として浮動小数点加算演算の誤差が何であったかを正確に計算するために、丸め誤差の後にこのようなキャンセルに依存しています。

関数 は 、点 で単純に評価された場合 、を丸める際に の桁のほとんどが失われます。しかし、関数 自体は付近の入力では条件が整っています。これを と書き直すと、 での 相殺を利用して、 直接評価した 場合の誤差を回避できます 。 ^[2] これが機能するのは、分子での相殺 と分母での相殺が 互いに打ち消し合うためです。関数は ゼロ付近で条件が整っており、 を 適切に近似し 、したがって を 適切に近似します 。 ${\displaystyle \log(1+x)}$${\displaystyle 0<x\lll 1}$${\displaystyle x}$${\displaystyle \operatorname {fl} (1+x)}$${\displaystyle \log(1+x)}$${\displaystyle 0}$$${\displaystyle \log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}}$$${\displaystyle {\hat {x}}:=\operatorname {fl} (1+x)-1}$${\displaystyle \log(1+x)}$${\displaystyle \log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})}$${\displaystyle {\hat {x}}=\operatorname {fl} (1+x)-1}$${\displaystyle \mu (\xi )=\log(1+\xi )/\xi }$${\displaystyle \mu ({\hat {x}})}$${\displaystyle \mu (x)}$${\displaystyle x\cdot \mu ({\hat {x}})}$${\displaystyle x\cdot \mu (x)=\log(1+x)}$