§3.3 Interpolation

The nodes or abscissas $z_k$ are real or complex; function values are $f_k=f(z_k)$. Given $n+1$ distinct points $z_k$ and $n+1$ corresponding function values $f_k$, the Lagrange interpolation polynomial is the unique polynomial $P_n(z)$ of degree not exceeding $n$ such that $P_n(z_k)=f_k$, $k=0,1,\mathrm{\dots },n$. It is given by

3.3.1		$$P_n(z)=\sum _{k=0}^n{\mathrm{\ell }}_k(z)f_k={\omega }_{n+1}(z)\sum _{k=0}^n\frac{{\tilde{\omega }}_k}{z-z_k}{f}_k=\sum _{k=0}^n\frac{{\tilde{\omega }}_k{f}_k}{z-z_k}/\sum _{k=0}^n\frac{{\tilde{\omega }}_k}{z-z_k},$$
ⓘ Symbols: $f_t$: function values, $z_k$: nodes of function, ${\mathrm{\ell }}_k(z)$: Lagrange interpolation polynomial and ${\omega }_{n+1}(z)$: nodal polynomial A&S Ref: 25.2.1 Referenced by: §3.3(i), Erratum (V1.1.3) for Subsection 3.3(i) Permalink: http://dlmf.nist.gov/3.3.E1 Encodings: TeX, pMML, png See also: Annotations for §3.3(i), §3.3 and Ch.3

where

3.3.2		${\mathrm{\ell }}_k(z)$	$=\underset{j=0\phantom{\prime }}{\overset{n\phantom{\prime }}{{\displaystyle {\prod }^{\prime }}}}{\displaystyle \frac{z-z_j}{z_k-z_j}},$
		${\mathrm{\ell }}_k(z_j)$	$={\delta }_{k,j}.$
ⓘ Defines: ${\mathrm{\ell }}_k(z)$: Lagrange interpolation polynomial (locally) Symbols: ${\delta }_{j,k}$: Kronecker delta and $z_k$: nodes of function Permalink: http://dlmf.nist.gov/3.3.E2 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §3.3(i), §3.3 and Ch.3

Here the prime signifies that the factor for $j=k$ is to be omitted, ${\delta }_{k,j}$ is the Kronecker symbol, and ${\omega }_{n+1}(z)$ is the nodal polynomial

3.3.3		$${\omega }_{n+1}(z)=\prod _{k=0}^n(z-z_k),$$
ⓘ Defines: ${\omega }_{n+1}(z)$: nodal polynomial (locally) Symbols: $z_k$: nodes of function Referenced by: §3.3(iii), Erratum (V1.1.3) for Subsection 3.3(i) Permalink: http://dlmf.nist.gov/3.3.E3 Encodings: TeX, pMML, png See also: Annotations for §3.3(i), §3.3 and Ch.3

and the weights ${\tilde{\omega }}_k$ are

3.3.3_1		$${\tilde{\omega }}_k=\frac{1}{{\omega }_{n+1}^{\prime }(z_k)}=\underset{j=0\phantom{\prime }}{\overset{n\phantom{\prime }}{{\prod }^{\prime }}}\frac{1}{z_k-z_j}.$$
ⓘ Symbols: $z_k$: nodes of function and ${\omega }_{n+1}(z)$: nodal polynomial Referenced by: §3.3(i), Erratum (V1.1.3) for Additions Permalink: http://dlmf.nist.gov/3.3.E3_1 Encodings: TeX, pMML, png Addition (effective with 1.1.3): This equation was added. See also: Annotations for §3.3(i), §3.3 and Ch.3

The final expression in (3.3.1) is the Barycentric form of the Lagrange interpolation formula. It is a direct consequence of the identity

3.3.3_2		$$1=\sum _{k=0}^n{\mathrm{\ell }}_k(z)={\omega }_{n+1}(z)\sum _{k=0}^n\frac{{\tilde{\omega }}_k}{z-z_k},$$
ⓘ Symbols: $z_k$: nodes of function, ${\mathrm{\ell }}_k(z)$: Lagrange interpolation polynomial and ${\omega }_{n+1}(z)$: nodal polynomial Referenced by: §3.3(i), Erratum (V1.1.3) for Additions Permalink: http://dlmf.nist.gov/3.3.E3_2 Encodings: TeX, pMML, png Addition (effective with 1.1.3): This equation was added. See also: Annotations for §3.3(i), §3.3 and Ch.3

