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
.
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.
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
,
while in the result of the first, supposedly exact calculation, there is no longer a single correct digit.
Assuming that in and the first four digits are still correct, this results
,
whereas above we traded with an absolute error of and thus a relative error of about 10%.
Example: Archimedes' algorithm for calculating circle numbers
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:
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 .
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 ):
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:
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).
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
With
It results:
Of course, it is a lucky coincidence that the subtraction “is canceled” in the numerator. Now the calculation goes as desired:
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.
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.
Differential calculus
In the numerical calculation of derivatives through difference quotients such as
If the h is too small, extinction occurs because the function values are then almost the same.
Individual evidence
- ↑ 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).