수치 해석(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\)의 상대 오차는 참 값의 차이에 반비례합니다:
\(\quad
\begin{align}
\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{align}
\)
따라서, 참 값의 차이 \(x - y\)로부터 근사의 정확한 차이 \(\tilde x - \tilde y\)의 상대 오차는 다음과 같습니다:
\(\quad\displaystyle \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) 함수를 계산할 때, 다음 로그 공식을 직접 사용하고 싶은 유혹을 느낄 수 있습니다:
\(\quad
\arcsin(z) = i \log \bigl(\sqrt{1 - z^2} - i z\bigr).
\)
어쨌든, \(y \ll 0\)에 대해 \(z = i y\)를 가정합니다. 그런-다음 \(\sqrt{1 - z^2} \approx -y\)이고 \(i z = -y\)입니다; 그것들 사이의 차이를 \(\varepsilon\)라고 부르며, 이 숫자는 거의 0에 가까운 매우 작은 차이입니다. 만약 \(\sqrt{1 - z^2}\)가 임의의 오차 \(\delta \ne 0\)를 갖는 다음을 제공하는 부동-점 산술에서 평가되면,
\(\quad
\operatorname{fl}\Bigl(\sqrt{\operatorname{fl}(1 - \operatorname{fl}(z^2))}\Bigr)
= \sqrt{1 - z^2}(1 + \delta)
\)
여기서 \(\operatorname{fl}(\cdots)\)는 부동-점 반올림을 나타내며, 둘 다 \(-y\)에 매우 가까운, 서로 가까운 두 개의 숫자의 다음 차이를 계산하는 것은
\(\quad
\sqrt{1 - z^2}(1 + \delta) - i z
\)
하나의 입력에서 오류 \(\delta\)를 \(1/\varepsilon\)의 계수로 증폭할 수 있습니다—이는 \(\varepsilon\)가 거의 0이기 때문에 매우 큰 인수입니다. 예를 들어, \(z = -1234567 i\)이면, \(\arcsin(z)\)의 실제 값은 근사적으로 \(-14.71937803983977i\)이지만, IEEE 754 binary64 산술에서 순진한 로그 공식을 사용하면 \(-14.719\underline{644263563968}i\)를 제공하며, 16 자릿수 중 5 자릿수만 정확하고 남은 부분 (밑줄 그어진)은 모든 쓰레기입니다.
\(y < 0\)에 대해 \(z = i y\)의 경우에서, 항등식 \(\arcsin(z) = -\arcsin(-z)\)을 사용하는 것은 취소를 방지하는데 왜냐하면 <math display="inline">\sqrt{1 - (-z)^2} = \sqrt{1 - z^2} \approx -y\)이지만 \(i (-z) = -i z = 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)됩니다. 그것을 다음과 같이 다시 작성하면,
\(\quad\displaystyle \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)\)에 대한 좋은 근사를 제공하는 영 근처에서 충분히-바르게 조건됩니다.