and according to Berrut and Trefethen (2004) it is the most efficient representation of $P_n(z)$.

With an error term the Lagrange interpolation formula for $f$ is given by

3.3.4		$$f(z)=\sum _{k=0}^n{\mathrm{\ell }}_k(z)f_k+R_n(z).$$
ⓘ Symbols: $f(z)$: function, $f_t$: function values, ${\mathrm{\ell }}_k(z)$: Lagrange interpolation polynomial and $R_n(x)$: remainder A&S Ref: 25.2.1 Referenced by: §3.3(ii), §3.4(i) Permalink: http://dlmf.nist.gov/3.3.E4 Encodings: TeX, pMML, png See also: Annotations for §3.3(i), §3.3 and Ch.3

If $f$, $x$ ($=z$), and the nodes $x_k$ are real, and $f^{(n+1)}$ is continuous on the smallest closed interval $I$ containing $x,x_0,x_1,\mathrm{\dots },x_n$, then the error can be expressed

3.3.5		$$R_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}{\omega }_{n+1}(x),$$
ⓘ Defines: $R_n(x)$: remainder (locally) Symbols: $!$: factorial (as in $n!$), $f(z)$: function and ${\omega }_{n+1}(z)$: nodal polynomial A&S Ref: 25.2.3 (modification of) Permalink: http://dlmf.nist.gov/3.3.E5 Encodings: TeX, pMML, png See also: Annotations for §3.3(i), §3.3 and Ch.3

for some $\xi \in I$. If $f$ is analytic in a simply-connected domain $D$ (§1.13(i)), then for $z\in D$,

3.3.6		$$R_n(z)=\frac{{\omega }_{n+1}(z)}{2\pi \mathrm{i}}{\int }_C\frac{f(\zeta )}{(\zeta -z){\omega }_{n+1}(\zeta )}d\zeta ,$$
ⓘ Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $dx$: differential of $x$, $\mathrm{i}$: imaginary unit, $\int$: integral, $f(z)$: function, ${\omega }_{n+1}(z)$: nodal polynomial, $R_n(x)$: remainder and $C$: simple closed contour in $D$ A&S Ref: 25.2.5 Permalink: http://dlmf.nist.gov/3.3.E6 Encodings: TeX, pMML, png See also: Annotations for §3.3(i), §3.3 and Ch.3

where $C$ is a simple closed contour in $D$ described in the positive rotational sense and enclosing the points $z,z_1,z_2,\mathrm{\dots },z_n$.

The $(n+1)$-point formula (3.3.4) can be written in the form

3.3.7		$$f_t=f(x_0+th)=\sum _{k=n_0}^{n_1}{A}_k^n{f}_k+R_{n,t},$$
,
ⓘ Symbols: $f(z)$: function, $A_k^n$: Lagrangian interpolation coefficients, $R_{n,t}(x)$: remainder and $f_t$: function values A&S Ref: 25.2.6 (modification of) Permalink: http://dlmf.nist.gov/3.3.E7 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

where the nodes $x_k=x_0+kh$ ($h>0$) and function $f$ are real,

3.3.8		$n_0$	$=-\frac{1}{2}(n-\sigma ),$
		$n_1$	$=\frac{1}{2}(n+\sigma ),$
ⓘ A&S Ref: 25.2.6 (modification of) Permalink: http://dlmf.nist.gov/3.3.E8 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

3.3.9		$$\sigma =\frac{1}{2}(1-{(-1)}^n),$$
ⓘ Permalink: http://dlmf.nist.gov/3.3.E9 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

and $A_k^n$ are the Lagrangian interpolation coefficients defined by

