Annihilation (numerical math)

Under extinction ( Engl. Cancellation ) is understood in the numerical loss of accuracy when subtracting almost equally large floating point numbers .

Examples

Numerical example

We subtract the numbers and from each other and get as a result ${\displaystyle a=2{,}345678}$ ${\displaystyle b=2{,}346789}$

${\displaystyle b-a=0{,}001111}$.

Come now and be already so are the low-order places affected from previous calculations due to rounding errors. If, however, the higher-order digits of and match, the valid digits are deleted and the difference results exclusively from rounding errors. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 0}$

Assume that the first three digits of and are correct and that all lower-order digits are corrupted by rounding errors. If we shorten the numbers to their correct digits, the result is ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle 2{,}34-2{,}34=0}$,

while in the result of the first, supposedly exact calculation, there is no longer a single correct digit. ${\displaystyle b-a=0{,}001111}$

Assuming that in and the first four digits are still correct, this results ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle 2{,}346-2{,}345=0{,}001}$,

whereas above we traded with an absolute error of and thus a relative error of about 10%. ${\displaystyle b-a=0{,}001111}$ ${\displaystyle 0{,}001111-0{,}001000=0{,}000111}$

Example: Archimedes' algorithm for calculating circle numbers

Calculation of pi according to Archimedes

Archimedes of Syracuse proved that the circumference of a circle is related to its diameter in the same way as the area of ​​the circle is related to the square of the radius. He did not call this ratio (now known as circle number ) π, but gave instructions on how to approach the ratio with the help of inscribed and circumscribed polygons to an arbitrarily high degree of accuracy, probably one of the oldest numerical methods in history. And he performed the calculation up to the 96-point with the following result:

${\displaystyle 3{,}1408450\dots =3+{\frac {10}{71}}<\pi <3+{\frac {10}{70}}=3{,}1428571\dots }$

As you can see from the numerical example, Archimedes had no chance of even noticing the erasure of the 96-sided.

In today's language one begins with directly calculable side lengths of polygons inscribed in a unit circle ( ), e.g. B. the two-corner , the triangle , the square or the hexagon . ${\displaystyle s_{n}=AB}$ ${\displaystyle MA=MB=MC=1}$ ${\displaystyle s_{2}=2}$ ${\displaystyle s_{3}={\sqrt {3}}}$ ${\displaystyle s_{4}={\sqrt {2}}}$ ${\displaystyle s_{6}=1}$

Then, for polygons with double the number of vertices, the length of the sides can easily be derived using the auxiliary segment and twice applying the Pythagorean theorem ( and ): ${\displaystyle s_{2n}=AC}$ ${\displaystyle \rho _{n}=MS}$ ${\displaystyle AM^{2}=MS^{2}+AS^{2},1=\rho _{n}^{2}+s_{n}^{2}/4,\rho _{n}={\sqrt {1-s_{n}^{2}/4}}}$ ${\displaystyle AC^{2}=AS^{2}+SC^{2},s_{2n}^{2}=s_{n}^{2}/4+(1-\rho _{n})^{2}=s_{n}^{2}/4+1-2\rho _{n}+\rho _{n}^{2}}$

${\displaystyle s_{2n}={\sqrt {2-2{\sqrt {1-{\tfrac {s_{n}^{2}}{4}}}}}}}$

With the four basic arithmetic operations and the extraction of the roots, one can therefore, starting with the two-cornered area, calculate the side length and the circumference of an inscribed polygon and thus indirectly an approximation for . In practice, however, the result is disappointing. Starting with n = 2, the following table shows the distance from the center of the page S to the edge of the circle, the lengths of the sides of the inscribed and circumscribed n-gon and their areas and , which should converge in the unit circle . The calculation was carried out in C with double precision according to IEEE 754 and thus approx. 15 decimal places. The numerical values ​​can also be traced back to any pocket calculator that knows square roots: ${\displaystyle \pi }$ ${\displaystyle 1-\rho _{n}}$ ${\displaystyle s_{n}}$ ${\displaystyle S_{n}=A'B'=s_{n}\cdot 1/\rho _{n}}$ ${\displaystyle a_{n}=ns_{n}\rho _{n}/2}$ ${\displaystyle A_{n}=nS_{n}/2}$ ${\displaystyle \pi }$

 ${\displaystyle n}$              ${\displaystyle 1-\rho _{n}}$         ${\displaystyle s_{n}}$          ${\displaystyle S_{n}}$             ${\displaystyle a_{n}}$                  ${\displaystyle A_{n}}$
