Divergence (Runge Phenomenon) for least-squares polynomial approximation on an equispaced grid and Mock–Chebyshev subset interpolation

doi:10.1016/j.amc.2008.12.087

Applied Mathematics and Computation

Volume 210, Issue 1, 1 April 2009, Pages 158-168

https://doi.org/10.1016/j.amc.2008.12.087 Get rights and content

Abstract

Runge showed more than a century ago that polynomial interpolation of a function f(x), using points evenly spaced on $x \in [- 1, 1]$ , could diverge on parts of this interval even if f(x) was analytic everywhere on the interval. Least-squares fitting of a polynomial of degree N to an evenly spaced grid with P points should improve accuracy if $P ≫ N$ . We show through numerical experiments that such an overdetermined fit reduces but does not eliminate the Runge Phenomenon. More precisely, define $β \equiv (N + 1) / P$ . The least-squares fit will fail to converge everywhere on [−1, 1] as $N \to \infty$ for fixed β if f(x) has a singularity inside a curve $D (β)$ in the complex-plane. The width of the region enclosed by the convergence boundary $D$ shrinks as β diminishes (i. e., more points for a fixed polynomial degree), but shrinks to the interval [−1, 1] only when $β \to 0$ . We also show that the Runge Phenomenon can be completely defeated by interpolation on a “mock–Chebyshev” grid: a subset of $(N + 1)$ points from an equispaced grid with $O (N^{2})$ points chosen to mimic the non-uniform $N + 1$ -point Chebyshev–Lobatto grid.

Introduction

If a function f(x) is free of singularities on $x \in [- 1, 1]$ and for a finite distance around this region, then interpolation of f(x) by a polynomial of degree N on a Chebyshev–Lobatto grid is guaranteed to converge at a rate which is exponential in N. (A more precise statement is given as Theorem 2 below; “singularities” denotes poles, logarithms and other branch points, discontinuities and all points of non-analyticity, just as in undergraduate complex variable theory.)

Unfortunately, this property of guaranteed exponential convergence is not true for polynomial interpolation on an evenly spaced grid. Indeed, our numerical experiments and a theorem of Rakhmanov’s [1] suggest that even with an overdetermined, least squares fit, polynomial approximation will diverge for some functions f(x) that are free of singularities on the interval spanned by the grid points, $x \in [- 1, 1]$ . This divergence is the Runge Phenomenon [2], [3], [4].

Previous theoretical work is reviewed by Rakhmanov [1]. Our numerical experiments are new; we shall make connections with existing theory (and its gaps) as we proceed.

Our experiments and Rakhmanov’s theory will characterize the Runge region as a function of $β \equiv (N + 1) / P$ . Before discussing what happens when $β < 1$ , it is useful to review classical interpolation where $β = 1$ . (Table 1 lists all symbols.)

Section snippets

Interpolation on an evenly spaced grid

Theorem 1

(Convergence of equispaced interpolation)Let $x_{k}$ denote the points of an evenly spaced grid with $N + 1$ points on the interval $x \in [- 1, 1]$ , $x_{k} = - 1 + 2 (k - 1) / N, k = 1, 2, \dots, N + 1 .$ Define $f_{N} (x)$ as the polynomial of degree N that interpolates f(x) at these points. Let $σ (x) \equiv \exp \{\frac{1}{2} \int_{- 1}^{1} \log (| x - t |) dt\} .$ Let $Ξ (r)$ denote the isolines of $σ (x)$ in the complex x-plane; these curves are lemniscates defined by $Ξ (r) = {w + iy : | σ (w + iy) | = r}$ (Note that r is always real-valued.) Suppose that f(x) has a singularity on the lemniscate $Ξ (ρ)$ but is

Least-squares fitting of a polynomial: theory

The least-squares fit to a function f(x) is defined to be the polynomial $f_{N} (x)$ which minimizes the cost function $J (f_{N} (x)) \equiv \sum_{j = 1}^{P} (f (x_{j}) - f_{N} (x_{j}))^{2}$ for a set of grid points ${x_{j}}$ . When $P = N + 1$ , the least-squares fit is the usual interpolant.

Let $f_{N}^{LS} (x)$ denote this least-squares polynomial. Now a function f(x) can always be approximated by another polynomial of the same degree which is the interpolant of f(x) at the points of a Chebyshev–Lobatto grid, $x_{k}^{Cheb} = \cos (π k / N), k = 0, \dots, N$ , which we will denote by $f_{N}^{}$

