Difference between revisions of "Interpolation in numerical mathematics"
(Importing text file) |
m (link) |
||
Line 71: | Line 71: | ||
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195085.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195085.png" /></td> </tr></table> | ||
− | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195086.png" /> is the divided difference of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195087.png" /> at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195088.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195089.png" />. Under certain conditions, the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195090.png" /> converges, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195091.png" />, to a solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195092.png" />. | + | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195086.png" /> is the [[divided difference]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195087.png" /> at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195088.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195089.png" />. Under certain conditions, the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195090.png" /> converges, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195091.png" />, to a solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195092.png" />. |
Another way to construct methods for solving an equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195093.png" /> is based on interpolating the inverse function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195094.png" />. Suppose that for interpolating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195095.png" /> the algebraic Lagrange interpolation polynomial | Another way to construct methods for solving an equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195093.png" /> is based on interpolating the inverse function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195094.png" />. Suppose that for interpolating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051950/i05195095.png" /> the algebraic Lagrange interpolation polynomial |
Revision as of 15:40, 3 January 2015
A method for approximating or precisely finding some quantity by known individual values of it or of other quantities related to it. On the basis of interpolation a whole series of approximate methods for solving mathematical problems has been developed.
Most significant in numerical mathematics is the problem of constructing means for the interpolation of functions. The interpolation of functionals and operators is also widely used in constructing numerical methods.
The approximate representation and calculation of functions.
Interpolation of functions is considered as one of the ways of approximating them. Interpolating a function on a segment
by its values at the nodes
of a grid
means constructing another function
such that
,
. In a more general setting, the problem of interpolating a function
consists of constructing
not only by prescribing values on a grid
, but also derivatives at individual nodes, up to a certain order, or by describing some other relation connecting
and
.
Usually is constructed in the form
![]() |
where is a certain system of linearly independent functions, chosen in advance. Such an interpolation is called linear with respect to
, while
is called an interpolation polynomial in the system
or an interpolation function.
The choice of is determined by the properties of the function class for which the interpolation formula is constructed. E.g., for the approximation of
-periodic functions on
one naturally takes the trigonometric system for
, for the approximation of bounded or increasing functions on
one takes the system of rational or exponential functions, taking into account the behaviour of the functions to be approximated at infinity, etc.
Most often one uses algebraic interpolation: ; its simplest variant (linear interpolation with two nodes
and
) is defined by the formula
![]() | (1) |
![]() |
Algebraic interpolation of a very high order is seldom used in practice in the problem of approximating functions on an entire segment . One usually restricts oneself to linear interpolation by (1) or to quadratic interpolation with three nodes on particular segments of the grid, by the formula
![]() | (2) |
![]() |
![]() |
There are several ways of writing the algebraic interpolation polynomials (cf. Interpolation formula). Interpolation by splines gains increasing application (cf. Spline; Interpolation spline)
Parabolic or cubic splines are most often used in practice. An interpolation spline of defect 1 for a function with respect to a given grid
is a function
that is a polynomial of degree three on each segment
, belongs to the class of twice continuously-differentiable functions, and satisfies the conditions
![]() |
There are still two free parameters in this definition; these are determined by additional boundary conditions: ,
;
,
, or other conditions.
As well as immediately in the problem of approximating functions, splines are also used in solving other problems; the splines are required then not only to coincide on a grid with the values of a function
, but also with those of the derivatives of this function, up to a certain order.
When processing empirical data one often determines the coefficients
in
by requiring
![]() |
to be minimal. The function thus constructed is called the interpolation function in the sense of least squares.
The interpolation of functions in several variables meets with a number of principal and numerical difficulties. E.g., in the case of algebraic interpolation the Lagrange interpolation polynomial of fixed degree need not, generally speaking, exist for an arbitrary system of different nodes. In particular, for a function in two variables such a polynomials
of total degree at most
can be constructed for nodes
only if these nodes do not lie on an algebraic curve of order
.
Another approach to the interpolation of functions in several variables is that one first interpolates the function with respect to
for fixed
,
, then with respect to the next variable
for fixed remaining nodes, etc. Now the interpolation polynomial
for
with nodes
![]() |
![]() |
has the form:
![]() |
![]() |
where
![]() |
Interpolation splines for functions of several variables are defined on a multi-dimensional grid, with corresponding changes, in analogy with the one-dimensional case. Interpolation of functions is used for replacing complicate functions by simpler ones that can be calculated quicker; for the approximate recovery of functions on their entire domain of values by their values at individual points; and for obtaining smoother functions described by a running process. This kind of problems is of both independent interest and arises in an auxiliary fashion in many branches of science and technology in solving complex problems. Interpolation of functions is also used in approximately finding limit values of functions, in problems of accelerating the convergence of series or sequences, etc.
Numerically solving systems of non-linear equations.
The general ideas for constructing interpolation methods for solving an equation or a system of equations
,
, are the same. The difficulties of the problem of interpolating functions of several variables especially arise when investigating and practically using this kind of methods for a large number of equations. The basic principle for obtaining interpolation methods for solving an equation
is the replacement of
by its interpolation polynomials
and subsequently solving
. The roots of
are taken as approximate values of those of
. The interpolation polynomial
is also used in constructing iteration methods for solving
.
E.g., taking for the root of the linear algebraic interpolation polynomial constructed with respect to the values
and
at
, or with respect to the values
and
at
and
, leads to the method of Newton (cf. Newton method) and the secant method, respectively:
![]() |
where is the divided difference of
at
and
. Under certain conditions, the sequence
converges, as
, to a solution of
.
Another way to construct methods for solving an equation is based on interpolating the inverse function
. Suppose that for interpolating
the algebraic Lagrange interpolation polynomial
![]() |
is taken. It is assumed that the inverse function exists in a neighbourhood of the required root of and that a table of values
and
,
, is available. The next approximate value
is the value of the interpolation polynomial at zero:
![]() |
Numerical integration.
The apparatus of interpolation lies at the basis of constructing a lot of quadrature and cubature formulas. Such formulas are constructed by replacing the functions in the integrands on the entire domain, or on a part of it, by interpolation polynomials of a certain kind and integrating these.
E.g., quadrature formulas of highest algebraic accuracy, also called Gauss quadrature formulas (cf. Gauss quadrature formula)
![]() |
where is a sign-definite weight function, are obtained by replacing
by algebraic interpolation polynomials constructed with respect to the roots
of the polynomial of degree
that is orthogonal to
.
If one partitions the complete integration interval in an even number
of equal parts of length
and if on each double part one replaces
by its quadratic interpolation polynomials with nodes at the end and middle points, then one is led to the compound Simpson formula
![]() |
![]() |
where ,
.
One may also take interpolation splines of some fixed degree as basis. The scheme for constructing formulas for the approximate computation of integrals explained above can be used in the multi-dimensional case as well.
Numerical differentiation.
Formulas for numerical differentiation are obtained as results of differentiating interpolation formulas. Here, as a rule, certain a priori information is available about the function to be differentiated, related to its smoothness.
Let be a certain interpolation polynomial of a function
, and let
be the remainder in the interpolation formula
![]() |
If in
![]() |
the quantity is neglected, one obtains a formula for the approximate computation of the
-th derivative of
:
![]() | (3) |
Formulas for numerical differentiation, with interpolation at their basis, are obtained from (3) depending on the choice of . For numerical differentiation one uses, as a rule, approximate values of the function at nodes; the error in a formula of numerical differentiation not only depends on the manner of interpolating and the interpolation step, but also on the errors in the values of the function at the nodes which are used. E.g., in the case of the linear approximation (1)
![]() | (4) |
and the remainder has the representation
![]() |
If and
are known with respective errors
,
,
, then the error in (4) will contain yet another term
, which decreases as the step
increases. When using formulas for numerical differentiation, the interpolation step must be in accordance with the errors in the values of the functions. Therefore, in practice it often happens that a function known to have some error on a dense grid is interpolated on a more coarse grid only.
Numerically solving integral equations.
The unknown function in the integral equation is replaced by some interpolation formula (an interpolation polynomial, an interpolation spline, etc.) with nodes
, and an approximate value
is determined from the system obtained after replacing the independent variable
by the nodes
.
E.g., for the linear Fredholm integral equation of the second kind
![]() | (5) |
one can use the Lagrange form of the interpolation polynomial,
![]() |
where is the remainder and
![]() |
Replacing in (5) by its interpolation polynomial
and
by
, one obtains the linear system of equations
![]() |
![]() |
for determining the approximate value of
at
. In the case of non-linear integral equations the approximate value
has to be determined from the corresponding non-linear system.
Numerically solving differential equations.
One of the possibilities for constructing numerical methods for solving differential equations consists of replacing the derivatives of the unknown functions by interpolation formulas for numerical differentiation, and in a number of cases also in replacing by interpolation other functions and expressions occurring in the equation.
Suppose one has the following formula for numerical differentiation with equally-spaced nodes :
![]() | (6) |
![]() |
obtained by differentiation of the formulas of linear and quadratic interpolation (1) and (2), respectively. Then for a second-order ordinary differential equation
![]() |
one obtains, under certain additional conditions, taking (6) into account, the finite-difference equation
![]() |
In it, together with the equations obtained from the additional conditions, the approximate values of the solution
at nodes
occur.
Often, reduction of partial differential equations to the corresponding finite-difference equations is often also carried out using formulas for numerical differentiation.
Interpolation methods are applied to solve differential equations written in integral form. E.g., to find an approximate solution of the Cauchy problem
![]() | (7) |
at points ,
one uses difference formulas of the form
![]() |
obtained by replacing the integrand in
![]() |
by an interpolation polynomial and subsequent integration. In particular, Adams' formula for first-order equations (7), Störmer's formula for second-order equations, etc., are obtained this way.
This approach makes it possible to construct numerical algorithms for a wide class of differential equations, including partial differential equations. The study of the solvability, exactness and stability of solutions of finite-difference equations that arise constitutes a fundamental and difficult part of the theory of numerically solving differential equations.
Interpolation of operators and some general approaches to the construction of numerical methods.
The construction of numerical methods for solving mathematical problems written as , where
and
are elements of certain sets
and
and
is a given operator, consists of replacing
,
and
, or only some of these three objects, by other objects that are convenient for calculating purposes. This replacement should be carried out in such a way that the solution to the new problem
![]() |
consisting of finding or
, is in some sense close to the solution of the original problem. One of the methods for replacing
by an approximation
is the use of interpolation of operators. The problem of the interpolation of operators has various formulations. A linear interpolation operator
for a given operator is written as
![]() | (8) |
where ,
are the interpolation nodes and
is the first-order divided-difference operator. The latter is defined as the linear operator for which
![]() |
The given definition of the divided-difference operator can be made concrete in a number of cases. Using linear interpolation (8), the "secant method" for the equation can be written as
![]() |
where is the operator inverse to
.
The formulation of the problem of interpolation of functionals, which is of interest in the theory of approximation methods, is as follows. Let be some fixed functionals, or classes of functionals, defined on
. A functional
is called an interpolation functional polynomial for a given functional
and system of points
in
if the relations
![]() |
hold.
Interpolation of functionals is used in the construction of approximate methods for computing continual integrals, in finding extrema of functionals, and in a number of other cases.
E.g., approximate interpolation formulas for computing continual integrals have the form
![]() |
where the integral over the interpolation polynomial with respect to a certain measure
can be computed exactly or can be reduced to a finite-dimensional integral. When
is the space
of continuous functions on an interval
, then
can be represented by a Stieltjes integral,
![]() |
![]() |
where ,
are the interpolation nodes while
![]() |
If is a constant or a linear functional, then
.
The use of interpolation in finding extremal values of functionals may be illustrated by two interpolation analogues of the gradient method for finding a local unconditional minimum of a functional that is defined on some Hilbert space. The first analogue is obtained if, in the gradient method,
is replaced by
, i.e.
![]() | (9) |
The second analogue uses the gradient of the interpolation polynomials. From approximations ,
,
to an extremum
of
one constructs the quadratic interpolation polynomial
![]() |
![]() |
where is the second-order divided difference of
with respect to
,
,
. The new approximation
is determined by
![]() | (10) |
![]() |
The interpolation methods (9), (10) use two, respectively, there, initial approximations.
The use of interpolation of operators and functionals in the construction of computational algorithms for solving concrete problems is based on the use of interpolation formulas with a small error. Such a kind or formulas must be constructed for individual classes of functionals and operators, taking specific features of these classes into account.
References
[1] | V.L. Goncharov, "The theory of interpolation and approximation of functions" , Moscow (1954) (In Russian) |
[2] | I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian) |
[3] | N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) |
[4] | V.I. Krylov, V.V. Bobkov, P.I. Monastyrnyi, "Numerical methods" , 1–2 , Moscow (1976–1977) (In Russian) |
[5] | S.B. Stechkin, Yu.N. Subbotin, "Splines in numerical mathematics" , Moscow (1976) (In Russian) |
[6] | A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian) |
[7] | L.A. Yanovich, "Approximate computation of continual integrals with respect to Gaussian measures" , Minsk (1976) (In Russian) |
Comments
A detailed theoretical treatment of interpolation theory is provided by the monograph [a2], while applications of interpolation in numerical mathematics can be found in [a1].
References
[a1] | F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974) |
[a2] | P.J. Davis, "Interpolation and approximation" , Dover, reprint (1975) pp. 108–126 |
[a3] | J.C. Mason (ed.) M.G. Cox (ed.) , Algorithms for approximation , Clarendon Press (1987) |
Interpolation in numerical mathematics. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interpolation_in_numerical_mathematics&oldid=36051