Interpolation in numerical mathematics

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)