I am reading the Handbook of Floating Point Arithmetic1 these days and I am shocked by the impacts of rounding error. Here is a short summary of reading.

In this book a recurrence is used to illustrate the strange behaviors:

Given initial conditions, can be computed iteratively. However, as it is shown by the book, the result is not correct.

In fact, by solving this recurrence analytically we can get:

( This paper2 shows how to solve this recurrence. In general, it substitutes into the original equation and transforms it into a linear recurrence:

which can be solved easily by computing the roots of its characteristic polynomial. )

According to the chosen initial conditions( and ), The coefficient should be zero but it was not due to the rounding error. Even this coefficient is really small(see the paper2), we get the incorrect answer because the “eigenvalue” dominates the result.

Comments

Previously in the Painless Conjugate Gradient paper3 I have seen how eigenvalues(spectrum radius) affect the convergence.

It seems that the issue of stability is very common in the iterative computation. And the eigenvalues play a decisive role.

References

  1. Muller, Jean-Michel, et al. Handbook of floating-point arithmetic. Springer Science & Business Media, 2009.

  2. How Futile are Mindless Assessments of Roundoff in Floating-Point Computation? 2

  3. Shewchuk, Jonathan Richard. “An introduction to the conjugate gradient method without the agonizing pain.” (1994).