Location–location–location

It is a truism of real estate that the price of a house of a given size, style and materials can vary enormously with location: a building in Manhattan or San Francisco may sell for ten times the price of the same building in rural Idaho. Realtors and homeowners all know the maxim: “Location. Location. Location.”

This mantra is equally applicable to the convergence and divergence of polynomial approximations. The theorems of the previous section and longer discussion in [9] show that the rate of

Mock–Chebyshev subset interpolation

Rakhmanov [1] predicts that convergence can be restored for singularities very close to the interval $x \in [- 1, 1]$ if and only if the number of points grows as the square of the polynomial degree (or faster). Here, we present numerical evidence on behalf of a stronger claim: if we select an artfully-chosen subset of our $N + 1$ samples of f(x) on an equispaced grid, then interpolation will converge geometrically fast in the degree of the interpolant.

Recall that the Chebyshev–Lobatto grid with $N + 1$ points

Function-adaptive overdetermined fits

Although it appears impossible to choose any $β > 0$ so that least-squares polynomial approximation on an evenly spaced grid can be guaranteed to work for all functions, there is always a value of β which will yield convergence for any particular f(x) – a small β if f(x) has singularities very near the expansion interval, and $β = 1$ (interpolation) if f(x) has only singularities outside the Runge region for interpolation. In principle, this observation could be the foundation for an adaptive scheme

Summary

Polynomial interpolation at the roots of Chebyshev polynomials converges everywhere on the interpolation interval $x \in [- 1, 1]$ for all f(x) which are free of singularities on [−1, 1]. In contrast, interpolation on an evenly spaced grid fails in the sense that the approximation diverges as the polynomial degree $(N \to \infty)$ near the endpoints if f(x) has singularities anywhere within a certain lemniscate, the “Runge region”, shaded in Fig. 1.

Our hope was that overdetermination, that is, fitting a

Acknowledgements

We thank Evguenii Rakhmanov for sending a preprint of his work and correspondence. We also thank Doron Lubinsky and Boris Shekhtman for helpful answers and suggestions. We thank the reviewers for their very detailed comments.

References (11)

L.N. Trefethen et al.
Two results on polynomial interpolation in equally spaced points
J. Approx. Theory
(1991)
J.P. Boyd
Exponentially accurate Runge-Free approximation of non-periodic functions from samples on an evenly-spaced grid
Appl. Math. Lett.
(2007)
E.A. Rakhmanov
Bounds for polynomials with a unit discrete norm
Ann. Math.
(2007)
C. Runge
Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten
Zeit. fur Math. Physik
(1901)
C. Meray
Observations sur la légitime de l’interpolation
Ann. Sci. Ec. Norm. Super.
(1884)

There are more references available in the full text version of this article.

Cited by (77)

