View source for Interpolation

<!--
i0519301.png
$#A+1 = 199 n = 7
$#C+1 = 199 : ~/encyclopedia/old_files/data/I051/I.0501930 Interpolation
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

In the simplest, classical, sense it is the constructive (possibly approximate) recovery of a function of a certain class by its known values, or by known values of its derivatives, at prescribed (given) points.

Suppose one is given  $  n+ 1 $
points  $  \{ x _ {k} \} _ {k=0} ^ {n} $
on the segment  $  \Delta = [ a , b ] $, 
where  $  a \leq  x _ {0} < \dots < x _ {n} \leq  b $, 
and a set of  $  n+ 1 $ (not necessarily different) values  $  \{ y _ {k} \} _ {k=0}  ^ {n} $. 
Suppose that it is known that a function  $  f $, 
belonging to some fixed class of functions  $  K $
that are defined at least on  $  \Delta $ (e.g.,  $  f \in \Pi _ {n} $, 
where  $  \Pi _ {n} $
is the set of algebraic polynomials of degree  $  \leq  n $, 
or  $  f \in C  ^ {n+1} ( \Delta ) $), 
satisfies the conditions

$$ \tag{i1 }
f ( x)  \in  K ; \  f ( x _ {k} )  =  y _ {k} ,\  k = 0 \dots n .
$$

The points  $  x _ {k} $
at which the values  $  f ( x _ {k} ) = y _ {k} $
are given are called the interpolation nodes, or interpolation knots, of  $  f $. 
The following two problems arose naturally, mainly through the demands of numerical analysis. They were the starting point for the development of the theory of interpolation. It is asked, imposing (i1) on  $  f $, 
how to obtain, with prescribed accuracy, information on the behaviour of  $  f ( x) $: 
1) on the intervals  $  ( x _ {k-1} , x _ {k} ) $, 
$  k = 1 \dots n $, 
i.e. between (in Latin: inter) the nodes  $  x _ {k} $, 
$  k = 0 \dots n $; 
and 2) outside (in Latin: extra) the interval  $  [ x _ {0} , x _ {n} ] $
containing all nodes  $  \{ x _ {k} \} _ {k=0}  ^ {n} $. 
The Latin words  "inter"  and  "extra"  led, respectively, to the terminology of calling 1) an interpolation problem and 2) an extrapolation problem for the function  $  f $; 
these both were later merged into the one interpolation problem (i1).

Problem (i1), regarded as the problem of exactly recovering functions, has a unique solution in, e.g., the class  $  K = \Pi _ {n} $. 
Its solution in  $  \Pi _ {n} $
is the Lagrange interpolation polynomial

$$ 
L _ {n}  ^ {f} ( x) =
$$

$$ 
= \ 
\sum _ { k=0} ^ { n }  y _ {k} 
\frac{( x - x _ {0} ) \dots ( x - x _ {k-1} ) ( x - x _ {k+1} ) \dots ( x - x _ {n} ) }{( x _ {k} - x _ {0} ) \dots ( x _ {k} - x _ {k-1} ) ( x _ {k} - x _ {k+1} ) \dots ( x _ {k} - x _ {n} ) }
 .
$$

However, if  $  f $
belongs to a class that is in a certain sense  "more extensive"  than  $  \Pi _ {n} $, 
problem (i1), in general, does not have, a unique solution. Nevertheless, the polynomial  $  L _ {n}  ^ {f} ( x) $
allows one to assess, to a certain extent, the behaviour of  $  f $
on  $  \Delta $
if it is considered that

$$ \tag{1 }
f ( x)  \approx  L _ {n}  ^ {f} ( x) ,\  x \in \Delta .
$$

In relation to this it is necessary to estimate the error

$$ 
R _ {n}  ^ {f} ( x)  =  f ( x) - L _ {n}  ^ {f} ( x)
$$

for  $  x \in \Delta $. 
The error depends mainly on the class  $  K $
to which  $  f $
belongs, in other words,  $  R _ {n}  ^ {f} ( x) $
depends on a priori known properties of  $  f $. 
E.g., if  $  K = C  ^ {n+1} ( \Delta ) $, 
then the remainder term for (i1) has the form

$$ 
R _ {n}  ^ {f} ( x)  =  
\frac{f ^ { ( n+ 1 ) } ( \xi ) }{( n+ 1 )! }
 A ( x) ,
$$