3.3.10		$$A_k^n=\frac{{(-1)}^{n_1+k}}{(k-n_0)!(n_1-k)!(t-k)}\prod _{m=n_0}^{n_1}(t-m).$$
ⓘ Defines: $A_k^n$: Lagrangian interpolation coefficients (locally) Symbols: $!$: factorial (as in $n!$) A&S Ref: 25.2.7 (modification of) Referenced by: §3.4(i) Permalink: http://dlmf.nist.gov/3.3.E10 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

The remainder is given by

3.3.11		$$R_{n,t}=R_n(x_0+th)=\frac{h^{n+1}}{(n+1)!}{f}^{(n+1)}(\xi )\prod _{k=n_0}^{n_1}(t-k),$$
ⓘ Defines: $R_{n,t}(x)$: remainder (locally) Symbols: $!$: factorial (as in $n!$) and $f(z)$: function A&S Ref: 25.2.8 (modification of) Permalink: http://dlmf.nist.gov/3.3.E11 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

where $\xi$ is as in §3.3(i).

Let $c_n$ be defined by

3.3.12		$$c_n=\frac{1}{(n+1)!}\max \prod _{k=n_0}^{n_1}\left|t-k\right|,$$
ⓘ Defines: $c_n$: bound coefficient (locally) Symbols: $!$: factorial (as in $n!$) Referenced by: §3.4(i) Permalink: http://dlmf.nist.gov/3.3.E12 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

where the maximum is taken over $t$-intervals given in the formulas below. Then for these $t$-intervals,

3.3.13		$$\left|R_{n,t}\right|\le c_n{h}^{n+1}\left|f^{(n+1)}(\xi )\right|.$$
ⓘ Symbols: $f(z)$: function, $R_{n,t}(x)$: remainder and $c_n$: bound coefficient Permalink: http://dlmf.nist.gov/3.3.E13 Encodings: TeX, pMML, png See also: Annotations for §3.3(ii), §3.3 and Ch.3

The divided differences of $f$ relative to a sequence of distinct points $z_0,z_1,z_2,\mathrm{\dots }$ are defined by

3.3.34		$\left[z_0\right]f$	$=f_0,$
		$\left[z_0,z_1\right]f$	$=(\left[z_1\right]f-\left[z_0\right]f)/(z_1-z_0),$
		$\left[z_0,z_1,z_2\right]f$	$=(\left[z_1,z_2\right]f-\left[z_0,z_1\right]f)/(z_2-z_0),$
ⓘ Defines: $\left[z_0,z_1,\mathrm{\dots },z_n\right]f$: divided difference Symbols: $f(z)$: function, $f_t$: function values and $z_k$: nodes of function A&S Ref: 25.1.4 Referenced by: Erratum (V1.1.2) for Equation (3.3.34) Permalink: http://dlmf.nist.gov/3.3.E34 Encodings: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png Errata (effective with 1.1.2): The leading divided difference operators were previously omitted from these formulas, due to programming error. Reported 2021-06-01 by Nico Temme See also: Annotations for §3.3(iii), §3.3 and Ch.3

and so on. Explicitly, the divided difference of order $n$ is given by

3.3.35		$$\left[z_0,z_1,\mathrm{\dots },z_n\right]f=\sum _{k=0}^n\left(f(z_k)/\prod _{\begin{array}{c}0\le j\le n\\ j\ne k\end{array}}(z_k-z_j)\right).$$
ⓘ Symbols: $\left[z_0,z_1,\mathrm{\dots },z_n\right]f$: divided difference, $f(z)$: function and $z_k$: nodes of function A&S Ref: 25.1.5 (in slightly different form) Permalink: http://dlmf.nist.gov/3.3.E35 Encodings: TeX, pMML, png See also: Annotations for §3.3(iii), §3.3 and Ch.3

If $f$ and the $z_k$ ($=x_k$) are real, and $f$ is $n$ times continuously differentiable on a closed interval containing the $x_k$, then

3.3.36		$$\left[x_0,x_1,\mathrm{\dots },x_n\right]f=\frac{f^{(n)}(\xi )}{n!}$$
ⓘ Symbols: $\left[z_0,z_1,\mathrm{\dots },z_n\right]f$: divided difference, $!$: factorial (as in $n!$) and $f(z)$: function A&S Ref: 25.1.10 Permalink: http://dlmf.nist.gov/3.3.E36 Encodings: TeX, pMML, png See also: Annotations for §3.3(iii), §3.3 and Ch.3

