The interpolation problem

In this chapter, we use $t_k$ for the nodes and $x$ to denote the continuous independent variable.

5.1.1Polynomials¶

Polynomials are the obvious first candidate to serve as interpolating functions. They are easy to work with, and in Polynomial interpolation we saw that a linear system of equations can be used to determine the coefficients of a polynomial that passes through every member of a set of given points in the plane. However, it’s not hard to find examples for which polynomial interpolation leads to unusable results.

In Chapter 9 we explore the large oscillations in the last figure of Demo 5.1.1; it turns out that one must abandon either equally spaced nodes or $n\to\infty$ for polynomials. In the rest of this chapter we will keep $n$ fairly small and let the nodes be unrestricted.

5.1.2Piecewise polynomials¶

In order to keep polynomial degrees small while interpolating large data sets, we will choose interpolants from the piecewise polynomials. Specifically, the interpolant $p$ must be a polynomial on each subinterval $[t_{k-1},t_k]$ for $k=1,\ldots,n$.

Usually we designate in advance a maximum degree $d$ for each polynomial piece of $p(x)$. An important property of the piecewise polynomials of degree $d$ is that they form a vector space: that is, any linear combination of piecewise polynomials of degree $d$ is another piecewise polynomial of degree $d$. If $p$ and $q$ share the same node set, then the combination is piecewise polynomial on that node set.

We will consider piecewise linear interpolation in more detail in Piecewise linear interpolation, and we look at piecewise cubic interpolation in Cubic splines.

5.1.3Conditioning of interpolation¶

In the interpolation problem we are given the values $(t_k,y_k)$ for $k=0,\ldots,n$. Let us consider the nodes $t_k$ of the problem to be fixed, and let $a=t_0$, $b=t_n$. Then the data for the interpolation problem consists of a vector $\mathbf{y}$, and the result of the problem is a function on $[a,b]$.

Let $\mathcal{I}$ be a prescription for producing the interpolant from a data vector. That is, $\mathcal{I}(\mathbf{y})=p$, where $p(t_k)=y_k$ for all $k$. The interpolation methods we will consider are all linear, in the sense that

for all vectors $\mathbf{y},\mathbf{z}$ and scalars $\alpha,\beta$.

Linearity greatly simplifies the analysis of interpolation. To begin with, for any data vector $\mathbf{y}$ we have the standard expression $\mathbf{y}=\sum y_k \mathbf{e}_k$, where as always $\mathbf{e}_k$ is a column of an identity matrix.^[1] Hence by linearity,

The functions appearing within the sum above have particular significance.

For any set of $n+1$ nodes, there are $n+1$ cardinal functions $\phi_0,\ldots,\phi_n$, each singling out a different interpolation node in the set. We finish (5.1.2) by writing

In the following result we use the function infinity-norm or max-norm defined by

5.1.4Exercises¶

1. ⌨ Create data by entering

   t = -2:4;  y = tanh.(t);

   (a) Use fit to construct and plot the polynomial interpolant of the data, superimposed on a scatter plot of the data.

   (b) Use Spline1D to construct and plot a piecewise cubic interpolant of the data, superimposed on a scatter plot of the data.

2. ⌨ The following table gives the life expectancy in the U.S. by year of birth.

   1980	1985	1990	1995	2000	2005	2010
   73.7	74.7	75.4	75.8	77.0	77.8	78.7

   (a) Defining “year since 1980” as the independent variable, use fit to construct and plot the polynomial interpolant of the data.

   (b) Use Spline1D to construct and plot a piecewise cubic interpolant of the data.

   (c) Use both methods to estimate the life expectancy for a person born in 2007. Which value is more believable?

3. ⌨ The following two vectors define a flying saucer shape.

   x = [ 0,0.51,0.96,1.06,1.29,1.55,1.73,2.13,2.61,
         2.19,1.76,1.56,1.25,1.04,0.58,0 ]
   y = [ 0,0.16,0.16,0.43,0.62,0.48,0.19,0.18,0,
         -0.12,-0.12,-0.29,-0.30,-0.15,-0.16,0 ]

   We can regard both $x$ and $y$ as functions of a parameter $s$, with the points being values given at $s=0,1,\ldots,15$.

   (a) Use Spline1D once on each coordinate as functions of $s$, and make a picture of the flying saucer.

   (b) One drawback of the result in part (a) is the noticeable corner at the left side, which corresponds to $s=0$ from above and $s=15$ from below. There is a periodic variation on cubic spline interpolation that you can invoke by adding the keyword periodic=true to the Spline1D call. Use this to re-plot the flying saucer.

4. ✍ Define

   $$q(s) = a\frac{s(s-1)}{2} - b (s-1)(s+1) + c \frac{s(s+1)}{2}.$$

   (5.1.9)

   (a) Show that $q$ is a polynomial interpolant of the points $(-1,a)$, $(0,b)$, $(1,c)$.

   (b) Find a change of variable $s=Ax+B$ so that the values $s=-1,0,1$ correspond to $x=x_0-h,x_0,x_0+h$.

   (c) Find a quadratic polynomial interpolant $\tilde{q}(x)$ for the points $(x_0-h,a)$, $(x_0,b)$, $(x_0+h,c)$.

5. ✍ (continuation) Use the result of the previous exercise and Theorem 5.1.1 to derive bounds on the condition number of quadratic polynomial interpolation at the nodes $x_0-h$, $x_0$, $x_0+h$.