Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Catastrophic cancellation
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.