Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Catastrophic cancellation
Summary
In numerical analysis, catastrophic cancellation is the phenomenon that subtracting good approximations to two nearby numbers may yield a very bad approximation to the difference of the original numbers.
For example, if there are two studs, one long and the other long, and they are measured with a ruler that is good only to the centimeter, then the approximations could come out to be and .
These may be good approximations, in relative error, to the true lengths: the approximations are in error by less than 2% of the true lengths, .
However, if the approximate lengths are subtracted, the difference will be , even though the true difference between the lengths is .
The difference of the approximations, , is in error by 100% of the magnitude of the difference of the
true values, .
Catastrophic cancellation isn't affected by how large the inputs are—it applies just as much to large and small inputs.
It depends only on how large the difference is, and on the error of the inputs.
Exactly the same error would arise by subtracting from as approximations to and , or by subtracting from as approximations to and .
Catastrophic cancellation may happen even if the difference is computed exactly, as in the example above—it is not a property of any particular kind of arithmetic like floating-point arithmetic; rather, it is inherent to subtraction, when the inputs are approximations themselves. Indeed, in floating-point arithmetic, when the inputs are close enough, the floating-point difference is computed exactly, by the Sterbenz lemma—there is no rounding error introduced by the floating-point subtraction operation.
Formally, catastrophic cancellation happens because subtraction is ill-conditioned at nearby inputs: even if approximations and have small relative errors and from true values and , respectively, the relative error of the difference of the approximations from the difference of the true values is inversely proportional to the difference of the true values:
Thus, the relative error of the exact difference of the approximations from the difference of the true values is
which can be arbitrarily large if the true values and are close.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.