where  $  \alpha < \xi < \beta $
and

$$ 
A ( x)  =  \prod _ { k=0} ^ { n }  ( x - x _ {k} ) .
$$

Here  $  \alpha $, 
$  \beta $
denote, respectively, the minimum and maximum of the numbers  $  x _ {0} $, 
$  x _ {n} $
and  $  x $. 
The given formula for the remainder is due to A.L. Cauchy, cf. [[#References|[3]]]. The quantity  $  R _ {n}  ^ {f} ( x) $
depends mainly on the form of the distribution and the number of interpolation nodes  $  \{ x _ {k} \} _ {k=0}  ^ {n} $
on  $  \Delta $. 
It is in this connection natural to assume that the more interpolation nodes  $  x _ {k} $
are taken and the more  "uniformly"  they are distributed on  $  \Delta $, 
then the more  "accurate"  relation (1) will be. This circumstance leads, in turn, to a more important interpolation problem, closely connected with (i1).

Suppose that  $  f $
belongs to a class  $  K $
of functions that are defined on  $  \Delta $, 
and such that  $  \Pi _ {n} \neq K $
for all  $  n = 0 , 1 , .  .  . $. 
It is assumed that the set of interpolation nodes  $  \{ x _ {k} \} \subset  \Delta $, 
$  x _ {k} \neq x _ {j} $
if  $  k \neq j $, 
is countable; suppose also that a sequence of values  $  \{ y _ {k} \} _ {k=0}  ^  \infty  $
is given. The question is: How to recover  $  f $
from the given data:

$$ \tag{i2 }
f  \in  K ; \  f ( x _ {k} )  =  y _ {k} ,\  k = 0 , 1 , \dots .
$$

The problem posed in this way is in the general case far from solvable, and has to be made more precise. This will be done below, but now only a sketch of a very natural and important approach to solving (i2) will be given. Usually one first solves the  "truncated"  problem (i1):

$$ 
f ( x _ {k _ {j}  } )  =  y _ {k _ {j}  } ,\  j = 1 \dots n+ 1 ,
$$

in  $  \Pi _ {n} $. 
Let  $  L _ {n}  ^ {f} ( x) $
be the interpolation polynomial that is the solution to this truncated problem and let it be written as a Lagrange interpolation polynomial. Then one considers the possibility of accomplishing, in some sense or another, a limit  $  L _ {n}  ^ {f} ( x) \rightarrow f ( x) $
as  $  n \rightarrow \infty $ (this is equivalent, in particular, to the study of the question of the remainder  $  R _ {n}  ^ {f} ( x) $
tending to zero as  $  n \rightarrow \infty $
in the sense considered). The given sketch of the scheme for solving (i2) is fundamental for the theory of convergence (and divergence) of interpolation processes (cf. [[Interpolation process|Interpolation process]]). It is one of the basic methods for solving interpolation problems and has applications not only in various branches of pure mathematics (e.g., number theory, cf. [[#References|[3]]]), but also in numerical methods (cf. [[Interpolation in numerical mathematics|Interpolation in numerical mathematics]], as well as [[#References|[1]]]).

In the latter, along with interpolation problems of the kind considered above and defined by the simplest functionals  $  f ( x _ {k} ) $, 
one also started to study other problems, in which, e.g., the values of derivatives  $  f ^ { ( m) } ( x _ {k} ) $, 
$  m = 0 \dots n _ {k} $, 
or more complicated functionals, are prescribed. In solving them one uses interpolation processes in which, instead of  $  \Pi _ {n} $, 
other underlying interpolating sets of functions are considered, e.g. the class  $  T _ {n} $
of trigonometric polynomials of degree  $  \leq  n $, 
classes of rational functions  $  \Pi _ {m , n }  $ (of the form  $  p _ {m} / q _ {n} $, 
where  $  p _ {m} \in \Pi _ {m} $
and  $  q _ {n} \in \Pi _ {n} $, 
$  q _ {n} \not\equiv 0 $), 
classes of entire functions of a special kind, etc. See also [[Interpolation formula|Interpolation formula]].

In its general form, the problem of interpolation reads as follows. Let  $  X $, 
$  Y $
be two non-empty sets; suppose that a family of mappings  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $, 
$  f _  \alpha  :  X \rightarrow Y $, 
$  \alpha \in \mathfrak A $, 
is given. Let  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
be a given set of elements (not necessarily different) in  $  Y $. 
Then there naturally arises the problem of determining the set of  $  x \in X $
satisfying

$$ \tag{i3 }
f _  \alpha  ( x)  =  y _  \alpha  \  \textrm{ for }  \textrm{ all }  \alpha
\in \mathfrak A .
$$

Generally speaking, not for every a priori given set of elements  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
does (i3) have a solution  $  x \in X $. 
Therefore, the formulated problem needs to be made more precise. This is done as follows.

1) Characterize the set  $  E = E ( X , f _  \alpha  ) $
of sets  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
for which the system of equations (i3) (which may be infinite) has at least one solution  $  x \in X $. 
In other words, it is required to give a constructive description of the set  $  E $
of all admissible sets  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $, 
for a given fixed family of mappings  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $, 
such that (i3) has a solution in  $  X $.

2) Let  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
be a fixed admissible set of elements of  $  Y $ (i.e. belonging to the set  $  E $
in 1) for (i3). It is required to find the set of all solutions  $  x \in X $
of (i3).

When solving 1) or 2), answers to the following questions of a more particular nature are important.

3) What is the subset  $  X _ {1} \subset  X $
on which (i3) has a unique solution  $  x \in X _ {1} $
for each admissible set  $  \{ y _  \alpha  \} $
for  $  X _ {1} $
with  $  \{ y _  \alpha  \} \in E ( X _ {1} , f _  \alpha  ) $?

