Namespaces
Variants
Actions

Difference between revisions of "Interpolation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fixing dots)
 
(2 intermediate revisions by 2 users not shown)
Line 14: Line 14:
  
 
Suppose one is given  $  n+ 1 $
 
Suppose one is given  $  n+ 1 $
points  $  \{ x _ {k} \} _ {k=} ^ {n} $
+
points  $  \{ x _ {k} \} _ {k=0} ^ {n} $
 
on the segment  $  \Delta = [ a , b ] $,  
 
on the segment  $  \Delta = [ a , b ] $,  
 
where  $  a \leq  x _ {0} < \dots < x _ {n} \leq  b $,  
 
where  $  a \leq  x _ {0} < \dots < x _ {n} \leq  b $,  
and a set of  $  n+ 1 $(
+
and a set of  $  n+ 1 $ (not necessarily different) values  $  \{ y _ {k} \} _ {k=0}  ^ {n} $.  
not necessarily different) values  $  \{ y _ {k} \} _ {k=} 0 ^ {n} $.  
 
 
Suppose that it is known that a function  $  f $,  
 
Suppose that it is known that a function  $  f $,  
 
belonging to some fixed class of functions  $  K $
 
belonging to some fixed class of functions  $  K $
that are defined at least on  $  \Delta $(
+
that are defined at least on  $  \Delta $ (e.g.,  $  f \in \Pi _ {n} $,  
e.g.,  $  f \in \Pi _ {n} $,  
 
 
where  $  \Pi _ {n} $
 
where  $  \Pi _ {n} $
 
is the set of algebraic polynomials of degree  $  \leq  n $,  
 
is the set of algebraic polynomials of degree  $  \leq  n $,  
or  $  f \in C  ^ {n+} 1 ( \Delta ) $),  
+
or  $  f \in C  ^ {n+1} ( \Delta ) $),  
 
satisfies the conditions
 
satisfies the conditions
  
 
$$ \tag{i1 }
 
$$ \tag{i1 }
f ( x)  \in  K ; \  f ( x _ {k} )  =  y _ {k} ,\  k = 0 \dots n .
+
f ( x)  \in  K ; \  f ( x _ {k} )  =  y _ {k} ,\  k = 0, \dots, n .
 
$$
 
$$
  
Line 37: Line 35:
 
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 $,  
 
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) $:  
 
how to obtain, with prescribed accuracy, information on the behaviour of  $  f ( x) $:  
1) on the intervals  $  ( x _ {k-} 1 , x _ {k} ) $,  
+
1) on the intervals  $  ( x _ {k-1} , x _ {k} ) $,  
$  k = 1 \dots n $,  
+
$  k = 1, \dots, n $,  
 
i.e. between (in Latin: inter) the nodes  $  x _ {k} $,  
 
i.e. between (in Latin: inter) the nodes  $  x _ {k} $,  
$  k = 0 \dots n $;  
+
$  k = 0, \dots, n $;  
 
and 2) outside (in Latin: extra) the interval  $  [ x _ {0} , x _ {n} ] $
 
and 2) outside (in Latin: extra) the interval  $  [ x _ {0} , x _ {n} ] $
containing all nodes  $  \{ x _ {k} \} _ {k=} 0 ^ {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 $;  
 
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).
 
these both were later merged into the one interpolation problem (i1).
Line 56: Line 54:
 
$$  
 
$$  
 
= \  
 
= \  
\sum _ { k= } 0 ^ { n }  y _ {k}  
+
\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} ) }
+
\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} ) }
 
  .
 
  .
 
$$
 
$$
Line 83: Line 81:
 
belongs, in other words,  $  R _ {n}  ^ {f} ( x) $
 
belongs, in other words,  $  R _ {n}  ^ {f} ( x) $
 
depends on a priori known properties of  $  f $.  
 
depends on a priori known properties of  $  f $.  
E.g., if  $  K = C  ^ {n+} 1 ( \Delta ) $,  
+
E.g., if  $  K = C  ^ {n+1} ( \Delta ) $,  
 
then the remainder term for (i1) has the form
 
then the remainder term for (i1) has the form
  
Line 96: Line 94:
  
 
$$  
 
$$  
A ( x)  =  \prod _ { k= } 0 ^ { n }  ( x - x _ {k} ) .
+
A ( x)  =  \prod _ { k=0} ^ { n }  ( x - x _ {k} ) .
 
$$
 
$$
  
Line 105: Line 103:
 
and  $  x $.  
 
and  $  x $.  
 
