Interpolasjonsproblemet

Gitt $n+1$ datapunkter $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$ med distinkte $x_i$, finn polynomet $p_n(x)$ av grad $\leq n$ som passerer gjennom alle punktene: $p_n(x_i) = y_i$.

Eksistens og entydighet: Det finnes nøyaktig ett polynom av grad $\leq n$ som interpolerer $n+1$ punkter med distinkte $x$-verdier.

Lagrange-interpolasjon

Lagrange-formelen:

$p_n(x) = \sum_{i=0}^n y_i \cdot L_i(x)$, der $L_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}$

$L_i$ er Lagrange-basisfunksjoner: $L_i(x_j) = \delta_{ij}$ (1 når $i=j$, 0 ellers).

Eksempel: Interpolér $(0, 1), (1, 3), (2, 2)$

$n = 2$ (grad $\leq 2$). Lagrange-basisfunksjonene:

$L_0(x) = \frac{(x-1)(x-2)}{(0-1)(0-2)} = \frac{(x-1)(x-2)}{2}$

$L_0(0) = 1$, $L_0(1) = 0$, $L_0(2) = 0$

$L_1(x) = \frac{(x-0)(x-2)}{(1-0)(1-2)} = \frac{x(x-2)}{-1} = -x(x-2)$

$L_1(1) = 1$

$L_2(x) = \frac{(x-0)(x-1)}{(2-0)(2-1)} = \frac{x(x-1)}{2}$

$L_2(2) = 1$

$p_2(x) = 1 \cdot \frac{(x-1)(x-2)}{2} + 3 \cdot (-x)(x-2) + 2 \cdot \frac{x(x-1)}{2}$

$= \frac{x^2 - 3x + 2}{2} - 3x^2 + 6x + x^2 - x = -\frac{3}{2}x^2 + \frac{7}{2}x + 1$

Sjekk: $p_2(0) = 1$ ✓, $p_2(1) = -3/2 + 7/2 + 1 = 3$ ✓, $p_2(2) = -6 + 7 + 1 = 2$ ✓

Newtons dividerte differanser

Newtons form: $p_n(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$

Dividerte differanser:

$f[x_i] = f(x_i)$

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

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

Interpolasjonsfeil

Feilformel: Hvis $f$ er $(n+1)$ ganger deriverbar, da er

$f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i)$

for et $\xi$ mellom de ytterste av $x, x_0, \ldots, x_n$.

Runges fenomen: Høygrads polynominterpolasjon med likfordelte punkter kan gi store oscillasjoner ved endepunktene. Løsning: bruk Chebyshev-noder (ikke-likfordelte) eller spliner.

Eksamentips: Lagrange-interpolasjon for hånd er en vanlig eksamensoppgave. Sett opp basisfunksjonene systematisk og sjekk alltid at $p_n(x_i) = y_i$ for alle punkter.

Studieguide: Interpolasjon

Studieguide: Interpolasjon