8.1 Polynomial interpolation

Although interpolation is not strictly a finite differencing topic, we briefly present it here because it is used below and in Section 9, when discussing spectral methods.

Given a set of (N + 1) distinct points {x }N j j=0 (sometimes referred to as nodal points or nodes) and arbitrary associated function values f(xj), the interpolation problem amounts to finding (in this case) a polynomial ℐN [f ](x) of degree less than or equal to N such that ℐN [f ](xj) = f(xj) for j = 0,1, 2,...,N.

It can be shown that there is one and only one such polynomial. Existence can be shown by explicit construction: suppose one had

N ∑ (N) ℐN [f](x ) = f (xj )lj (x), (8.1 ) j=0
where, for each j = 0,1,...,N, l(jN)(x) is a polynomial of degree less than or equal to N such that
(N) lj (xi) = δij for i = 0,1,...,N. (8.2 )
Then ℐN [f ](x ) as given by Eq. (8.1View Equation) would interpolate f(x) at the (N + 1) nodal points {xi}. The Lagrange polynomials, defined as
( N ) ( N ) −1 (N ) ∏ ∏ lj (x ) = (x − xk ) (xj − xk) , (8.3 ) k=0,k⁄=j k=0,k⁄=j
indeed do satisfy Eq. (8.2View Equation). Uniqueness of the interpolant can be shown by using the property that polynomials of order N can have at most N roots, applied to the difference between any two interpolants.

Defining the interpolation error by

EN (x) = |f(x) − ℐN [f ](x )| (8.4 )
and assuming that f is differentiable enough, it can be seen that EN satisfies
1 (N+1 ) EN (x) = ---------|f (ξx)ωN+1 (x )|, (8.5 ) (N + 1)!
where ∏ ωN+1 (x) := Nj=0(x − xj) is called the nodal polynomial of degree (N + 1 ), and ξx is in the smallest interval ℐx containing {x0,x1,...,xN } and x. In other words, if we assume the ordering x0 < x1 < ...< xN, then x can actually be outside [x0,xN ]. For example, if x < x0, then ℐx = [x,xN ]. Sometimes, approximating f(x ) by ℐN [f](x) when x∈∕ [x0,xN ] is called extrapolation, and interpolation only if x ∈ [x ,x ] 0 N, even though an interpolating polynomial is used as approximation.
  Go to previous page Go up Go to next page