The given formula for the remainder is due to A.L. Cauchy, cf. [[#References|[3]]]. The quantity  $  R _ {n}  ^ {f} ( 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} $
+
depends mainly on the form of the distribution and the number of interpolation nodes  $  \{ x _ {k} \} _ {k=0}  ^ {n} $
 
on  $  \Delta $.  
 
on  $  \Delta $.  
 
It is in this connection natural to assume that the more interpolation nodes  $  x _ {k} $
 
It is in this connection natural to assume that the more interpolation nodes  $  x _ {k} $
Line 119: Line 117:
 
$  x _ {k} \neq x _ {j} $
 
$  x _ {k} \neq x _ {j} $
 
if  $  k \neq j $,  
 
if  $  k \neq j $,  
is countable; suppose also that a sequence of values  $  \{ y _ {k} \} _ {k=} 0 ^  \infty  $
+
is countable; suppose also that a sequence of values  $  \{ y _ {k} \} _ {k=0}  ^  \infty  $
 
is given. The question is: How to recover  $  f $
 
is given. The question is: How to recover  $  f $
 
from the given data:
 
from the given data:
Line 130: Line 128:
  
 
$$  
 
$$  
f ( x _ {k _ {j}  } )  =  y _ {k _ {j}  } ,\  j = 1 \dots n+ 1 ,
+
f ( x _ {k _ {j}  } )  =  y _ {k _ {j}  } ,\  j = 1, \dots, n+ 1 ,
 
$$
 
$$
  
Line 136: Line 134:
 
Let  $  L _ {n}  ^ {f} ( x) $
 
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) $
 
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 $(
+
as  $  n \rightarrow \infty $ (this is equivalent, in particular, to the study of the question of the remainder  $  R _ {n}  ^ {f} ( x) $
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 $
 
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 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]]]).
Line 143: Line 140:
 
In the latter, along with interpolation problems of the kind considered above and defined by the simplest functionals  $  f ( x _ {k} ) $,  
 
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} ) $,  
 
one also started to study other problems, in which, e.g., the values of derivatives  $  f ^ { ( m) } ( x _ {k} ) $,  
$  m = 0 \dots n _ {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} $,  
 
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} $
 
other underlying interpolating sets of functions are considered, e.g. the class  $  T _ {n} $
 
of trigonometric polynomials of degree  $  \leq  n $,  
 
of trigonometric polynomials of degree  $  \leq  n $,  
classes of rational functions  $  \Pi _ {m , n }  $(
+
classes of rational functions  $  \Pi _ {m , n }  $ (of the form  $  p _ {m} / q _ {n} $,  
of the form  $  p _ {m} / q _ {n} $,  
 
 
where  $  p _ {m} \in \Pi _ {m} $
 
where  $  p _ {m} \in \Pi _ {m} $
 
and  $  q _ {n} \in \Pi _ {n} $,  
 
and  $  q _ {n} \in \Pi _ {n} $,  
Line 182: Line 178:
  
 
2) Let  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
 
2) Let  $  \{ y _  \alpha  \} _ {\alpha \in \mathfrak A }  $
be a fixed admissible set of elements of  $  Y $(
+
be a fixed admissible set of elements of  $  Y $ (i.e. belonging to the set  $  E $
i.e. belonging to the set  $  E $
 
 
in 1) for (i3). It is required to find the set of all solutions  $  x \in X $
 
in 1) for (i3). It is required to find the set of all solutions  $  x \in X $
 
of (i3).
 
of (i3).
Line 202: Line 197:
 
The specification of sets  $  X $,  
 
The specification of sets  $  X $,  
 
$  Y $,  
 
$  Y $,  
families of mappings  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $(
+
families of mappings  $  \{ f _  \alpha  \} _ {\alpha \in \mathfrak A }  $ ($  f _  \alpha  :  X \rightarrow Y $
$  f _  \alpha  :  X \rightarrow Y $
 
 
for all  $  \alpha \in \mathfrak A $)  
 
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.
 
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.
Line 215: Line 209:
 
$  Y = [ 0 , 1 ) $,  
 
$  Y = [ 0 , 1 ) $,  
 
$  f _ {n} ( x) = \{ x  ^ {n} \} $,  
 
$  f _ {n} ( x) = \{ x  ^ {n} \} $,  
$  n = 1 , 2 \dots $
+
$  n = 1 , 2, \dots $
 
and the following concrete version of the interpolation problem (i3) is considered:
 
and the following concrete version of the interpolation problem (i3) is considered:
  
 
$$ \tag{2 }
 
$$ \tag{2 }
 
f _ {n} ( x )  =  \{ x  ^ {n} \}  =  y _ {n} ,\ \  
 
f _ {n} ( x )  =  \{ x  ^ {n} \}  =  y _ {n} ,\ \  
n= 1, 2 , .  .  . .
+
n= 1, 2 , \dots .
 
$$
 
$$
  
Line 235: Line 229:
 
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) $
 
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} ) $,  
 
or  $  F ( q  ^ {n} ) $,  
$  n = 0 , 1 \dots $
+
$  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) $
 
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 $
 
of exponential type  $  \sigma <  \mathop{\rm ln}  2 $
 
is such that its values  $  F ( n) $,  
 
