Let us consider a continuous function and a family of grids with nodes . Then, there exists a unique polynomial of degree , , that coincides with at each node:
is called the interpolant of through the grid . can be expressed in terms of the Lagrange cardinal polynomials:except at , where it is equal to one. It is easy to show that the Lagrange cardinal polynomials can be written as
Thanks to Chebyshev alternate theorem, one can see that the best approximation of degree is an interpolant of the function at nodes. However, in general, the associated grid is not known. The difference between the error made by interpolating on a given grid can be compared to the smallest possible error for the best approximation. One can show that (see Prop. 7.1 of ):Lebesgue constant of the grid and is defined as:
A theorem by Erdös  states that, for any choice of grid , there exists a constant such that: that states that for any grid, there always exists at least one continuous function , whose interpolant does not converge uniformly to . An example of such failure of convergence is show in Figure 4, where the convergence of the interpolant to the function is clearly nonuniform (see the behavior near the boundaries of the interval). This is known as the Runge phenomenon.
Moreover, a theorem by Cauchy (theorem 7.2 of ) states that, for all functions , the interpolation error on a grid of nodes is given by
In Equation (25), one has a priori no control on the term involving . For a given function, it can be rather large and this is indeed the case for the function shown in Figure 4 (one can check, for instance, that 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 (see Section 2.3 for more details on Chebyshev polynomials). With such a grid, one can achieve). 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 , the uniform convergence of the interpolant to the function is recovered. This is because decreases faster than 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).
Living Rev. Relativity 12, (2009), 1
This work is licensed under a Creative Commons License.