Catastrophic cancellation

Original article: w:Catastrophic cancellation

수치 해석(numerical analysis)에서, 치명적 취소(catastrophic cancellation)는 두 개의 가까운 숫자에 대한 좋은 근사를 빼면 원래 숫자의 차이에 대해 매우 나쁜 근사를 산출할 수 있는 현상입니다.

예를 들어, 두 개의 기둥이 있으며, 하나가 $L_{1}=253.5\,{\text{cm}}$ 길이이고 다른 하나가 $L_{2}=252.5\,{\text{cm}}$ 길이이고, 그것들이 센티미터까지만 적합한 자로 측정되면, 근사는 ${\tilde {L}}_{1}=254\,{\text{cm}}$와 ${\tilde {L}}_{2}=252\,{\text{cm}}$가 될 수 있습니다. 이것들은 실제 길이에 대한, 상대 오차(relative error)에서, 좋은 근사일 수 있습니다: 근사는 오차에서 실제 길이의 2% 미만, $|L_{1}-{\tilde {L}}_{1}|/|L_{1}|<2\%$입니다.

어쨌든, 만약 근사적인 길이는 빼면, 그 차이는 ${\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}$일 것이지만, 심지어 길이 사이의 실제 차이는 $L_{1}-L_{2}=253.5\,{\text{cm}}-252.5\,{\text{cm}}=1\,{\text{cm}}$입니다. 근사의 차이 $2\,{\text{cm}}$는 실제 값의 차이 크기 $1\,{\text{cm}}$의 100%만큼 오차입니다.

치명적 취소는 입력의 크기에 영향을 받지 않습니다—그것은 크고 작은 입력에 똑같이 적용됩니다. 그것은 차이의 크기와 입력 오차에 따라 달라집니다. $52.5\,{\text{cm}}$와 $53.5\,{\text{cm}}$에 대한 근사로 $54\,{\text{cm}}$에서 $52\,{\text{cm}}$를 빼거나, $2.000525\,{\text{km}}$와 $2.000535\,{\text{km}}$에 대한 근사로 $2.00054\,{\text{km}}$에서 $2.00052\,{\text{km}}$를 빼면 정확하게 같은 오차가 발생합니다.

위의 예제에서와 같이, 차이가 정확하게 계산되더라도 치명적 취소가 발생할 수 있습니다—이는 부동-점 산술(floating-point arithmetic)과 같은 특정 종류의 산술 속성이 아닙니다; 오히려, 그것은 입력이 자체로 근사일 때 뺄셈에 내재되어 있습니다. 실제로, 부동-점 산술에서, 입력이 충분히 가까울 때, 부동-점 차이는 스테벤츠 보조정리(Sterbenz lemma)에 의해 정확하게 계산됩니다—부동-점 뺄셈 연산에 의해 도입되는 반올림 오차는 없습니다.

Formal analysis

형식적으로, 치명적 취소는 뺄셈이 입력 근처에서 나쁜-조건되기 때문에 발생합니다: 심지어 근사 ${\tilde {x}}=x(1+\delta _{x})$와 ${\tilde {y}}=y(1+\delta _{y})$가 각각 참 값 $x$와 $y$로부터 작은 상대 오차(relative errors) $|\delta _{x}|=|x-{\tilde {x}}|/|x|$와 $|\delta _{y}|=|y-{\tilde {y}}|/|y|$를 가지더라도, 참 값의 차이 $x-y$로부터 근사의 차이 ${\tilde {x}}-{\tilde {y}}$의 상대 오차는 참 값의 차이에 반비례합니다:

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

따라서, 참 값의 차이 $x-y$로부터 근사의 정확한 차이 ${\tilde {x}}-{\tilde {y}}$의 상대 오차는 다음과 같습니다:

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

이는 참 값 $x$와 $y$가 가까우면 임의적으로 커질 수 있습니다.

In numerical algorithms

부동-점 산술에서 가까운 숫자를 빼는 것이 항상 치명적 취소 또는 어떤 오류를 유발하는 것은 아닙니다—스테벤츠 보조정리(Sterbenz lemma)에 의해, 만약 숫자가 충분히 가깝다면, 부동-점 차이는 정확합니다. 그러나 취소는 다른 부동-점 산술에서 반올림으로 인해 발생한 입력에서 오차를 증폭시킬 수 있습니다.

Example: Difference of squares

숫자 $x$와 $y$가 주어지면, 부동-점 산술 $\operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))$에 의해 수학 함수 $x^{2}-y^{2}$를 계산하려는 순진한 시도는 $x$와 $y$가 크기에서 가까울 때 치명적인 취소의 대상이 되는데, 왜냐하면 뺄셈은 제곱에서 반올림 오류를 노출할 수 있기 때문입니다. 부동-점 산술 $\operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))$에 의해 평가되는 대안적인 인수화 $(x+y)(x-y)$는 치명적 취소를 방지하는데, 왜냐하면 그것은 뺄셈에서 이어지는 반올림 오차 도입을 방지하기 때문입니다.

예를 들어, $x=1+2^{-29}\approx 1.0000000018626451$이고 $y=1+2^{-30}\approx 1.0000000009313226$이면, 차이 $x^{2}-y^{2}$의 참 값은 $x^{2}-y^{2}$입니다. IEEE 754 binary64 산술에서, 대안적인 인수화 $(x+y)(x-y)$를 평가하는 것은 (반올림 없이) 정확한 결과를 제공하지만, 순진한 표현 $x^{2}-y^{2}$을 평가하는 것은 부동-점 숫자 $2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}$를 제공하며, 그 중 절반 미만의 자릿수가 정확하고 나머지 (밑줄이 그어진) 자릿수는 중간 제곱 값을 계산할 때 반올림으로 인해 손실된 누락된 항 $2^{-59}+2^{-60}$을 반영합니다.