and again $\xi$ is as in §3.3(i). If $f$ is analytic in a simply-connected domain $D$, then for $z\in D$,

3.3.37		$$\left[z_0,z_1,\mathrm{\dots },z_n\right]f=\frac{1}{2\pi \mathrm{i}}{\int }_C\frac{f(\zeta )}{{\omega }_{n+1}(\zeta )}d\zeta ,$$
ⓘ Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $dx$: differential of $x$, $\left[z_0,z_1,\mathrm{\dots },z_n\right]f$: divided difference, $\mathrm{i}$: imaginary unit, $\int$: integral, $f(z)$: function, $C$: simple closed contour in $D$, $z_k$: nodes of function and ${\omega }_{n+1}(z)$: nodal polynomial Permalink: http://dlmf.nist.gov/3.3.E37 Encodings: TeX, pMML, png See also: Annotations for §3.3(iii), §3.3 and Ch.3

where ${\omega }_{n+1}(\zeta )$ is given by (3.3.3), and $C$ is a simple closed contour in $D$ described in the positive rotational sense and enclosing $z_0,z_1,\mathrm{\dots },z_n$.

This represents the Lagrange interpolation polynomial in terms of divided differences:

3.3.38		$$f(z)=\begin{array}{l}\left[z_0\right]f+(z-z_0)\left[z_0,z_1\right]f+(z-z_0)(z-z_1)\left[z_0,z_1,z_2\right]f\\ +\mathrm{\cdots }+(z-z_0)(z-z_1)\mathrm{\cdots }(z-z_{n-1})\left[z_0,z_1,\mathrm{\dots },z_n\right]f+R_n(z).\end{array}$$
ⓘ Symbols: $\left[z_0,z_1,\mathrm{\dots },z_n\right]f$: divided difference, $f(z)$: function, $z_k$: nodes of function and $R_n(x)$: remainder A&S Ref: 25.2.26 Referenced by: §3.3(v), §3.3(v), §3.3(iv) Permalink: http://dlmf.nist.gov/3.3.E38 Encodings: TeX, pMML, png See also: Annotations for §3.3(iv), §3.3 and Ch.3

The interpolation error $R_n(z)$ is as in §3.3(i). Newton’s formula has the advantage of allowing easy updating: incorporation of a new point $z_{n+1}$ requires only addition of the term with $\left[z_0,z_1,\mathrm{\dots },z_{n+1}\right]f$ 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 $z_0,z_1,\mathrm{\dots },z_n$. For example, for $k+1$ coincident points the limiting form is given by $\left[z_0,z_0,\mathrm{\dots },z_0\right]f=f^{(k)}(z_0)/k!$.

In this method we interchange the roles of the points $z_k$ and the function values $f_k$. It can be used for solving a nonlinear scalar equation $f(z)=0$ approximately. Another approach is to combine the methods of §3.8 with direct interpolation and §3.4.

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 $f$ on $ℝ$ the cardinal function of $f$ is defined by

3.3.43		$$C(f,h)(x)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}f(kh)S(k,h)(x),$$
ⓘ Defines: $C(f,h)$: cardinal function of $f$ (locally) Symbols: $f(z)$: function and $S(k,h)(x)$: Sinc function Permalink: http://dlmf.nist.gov/3.3.E43 Encodings: TeX, pMML, png See also: Annotations for §3.3(vi), §3.3 and Ch.3

where

3.3.44		$$S(k,h)(x)=\frac{\sin \left(\pi (x-kh)/h\right)}{\pi (x-kh)/h},$$
ⓘ Defines: $S(k,h)(x)$: Sinc function (locally) Symbols: $\pi$: the ratio of the circumference of a circle to its diameter and $\sin z$: sine function Permalink: http://dlmf.nist.gov/3.3.E44 Encodings: TeX, pMML, png See also: Annotations for §3.3(vi), §3.3 and Ch.3

is called the Sinc function. For theory and applications see Stenger (1993, Chapter 3).