Interpolation

GUIDING QUESTION: How can I read between the lines? Given a data table sampling continuous a function $f$, which values best approximate $f$ between samples?

Polynomial fitting

Guiding philosophy: We've developed good methods for solving linear systems. Let's use them to solve the interpolation problem!

Let's be more precise

Given $\bbox[3pt, border: 3pt solid var(--emphColor)]{n + 1}$ data points $(x_\color{var(--emphColor)}{0}, y_\color{var(--emphColor)}{0}), (x_1, y_1), \ldots, (x_\color{var(--emphColor)}{n}, y_\color{var(--emphColor)}{n})$, we seek an interpolating function $f$.

We say that a function $f$ interpolates the given data if $$f(x_i) = y_i$$ for every given node or abscissa $x_0, x_1, \ldots, x_n$.

Polynomial interpolants

In this module we'll focus on polynomial interpolants.
In particular, we seek a function $f$ of the form $$f(x) = c_0 + c_1 x + \cdots + c_n x^\color{var(--emphColor)}{n}$$
satisfying $$f(x_i) = y_i$$ for each of the $\bbox[3pt, border: 3pt solid var(--emphColor)]{n + 1}$ given data points $(x_\color{var(--emphColor)}{0}, y_\color{var(--emphColor)}{0}), (x_1, y_1), \ldots, (x_\color{var(--emphColor)}{n}, y_\color{var(--emphColor)}{n})$.

Why focus on polynomials?

First, Weierstrass' approximation theorem tells us that every continuous function is well-approximated by some polynomial.
(Weierstrass) If $f$ is continuous on the interval $[a, b]$, then for any $\epsilon > 0$ there exists a polynomial $p$ such that $$\max_{x \in [a, b]} |f(x) - p(x)| < \epsilon.$$
(Weierstrass) If $f$ is continuous on the interval $[a, b]$, then for any $\epsilon > 0$ there exists a polynomial $p$ such that $$\max_{x \in [a, b]} |f(x) - p(x)| < \epsilon.$$
Roughly speaking, Weierstrass' theorem suggests that, given enough data points, we may approximate a continuous function by a polynomial to any specified tolerance.

Why focus on polynomials?

Second, in many applications the interpolant is merely a building block in a more complex algorithm intended to differentiate or integrate some function, or to solve a differential equation.
So it's important that we're able to easily differentiate and integrate our interpolant, and we can certainly write down simple formulas expressing derivatives and integrals of polynomials.
We'll discuss the use of polynomial interpolants in numerical differentiation and integration, and in solving differntial equations, later in the course.

Why focus on polynomials?

Third, we can evaluate polynomials efficiently.
We may compute $p(x) = a_0 + a_1 x \cdots + a_n x^n$ in linear time! 
										\begin{algorithm}
										\caption{Efficient polynomial evaluation}
										\begin{algorithmic}
										\Input{$x$, coefficients $a_0, a_1, \ldots, a_n$}
										\STATE{$p \gets a_n$}
										\FOR{$i \gets n-1$ to $0$}
										 \STATE{$p \gets a_i + x\cdot p$}
										\ENDFOR
										\end{algorithmic}
										\end{algorithm}
Our procedure is based on the identity \begin{align} p(x) &= a_0 + a_1 x \cdots + a_n x^n \\ &= a_0 + x\bigg(a_1 + x \big(a_2 + x (a_3 + \cdots + x (a_{n-1} + x a_n))\big)\bigg), \end{align} which can be obtained using synthetic division.

There's lots going for polynomials

So, given $n+1$ data points $(x_i, y_i)$, how can I compute the corresponding polynomial interpolant?
We'll frame this as a linear root finding problem.
The key is to notice that any polynomial of degree at most $n$ is a linear combination of the linearly independent functions $1, x, x^2, \ldots, x^n$.
Given $\bbox[3pt, border: 3pt solid var(--emphColor)]{n + 1}$ data points, we'll consider only polynomials of degree at most $\color{var(--emphColor)}{n}$.
We'll justify this choice in a few slides.

Key idea

The polynomial interpolant $f$ can be written as $$f(x) = \color{var(--emphColor)}{c_0} + \color{var(--emphColor)}{c_1} x + \cdots + \color{var(--emphColor)}{c_n} x^n,$$ for some coefficiens $\color{var(--emphColor)}{c_i}$.

Key idea

Our task is to determine the $\color{var(--emphColor)}{c_i}$ making $f$ interpolate the given data.