4) Let  $  E _ {1} $
be a subset of  $  E $, 
usually only given by some restrictive property. It is required to give a constructive characterization of the set of solutions  $  x \in X $
of (i3) under the condition that the right-hand side of (i3)  "runs over"   $  E _ {1} $.

The specification of sets  $  X $, 
$  Y $, 
families of mappings  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $ ($  f _  \alpha  :  X \rightarrow Y $
for all  $  \alpha \in \mathfrak A $) 
together with the questions 1) and 2) (and usually with the related question 3), or sometimes 4)) determine the interpolation problem (i3). A class of problems of this kind is called a class of direct interpolation problems.

Each of the above problems 1)–4) is of scientific interest in itself. Problem 1) has a  "multi-faceted character" : it is studied in number theory, functional analysis, function theory, etc. Suppose, e.g., that  $  x $
is a real number,  $  x \in \mathbf R $, 
and let  $  \{ x \} $
be its fractional part. A family of mappings  $  f _ {n} :  X \rightarrow Y $, 
$  n \in \mathbf N $, 
is given as follows:  $  X \subset  \mathbf R $, 
$  Y = [ 0 , 1 ) $, 
$  f _ {n} ( x) = \{ x  ^ {n} \} $, 
$  n = 1 , 2 \dots $
and the following concrete version of the interpolation problem (i3) is considered:

$$ \tag{2 }
f _ {n} ( x )  =  \{ x  ^ {n} \}  =  y _ {n} ,\ \ 
n= 1, 2 , \dots .
$$

For certain subsets  $  X \subset  \mathbf R $
one has investigated 1) for problem (2) to a certain extent. Problem (2) as a whole is difficult: Up till now (1978), e.g., no solution is known to the problem of the distribution of the fractional parts  $  \{ e  ^ {n} \} $
of powers of the number  $  e $. 
This is a very particular subproblem of 1) for (2). A relation between 1) and the basis problem for systems of elements in various function spaces has been observed in, e.g., [[#References|[9]]].

Problem 2) is the oldest of the theory of interpolation; it is the starting point of the theory of interpolation, and the names of I. Newton, J.L. Lagrange, N.H. Abel, Ch. Hermite, etc. are connected with it. Problems 1), 3) and 4) were not considered until the 20th century, while the solution to 2) was, as a rule, formal.