Example: Complex arcsine

복소 아크사인(complex arcsine) 함수를 계산할 때, 다음 로그 공식을 직접 사용하고 싶은 유혹을 느낄 수 있습니다:

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

어쨌든, $y\ll 0$에 대해 $z=iy$를 가정합니다. 그런-다음 ${\sqrt {1-z^{2}}}\approx -y$이고 $iz=-y$입니다; 그것들 사이의 차이를 $\varepsilon$라고 부르며, 이 숫자는 거의 0에 가까운 매우 작은 차이입니다. 만약 ${\sqrt {1-z^{2}}}$가 임의의 오차 $\delta \neq 0$를 갖는 다음을 제공하는 부동-점 산술에서 평가되면,

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

여기서 $\operatorname {fl} (\cdots )$는 부동-점 반올림을 나타내며, 둘 다 $-y$에 매우 가까운, 서로 가까운 두 개의 숫자의 다음 차이를 계산하는 것은

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

하나의 입력에서 오류 $\delta$를 $1/\varepsilon$의 계수로 증폭할 수 있습니다—이는 $\varepsilon$가 거의 0이기 때문에 매우 큰 인수입니다. 예를 들어, $z=-1234567i$이면, $\arcsin(z)$의 실제 값은 근사적으로 $-14.71937803983977i$이지만, IEEE 754 binary64 산술에서 순진한 로그 공식을 사용하면 $-14.719{\underline {644263563968}}i$를 제공하며, 16 자릿수 중 5 자릿수만 정확하고 남은 부분 (밑줄 그어진)은 모든 쓰레기입니다.

$y<0$에 대해 $z=iy$의 경우에서, 항등식 $\arcsin(z)=-\arcsin(-z)$을 사용하는 것은 취소를 방지하는데 왜냐하면 ${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$이지만 $i(-z)=-iz=y$이므로, 뺄셈은 뺄셈은 취소되지 않는 같은 부호로 사실상 덧셈입니다.

Example: Radix conversion

소프트웨어 프로그램의 숫자 상수는 종종 C 조각 double x = 1.000000000000001과 같이 십진수로 작성됩니다; x라는 IEEE 754 binary64 변수를 선언하고 초기화하는 것입니다. 어쨌든, $1.000000000000001$은 binary64 부동-점 숫자가 아닙니다; 이 조각에서 x가 초기화될 가장 가까운 값은 $1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}$입니다. 비록 10진수 부동-점에서 2진수 부동-점으로의 기수 변환은 작은 상대 오류만 발생하지만, 치명적 취소로 인해 훨씬 더 큰 오류로 증폭될 수 있습니다:

double x = 1.000000000000001;  // rounded to 1 + 5*2^{-52}
double y = 1.000000000000002;  // rounded to 1 + 9*2^{-52}
double z = y - x;              // difference is exactly 4*2^{-52}

차이 $1.000000000000002-1.000000000000001$는 $0.000000000000001=1.0\times 10^{-15}$입니다. $1.000000000000001$에서 x와 $1.000000000000002$에서 y의 상대 오차는 둘 다 $10^{-15}=0.0000000000001\%$ 미만이고, 부동-점 뺄셈 y - x은 스테벤츠 보조정리에 의해 정확하게 계산됩니다.

그러나 비록 입력이 좋은 근사치이고, 뺄셈이 정확하게 계산되더라도, 근사의 차이 ${\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}$은 십진수로 쓰일 때 원래 값의 차이 $1.0\times 10^{-15}$에서 $11\%$ 이상의 상대 오차를 가집니다: 치명적 취소는 기수 변환에서 작은 오차를 출력에서 큰 오차로 증폭시켰습니다.

Benign cancellation

취소는 때때로 수치 알고리듬에서 유용하고 바람직합니다. 예를 들어, 2Sum 및 Fast2Sum 알고리듬은 모두 부동-점 숫자 자체로서 부동-점 덧셈 연산에서 오차가 무엇인지 정확하게 계산하기 위해 반올림 오차 후 그러한 취소에 의존합니다.

함수 $\log(1+x)$는, 점 $0<x\lll 1$에서 순진하게 평가되면, $\operatorname {fl} (1+x)$를 반올림할 때 $x$의 자릿수 대부분을 잃게 됩니다. 어쨌든, 함수 $\log(1+x)$ 자체는 0에 가까운 입력에서 바른-조건(well-conditioned)됩니다. 그것을 다음과 같이 다시 작성하면,$$\log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}$$ ${\hat {x}}:=\operatorname {fl} (1+x)-1$에서 취소를 이용하여 직접 평가되는 $\log(1+x)$에서 오차를 방지합니다. 이것은 분자 $\log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})$에서 취소와 분모 ${\hat {x}}=\operatorname {fl} (1+x)-1$에서 취소가 서로 상쇄되기 때문에 작동합니다; 함수 $\mu (\xi )=\log(1+\xi )/\xi$는 $\mu ({\hat {x}})$가 $\mu (x)$에 대한 좋은 근사를 제공하고 따라서 $x\cdot \mu ({\hat {x}})$가 $x\cdot \mu (x)=\log(1+x)$에 대한 좋은 근사를 제공하는 영 근처에서 충분히-바르게 조건됩니다.