That is, we seek $\color{var(--emphColor)}{c_0}, \color{var(--emphColor)}{c_1}, \ldots, \color{var(--emphColor)}{c_n}$ such that \begin{alignat}{4} \color{var(--emphColor)}{c_0} & &+ \color{var(--emphColor)}{c_1} & x_0 +\cdots +\color{var(--emphColor)}{c_n} & x_0^n & =& f(x_0) = &y_0\\ &\vdots & &\vdots &\vdots & && \vdots\\ \color{var(--emphColor)}{c_0} & &+ \color{var(--emphColor)}{c_1} & x_n+\cdots + \color{var(--emphColor)}{c_n} & x_n^n & =& f(x_n) = &y_n \end{alignat}
These are linear equations in the variables $\color{var(--emphColor)}{c_i}$ and we can assemble them into a single matrix equation.

Key idea

Our task is to determine the $\color{var(--emphColor)}{c_i}$ making $f$ interpolate the given data.

That is, we seek $\color{var(--emphColor)}{c_0}, \color{var(--emphColor)}{c_1}, \ldots, \color{var(--emphColor)}{c_n}$ such that \begin{align} \begin{bmatrix} 1 & x_0 & \cdots & x_0^n \\ \vdots & \vdots &\ddots& \vdots\\ 1 & x_n & \cdots & x_n^n \end{bmatrix} \begin{bmatrix} \color{var(--emphColor)}{c_0}\\ \vdots\\ \color{var(--emphColor)}{c_n} \end{bmatrix}= \begin{bmatrix} y_0\\ \vdots\\ y_n \end{bmatrix} \end{align}
These are linear equations in the variables $\color{var(--emphColor)}{c_i}$ and we can assemble them into a single matrix equation.

Let's find the quadratic polynomial interpolating the data $$(-1, 3), (0, 5), (1, 3).$$
The quadratic interpolant $f$ can be written as $f(x) = c_0 + c_1 x + c_2 x^2,$ for some coefficients $c_i$ satisfying
$$\begin{bmatrix} 1 & -1 & (-1)^2 \\ 1 & 0 & 0^2 \\ 1 & 1 & 1^2 \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 3 \\ 5 \\ 3 \end{bmatrix}.$$

Vandermonde systems

For any given nodes $x_i$, the matrix $$V = \begin{bmatrix} 1 & x_0 & \cdots & x_0^n \\ \vdots & \vdots &\ddots& \vdots\\ 1 & x_n & \cdots & x_n^n \end{bmatrix}$$ is known as a Vandermonde matrix.
Vandermonde matrices are known to be invertible when the nodes are distinct.
The coefficients $c_i$ defining our polynomial interpolant satisfy $Vc = y$, so the invertibility of $V$ guarantees that there is a unique polynomial of degree at most $\color{var(--emphColor)}{n}$ interpolating any $\bbox[3pt, border: 3pt solid var(--emphColor)]{n + 1}$ data points $(x_i, y_i)$ (assuming the nodes are distinct).
We'll come back to this point later in the lecture, when we can prove it without unsubstantiated claims about Vandermonde matrices.

Generalizing our method

In general, we first choose $n+1$ linearly independent functions $\phi_0$, $\phi_1, \ldots, \phi_n$ and write the inerpolant we seek as the linear combination $$f(x) = \sum_{i=0}^n \color{var(--emphColor)}{c_i}\phi_i(x),$$ for some coefficients $\color{var(--emphColor)}{c_i}$.

Generalizing our method

As before, we may determine the coefficients making $f$ interpolate the given data by solving a linear system.
In general, the $\color{var(--emphColor)}{c_i}$ satisfy \begin{align} \begin{bmatrix} \phi_0(x_0) & \phi_1(x_0) & \cdots & \phi_n(x_0)\\ \vdots & \vdots && \vdots\\ \phi_0(x_n) & \phi_1(x_n) & \cdots & \phi_n(x_n) \end{bmatrix} \begin{bmatrix} \color{var(--emphColor)}{c_0}\\ \vdots\\ \color{var(--emphColor)}{c_n} \end{bmatrix}= \begin{bmatrix} y_0\\ \vdots\\ y_n \end{bmatrix} \end{align}
No matter what $\phi_i$ is, the nodes $x_0, x_1, \ldots, x_n$ are given, so the entries $$a_{ij} = \phi_i(x_j)$$ are known scalars.
To obtain the polynomial interpolant, we may set $$\phi_i(x) = x^i.$$
For trigonometric interpolation, we may set, for instance, $$\phi_j(x) = \begin{cases} \cos(jx), & \text{if } j \text{ is even,} \\ \sin(jx), & \text{if } j \text{ is odd.} \end{cases} $$

Great approach! But...

While our approach is straightforward, it still involves solving a linear system, which may be costly.
Even worse, Vandermonde matrices tend to be ill-conditioned, so the resulting coefficients may be imprecise.

Is there a better way?

One possibility involves finding a different way of writing the interpolant as a linear combination of other polynomials.
We seek a different basis for the space of polynomials of degree at most $n$.

Let's start small

Suppose we want a degree $1$ polynomial $f(x) = c_0 + c_1 x$ interpolating the two data points $(x_0,y_0),(x_1,y_1)$.