Problem 3) is closely related to 2), but is of interest only because in many problems it is equivalent to the completeness problem, and sometimes to the basis problem for various systems of elements  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $
in corresponding function spaces. (Completeness is usually established by Banach's criterion, in which the equivalence of completeness problems with a certain uniqueness problem is shown.)

An important topic of research related to 4) is that of studying classes of functions taking integer values on a given set of points (e.g.,  $  F ( n) $
or  $  F ( q  ^ {n} ) $, 
$  n = 0 , 1 \dots $
must be integers). This area was especially rapidly developed after the following result of G. Pólya: If an entire function  $  F ( z) $
of exponential type  $  \sigma <  \mathop{\rm ln}  2 $
is such that its values  $  F ( n) $, 
$  n = 0 , 1 \dots $
are integers, then  $  F ( z) $
is a polynomial. The constant  $   \mathop{\rm ln}  2 $
in this theorem is best possible, since  $  F ( z) = 2  ^ {z} = e ^ {z   \mathop{\rm ln}  2 } $
is an entire function of exponential type  $  \sigma =  \mathop{\rm ln}  2 $, 
which is different from a polynomial, and which takes integer values at  $  n = 0 , 1 , \cdots $ (cf., e.g., [[#References|[5]]], [[#References|[10]]]).

If the set  $  X $
in (i3) is a topological space and if a reduced problem (i3) (in some sense or another) has a solution  $  x  ^ {*} $, 
then one of the methods for solving it is an interpolation process in which the convergence of  $  x  ^ {*} $
to the solution of (i3) is studied. Particular forms of processes of this kind can be found above. However, in many cases problems of type (i3) can be solved effectively by functional-analytic methods (cf., e.g., [[#References|[10]]]).

Next to direct interpolation problems, inverse interpolation problems have some interest. The main contents of studies in this direction consist of the following.

Suppose that non-empty sets  $  X $, 
$  Y $
and a certain class  $  F $
of families of mappings  $  \{ {f _  \alpha  } : { {\alpha \in \mathfrak A } } \} $
acting from  $  X $
into  $  Y $
are given. Let  $  M = \{ {y _  \alpha  } : { {\alpha \in \mathfrak A } } \} $
be a certain family of sets of elements of  $  Y $. 
The problem is to find necessary and sufficient conditions on a subclass  $  F _ {M} \subset  F $
such that there is a family  $  \{ {f _  \alpha  } : { {\alpha \in \mathfrak A } } \} \in F _ {M} $
with the property that the set  $  \{ {f _  \alpha  ( x) } : { {\alpha \in \mathfrak A } } \} $
coincides with  $  M $ (or  $  \subset  M $, 
or  $  \supset M $) 
if  $  x $
runs over the entire set  $  X $. 
The sets  $  F $
and  $  M $
are strongly related to one another. Therefore it is usual in studies related to the branch of inverse interpolation problems to consider the pair  $  ( F , M ) $
as one entity. As an example of an inverse problem of the kind described above one may take one of the formulations of the circle of problems related to the well-known Nevanlinna–Pick interpolation problem: Let  $  \{ z _ {k} \} $
be a sequence of points in the open unit disc  $  | z | < 1 $
of the complex plane  $  \mathbf C $. 
Each function  $  x ( z) $
of class  $  H  ^  \infty  $ ($  H  ^  \infty  $
is the class of bounded analytic functions in  $  | z | < 1 $) 
is associated with its sequence of values at  $  z _ {k} $:

$$ 
S ( x)  =  \{ f _ {k} ( x) = x ( z _ {k} ) \} _ {k=1}  ^  \infty  .
$$

Thus, a certain kind of mappings  $  F $
from  $  X = H  ^  \infty  $
into  $  Y = \mathbf C $
is given. Let  $  M $
be the space  $  l _  \infty  $ (of bounded sequences of complex numbers  $  c = ( c _ {1} , c _ {2} , \cdots ) $
with norm  $  \| c \| = \sup _ {k}  | c _ {k} | $). 
In this case, the inverse problem has the following concrete form: Characterize the set of all sequences  $  \{ z _ {k} \} $
in  $  | z | < 1 $ (i.e. of the class  $  F _ {M} = F _ {l _  \infty   } $
of mappings of the particular form  $  f _ {k} ( x) = x ( z _ {k} ) $) 
with the property that the operator  $  S ( x) $
maps all of  $  H  ^  \infty  $
onto  $  l _  \infty  $. 
Sequences  $  \{ z _ {k} \} $
with this property are called interpolating sequences. Thus, the set of all interpolating sequences  $  \{ z _ {k} \} $
determines the class  $  F _ {M} = F _ {l _  \infty   } $
in the given situation. The solution to this problem is Carleson's theorem: A sequence  $  \{ z _ {k} \} $
in  $  | z | < 1 $
is interpolating if and only if a  $  \delta > 0 $
exists such that

$$ 
\prod _ {j \neq k } \left |

\frac{z _ {k} - z _ {j} }{1 - \overline{ {z }}\; _ {j} z _ {k} }
 \ 
\right |  >  \delta ,\ \ 
k = 1 , 2 , \cdots
$$

(the so-called separation condition). Inverse interpolation problems of the kind solved by L. Carleson have also been considered for other function classes and corresponding spaces of sequences of numbers (cf., e.g., [[#References|[9]]], [[#References|[12]]], [[#References|[13]]], [[#References|[14]]]).

See also [[Abel–Goncharov problem|Abel–Goncharov problem]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.O. [A.O. Gel'fond] Gelfond,   "Differenzenrechnung" , Deutsch. Verlag Wissenschaft.  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.L. Goncharov,   "The theory of interpolation and approximation of functions" , Moscow  (1954)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  J.L. Walsh,   "Interpolation and approximation by rational functions in the complex domain" , Amer. Math. Soc.  (1969)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L. Bieberbach,   "Analytische Fortsetzung" , Springer  (1955)  pp. Sect. 3</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  N.E. Nörlund,   "Volesungen über Differenzenrechnung" , Springer  (1924)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  N.E. Nörlund,   "Leçons sur les séries d'interpolation" , Gauthier-Villars  (1926)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  J.M. Whittaker,   "Interpolatory function theory" , Cambridge Univ. Press  (1935)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  P.L. Duren,   "Theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930200.png" /> spaces" , Acad. Press  (1970)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  Yu.A. Kaz'min,   "Interpolation methods for analytic functions and their applications" , Moscow  (1972)  (In Russian)  (Thesis)</TD></TR><TR><TD valign="top">[11a]</TD> <TD valign="top">  Yu.F. Korobeinik,   "On a dual problem 1. General results. Application to Fréchet spaces"  ''Math. USSR Sb.'' , '''26'''  (1975)  pp. 181–212  ''Mat. Sb.'' , '''97''' :  2  (1975)  pp. 193–229</TD></TR><TR><TD valign="top">[11b]</TD> <TD valign="top">  Yu.F. Korobeinik,   "On a dual problem 2. Applications to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930201.png" />-spaces and other questions"  ''Math. USSR Sb.'' , '''27'''  (1976)  pp. 1–22  ''Mat. Sb.'' , '''98''' :  1  (1975)  pp. 3–26</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  V. Kabaila,   "Interpolation sequences for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930202.png" /> classes in case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930203.png" />"  ''Litovsk. Mat. Sb.'' , '''3''' :  1  (1963)  pp. 141–147  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  A.M. [A.M. Sedletskii] Sedleckii,   "Interpolation in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930204.png" /> spaces over a half-plane"  ''Soviet Math. Dokl.'' , '''14'''  (1973)  pp. 276–278  ''Dokl. Akad. Nauk. SSSR'' , '''208''' :  6  (1973)  pp. 1293–1295</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  S.V. Shvedenko,   "The interpolation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930205.png" /> sequences by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051930/i051930206.png" /> functions"  ''Math. Notes'' , '''21'''  (1977)  pp. 281–284  ''Mat. Zametki'' , '''21''' :  4  (1977)  pp. 503–508</TD></TR></table>

====Comments====
The topic of interpolation is a vast one, and is the subject of numerous papers and several treatises. It also includes e.g. interpolation by (all kinds of) spline functions [[#References|[a4]]] and so-called Birkhoff interpolation (cf. [[Interpolation process|Interpolation process]]) [[#References|[a3]]]. Interpolation in several variables has also been studied in detail (cf. [[#References|[a2]]]).

More on interpolating sequences can be found in, e.g., [[#References|[a5]]]. See also [[Pick theorem|Pick theorem]]; [[Nevanlinna–Pick problem|Nevanlinna–Pick problem]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Carleson,   "An interpolation problem for bounded analytic functions"  ''Amer. J. Math.'' , '''80'''  (1958)  pp. 921–930</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.R. Graves-Morris (ed.)  E.B. Saff (ed.)  R.S. Varga (ed.) , ''Rational Approximation and Interpolation (Tampa, 1983)'' , ''Lect. notes in math.'' , '''1105''' , Springer  (1984)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.G. Lorentz,   K. Jetter,   S.D. Riemenschneider,   "Birkhoff interpolation" , Wiley  (1983)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L.L. Schumaker,   "Spline functions, basic theory" , Wiley  (1981)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J.B. Garnett,   "Bounded analytic functions" , Acad. Press  (1984)</TD></TR></table>