Friday, December 17, 2010

Subtracting Large Numbers

One of the most notorious difficulties in numerical computations is the loss of precision when subtracting two similar, large numbers to obtain a smaller one. Russ Hobbie and I illustrate this hazard in Chapter 11 of the 4th edition of Intermediate Physics for Medicine and Biology. We begin this chapter with a discussion of the method of least squares, and we derive the formulas (Eqs. 11.5a and 11.5b) for fitting data to a straight line, y=ax+b. We then add “In doing computations where the range of data is small compared to the mean, better numerical accuracy can be obtained from…” and then present alternative formulas (Eqs. 11.5c, 11.5d, and 11.5e). Homework Problem 7 in Chapter 11 (one of the many new problems in the 4th edition) illustrates the advantage of the second set of equations.
"Problem 7 Consider the data

x y
100 4004
101 4017
102 4039
103 4063

(a) Fit these data with a straight line y=ax+b using Eqs. 11.5a and 11.5b to find a.
(b) Use Eq. 11.5c to determine a. Your result should be the same as in part (a)
(c) Repeat parts (a) and (b) while rounding all the intermediate numbers to 4 significant figures. Do Eqs. 11.5a and 11.5b give the same result as Eq. 11.5c? If not, which is more accurate?"
(Spoiler alert: Don’t continue reading if you want to solve the problem yourself first, as you should.) If you solve this problem, you will find that Eqs. 11.5a and 11.5b do not work very well at all for this problem. Their flaw is that they require you to subtract two really big numbers to get a much smaller one.

A good discussion of this issue can be found in Forman Acton’s book Numerical Methods that Work.
“The following problem often appears as a puzzle in Sunday Supplements. The difficulties are numerical rather than formulative and hence it is an especially appropriate challenge to the aspiring numerical analyst. We strongly urge that the reader solve it in his own way before turning to the ‘official’ solution.

A railroad rail 1 mile long is firmly fixed at both ends. During the night some prankster cuts the rail and welds in an additional foot, causing the rail to bow up in the arc of a circle. The classical question concerns the maximum height this rail now achieves over its former position. To put it more precisely: We are faced…with the chord of a circle AB that is exactly 1 mile long and the corresponding arc AB that is 1 mile plus 1 foot and our question concerns the distance d between the chord and the arc at their midpoints. [See Acton’s book for the accompanying figure]

The relationships available are the simple ones from trigonometry involving the subtended half angle, θ, and the Pythagorean relationship. The student at this point should attempt to solve the problem before turning to the solution given in Chapter 2. He should attempt to find the distance d to an accuracy of three significant figures. In his effort he will probably be faced with subtracting two large and nearly equal numbers, which will cause a horrendous loss of significant figures. He can live with this process by shear brute force, but it will involve use eight-significant-figure trigonometric tables to preserve three figures in his answer. The point of the problem here is to find another method of calculating d, one that does not require such extreme measures. The three-figure answer can, indeed, be obtained rather easily using nothing more than pencil, paper, and a slide rule. The student should seek such a method.”
If you find numerical methods interesting (as I do), you will love Acton’s delightfully written book. Originally published in 1970, it is all the more charming for its now-quaint references to slide rules and trigonometric tables. Yet, the concepts are not out-of-date. Even with powerful computers, errors can arise from subtracting nearly equal numbers. I have run into the issue myself when using the finite difference method and relaxation to solve Laplace’s equation with a fine grid and only single precision arithmetic.

Unfortunately, Acton’s book is not cited in the 4th edition of Intermediate Physics for Medicine and Biology (we’ll have to fix that in later editions), although I have mentioned it before in this blog. Acton is an emeritus professor in the Department of Computer Science at Princeton University (a department with an illustrious history). Also interesting is his more recent book Real Computing Made Real: Preventing Errors in Scientific and Engineering Calculations.

No comments:

Post a Comment