Newton-Interpolation

Studium

p(x) = \sum_{k=0}^{n} f[x_0, \ldots, x_k] \prod_{j=0}^{k-1} (x - x_j)

Voraussetzung: $x_0, \ldots, x_n$ $paarweise verschieden$

$p(x)$: Interpolationspolynom vom Grad höchstens n mit p(x_i) = f(x_i)
$x_0, \ldots, x_n$: Stützstellen
$f[x_0, \ldots, x_k]$: dividierte Differenz der Ordnung k
$n$: Anzahl der Stützstellen minus 1

Die Newton-Form baut das Interpolationspolynom aus dividierten Differenzen auf; eine neue Stützstelle fügt nur ein Glied hinzu.

Erklärung

Durch $n + 1$ Punkte $(x_i, f(x_i))$ mit verschiedenen Stützstellen geht genau ein Polynom vom Grad höchstens $n$ . Die Newton-Form schreibt es als

p(x) = c_0 + c_1 (x - x_0) + c_2 (x - x_0)(x - x_1) + \ldots + c_n (x - x_0) \cdots (x - x_{n-1})

Die Koeffizienten $c_k = f[x_0, \ldots, x_k]$ sind dividierte Differenzen, rekursiv definiert durch

f[x_i] = f(x_i), \qquad f[x_i, \ldots, x_j] = \frac{f[x_{i+1}, \ldots, x_j] - f[x_i, \ldots, x_{j-1}]}{x_j - x_i}

Man berechnet sie in einem dreieckigen Differenzenschema; die Koeffizienten stehen auf der oberen Schräge.

Vorteile gegenüber der Lagrange-Form:

Kommt eine Stützstelle hinzu, bleiben alle bisherigen Koeffizienten gleich. Man ergänzt nur eine Zeile im Schema und ein Glied im Polynom.
Ausgewertet wird effizient mit einem Horner-artigen Schema von innen nach außen.

Es entsteht dasselbe Polynom wie bei Lagrange, nur anders dargestellt.

Beispiele

Gegeben sind $(0, 1)$ , $(1, 3)$ , $(3, 2)$ . Das Differenzenschema:

$x_i$	$f[x_i]$	1. Ordnung	2. Ordnung
0	1
		$\frac{3 - 1}{1 - 0} = 2$
1	3		$\frac{-0{,}5 - 2}{3 - 0} = -\frac{5}{6}$
		$\frac{2 - 3}{3 - 1} = -0{,}5$
3	2

Damit ist

p(x) = 1 + 2x - \frac{5}{6}\,x\,(x - 1)

Probe: $p(3) = 1 + 6 - 5 = 2$ . Für $x = 2$ ergibt sich $p(2) = 5 - \frac{5}{3} = \frac{10}{3} \approx 3{,}3333$ .

Kommt der Punkt $(4, 0)$ hinzu, berechnet man nur die neue Schräge: $f[x_2, x_3] = -2$ , $f[x_1, x_2, x_3] = -0{,}5$ und $f[x_0, \ldots, x_3] = \frac{-0{,}5 + 5/6}{4} = \frac{1}{12}$ . Das neue Polynom ist

p_3(x) = 1 + 2x - \frac{5}{6}\,x\,(x - 1) + \frac{1}{12}\,x\,(x - 1)(x - 3)

Das zusätzliche Glied ist an den alten Stützstellen null, und es gilt $p_3(4) = 0$ .

Typische Fehler

Im Nenner die benachbarten statt der äußeren Stützstellen nehmen: Bei $f[x_0, x_1, x_2]$ steht $x_2 - x_0$ im Nenner, nicht $x_2 - x_1$ .
Die falschen Koeffizienten aus dem Schema ablesen. Es sind die obersten Einträge jeder Spalte, die alle zu $x_0$ gehören.
Im Produkt einen Faktor zu viel nehmen: Zu $c_k$ gehören die Faktoren $(x - x_0)$ bis $(x - x_{k-1})$ , nicht bis $(x - x_k)$ .
Bei vielen gleichabständigen Stützstellen erwarten, dass das Polynom die Funktion gut wiedergibt. Am Rand kann es stark schwingen (Runge-Phänomen).

Newton-Interpolation