Editing Round-off error (section)

== Accumulation of roundoff error ==

Errors can be magnified or accumulated when a sequence of calculations is applied on an initial input with roundoff error due to inexact representation.

=== Unstable algorithms ===

An algorithm or numerical process is called '''stable''' if small changes in the input only produce small changes in the output, and '''unstable''' if large changes in the output are produced.<ref name="Collins_2005">{{cite web |author-last=Collins |author-first=Charles |title=Condition and Stability |url=https://www.math.utk.edu/~ccollins/M577/Handouts/cond_stab.pdf |website=Department of Mathematics in University of Tennessee |date=2005 |access-date=2018-10-28}}</ref> For example, the computation of <math>f(x) = \sqrt{1 + x} - 1</math> using the "obvious" method is unstable near <math>x = 0</math> due to the large error introduced in subtracting two similar quantities, whereas the equivalent expression <math>\textstyle{f(x) = \frac{x}{\sqrt{1+x} + 1}}</math> is stable.<ref name="Collins_2005"/>

=== Ill-conditioned problems ===

Even if a stable algorithm is used, the solution to a problem may still be inaccurate due to the accumulation of roundoff error when the problem itself is '''ill-conditioned'''.

The [[condition number]] of a problem is the ratio of the relative change in the solution to the relative change in the input.<ref name="Forrester_2018"/> A problem is '''well-conditioned''' if small relative changes in input result in small relative changes in the solution. Otherwise, the problem is '''ill-conditioned'''.<ref name="Forrester_2018"/> In other words, a problem is '''ill-conditioned''' if its conditions number is "much larger" than 1.

The condition number is introduced as a measure of the roundoff errors that can result when solving ill-conditioned problems.<ref name="Chapra_2012"/>