Thursday, April 21, 2016

Thoughts on Truncation and Round-off Errors

In scientific computing or numerical analysis, truncation and roundoff errors pop up all over the place. In some operations the former dominates, in others it is the latter, and in a few others, they both conspire in surprising ways.

Truncation error is "is the error made by truncating an infinite sum and approximating it by a finite sum". Or as I sometimes like to say, "somewhere a Taylor series is truncated, and it is not happy!" 

For example, in numerical quadrature, different Newton-Cotes formulas may be derived by locally "fitting" the integrand function with polynomial approximations (Taylor series), and computing the area under the polynomial, since it is much easier to do.

In the solution of ordinary differential equations using Runge-Kutta or linear multistep methods, one tries to perform a term-by-term comparison with a Taylor series expansion, and use polynomial interpolation of the recent past, respectively, to develop different formulas.

In these operations, from a practical standpoint, truncation error dominates!

Roundoff error is the difference between a mathematical number and its finite precision computer representation. It is purely an artifact of the fixed word size used in modern computers. It often dominates the conversation, when subtraction of nearly equal numbers is carried out numerically.

For instance, in solving a system of linear equations, the idea is to take linear combinations of equations to subtract and zero out certain coefficients. In linear systems, there is clearly no Taylor series, and roundoff error is the root cause of ill-conditioning. In fact, if we had infinitely precise number representation on computers, it might be argued that we don't have to worry about conditioning at all!

Since linear systems are at the root of nearly all problems in scientific computing, round-off error is always lurking around the corner.

There are some spectacular cases like numerical differentiation where both roundoff error and truncation error play an "equally" important role. In deriving finite difference formulae, we truncate appropriate Taylor expansions. Furthermore, the derivative itself involves ratios of differences of nearly identical terms.

No comments: