§3.3 Interpolation
Contents
- §3.3(i) Lagrange Interpolation
- §3.3(ii) Lagrange Interpolation with Equally-Spaced Nodes
- §3.3(iii) Divided Differences
- §3.3(iv) Newton’s Interpolation Formula
- §3.3(v) Inverse Interpolation
- §3.3(vi) Other Interpolation Methods
§3.3(i) Lagrange Interpolation
The nodes or abscissas are real or complex; function values
are
. Given
distinct points
and
corresponding
function values
, the Lagrange interpolation polynomial is the
unique polynomial
of degree not exceeding
such that
,
. It is given by
![P_{n}(z)=\sum _{{k=0}}^{n}\ell _{k}(z)f_{k}=\sum _{{k=0}}^{n}\frac{\omega _{{n+1}}(z)}{(z-z_{k})\omega _{{n+1}}^{{\prime}}(z_{k})}f_{k},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E1.png)
where
![\ell _{k}(z)={\sideset{}{{}^{{\prime}}}{\prod}_{{j=0}}^{n}}\frac{z-z_{j}}{z_{k}-z_{j}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E2a.png)
![\ell _{k}(z_{j})=\delta _{{k,j}}.](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E2b.png)
Here the prime signifies that the factor for is to be omitted,
is the Kronecker symbol, and
is the nodal
polynomial
![\omega _{{n+1}}(z)=\prod _{{k=0}}^{n}(z-z_{k}).](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E3.png)
With an error term the Lagrange interpolation formula for is given
by
![f(z)=\sum _{{k=0}}^{n}\ell _{{k}}(z)f_{k}+R_{n}(z).](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E4.png)
If ,
(
), and the nodes
are real, and
is
continuous on the smallest closed interval
containing
, then the error can be expressed
![R_{n}(x)=\frac{f^{{(n+1)}}(\xi)}{(n+1)!}\,\omega _{{n+1}}(x),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E5.png)
for some . If
is analytic in a simply-connected domain
(§1.13(i)), then for
,
![R_{n}(z)=\frac{\omega _{{n+1}}(z)}{2\pi i}\int _{C}\frac{f(\zeta)}{(\zeta-z)\omega _{{n+1}}(\zeta)}d\zeta,](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E6.png)
where is a simple closed contour in
described in the positive
rotational sense and enclosing the points
.
§3.3(ii) Lagrange Interpolation with Equally-Spaced Nodes
The -point formula (3.3.4) can be written in the
form
![f_{t}=f(x_{0}+th)=\sum _{{k=n_{0}}}^{{n_{1}}}A_{k}^{n}f_{k}+R_{{n,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E7.png)
![n_{0}<t<n_{1}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m144.png)
where the nodes (
) and function
are real,
![n_{0}=-\tfrac{1}{2}(n-\sigma),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E8a.png)
![n_{1}=\tfrac{1}{2}(n+\sigma),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E8b.png)
![\sigma=\tfrac{1}{2}(1-(-1)^{n}),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E9.png)
and are the Lagrangian interpolation coefficients defined by
![A_{k}^{n}=\frac{(-1)^{{n_{1}+k}}}{(k-n_{0})!\,(n_{1}-k)!(t-k)}\,\prod _{{m=n_{0}}}^{{n_{1}}}(t-m).](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E10.png)
Let be defined by
![c_{n}=\frac{1}{(n+1)!}\max\prod _{{k=n_{0}}}^{{n_{1}}}\left|t-k\right|,](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E12.png)
where the maximum is taken over -intervals given in the formulas below. Then
for these
-intervals,
![\left|R_{{n,t}}\right|\leq c_{n}h^{{n+1}}\left|f^{{(n+1)}}(\xi)\right|.](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E13.png)
¶ Linear Interpolation
![f_{t}=(1-t)f_{0}+tf_{1}+R_{{1,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E14.png)
![0<t<1](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m88.png)
![c_{1}=\tfrac{1}{8},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E15.png)
![0<t<1](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m88.png)
¶ Three-Point Formula
![f_{t}=\sum _{{k=-1}}^{1}A_{k}^{2}f_{k}+R_{{2,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E16.png)
![\left|t\right|<1](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m114.png)
![A_{{-1}}^{2}=\tfrac{1}{2}t(t-1),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E17a.png)
![A_{0}^{2}=1-t^{2},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E17b.png)
![A_{1}^{2}=\tfrac{1}{2}t(t+1),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E17c.png)
![c_{2}=1/(9\sqrt{3})=0.0641\ldots,](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E18.png)
![\left|t\right|<1](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m114.png)
¶ Four-Point Formula
![f_{t}=\sum _{{k=-1}}^{2}A_{k}^{3}f_{k}+R_{{3,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E19.png)
![-1<t<2](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m85.png)
![A_{{-1}}^{3}=-\tfrac{1}{6}t(t-1)(t-2),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E20a.png)
![A_{0}^{3}=\tfrac{1}{2}(t^{2}-1)(t-2),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E20b.png)
![A_{1}^{3}=-\tfrac{1}{2}t(t+1)(t-2),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E20c.png)
![A_{2}^{3}=\tfrac{1}{6}t(t^{2}-1),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E20d.png)
![c_{3}=\begin{cases}\tfrac{3}{128}=0.0234\ldots,&0<t<1,\\
\tfrac{1}{24}=0.0416\ldots,&-1<t<0\mbox{ or }1<t<2.\\
\end{cases}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E21.png)
¶ Five-Point Formula
![f_{t}=\sum _{{k=-2}}^{2}A_{k}^{4}f_{k}+R_{{4,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E22.png)
![\left|t\right|<2](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m115.png)
![A_{{-2}}^{4}=\tfrac{1}{24}t(t^{2}-1)(t-2),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E23a.png)
![A_{{-1}}^{4}=-\tfrac{1}{6}t(t-1)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E23b.png)
![A_{0}^{4}=\tfrac{1}{4}(t^{2}-1)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E23c.png)
![A_{1}^{4}=-\tfrac{1}{6}t(t+1)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E23d.png)
![A_{2}^{4}=\tfrac{1}{24}t(t^{2}-1)(t+2),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E23e.png)
![c_{4}=\begin{cases}0.0118\ldots,&\left|t\right|<1,\\
0.0302\ldots,&1<\left|t\right|<2.\\
\end{cases}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E24.png)
¶ Six-Point Formula
![f_{t}=\sum _{{k=-2}}^{3}A_{k}^{5}f_{k}+R_{{5,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E25.png)
![-2<t<3](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m86.png)
![A_{{-2}}^{5}=-\tfrac{1}{120}t(t^{2}-1)(t-2)(t-3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26a.png)
![A_{{-1}}^{5}=\tfrac{1}{24}t(t-1)(t^{2}-4)(t-3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26b.png)
![A_{0}^{5}=-\tfrac{1}{12}(t^{2}-1)(t^{2}-4)(t-3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26c.png)
![A_{1}^{5}=\tfrac{1}{12}t(t+1)(t^{2}-4)(t-3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26d.png)
![A_{2}^{5}=-\tfrac{1}{24}t(t^{2}-1)(t+2)(t-3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26e.png)
![A_{3}^{5}=\tfrac{1}{120}t(t^{2}-1)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E26f.png)
![c_{5}=\begin{cases}0.00488\ldots,&0<t<1,\\
0.00701\ldots,&-1<t<0\mbox{ or }1<t<2,\\
0.0234\ldots,&-2<t<-1\mbox{ or }2<t<3.\end{cases}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E27.png)
¶ Seven-Point Formula
![f_{t}=\sum _{{k=-3}}^{3}A_{k}^{6}f_{k}+R_{{6,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E28.png)
![\left|t\right|<3](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m116.png)
![A_{{-3}}^{6}=\tfrac{1}{720}t(t^{2}-1)(t-3)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29a.png)
![A_{{-2}}^{6}=-\tfrac{1}{120}t(t^{2}-1)(t-2)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29b.png)
![A_{{-1}}^{6}=\tfrac{1}{48}t(t-1)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29c.png)
![A_{0}^{6}=-\tfrac{1}{36}(t^{2}-1)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29d.png)
![A_{1}^{6}=\tfrac{1}{48}t(t+1)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29e.png)
![A_{2}^{6}=-\tfrac{1}{120}t(t^{2}-1)(t+2)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29f.png)
![A_{3}^{6}=\tfrac{1}{720}t(t^{2}-1)(t+3)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E29g.png)
![c_{6}=\begin{cases}0.00245\ldots,&\left|t\right|<1,\\
0.00459\ldots,&1<\left|t\right|<2,\\
0.0190\ldots,&2<\left|t\right|<3.\\
\end{cases}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E30.png)
¶ Eight-Point Formula
![f_{t}=\sum _{{k=-3}}^{4}A_{k}^{7}f_{k}+R_{{7,t}},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E31.png)
![-3<t<4](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/m87.png)
![A_{{-3}}^{7}=-\tfrac{1}{5040}t(t^{2}-1)(t-3)(t-4)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32a.png)
![A_{{-2}}^{7}=\tfrac{1}{720}t(t^{2}-1)(t-2)(t-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32b.png)
![A_{{-1}}^{7}=-\tfrac{1}{240}t(t-1)(t-4)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32c.png)
![A_{0}^{7}=\tfrac{1}{144}(t^{2}-1)(t-4)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32d.png)
![A_{1}^{7}=-\tfrac{1}{144}t(t+1)(t-4)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32e.png)
![A_{2}^{7}=\tfrac{1}{240}t(t^{2}-1)(t+2)(t-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32f.png)
![A_{3}^{7}=-\tfrac{1}{720}t(t^{2}-1)(t+3)(t-4)(t^{2}-4),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32g.png)
![A_{4}^{7}=\tfrac{1}{5040}t(t^{2}-1)(t^{2}-4)(t^{2}-9),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E32h.png)
![c_{7}=\begin{cases}0.00106\ldots,&0<t<1,\\
0.00139\ldots,&-1<t<0\mbox{ or }1<t<2,\\
0.00321\ldots,&-2<t<-1\mbox{ or }2<t<3,\\
0.0158\ldots,&-3<t<-2\mbox{ or }3<t<4.\\
\end{cases}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E33.png)
§3.3(iii) Divided Differences
The divided differences of relative to a sequence of distinct points
are defined by
![f=f_{0},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E34a.png)
![f=({[z_{1}]}f-{[z_{0}]}f)/(z_{1}-z_{0}),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E34b.png)
![f=({[z_{1},z_{2}]}f-{[z_{0},z_{1}]}f)/(z_{2}-z_{0}),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E34c.png)
and so on. Explicitly, the divided difference of order is given by
![[z_{0},z_{1},\dots,z_{n}]f=\sum _{{k=0}}^{n}\left(\ifrac{f(z_{k})}{\prod _{{\substack{0\leq j\leq n\\
j\neq k}}}(z_{k}-z_{j})}\right).](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E35.png)
If and the
(
) are real, and
is
times continuously
differentiable on a closed interval containing the
, then
![[x_{0},x_{1},\dots,x_{n}]f=\frac{f^{{(n)}}(\xi)}{n!}](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E36.png)
and again is as in §3.3(i).
If
is analytic in a simply-connected domain
, then for
,
![[z_{0},z_{1},\dots,z_{n}]f=\frac{1}{2\pi i}\int _{C}\frac{f(\zeta)}{\omega _{{n+1}}(\zeta)}d\zeta,](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E37.png)
where is given by (3.3.3), and
is a
simple closed contour in
described in the positive
rotational sense and enclosing
.
§3.3(iv) Newton’s Interpolation Formula
This represents the Lagrange interpolation polynomial in terms of divided differences:
![f(z)=[z_{0}]f+(z-z_{0})[z_{0},z_{1}]f+(z-z_{0})(z-z_{1})[z_{0},z_{1},z_{2}]f+\cdots+(z-z_{0})(z-z_{1})\cdots(z-z_{{n-1}})[z_{0},z_{1},\dots,z_{n}]f+R_{n}(z).](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E38.png)
The interpolation error is as in §3.3(i). Newton’s
formula has the advantage of allowing easy updating: incorporation of a new
point
requires only addition of the term with
to (3.3.38), plus the computation
of this divided difference. Another advantage is its robustness with respect to
confluence of the set of points
. For example, for
coincident points the limiting form is given by
.
§3.3(v) Inverse Interpolation
In this method we interchange the roles of the points and the function
values
. It can be used for solving a nonlinear scalar equation
approximately. Another approach is to combine the methods of §3.8
with direct interpolation and §3.4.
¶ Example
To compute the first negative zero of the Airy
function
(§9.2). The inverse interpolation
polynomial is given by
![x(f)=[f_{0}]x+(f-f_{0})[f_{0},f_{1}]x+(f-f_{0})(f-f_{1})[f_{0},f_{1},f_{2}]x;](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E39.png)
compare (3.3.38). With ,
,
, we obtain
![x=-2.2+1.44011\; 1973(f-0.09614\; 53780)+0.08865\; 85832\*(f-0.09614\; 53780)(f-0.02670\; 63331),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E40.png)
and with we find that
, with 4 correct digits. By
using this approximation to
as a new point,
, and evaluating
, we find that
, with
9 correct digits.
For comparison, we use Newton’s interpolation formula (3.3.38)
![f(x)=0.09614\; 53780+0.69439\; 0 4495(x+2.1)-0.03007\; 14275(x+2.2)(x+2.3),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E41.png)
with the derivative
![f^{{\prime}}(x)=0.55906\; 90257-0.06014\; 28550x,](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E42.png)
and compute an approximation to by using Newton’s rule
(§3.8(ii))
with starting value
. This gives the new point
. Then by using
in Newton’s interpolation
formula, evaluating
and
recomputing
, another
application of Newton’s rule with starting value
gives the
approximation
, with 8 correct digits.
§3.3(vi) Other Interpolation Methods
For Hermite interpolation, trigonometric interpolation, spline interpolation, rational interpolation (by using continued fractions), interpolation based on Chebyshev points, and bivariate interpolation, see Bulirsch and Rutishauser (1968), Davis (1975, pp. 27–31), and Mason and Handscomb (2003, Chapter 6). These references also describe convergence properties of the interpolation formulas.
For interpolation of a bounded function on
the cardinal
function of
is defined by
![C(f,h)(x)=\sum _{{k=-\infty}}^{\infty}f(kh)S(k,h)(x),](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E43.png)
where
![S(k,h)(x)=\frac{\mathop{\sin\/}\nolimits\!\left(\pi(x-kh)/h\right)}{\pi(x-kh)/h},](https://webarchive.library.unt.edu/web/20130224162819im_/http://dlmf.nist.gov/3/3/E44.png)
is called the Sinc function. For theory and applications see Stenger (1993, Chapter 3).