Numerical approximation of Fredholm integral equation by the constrained mock-Chebyshev least squares operator
2024, Journal of Computational and Applied Mathematics
In this paper, we propose two numerical approaches for approximating the solution of the following kind of integral equation where $f$ is the unknown solution, $μ \in R ∖ {0}$ , $k, g$ are given functions not necessarily known in the analytical form, and $w$ is a Jacobi weight. The proposed projection methods are based on the constrained mock-Chebyshev least squares polynomials, and starting from data known at equally spaced points, provide a fine approximation of the solution. Such peculiarity can be helpful in all cases we deal with experimental data, typically measured at equispaced points. We prove the introduced methods are stable and convergent in some Sobolev subspace of $C [- 1, 1]$ . Several numerical tests confirm the theoretical estimates and numerical effectiveness of the proposed methods.
Polynomial approximation of derivatives through a regression–interpolation method
2024, Applied Mathematics Letters
The constrained mock-Chebyshev least squares operator is a linear approximation operator based on an equispaced grid of points. Like other polynomial or rational approximation methods, it was recently introduced in order to defeat the Runge phenomenon that occurs when using polynomial interpolation on large sets of equally spaced points. The idea is to improve the mock-Chebyshev subset interpolation, where the considered function $f$ is interpolated only on a proper subset of the uniform grid, formed by nodes that mimic the behavior of Chebyshev–Lobatto nodes. In the mock-Chebyshev subset interpolation all remaining nodes are discarded, while in the constrained mock-Chebyshev least squares interpolation they are used in a simultaneous regression, with the aim to further improving the accuracy of the approximation provided by the mock-Chebyshev subset interpolation. The goal of this paper is to introduce a method for approximating the successive derivatives of $f$ at any point $x$ in the interval $[- 1, 1]$ , based on the constrained mock-Chebyshev least squares operator. Several numerical tests demonstrate the effectiveness of the proposed method.
A new fast algorithm for computing the mock-Chebyshev nodes
2024, Applied Numerical Mathematics
Interpolation by polynomials on equispaced points is not always convergent due to the Runge phenomenon, and also, the interpolation process is exponentially ill-conditioned. By taking advantage of the optimality of the interpolation processes on the Chebyshev-Lobatto nodes, one of the best strategies to defeat the Runge phenomenon is to use the mock-Chebyshev nodes for polynomial interpolation. Mock-Chebyshev nodes asymptotically follow the Chebyshev distribution, and they are selected from a sufficiently large set of equispaced nodes. However, there are few studies in the literature regarding the computation of these points.
In a recent paper [1], we have introduced a fast algorithm for computing the mock-Chebyshev nodes for a given set of $(n + 1)$ Chebyshev-Lobatto points using the distance between each pair of consecutive points. In this study, we propose a modification of the algorithm by changing the function to compute the quotient of the distance and show that this modified algorithm is also fast and stable; and gives a more accurate grid satisfying the conditions of a mock-Chebyshev grid with the complexity being $O (n)$ . Some numerical experiments using the points obtained by this modified algorithm are given to show its effectiveness and numerical results are also provided. A bivariate generalization of the mock-Chebyshev nodes to the Padua interpolation points is discussed.
Enhanced trapezoidal rule for discontinuous functions
2023, Journal of Computational Physics
In many applications, data to be integrated is available only in the form of function values at predetermined equispaced points. For smooth periodic functions, the trapezoidal rule gives very accurate approximations to the integral, but is only second order accurate in more commonly arising non-periodic cases. The Gregory approach for end corrections can improve the accuracy order to 9 before the onset of negative weights, and of rapidly increasing ill-conditioning. In recent work, this has been extended to accuracy orders around 20.
This present study focuses on the more general case when one or both end points of the integration interval do not coincide with any of the equispaced grid points. We show that accuracy orders up to around 10 can also then be achieved, with all quadrature weights still remaining non-negative. This method can be utilized for example when functions to be integrated feature discontinuities at locations that can be separately determined (at or in between the equispaced grid points).
Constrained mock-Chebyshev least squares quadrature
2022, Applied Mathematics Letters
Generalizations of the constrained mock-Chebyshev least squares in two variables: Tensor product vs total degree polynomial interpolation
2022, Applied Mathematics Letters
The constrained mock-Chebyshev least squares interpolation is a univariate polynomial interpolation technique exploited to cut-down the Runge phenomenon. It takes advantage of the optimality of the interpolation on the mock-Chebyshev nodes, i.e. the subset of the uniform grid formed by nodes that mimic the behavior of Chebyshev–Lobatto nodes. The other nodes of the grid are not discarded, rather they are used in a simultaneous regression to improve the accuracy of the approximation of the mock-Chebyshev subset interpolant. In this paper we extend the univariate constrained mock-Chebyshev least squares interpolation to the bivariate case in two different ways, relying on the tensor product interpolation and on the interpolation at the mock-Padua nodes. Numerical experiments demonstrate the effectiveness of such extensions.

View all citing articles on Scopus

^☆: This work was supported by the National Science Foundation through Grant OCE99863683 and OCE 0451951 and by the Undergraduate Research Opportunities Program (UROP) at the University of Michigan.

View full text

Divergence (Runge Phenomenon) for least-squares polynomial approximation on an equispaced grid and Mock–Chebyshev subset interpolation☆

Abstract

Introduction

Section snippets

Interpolation on an evenly spaced grid

Least-squares fitting of a polynomial: theory

Location–location–location

Mock–Chebyshev subset interpolation

Function-adaptive overdetermined fits

Summary

Acknowledgements

J. Approx. Theory

Appl. Math. Lett.

Bounds for polynomials with a unit discrete norm

Ann. Math.

Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten

Zeit. fur Math. Physik

Observations sur la légitime de l’interpolation

Ann. Sci. Ec. Norm. Super.