World Library  
Flag as Inappropriate
Email this Article

Catastrophic cancellation

Article Id: WHEBN0019985542
Reproduction Date:

Title: Catastrophic cancellation  
Author: World Heritage Encyclopedia
Language: English
Subject: Algorithms for calculating variance
Publisher: World Heritage Encyclopedia

Catastrophic cancellation

Loss of significance is an undesirable effect in calculations using floating-point arithmetic. It occurs when an operation on two numbers increases relative error substantially more than it increases absolute error, for example in subtracting two nearly equal numbers (known as catastrophic cancellation). The effect is that the number of accurate (significant) digits in the result is reduced unacceptably. Ways to avoid this effect are studied in numerical analysis.

Demonstration of the problem

The effect can be demonstrated with decimal numbers. The following example demonstrates loss of significance for a decimal floating-point data type with 10 significant digits:

Consider the decimal number


A floating-point representation of this number on a machine that keeps 10 floating-point digits would be


which is fairly close – the difference is very small in comparison with either of the two numbers.

Now perform the calculation

   0.1234567891234567890 − 0.1234567890

The answer, accurate to 10 digits, is


However, on the 10-digit floating-point machine, the calculation yields

   0.1234567891 − 0.1234567890 = 0.0000000001

Whereas the original numbers are accurate in all of the first (most significant) 10 digits, their floating-point difference is only accurate in its first nonzero digit. This amounts to loss of significance.


It is possible to do computations using an exact fractional representation of rational numbers and keep all significant digits, but this is often prohibitively slower than floating-point arithmetic. Furthermore, it usually only postpones the problem: What if the data are accurate to only ten digits? The same effect will occur.

One of the most important parts of numerical analysis is to avoid or minimize loss of significance in calculations. If the underlying problem is well-posed, there should be a stable algorithm for solving it. The art is in finding it.

Loss of significant bits

Let x and y be positive normalized floating point numbers.

In the subtraction xy, r significant bits are lost where

q \le r \le p
2^{-p} \le 1 - \frac{y}{x} \le 2^{-q}

for some positive integers p and q.

Instability of the quadratic equation

For example, consider the quadratic equation:

a x^2 + b x + c = 0,

with the two exact solutions:

x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}.

This formula may not always produce an accurate result. For example, when c is very small, loss of significance can occur in either of the root calculations, depending on the sign of b.

The case a = 1, b = 200, c = -0.000015 will serve to illustrate the problem:

x^2 + 200 x - 0.000015 = 0.

We have

\sqrt{b^2 - 4 a c} = \sqrt{200^2 + 4 \times 1 \times 0.000015} = 200.00000015...

In real arithmetic, the roots are

( -200 - 200.00000015 ) / 2 = -200.000000075,
( -200 + 200.00000015 ) / 2 = 0.000000075.

In 10-digit floating-point arithmetic,

( -200 - 200.0000001 ) / 2 = -200.00000005,
( -200 + 200.0000001 ) / 2 = 0.00000005.

Notice that the solution of greater magnitude is accurate to ten digits, but the first nonzero digit of the solution of lesser magnitude is wrong.

Because of the subtraction that occurs in the quadratic equation, it does not constitute a stable algorithm to calculate the two roots.

A better algorithm

A careful floating point computer implementation combines several strategies to produce a robust result. Assuming the discriminant, b2 − 4ac, is positive and b is nonzero, the computation would be as follows:[1]


x_1 &= \frac{-b - \sgn (b) \,\sqrt {b^2-4ac}}{2a}, \\ x_2 &= \frac{2c}{-b - \sgn (b) \,\sqrt {b^2-4ac}} = \frac{c}{ax_1}. \end{align}

Here sgn denotes the sign function, where sgn(b) is 1 if b is positive and −1 if b is negative. This avoids cancellation problems between b and the square root of the discriminant by ensuring that only numbers of the same sign are added.

To illustrate the instability of the standard quadratic formula versus this variant formula, consider a quadratic equation with roots 1.786737589984535 and 1.149782767465722 \times 10^{-8}. To sixteen significant figures, roughly corresponding to double-precision accuracy on a computer, the monic quadratic equation with these roots may be written as:

x^2 - 1.786737601482363 x + 2.054360090947453 \times 10^{-8} = 0

Using the standard quadratic formula and maintaining sixteen significant figures at each step, the standard quadratic formula yields

\sqrt{\Delta} = 1.786737578486707
x_1 = (1.786737601482363 + 1.786737578486707) / 2 = 1.786737589984535
x_2 = (1.786737601482363 - 1.786737578486707) / 2 = 0.000000011497828

Note how cancellation has resulted in x_2 being computed to only eight significant digits of accuracy. The variant formula presented here, however, yields the following:

x_1 = (1.786737601482363 + 1.786737578486707) / 2 = 1.786737589984535
x_2 = 2.054360090947453 \times 10^{-8} / 1.786737589984535 = 1.149782767465722 \times 10^{-8}

Note the retention of all significant digits for x_2 .

Note that while the above formulation avoids catastrophic cancellation between b and \scriptstyle\sqrt{b^2-4ac}, there remains a form of cancellation between the terms b^2 and -4ac of the discriminant, which can still lead to loss of up to half of correct significant figures.[2][3] The discriminant b^2-4ac needs to be computed in arithmetic of twice the precision of the result to avoid this (e.g. quad precision if the final result is to be accurate to full double precision).[4] This can be in the form of a fused multiply-add operation.[2]

To illustrate this, consider the following quadratic equation, adapted from Kahan (2004):[2]

94906265.625x^2 - 189812534x + 94906268.375

This equation has \Delta = 7.5625 and has roots

x_1 = 1.000000028975958
x_2 = 1.000000000000000 .

However, when computed using IEEE 754 double-precision arithmetic corresponding to 15 to 17 significant digits of accuracy, \Delta is rounded to 0.0, and the computed roots are

x_1 = 1.000000014487979
x_2 = 1.000000014487979

which are both false after the eighth significant digit. This is despite the fact that superficially, the problem seems to require only eleven significant digits of accuracy for its solution.

See also


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.