Sitemap

Page Not Found

Page Not Found

Page not found. Your pixels are in another canvas.

ABOUT

ABOUT

Archive Layout with Content

Awards

Blog Posts

Posts by Category

Posts by Collection

CV

Markdown

Page not in menu

This is a page not in th emain menu

Page Archive

Publications

Research

Sitemap

Posts by Tags

Talk map

Terms and Privacy Policy

Blog posts

Jupyter notebook markdown generator

Interpolation Theory

Published: July 09, 2019

Let $x_0, x_1, … , x_n$ be distinct real or complex numbers, and let $y_0 , y_1, …, y_n$ be associated function values. We now study the problem of finding a polynomial p (x) that interpolates the given data:

By writing: $p(x) = a_0 + a_1x + … + a_mx^m$

Consider that m = n, then

It can be written that $Xa = y$, with

The matrix X is called a Vandermonde matrix.

Theorem

Given n + 1 distinct points $x_0, … , x_n$ and n + 1 ordinates $y_0, …, y_n$, there is a polynomial p(x) of $degree \le n$ that interpolates $y_i$ at $x_i$, i = 0, 1, … , n. This polynomial p(x) is unique among the set of all polynomials of degree at most n.

Below are three kinds of proofs.

Proof

• It can be shown that for the matrix X,

  $$det(X) = \prod_{0 \le j < i \le n}(x_i - x_j)$$

  This shows that $det(X) \ne 0$, since the points $x_i$ are distinct. Thus X is nonsingular and the system $Xa = y$ has a unique solution a. This proves the existence and uniqueness of an interpolating polynomial of $degree \le n$.

• The system $Xa = y$ has a unique solution iff the homogeneous system $Xb = 0$ has only the trivial solution b = 0. Therefore, assume $Xb = 0$ for some b. Using b, define

  $$p(x) = b_0 + b_1x + ... + b_nx^n$$

  From the system $Xb = 0$, we have

  $$p(x_i) = 0, \ \ \ \ i = 0, 1, ..., n$$

  The polynomial p(x) has n + 1 zeros and degree $p(x) \le n$. This is not possible unless $p(x) \equiv 0$. But then all coefficients $b = 0, i = 0, 1, … , n$, completing the proof.

• Consider a special polynomial

  $$l_i(x) = \prod_{j \ne i} (\frac{x - x_j}{x_i - x_j}), \ \ i = 0, 1, ..., n$$

  Then the polynomial can be rewritten

  $$p(x) = y_0l_0(x) + y_1l_1(x) + ... + y_nl_n(x)$$

  Since all $l_i(x)$ have degree n, degree $p(x) \le n$.

  To prove uniqueness, suppose q(x) is another polynomial of degree $\le$ n that satisfies (1). Define

  $$r(x) = p(x) - q(x)$$

  Then degree $r(x) \le n$, and

  $$r(x_i) = p(x_i) - q(x_i) = y_i - y_i = 0 \ \ i = 0, 1, ..., n$$

  Since r(x) has n + 1 zeros, we must have $r(x) \equiv 0$, which proves $p(x) \equiv q(x)$, completing the proof.

Reference

• Godfrey Harold Hardy, Edward Maitland Wright，E. W. (Edward Maitland) Wright，An Introduction to Numerical Analysis, 131-134. Clarendon Press, 1979.