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
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
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- Adding interpolation points can increase error
- Chebyshev interpolation
- Linear interpolation calculator
[1] Numerical Methods and Computing by Ward Cheney and David Kincaid.
The post Tables and interpolation first appeared on John D. Cook.