Interpolation on a grid

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:

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

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

Figure 2

shows some examples of Lagrange cardinal polynomials. An example of a function and its interpolant on a uniform grid can be seen in Figure 3

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.

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 [179 ]):

where $Λ$ is the Lebesgue constant of the grid $X$ and is defined as:

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

It immediately follows that $ΛN → ∞$ when $N → ∞$ . This is related to a result from 1914 by Faber [73

] 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 4

, 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.

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 [179 ]) states that, for all functions $(N+1 ) f ∈ 𝒞$ , the interpolation error on a grid $X$ of $N + 1$ nodes is given by

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

In Equation (25 ), 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 4 (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

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 5

, which shows the same function and its interpolants as in Figure 4

, 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).

Figure 5: Same as Figure 4

but using a grid based on the zeros of Chebyshev polynomials. The Runge phenomenon is no longer present.