Training Numerical Methods Interpolation
2 / 5

Interpolation

25 min Numerical Methods

Interpolation

Polynomial Interpolation

Given $n+1$ data points $(x_0,y_0), \ldots, (x_n,y_n)$ with distinct $x_i$, there is a unique polynomial of degree $\leq n$ passing through all points.

Lagrange Form

$$P(x) = \sum_{i=0}^{n} y_i \prod_{\substack{j=0 \\ j\neq i}}^{n} \frac{x-x_j}{x_i-x_j}$$

Newton's Divided Differences

$$P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots$$

where $f[x_i,x_{i+1}] = \frac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i}$.

Example 1

Find the Lagrange polynomial through $(1,1)$, $(2,4)$, $(3,9)$.

$P(x) = 1\cdot\frac{(x-2)(x-3)}{(1-2)(1-3)} + 4\cdot\frac{(x-1)(x-3)}{(2-1)(2-3)} + 9\cdot\frac{(x-1)(x-2)}{(3-1)(3-2)}$

$= \frac{(x-2)(x-3)}{2} - 4(x-1)(x-3) + \frac{9(x-1)(x-2)}{2} = x^2$.

Example 2

Compute divided differences for $(0,1)$, $(1,3)$, $(2,7)$.

$f[x_0,x_1] = (3-1)/(1-0)=2$. $f[x_1,x_2]=(7-3)/(2-1)=4$.

$f[x_0,x_1,x_2]=(4-2)/(2-0)=1$.

$P(x) = 1 + 2x + 1 \cdot x(x-1) = x^2+x+1$.

Example 3

Use the polynomial from Ex. 2 to estimate $f(1.5)$.

$P(1.5) = 2.25+1.5+1 = 4.75$.

Practice Problems

1. Linear interpolation: $(1,2)$ and $(3,8)$. Estimate $f(2)$.
2. Lagrange: $(0,1)$, $(1,0)$. Find $P(x)$.
3. Degree of polynomial through 4 points?
4. Divided differences: $(0,0)$, $(1,1)$, $(2,8)$.
5. What is Runge's phenomenon?
6. Lagrange: $(0,1)$, $(1,2)$, $(2,5)$. Find $P(1.5)$.
7. Why prefer Newton form over Lagrange?
8. Interpolation error bound involves what derivative?
9. Linear interpolation: $(2,4)$, $(5,13)$. Estimate $f(3)$.
10. Is interpolation the same as curve fitting?
11. When should you use splines instead?
12. $f[x_0,x_1,\ldots,x_n]$ for $f(x) = x^n$ equals?
Show Answer Key

1. $P(x) = 2+3(x-1)$; $P(2) = 5$

2. $P(x) = 1-x$

3. At most 3

4. $f[0,1]=1$, $f[1,2]=7$, $f[0,1,2]=3$. $P(x)=x+3x(x-1)=3x^2-2x$

5. Oscillation at edges with high-degree polynomials on equally spaced points

6. $P(x) = 1-\frac{x(x-2)}{2}+5\cdot\frac{x(x-1)}{2}$; compute $P(1.5) \approx 3.25$

7. Easier to add new points without recomputing everything

8. The $(n+1)$th derivative of $f$

9. Slope $= 9/3 = 3$. $f(3) \approx 4+3(1) = 7$

10. No — interpolation passes through all points; curve fitting minimizes error

11. Many data points or need smoothness without high-degree oscillation

12. $1$ (the leading coefficient)

Root-Finding Methods Numerical Integration