NavList:

   

Reply

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.

   

Reply