2.2 Interpolation on a grid

A grid X on the interval [− 1,1] is a set of N + 1 points xi ∈ [− 1, 1], 0 ≤ i ≤ N. These points are called the nodes of the grid X.

Let us consider a continuous function f and a family of grids X with N + 1 nodes xi. Then, there exists a unique polynomial of degree N, X IN f, that coincides with f at each node:

IXN f (xi) = f (xi) 0 ≤ i ≤ N. (19 )

X INf is called the interpolant of f through the grid X. X INf can be expressed in terms of the Lagrange cardinal polynomials:

N X ∑ X IN f = f (xi) ℓi (x ), (20 ) i=0
where ℓXi are the Lagrange cardinal polynomials. By definition, ℓXi is the unique polynomial of degree N that vanishes at all nodes of the grid X, except at xi, where it is equal to one. It is easy to show that the Lagrange cardinal polynomials can be written as
∏N ℓX (x ) = x-−-xj-. (21 ) i j=0,j⁄=i xi − xj
Figure 2View Image shows some examples of Lagrange cardinal polynomials. An example of a function and its interpolant on a uniform grid can be seen in Figure 3View Image.
View Image

Figure 2: Lagrange cardinal polynomials ℓX 3 (red curve) and ℓX 7 on an uniform grid with N = 8. The black circles denote the nodes of the grid.
View Image

Figure 3: Function f = cos3(πx ∕2) + (x + 1)3 ∕8 (black curve) and its interpolant (red curve)on a uniform grid of five nodes. The blue circles show the position of the nodes.

Thanks to Chebyshev alternate theorem, one can see that the best approximation of degree N is an interpolant of the function at N + 1 nodes. However, in general, the associated grid is not known. The difference between the error made by interpolating on a given grid X can be compared to the smallest possible error for the best approximation. One can show that (see Prop. 7.1 of [178Jump To The Next Citation Point]):

∥ ∥ ∥f − IXN f∥∞ ≤ (1 + ΛN (X ))∥f − p⋆N∥∞ , (22 )
where Λ is the Lebesgue constant of the grid X and is defined as:
N∑ | X | ΛN (X ) = maxx ∈[− 1,1] |ℓi (x)|. (23 ) i=0

A theorem by Erdös [72] states that, for any choice of grid X, there exists a constant C > 0 such that:

2 ΛN (X ) > --ln (N + 1) − C. (24 ) π
It immediately follows that ΛN → ∞ when N → ∞. This is related to a result from 1914 by Faber [73Jump To The Next Citation Point] that states that for any grid, there always exists at least one continuous function f, whose interpolant does not converge uniformly to f. An example of such failure of convergence is show in Figure 4View Image, where the convergence of the interpolant to the function 1 f = --------2 1 + 16x is clearly nonuniform (see the behavior near the boundaries of the interval). This is known as the Runge phenomenon.
View Image

Figure 4: Function ----1---- f = 1 + 16x2 (black curve) and its interpolant (red curve) on a uniform grid of five nodes (left panel) and 14 nodes (right panel). The blue circles show the position of the nodes.

Moreover, a theorem by Cauchy (theorem 7.2 of [178]) states that, for all functions (N+1 ) f ∈ 𝒞, the interpolation error on a grid X of N + 1 nodes is given by

X fN+1 (𝜖) X f (x ) − IN f (x) = (N-+-1)!w N+1 (x), (25 )
where 𝜖 ∈ [− 1,1]. wXN+1 is the nodal polynomial of X, being the only polynomial of degree N + 1, with a leading coefficient of 1, and that vanishes on the nodes of X. It is then easy to show that
N wX (x) = ∏ (x − x ). (26 ) N+1 i i=0

In Equation (25View Equation), one has a priori no control on the term involving fN+1. For a given function, it can be rather large and this is indeed the case for the function f shown in Figure 4View Image (one can check, for instance, that || N+1 || f (1) becomes larger and larger). However, one can hope to minimize the interpolation error by choosing a grid such that the nodal polynomial is as small as possible. A theorem by Chebyshev states that this choice is unique and is given by a grid, whose nodes are the zeros of the Chebyshev polynomial TN+1 (see Section 2.3 for more details on Chebyshev polynomials). With such a grid, one can achieve

∥ X ∥ 1 ∥w N+1∥∞ = 2N-, (27 )
which is the smallest possible value (see Equation (18), Section 4.2, Chapter 5 of [122]). So, a grid based on nodes of Chebyshev polynomials can be expected to perform better that a standard uniform one. This is what can be seen in Figure 5View Image, which shows the same function and its interpolants as in Figure 4View Image, but with a Chebyshev grid. Clearly, the Runge phenomenon is no longer present. One can check that, for this choice of function f, the uniform convergence of the interpolant to the function is recovered. This is because ∥ X ∥ ∥wN+1 ∥∞ decreases faster than N+1 f ∕ (N + 1)! increases. Of course, Faber’s result implies that this cannot be true for all the functions. There still must exist some functions for which the interpolant does not converge uniformly to the function itself (it is actually the class of functions that are not absolutely continuous, like the Cantor function).
View Image

Figure 5: Same as Figure 4View Image but using a grid based on the zeros of Chebyshev polynomials. The Runge phenomenon is no longer present.

  Go to previous page Go up Go to next page