Discussion 5A

Polynomials

A polynomial of degree $d$ has the form $p(x) = a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1 x^1 + a_0$

If $r$ is a root then $p(x)$ can be factored as $p(x) = (x-r) q(x)$ where $q(x)$ has degree $d-1$

With $d+1$ points $(x_i, p(x_i))$ there is one degree $d$ polynomial that fits the points

this can be interpreted as the number of points required to figure out the $d+1$ coefficients of $p(x)$

Lagrange Interpolation

Given

d+1

points, how do you find a degree

d

polynomial that fits all

d+1

points?

The idea is similar to that of Chinese Remainder Theorem:

For each $x_i$ , create a polynomial $\Delta_{x_i} (x) = \begin{cases} 1 & \text{if } x=x_i \\ 0 & \text{otherwise} \end{cases}$

Then the polynomial $p(x) = y_0 \Delta_{x_0} (x) + y_1 \Delta_{x_1} (x) + \cdots + y_d \Delta_{x_d} (x)$ fits all the points

$p(x_0) = y_0 \Delta_{x_0} (x_0) + y_1 \Delta_{x_1} (x_0) + \cdots + y_d \Delta_{x_d} (x_0) = y_0 + 0 + \cdots + 0 = y_0$

Letting

\Delta_{x_i} (x) = \frac{\prod_{j \neq i} x - x_j}{\prod_{j \neq i} x_i - x_j} = \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_d)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i-x_{i+1}) \cdots (x_i-x_d)}

works because when you plug in

x_i

, all terms in the numerator and denominator cancel, evaluating to

1

, and when you plug in another value

x_j

, one of the terms in the numerator is

(x_j-x_j)

, so the polynomial evaluates to

0

.