A Community Devoted to the Preservation and Practice of Celestial Navigation and Other Methods of Traditional Position-Finding
From: Paul Hirose
Date: 2017 Oct 9, 17:02 -0700
Let's look at linear interpolation in a table of sines: sin 45 = .707107 .012233 sin 46 = .719340 (The .012233 is the difference between the adjacent sines.) Suppose we want the sine of 45.5°. That's midway between table entries, so the interpolating factor (often called "p") is 0.5. In a linear interpolation you multiply p and the difference between entries (.012233) to obtain the increment to be added to sin 45. Thus the linearly interpolated sine is .713224. But a calculator says sin 45.5 is actually .713250, so the linear interpolation was good to only 4 digits. The full accuracy of the table can be realized if second differences are applied. Begin by expanding the table to show the first and second differences: sin 44 = .694658 12449 sin 45 = .707107 -216 12233 sin 46 = .719340 -219 12014 sin 47 = .731354 It's common practice to write the differences as integers, so the first difference between sin 45 and sin 46 is simply 12233. The two applicable second differences are -216 and -219. Bessel's interpolation formula is a linear interpolation plus a correction which includes second differences. The interpolating factor p is 0.5 as before. The coefficient B2 is defined as p * (p - 1) / 4. Since p is always between 0 and 1, B2 is always negative. In this case it's -.0625. The Bessel formula is increment = p * 12233 + B2 * (-216 + -219) = 6144 Mentally convert the increment to .006144 and apply it: sin 45.5 = .707107 + .006144 = .713251. That's off by only one unit in the last place. How do you know when to apply second differences? If they are ignored, the maximum error is about 1/8 of the nearest second difference. So in the above example, the max error of a linear interpolation between 45° and 46° should be about 28 units in the last place. Actual error of the linear interpolation was 26. Bessel's formula also provides for higher order differences. Maximum error is 1/120 of the third difference if it's ignored. In my example the third difference is only 3, so its effect would be insignificant. In the old days when tables were computed by hand, interpolation with higher order differences was a big labor saver. A table could be computed with high accuracy but a relatively coarse interval, then the gaps filled by interpolation.