Tricki
a repository of mathematical know-how

Interpolation and approximation

Quick description

Interpolation is the task of finding a function p from a certain class that matches given data (x_1,y_i), i=1,2,\ldots,N. That is,

 p(x_i)=y_i,\qquad i=1,2,\ldots,N.

Typically, p is taken from the set of polynomials of degree \leq d.

Approximation is the task, given a function A\to X, where X is a suitable space, to find a function A\to X taken from a certain class that is in some sense close to f. Often we consider, for example, polynomial interpolation where A is a bounded subset of \R^d and X=\R.

Different measures of closeness can be used for determining how close functions are. The most common are:

\begin{align} \|f-p\|_\infty&=\sup_{a\in A}\|f(a)-p(a)\|,\\ \|f-p\|_2     &=\left[\int_A \|f(a)-p(a)\|^2\,da\right]^{1/2}. \end{align}

In polynomial approximation p is required to be a polynomial of degree \leq d for some fixed d. Often approximations can be found by interpolation: the data used is simply (x_i,f(x_i)), i=1,2,\ldots,N for suitably chosen points x_i.

Prerequisites

Calculus, real analysis.

Example 1

Polynomial interpolation in an interval with data (x_i,y_i), i=1,2,\ldots,N can be done with polynomials of degree \leq d provided that N\geq d+1 and all x_i's are distinct. The interpolant is unique (amongst all polynomials of degree \leq d) provided in addition, N=d+1. There are a number of different ways of computing the polynomial interpolant for N=d+1, including solving linear systems with Van der Monde matrices, Lagrange interpolation polynomials, and Newton divided differences.

If the data for polynomial interpolation comes from a smooth function [a,b]\to\R, then there is a commonly used formula for the error in the interpolant:

 f(x)-p(x) = \frac{f^{(d+1)}(c)}{(d+1)!}\prod_{i=1}^N(x-x_i),

for some c between \min(x,x_1,\ldots,x_N) and \max(x,x_1,\ldots,x_N).

General discussion