Chapter 4: Summation
Overview
I do hate sums. There is no greater mistake than to call arithmetic an exact science. There are ... hidden laws of Number which it requires a mind like mine to perceive. For instance, if you add a sum from the bottom up, and then again from the top down, the result is always different.
- MRS. LA TOUCHE [7]
Joseph Fourier introduced this delimited ?-notation in 1820, and it soon took the mathematical world by storm.
- RONALD L. GRAHAM, DONALD E. KNUTH, and OREN PATASHNIK, Concrete Mathematics (1994)
One of the major difficulties in a practical [error] analysis is that of description. An ounce of analysis follows a pound of preparation.
- BERESFORD N. PARLETT, Matrix Eigenvalue Problems (1965)
[7]Quoted in Mathematical Gazette [819, 1924].
Overview
Sums of floating point numbers are ubiquitous in scientific computing. They occur when evaluating inner products, means, variances, norms, and all kinds of nonlinear functions. Although at first sight summation might appear to offer little scope for algorithmic ingenuity, the usual "recursive summation" (with various orderings) is just one of a variety of possible techniques. We describe several summation methods and their error analyses in this chapter. No one method is uniformly more accurate than the others, but some guidelines can be given on the choice of method in particular cases.
4.1 Summation Methods
In most circumstances in scientific computing we would naturally translate a sum ? n i=1 x i into code of...