2          1.000e+00  2.00e+00       Inf  0.00000000000000               Inf
4          2.929e-01  1.41e+00  2.00e+00  2.00000000000000  4.00000000000000
8          7.612e-02  7.65e-01  8.28e-01  2.82842712474619  3.31370849898476
16         1.921e-02  3.90e-01  3.98e-01  3.06146745892072  3.18259787807453
32         4.815e-03  1.96e-01  1.97e-01  3.12144515225805  3.15172490742926
64         1.205e-03  9.81e-02  9.83e-02  3.13654849054593  3.14411838524589
128        3.012e-04  4.91e-02  4.91e-02  3.14033115695474  3.14222362994244
256        7.530e-05  2.45e-02  2.45e-02  3.14127725093262  3.14175036916881
512        1.882e-05  1.23e-02  1.23e-02  3.14151380114509  3.14163208070397
1024       4.706e-06  6.14e-03  6.14e-03  3.14157294036989  3.14160251025961
2048       1.177e-06  3.07e-03  3.07e-03  3.14158772527060  3.14159511774302
4096       2.941e-07  1.53e-03  1.53e-03  3.14159142155216  3.14159326967027
8192       7.353e-08  7.67e-04  7.67e-04  3.14159234553025  3.14159280755978
1.638e+04  1.838e-08  3.83e-04  3.83e-04  3.14159257570956  3.14159269121694
3.277e+04  4.596e-09  1.92e-04  1.92e-04  3.14159264036917  3.14159266924601
6.554e+04  1.149e-09  9.59e-05  9.59e-05  3.14159264171161  3.14159264893082
1.311e+05  2.872e-10  4.79e-05  4.79e-05  3.14159260647332  3.14159260827812
2.621e+05  7.181e-11  2.40e-05  2.40e-05  3.14159291071407  3.14159291116527
5.243e+05  1.795e-11  1.20e-05  1.20e-05  3.14159169662728  3.14159169674009
1.049e+06  4.488e-12  5.99e-06  5.99e-06  3.14159655369072  3.14159655371892
2.097e+06  1.122e-12  3.00e-06  3.00e-06  3.14159655370129  3.14159655370834
4.194e+06  2.804e-13  1.50e-06  1.50e-06  3.14151884046467  3.14151884046643
8.389e+06  7.017e-14  7.49e-07  7.49e-07  3.14120796828205  3.14120796828249
1.678e+07  1.754e-14  3.75e-07  3.75e-07  3.14245127249408  3.14245127249419
3.355e+07  4.441e-15  1.87e-07  1.87e-07  3.14245127249412  3.14245127249415
6.711e+07  1.110e-15  9.42e-08  9.42e-08  3.16227766016838  3.16227766016838
1.342e+08  2.220e-16  4.71e-08  4.71e-08  3.16227766016838  3.16227766016838
2.684e+08  0.000e+00  2.11e-08  2.11e-08  2.82842712474619  2.82842712474619
5.369e+08  0.000e+00  0.00e+00  0.00e+00  0.00000000000000  0.00000000000000

One can clearly see at the beginning the convergence against . After reaching about half the number of digits in the 32768 corner, however, the cancellation becomes noticeable when the almost equally large numbers 2 and are subtracted . The result is now more inaccurate and at the end wrong (2-2.000 ... 000xxx = 0). ${\displaystyle \pi }$ ${\displaystyle 2{\sqrt {1-s_{n}^{2}/4}}}$

In many cases, including this one, one can avoid cancellation simply by avoiding the affected subtractions. Here you can do this by transforming the formula into an equivalent form without subtraction using

${\displaystyle a^{2}-b^{2}=(a+b)(a-b)\rightarrow a-b={\frac {a^{2}-b^{2}}{a+b}}}$

With ${\displaystyle a=2,b=2{\sqrt {1-{\tfrac {s_{n}^{2}}{4}}}}}$

It results:

${\displaystyle s_{2n}={\sqrt {2-2{\sqrt {1-{\frac {s_{n}^{2}}{4}}}}}}={\sqrt {\frac {4-4(1-{\frac {s_{n}^{2}}{4}})}{2+2{\sqrt {1-{\frac {s_{n}^{2}}{4}}}}}}}={\sqrt {2{\frac {1-1+{\frac {s_{n}^{2}}{4}}}{1+{\sqrt {1-{\frac {s_{n}^{2}}{4}}}}}}}}={\sqrt {{\frac {1}{2}}s_{n}^{2}{\frac {1}{1+{\sqrt {1-{\frac {s_{n}^{2}}{4}}}}}}}}}$

