Math 441

Interpolation: Introduction

What is Interpolation?

Given \(n+1\) data points \((x_i,y_i)\), find a function \(f\) such that \(f(x_i) = y_i\) for \(i = 0, 1, \dots, n\):

𝑥 𝑥 0 𝑥 1 𝑥 2 𝑥 3 𝑥 4 𝑥 5

What kind of function?

Given \(n+1\) data points \((x_i,y_i)\), find a function \(f\) such that

\[f(x_i) = y_i \text{ for } i = 0, 1, \dots, n\]

What kind of function?

  • A polynomial of degree \(m\)
  • A trigonometric function (e.g. if data points are periodic)
  • A piece-wise function of some sort
  • …

Question: Does such function even exist?

Question: How do we find it?

Vector Spaces

Definition: A real vector space is a non-empty set \(V\) together with an operation \({}+{}\colon V\times V \to V\) (addition) and a function from \(\mathbb{R}\times V\) to \(V\) (scalar multiple) denoted using superposition: \(a\mathbf{v}\), with the following properties:

  • \(\forall \mathbf{u}\in V\;\forall\mathbf{v}\in V: \mathbf{u} + \mathbf{v} \in V\)
  • \((\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})\)
  • \(\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}\)
  • \(\exists \mathbf{0}\in V: \forall \mathbf{v}\in V, \mathbf{v} + \mathbf{0} = \mathbf{v}\)
  • \(\forall \mathbf{v}\in V\, \exists -\mathbf{v}\in V: \mathbf{v} + (-\mathbf{v}) = \mathbf{0}\)
  • \(\forall a\in \mathbb{R}\;\forall\mathbf{v}\in V: a \mathbf{v} \in V\)
  • \(a(b\mathbf{v}) = (ab)\mathbf{v}\)
  • \(1\mathbf{v} = \mathbf{v}\)
  • \(a(\mathbf{u} + \mathbf{v}) = a\mathbf{u} + a\mathbf{v}\)
  • \((a + b)\mathbf{u} = a\mathbf{u} + b\mathbf{u}\)

\(V\) is closed under addition.

\(V\) is closed under scalar multiple.

Associativity of addition.

Commutativity of addition.

Additive identity.

Additive inverse.

Compatibility of scalar multiplication with multiplication of real numbers.

Scalar identity.

Distributing over vector addition.

Distributing over scalar addition.

Bases

  • Linear combination: Given scalars \(a_1, a_2, \dots, a_n\) and vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\), a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\) with coefficients \(a_1, a_2, \dots, a_n\) is \[\sum_{i=1}^n a_i\mathbf{v}_i\]
  • Linear independence: We say that \(A \subset V\) is linearly independent if none of the vectors in \(A\) can be written as a linear combination of the other vectors in \(A\).
  • Generating set: We say that a set \(A \subset V\) generates the vector space \(V\) if every \(\mathbf{v} \in V\) can be written as a linear combination of vectors from \(A\).
  • Bases: A set \(B \subset V\) is called a bases of \(V\) if it is linearly independent and generates \(V\).
  • If a vector space \(V\) has a bases with exactly \(n\) vectors, we say that \(V\) is \(n\)-dimensional.

Examples

  • Two-dimensional real vectors, with bases \(\{(1,0), (0,1)\}\).
  • \(2\times 2\) matrices, with bases \(\left\{ \begin{bmatrix} 1 & 0\\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 1\\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0\\ 1 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0\\ 0 & 1 \end{bmatrix} \right\}\).
  • Polynomials of degree \(3\) or lower, with bases \(\{1, x, x^2, x^3\}\).
  • All polynomials, with bases \(\{1, x, x^2, x^3, \dots\}\).
  • All functions from \(\mathbb{R}\) to \(\mathbb{R}\). We can prove that bases exists, using the axiom of choice, but we cannot explicitly construct it.

Linear Algebra Problem

Given \(n + 1\) data points \((x_i,y_i)\), \(i = 0, 1, \dots, n\), find a function \(f\) that belongs to an \(n+1\)-dimensional vector space \(V\) with bases \[\left\{\phi_0, \phi_1, \dots, \phi_n\right\}\] such that \[f(x_i) = y_i \text{ for } i = 0, 1, \dots, n.\]

We know that \(f\) can be written as a linear combination of \(\phi_0, \phi_1, \dots, \phi_n\):

\[f(x) = \sum_{k = 0}^n a_k\phi_k(x).\]

\[f(x_i) = \sum_{k = 0}^n a_k\phi_k(x_i) = y_i \text{ for } i = 0, 1, \dots, n.\]

System of Equations

\[\sum_{k = 0}^n a_k\class{emph}{\phi_k(x_i)} = \class{emph}{y_i} \text{ for } i = 0, 1, \dots, n.\]

Matrix form:

\[ \class{emph}{\begin{bmatrix} \phi_0(x_0) & \phi_1(x_0) & \phi_2(x_0) & \cdots & \phi_n(x_0)\\ \phi_0(x_1) & \phi_1(x_1) & \phi_2(x_1) & \cdots & \phi_n(x_1)\\ \phi_0(x_2) & \phi_1(x_2) & \phi_2(x_2) & \cdots & \phi_n(x_2)\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \phi_0(x_n) & \phi_1(x_n) & \phi_2(x_n) & \cdots & \phi_n(x_n)\\ \end{bmatrix}} \begin{bmatrix} a_0\\a_1\\a_2\\\vdots\\a_n \end{bmatrix} = \class{emph}{\begin{bmatrix} y_0\\y_1\\y_2\\\vdots\\y_n \end{bmatrix}} \]

If the matrix is non-singular, there is a unique solution.

It would be good if this system was also easy to solve.

Polynomial Interpolation

  • Data: \((x_i,y_i)\), \(i = 0, 1, \dots, n\)
  • Interpolating functions: polynomials of degree at most \(n\)

Theorem: If points \(x_0, x_1, \dots, x_n\) are distinct, then for any real values \(y_0, y_i, \dots, y_n\) there is a unique polynomial \(p\) of degree at most \(n\) such that \(p(x_i) = y_i\) for \(i = 0, 1, \dots, n\).

The matrix

\[ \begin{bmatrix} \phi_0(x_0) & \phi_1(x_0) & \phi_2(x_0) & \cdots & \phi_n(x_0)\\ \phi_0(x_1) & \phi_1(x_1) & \phi_2(x_1) & \cdots & \phi_n(x_1)\\ \phi_0(x_2) & \phi_1(x_2) & \phi_2(x_2) & \cdots & \phi_n(x_2)\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \phi_0(x_n) & \phi_1(x_n) & \phi_2(x_n) & \cdots & \phi_n(x_n)\\ \end{bmatrix} \]

is non-singular

Monomial Bases

\[B = \{1, x, x^2, \dots, x^n\}\]

in other words, \(\phi_k(x) = x^k\) for \(k = 0, 1, \dots, n\).

Example:

Find a polynomial \(p\) of degree 2 such that \(p(-1) = 11\), \(p(1) = -1\), and \(p(2) = 2\).