Interpolation and splines · Definition

Interpolation error

numerical methodsinterpolation and splines

Before you start you need to know

When approximating a function by a polynomial, it matters how far that approximation can be off between the nodes. This error is controlled by a formula that combines higher-order derivatives and the position of the points.

Definition

The interpolation error is the difference between \(f(x)\) and the polynomial \(P(x)\) that approximates it at the nodes \(x_0,\dots,x_n\); it depends on \(f^{(n+1)}\) and on \(\prod(x-x_i)\).

\[f(x)-P_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)\]

The error formula states that, if f is n+1 times continuously differentiable on \([a,b]\), there exists \(\xi\) in the interval such that the error at x is \(\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)\). Its proof applies Rolle's theorem repeatedly to an auxiliary function that vanishes at all nodes. The error is zero at each node because the product vanishes there.

For \(f(x)=\sin(x)\) with nodes \(0,\ \pi/2,\ \pi\) and \(n=2\), the bound is \(|f(x)-P_2(x)|\le \frac{1}{3!}\max|\,x(x-\pi/2)(x-\pi)|\). Since \(|\sin^{(3)}|\le 1\), this gives an explicit bound that can be evaluated over the interval of interest.

A typical mistake is forgetting that \(\xi\) depends on x and treating it as a fixed known value. Another is using \((n+1)!\) where \(n!\) belongs, which yields a bound that is too large or too small depending on the case.

Think about it

Why does the error formula give a bound rather than the exact error at a point?

Because \(\xi\) is unknown and only known to lie in the interval, so the formula only lets us bound the error.

Exercises 10

  1. What is the error factor \(\prod_{i=0}^{n}(x-x_i)\) for nodes \(x_0=0,\ x_1=1\)?
  2. What is the value of \((n+1)!\) when \(n=3\)?
  3. In the error formula for the degree-\(n\) interpolant, which derivative of \(f\) appears?
  4. At which points does the interpolation error vanish?
  5. Which theorem is used in the proof of the error formula?
  6. For \(f(x)=e^x\) with nodes \(0,1\) (\(n=1\)), what is the error bound at \(x=0.5\) if \(|f''|\le e\) on \([0,1]\)?
  7. With nodes \(x_0=0,\ x_1=2\) and \(f(x)=x^3\) (\(n=1\)), what is \(\prod(x-x_i)\) at \(x=1\)?
  8. If \(|f'''(x)|\le 6\) and nodes are \(0,1,2\) (\(n=2\)), what is the bound at \(x=0.5\)?
  9. For \(f(x)=\cos(x)\) with nodes \(0,\pi\) (\(n=1\)), what is the bound at \(x=\pi/2\) using \(|f''|\le 1\)?
  10. For \(f(x)=\ln(x)\) with nodes \(1,2,3\) (\(n=2\)), what error bound at \(x=2.5\) follows from \(|f'''(x)|=2/x^3\le 2\) on \([1,3]\)?

What comes next

References

  • Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
  • Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.