Rounding errors
I am reading the Handbook of Floating Point Arithmetic^{1} 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 paper^{2} 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 paper^{2}), we get the incorrect answer because the “eigenvalue” dominates the result.
Comments
Previously in the Painless Conjugate Gradient paper^{3} 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

Muller, JeanMichel, et al. Handbook of floatingpoint arithmetic. Springer Science & Business Media, 2009. ↩

How Futile are Mindless Assessments of Roundoff in FloatingPoint Computation? ↩ ↩^{2}

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