is such that its values  $  F ( n) $,  
$  n = 0 , 1 \dots $
+
$  n = 0 , 1, \dots $
 
are integers, then  $  F ( z) $
 
are integers, then  $  F ( z) $
 
is a polynomial. The constant  $  \mathop{\rm ln}  2 $
 
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 } $
 
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 $,  
 
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 , .  .  . $(
+
which is different from a polynomial, and which takes integer values at  $  n = 0 , 1 , \dots $ (cf., e.g., [[#References|[5]]], [[#References|[10]]]).
cf., e.g., [[#References|[5]]], [[#References|[10]]]).
 
  
 
If the set  $  X $
 
If the set  $  X $
Line 265: Line 258:
 
such that there is a family  $  \{ {f _  \alpha  } : { {\alpha \in \mathfrak A } } \} \in F _ {M} $
 
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 } } \} $
 
with the property that the set  $  \{ {f _  \alpha  ( x) } : { {\alpha \in \mathfrak A } } \} $
coincides with  $  M $(
+
coincides with  $  M $ (or  $  \subset  M $,  
or  $  \subset  M $,  
 
 
or  $  \supset M $)  
 
or  $  \supset M $)  
 
if  $  x $
 
if  $  x $
Line 277: Line 269:
 
of the complex plane  $  \mathbf C $.  
 
of the complex plane  $  \mathbf C $.  
 
Each function  $  x ( z) $
 
Each function  $  x ( z) $
of class  $  H  ^  \infty  $(
+
of class  $  H  ^  \infty  $ ($  H  ^  \infty  $
$  H  ^  \infty  $
 
 
is the class of bounded analytic functions in  $  | z | < 1 $)  
 
is the class of bounded analytic functions in  $  | z | < 1 $)  
 
is associated with its sequence of values at  $  z _ {k} $:
 
is associated with its sequence of values at  $  z _ {k} $:
  
 
$$  
 
$$  
S ( x)  =  \{ f _ {k} ( x) = x ( z _ {k} ) \} _ {k=} 1 ^  \infty  .
+
S ( x)  =  \{ f _ {k} ( x) = x ( z _ {k} ) \} _ {k=1}  ^  \infty  .
 
$$
 
$$
  
Line 290: Line 281:
 
into  $  Y = \mathbf C $
 
into  $  Y = \mathbf C $
 
is given. Let  $  M $
 
is given. Let  $  M $
be the space  $  l _  \infty  $(
+
be the space  $  l _  \infty  $ (of bounded sequences of complex numbers  $  c = ( c _ {1} , c _ {2} , \dots ) $
of bounded sequences of complex numbers  $  c = ( c _ {1} , c _ {2} , .  .  . ) $
 
 
with norm  $  \| c \| = \sup _ {k}  | c _ {k} | $).  
 
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 this case, the inverse problem has the following concrete form: Characterize the set of all sequences  $  \{ z _ {k} \} $
in  $  | z | < 1 $(
+
in  $  | z | < 1 $ (i.e. of the class  $  F _ {M} = F _ {l _  \infty  } $
i.e. of the class  $  F _ {M} = F _ {l _  \infty  } $
 
 
of mappings of the particular form  $  f _ {k} ( x) = x ( z _ {k} ) $)  
 
of mappings of the particular form  $  f _ {k} ( x) = x ( z _ {k} ) $)  
 
with the property that the operator  $  S ( x) $
 
with the property that the operator  $  S ( x) $
Line 314: Line 303:
 
  \  
 
  \  
 
\right |  >  \delta ,\ \  
 
\right |  >  \delta ,\ \  
k = 1 , 2 , .  .  .
+
k = 1 , 2 , \dots
 
$$
 
$$
  

Latest revision as of 07:44, 21 January 2022


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. [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). 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. [3]), but also in numerical methods (cf. Interpolation in numerical mathematics, as well as [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.

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., [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 , \dots $ (cf., e.g., [5], [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., [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} , \dots ) $ 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 , \dots $$

(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., [9], [12], [13], [14]).

See also Abel–Goncharov problem.

References

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

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 [a4] and so-called Birkhoff interpolation (cf. Interpolation process) [a3]. Interpolation in several variables has also been studied in detail (cf. [a2]).

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

References

[a1] L. Carleson, "An interpolation problem for bounded analytic functions" Amer. J. Math. , 80 (1958) pp. 921–930
[a2] 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)
[a3] G.G. Lorentz, K. Jetter, S.D. Riemenschneider, "Birkhoff interpolation" , Wiley (1983)
[a4] L.L. Schumaker, "Spline functions, basic theory" , Wiley (1981)
[a5] J.B. Garnett, "Bounded analytic functions" , Acad. Press (1984)
How to Cite This Entry:
Interpolation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interpolation&oldid=47391
This article was adapted from an original article by Yu.A. Kaz'min (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article