Tables and interpolation

The previous post about hand calculations involved finding the logarithm of a large integer using only tables.

We wanted to know the log base 10 of 8675310 and all we had was a table of logarithms of integers up to 1350. We used

log10 867 = 2.9380190975
log10 868 = 2.9385197252

and linear interpolation to estimate

log10 867.5310 = 2.9382849308.

How accurate is this estimate? How might we get more accuracy?

Nobody looks up logarithms in a table any more, but interpolation is still commonly used to estimate the value of a function at points you haven’t computed (or measured).

Here’s a theorem that will let us estimate the error in our interpolation. See, for example, [1].

Let f be a function with n+1 continuous derivatives on [a, b] with

|f^{(n+1)}(x)| \leq M

on [a, b]. Let p be the polynomial of degree at most n that interpolates f at n+1 evenly spaced nodes on [a, b]. Then

|f(x) - p(x)| \leq \frac{M}{4(n+1)} \left( \frac{b-a}{n}\right)^{n+1}

In our case the function we’re interpolating is

f(x) = log10 x = log(x)/log(10).

We have a = 867, b = 868, and n = 1. The second derivative of f is given by

f ” (x) = − x−2/log(10)

and so the upper bound M in our theorem is

1/(8672 log(10)) = 5.7776 × 10−7.

It follows that the theoretical bound on our error is 7.222×10−7. The actual error is 7.186×10−7, close to the theoretical bound.

If we use quadratic interpolation at three points rather than linear interpolation at two points, our theoretical error bound becomes smaller because M is smaller: the third derivative of f involves x−3 rather than x−2. However, we’re unlikely to actually reduce our error much because of numerical error.

Interpolation involves subtracting function values at each of the interpolation points. We know these values to 11 significant figures, but they agree to 4 significant figures, so we can only expect 7 significant figures in their differences. This means that the linear interpolation error is on the same order of magnitude as numerical error. Higher order interpolation is unlikely to improve computational accuracy even though it reduces approximation error because numerical error becomes the limiting factor.

More interpolation posts

[1] Numerical Methods and Computing by Ward Cheney and David Kincaid.