Of course, it is a lucky coincidence that the subtraction “is canceled” in the numerator. Now the calculation goes as desired:

 ${\displaystyle n}$              ${\displaystyle 1-\rho _{n}}$         ${\displaystyle s_{n}}$          ${\displaystyle S_{n}}$             ${\displaystyle a_{n}}$                  ${\displaystyle A_{n}}$
2.000e+00  1.000e+00  2.00e+00       Inf  0.00000000000000               Inf
4.000e+00  2.929e-01  1.41e+00  2.00e+00  2.00000000000000  4.00000000000000
8.000e+00  7.612e-02  7.65e-01  8.28e-01  2.82842712474619  3.31370849898476
1.600e+01  1.921e-02  3.90e-01  3.98e-01  3.06146745892072  3.18259787807453
3.200e+01  4.815e-03  1.96e-01  1.97e-01  3.12144515225805  3.15172490742926
6.400e+01  1.205e-03  9.81e-02  9.83e-02  3.13654849054594  3.14411838524590
1.280e+02  3.012e-04  4.91e-02  4.91e-02  3.14033115695475  3.14222362994246
2.560e+02  7.530e-05  2.45e-02  2.45e-02  3.14127725093277  3.14175036916897
5.120e+02  1.882e-05  1.23e-02  1.23e-02  3.14151380114430  3.14163208070318
1.024e+03  4.706e-06  6.14e-03  6.14e-03  3.14157294036709  3.14160251025681
2.048e+03  1.177e-06  3.07e-03  3.07e-03  3.14158772527716  3.14159511774959
4.096e+03  2.941e-07  1.53e-03  1.53e-03  3.14159142151120  3.14159326962931
8.192e+03  7.353e-08  7.67e-04  7.67e-04  3.14159234557012  3.14159280759964
1.638e+04  1.838e-08  3.83e-04  3.83e-04  3.14159257658487  3.14159269209225
3.277e+04  4.596e-09  1.92e-04  1.92e-04  3.14159263433856  3.14159266321541
6.554e+04  1.149e-09  9.59e-05  9.59e-05  3.14159264877699  3.14159265599620
1.311e+05  2.872e-10  4.79e-05  4.79e-05  3.14159265238659  3.14159265419140
2.621e+05  7.181e-11  2.40e-05  2.40e-05  3.14159265328899  3.14159265374019
5.243e+05  1.795e-11  1.20e-05  1.20e-05  3.14159265351459  3.14159265362739
1.049e+06  4.488e-12  5.99e-06  5.99e-06  3.14159265357099  3.14159265359919
2.097e+06  1.122e-12  3.00e-06  3.00e-06  3.14159265358509  3.14159265359214
4.194e+06  2.804e-13  1.50e-06  1.50e-06  3.14159265358862  3.14159265359038
8.389e+06  7.017e-14  7.49e-07  7.49e-07  3.14159265358950  3.14159265358994
1.678e+07  1.754e-14  3.75e-07  3.75e-07  3.14159265358972  3.14159265358983
3.355e+07  4.441e-15  1.87e-07  1.87e-07  3.14159265358978  3.14159265358980
6.711e+07  1.110e-15  9.36e-08  9.36e-08  3.14159265358979  3.14159265358980
1.342e+08  2.220e-16  4.68e-08  4.68e-08  3.14159265358979  3.14159265358979
2.684e+08  0.000e+00  2.34e-08  2.34e-08  3.14159265358979  3.14159265358979

The full accuracy of almost 16 decimal places is already achieved with the 268435456 corner. The abort signal is the 0 in the second column.

Rule of thumb

If you subtract two -digit, almost equally large numbers that match in the first digits, the result is lost from the actually possible digits . So there are only places other than zero. The information that the first digits have canceled each other out to zero is lost. The accuracy of the result is reduced by these places. ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p-k}$ ${\displaystyle k}$ ${\displaystyle k}$

If the figures in the last digits only differ in terms of rounding errors, then the result has no meaningfulness. As such, it should not be included in any further calculations. ${\displaystyle p-k}$

Differential calculus

In the numerical calculation of derivatives through difference quotients such as

${\displaystyle f'(x)\approx {\frac {f(x+h)-f(x)}{h}}}$

If the h is too small, extinction occurs because the function values ​​are then almost the same.

Individual evidence

1. ↑ Wolfgang Dahmen, Arnold Reusken: Numerics for engineers and natural scientists. 2nd Edition. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2 , p. 41 ( limited preview in the Google book search).