In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, Runge's phenomenon () is a problem of oscillation at the edges of an interval that occurs when using
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
with polynomials of high degree over a set of equispaced interpolation points. It was discovered by
Carl David Tolmé Runge
Carl David Tolmé Runge (; 30 August 1856 – 3 January 1927) was a German mathematician, physicist, and spectroscopist.
He was co-developer and co-eponym of the Runge–Kutta method (German pronunciation: ), in the field of what is today known a ...
(1901) when exploring the behavior of errors when using polynomial interpolation to approximate certain functions.
The discovery was important because it shows that going to higher degrees does not always improve accuracy. The phenomenon is similar to the
Gibbs phenomenon
In mathematics, the Gibbs phenomenon, discovered by Available on-line at:National Chiao Tung University: Open Course Ware: Hewitt & Hewitt, 1979. and rediscovered by , is the oscillatory behavior of the Fourier series of a piecewise continuousl ...
in Fourier series approximations.
Introduction
The
Weierstrass approximation theorem
Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern analysis". Despite leaving university without a degree, he studied mathematics ...
states that for every
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
''f''(''x'') defined on an
interval 'a'',''b'' there exists a set of
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
functions ''P''
''n''(''x'') for ''n''=0, 1, 2, …, each of degree at most ''n'', that approximates ''f''(''x'') with
uniform convergence
In the mathematical field of analysis, uniform convergence is a mode of convergence of functions stronger than pointwise convergence. A sequence of functions (f_n) converges uniformly to a limiting function f on a set E if, given any arbitrarily s ...
over
'a'',''b''as ''n'' tends to infinity, that is,
:
Consider the case where one desires to
interpolate
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
through ''n''+1 equispaced points of a function ''f''(''x'') using the ''n''-degree polynomial ''P''
''n''(''x'') that passes through those points. Naturally, one might expect from Weierstrass' theorem that using more points would lead to a more accurate reconstruction of ''f''(''x''). However, this ''particular'' set of polynomial functions ''P''
''n''(''x'') is not guaranteed to have the property of uniform convergence; the theorem only states that a set of polynomial functions exists, without providing
a general method of finding one.
The ''P''
''n''(''x'') produced in this manner may in fact diverge away from ''f''(''x'') as ''n'' increases; this typically occurs in an oscillating pattern that magnifies near the ends of the interpolation points. The discovery of this phenomenon is attributed to Runge.
Problem
Consider the Runge function
:
(a scaled version of the
Witch of Agnesi
In mathematics, the witch of Agnesi () is a cubic plane curve defined from two diametrically opposite points of a circle. It gets its name from Italian mathematician Maria Gaetana Agnesi, and from a mistranslation of an Italian word for a sail ...
).
Runge found that if this function is
interpolated
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
at equidistant points ''x''
''i'' between −1 and 1 such that:
:
with a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
''P''
''n''(''x'') of degree ≤ ''n'', the resulting interpolation oscillates toward the end of the interval, i.e. close to −1 and 1. It can even be proven that the interpolation error increases (without bound) when the degree of the polynomial is increased:
:
This shows that high-degree polynomial interpolation at equidistant points can be troublesome.
Reason
Runge's phenomenon is the consequence of two properties of this problem.
* The magnitude of the ''n''-th order derivatives of this particular function grows quickly when ''n'' increases.
* The equidistance between points leads to a
Lebesgue constant that increases quickly when ''n'' increases.
The phenomenon is graphically obvious because both properties combine to increase the magnitude of the oscillations.
The error between the generating function and the interpolating polynomial of order ''n'' is given by
:
for some
in (−1, 1). Thus,
:
.
Denote by
the nodal function
:
and let
be the maximum of the magnitude of the
function:
:
.
It is elementary to prove that with equidistant nodes
:
where
is the step size.
Moreover, assume that the (''n''+1)-th derivative of
is bounded, i.e.
:
.
Therefore,
:
.
But the magnitude of the (''n''+1)-th derivative of Runge's function increases when ''n'' increases, since
. The consequence is that the resulting upper bound,
, tends to infinity when ''n'' tends to infinity.
Although often used to explain the Runge phenomenon, the fact that the upper bound of the error goes to infinity does not necessarily
imply, of course, that the error itself also diverges with ''n.''
Mitigations
Change of interpolation points
The oscillation can be minimized by using nodes that are distributed more densely towards the edges of the interval, specifically, with asymptotic density (on the interval ) given by the formula
.
A standard example of such a set of nodes is
Chebyshev nodes
In numerical analysis, Chebyshev nodes are specific real algebraic numbers, namely the roots of the Chebyshev polynomials of the first kind. They are often used as nodes in polynomial interpolation because the resulting interpolation polynomial ...
, for which the maximum error in approximating the Runge function is guaranteed to diminish with increasing polynomial order.
S-Runge algorithm without resampling
When equidistant samples must be used because resampling on well-behaved sets of nodes is not feasible, the S-Runge algorithm can be considered.
[
] In this approach, the original set of nodes is mapped on the set of
Chebyshev nodes
In numerical analysis, Chebyshev nodes are specific real algebraic numbers, namely the roots of the Chebyshev polynomials of the first kind. They are often used as nodes in polynomial interpolation because the resulting interpolation polynomial ...
, providing a stable polynomial reconstruction. The peculiarity of this method is that there is no need of resampling at the mapped nodes, which are also called ''
fake nodes''. A
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
implementation of this procedure can be foun
here
Use of piecewise polynomials
The problem can be avoided by using
spline curve
In mathematics, a spline is a special function defined piecewise by polynomials.
In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree poly ...
s which are piecewise polynomials. When trying to decrease the interpolation error one can increase the number of polynomial pieces which are used to construct the spline instead of increasing the degree of the polynomials used.
Constrained minimization
One can also fit a polynomial of higher degree (for instance, with
points use a polynomial of order
instead of
), and fit an interpolating polynomial whose first (or second) derivative has minimal
norm.
A similar approach is to minimize a constrained version of the
distance between the polynomial's
-th derivative and the mean value of its
-th derivative. Explicitly, to minimize
:
where
and
, with respect to the polynomial coefficients and the
Lagrange multiplier
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied ex ...
s,
. When
, the constraint equations generated by the Lagrange multipliers reduce
to the minimum polynomial that passes through all
points. At the opposite end,
will approach a form very similar to a piecewise polynomials approximation. When
, in particular,
approaches the linear piecewise polynomials, i.e. connecting the interpolation points with straight lines.
The role played by
in the process of minimizing
is to control the importance of the size of the fluctuations away from the mean value. The larger
is, the more large fluctuations are penalized compared to small ones. The greatest advantage of the Euclidean norm,
, is that it allows for analytic solutions and it guarantees that
will only have a single minimum. When
there can be multiple minima in
, making it difficult to ensure that a particular minimum found will be the
global minimum
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
instead of a local one.
Least squares fitting
Another method is fitting a polynomial of lower degree using the method of
least squares
The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems (sets of equations in which there are more equations than unknowns) by minimizing the sum of the squares of the res ...
. Generally, when using
equidistant points, if
then least squares approximation
is well-conditioned.
Bernstein polynomial
Using
Bernstein polynomial
In the mathematical field of numerical analysis, a Bernstein polynomial is a polynomial that is a linear combination of Bernstein basis polynomials. The idea is named after Sergei Natanovich Bernstein.
A numerically stable way to evaluate polyn ...
s, one can uniformly approximate every continuous function in a closed interval, although this method is rather computationally expensive.
External fake constraints interpolation
This method proposes to optimally stack a dense distribution of constraints of the type on nodes positioned externally near the endpoints of each side of the interpolation interval, where P"(x) is the second derivative of the interpolation polynomial. Those constraints are called External Fake Constraints as they do not belong to the interpolation interval and they do not match the behaviour of the Runge function. The method has demonstrated that it has a better interpolation performance than Piecewise polynomials (splines) to mitigate the Runge phenomenon.
Related statements from the
approximation theory
In mathematics, approximation theory is concerned with how function (mathematics), functions can best be approximation, approximated with simpler functions, and with quantitative property, quantitatively characterization (mathematics), characteri ...
For every predefined table of interpolation nodes there is a continuous function for which the sequence of interpolation polynomials on those nodes diverges.
For every continuous function there is a table of nodes on which the interpolation process converges. {{Citation needed, date=March 2014 Chebyshev interpolation (i.e., on
Chebyshev nodes
In numerical analysis, Chebyshev nodes are specific real algebraic numbers, namely the roots of the Chebyshev polynomials of the first kind. They are often used as nodes in polynomial interpolation because the resulting interpolation polynomial ...
) converges uniformly for every absolutely continuous function.
See also
*
Chebyshev nodes
In numerical analysis, Chebyshev nodes are specific real algebraic numbers, namely the roots of the Chebyshev polynomials of the first kind. They are often used as nodes in polynomial interpolation because the resulting interpolation polynomial ...
* Compare with the
Gibbs phenomenon
In mathematics, the Gibbs phenomenon, discovered by Available on-line at:National Chiao Tung University: Open Course Ware: Hewitt & Hewitt, 1979. and rediscovered by , is the oscillatory behavior of the Fourier series of a piecewise continuousl ...
for sinusoidal basis functions
*
Occam's razor
Occam's razor, Ockham's razor, or Ocham's razor ( la, novacula Occami), also known as the principle of parsimony or the law of parsimony ( la, lex parsimoniae), is the problem-solving principle that "entities should not be multiplied beyond neces ...
argues for simpler models
*
Schwarz lantern
In mathematics, the Schwarz lantern is a polyhedral approximation to a cylinder, used as a pathological example of the difficulty of defining the area of a smooth (curved) surface as the limit of the areas of polyhedra. It is formed by stack ...
, another example of failure of convergence
*
Stone–Weierstrass theorem
*
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
References
Interpolation
Theory of continuous functions
Numerical artefacts
de:Polynominterpolation#Runges Phänomen