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

3451 reads
Subscribe

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)