1.3. NEWTON-Interpolation
Für die NEWTONsche Darstellung des Interpolationspolynom wird folgender Ansatz gemacht:
| |
pn(x) = c0 + c1(x-x0)
+ c2(x - x0)(x - x1) + ...
+ cn(x - x0)(x - x1).....(x - xn-1)
|
(1.6) |
Aus der Interpolationsforderung folgt:
|
|
 |
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
... |
0 |
|
|
. |
|
|
c0 |
|
|
= |
|
|
f0 |
|
|
| 1 |
x1-x0 |
0 |
... |
0 |
c1 |
f1 |
| 1 |
x2-x0 |
(x2-x0)(x2-x1) |
... |
0 |
c2 |
f2 |
| : |
: |
: |
|
: |
: |
: |
| 1 |
xn-x0 |
(xn-x0)(xn-x1) |
... |
(xn-x0)(xn-x1)
.....(xn-xn-1) |
cn |
fn |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1.7) |
Um die Koeffizienten des NEWTONschen Interpolationspolynoms zu berechenen, muss das
Gleichungssystem (1.7) gelöst werden.
Die ci werden als Steigungen bezeichnet.
- Definition 1.1 (k-te Steigung):
- Die k-te Steigung f[xi,...,xi+k] (auch: k-te Differenz)
ist rekursiv definiert durch f[xi]:=f(xi) für i = 0, 1, ..., n und
| f[xi,...,xi+k] := |
f[xi+1,...,xi+k]
- f[xi,...,xi+k-1>]xi+k
- xi |
. |
Es gilt ci = f[x0,...,xi], i = 0, 1, ..., n.
Steigungs-/Differenzenschema:
Das Steigungs- oder Differenzenschema ist eine vorteilhafte Möglichkeit zur Berechnung der
Steigungen/Differenzen.
i |
|
xi |
|
0. Steigung
f[xi] |
|
1. Steigung
f[xi,xi+1] |
|
2. Steigung
f[xi,xi+1,xi+2] |
|
... |
|
n. Steigung
f[xi,xi+1,...,xi+n] |
|
|
|
|
|
|
|
| 0 |
x0
|
f[x0] = f0
|
|
|
|
| f[x0,x1,...,xn] = |
f[x1,...,xn]-f[x0,...,xn-1]
xn-x0 |
|
| 1 |
x1 |
f[x1] = f1 |
|
| f[x0,x1,x2] = |
f[x1,x2]-f[x0,x1]
x2-x0 |
|
| 2 |
x2 |
f[x2] = f2 |
|
| f[x1,x2,x3] = |
f[x2,x3]-f[x1,x2]
x3-x1 |
|
| 3 |
x3 |
f[x3] = f3 |
| : |
: |
: |
: |
: |
: |
| n - 1 |
xn-1 |
f[xn-1] = fn-1 |
| f[xn-1,xn] = |
fn-fn-1
xn-xn-1 |
|
| n |
xn |
f[xn] = fn |
Doppeltes Steigungsschema:
Im Steigungsschema werden die Differenzen zwischen Stützstellen
(xi - xj) benötigt. Wenn man im Steigungsschema auf
der linken Seite die Differenzen ergänzt, wird es übersichtlicher. Man erhält
das doppelte Steigungsschema.
| x |
f(x) |
|
|
|
x0 |
|
|
x1-x0 |
|
x2-x0 |
|
x1 |
| . |
|
x2-x1 |
|
| . |
x3-x1 |
|
x2 |
| . |
|
x3-x2 |
|
|
|
|
x3 |
| | | : |
|
|
|
xn |
|
| f0 |
|
(f1-f0) ÷ (x1-x0) |
| f1 |
|
(f[x1, x2]-f[x0, x1])
÷ (x2-x0) |
|
(f2-f1) ÷ (x2-x1) |
|
. |
| f2 |
|
(f[x2, x3]-f[x1, x2])
÷ (x3-x1) |
. |
|
(f3-f2) ÷ (x3-x2) |
|
. |
| f3 |
|
| : |
| fn |
|
Beispiel 1.3:
| |
Berechne die Koeffizienten des NEWTON-Interpolationspolynoms bei gegebenen
Stützstellen (x0 = -1, f(x0) = -1, x1 = 0,
f(x1) = 3, x2 = 2, f(x2) = 11, x3 = 3,
f(x3)= 27) mit Hilfe des Steigungsschemas.
|
|
p3(x) = -1 + 4(x+1)+0(x+1)(x-0) + 1(x+1)(x-0)(x-2)
|
Gegeben sind 3 Stützstellen (xi,f(xi)).
Stelle p2 als NEWTONsches Interpolationspolynom dar.
|
Bezeichung:
pi, ..., i+k(x) ist das eindeutig bestimmte
Interpolationspolynom durch die Punkte (xi,fi),
(xi+1,fi+1), ..., (xi+k,fi+k).
Beweis 1.3:
| |
| Behauptung: pi,...,i+k(x) = |
(x-xi)pi+1,...,i+k(x)
- (x-xi+k)pi,...,i+k-1(x)
xi+k - xi |
|
(1.8) |
Fall 1: x = x
i
| |
(xi - xi)pi+1,...,i+k(xi)
- (xi - xi+k)pi,...,i+k-1(xi)
xi+k - xi |
= |
(xi+k - xi)pi,...,i+k-1(xi)
xi+k - xi |
= fi |
Da auch pi,...,i+k(xi) = fi
gilt, ist die Gleichung (1.8) für x = xi wahr.
Fall 2: x = x
j, j = i + 1, i + 2, ..., i + k - 1
Da sowohl p
i,...,i+k-1(x) als auch p
i+1,...,i+k(x) durch
die Punkte
(xi+1,fi+1),
(xi+2,fi+2), ...,
(xi+k-1,fi+k-1) geht, gilt
pi, ..., i+k-1(xj) = pi+1,...,i+k(xj)
= fj.
Daraus folgt
| (xj - xi)pi+1,...,i+k(xj)
- (xj - xi+k)pi,...,i+k-1(xj)
xi+k - xi |
= |
(xj - xi - xj + xi+k)fj
xi+k - xi |
Da auch p
i,...,i+k(x
j) = f
j gilt, ist die Gleichung (1.8)
für x = x
j, j = i + 1, i + 2, ..., i + k - 1 wahr.
x = x
i+k
| (xi+k - xi)pi+1,...,i+k(xi+k)
- (xi+k - xi+k)pi,...,i+k-1(xi+k)
xi+k - xi |
= |
(xi+k - xi)pi+1,...,i+k(xi+k)
xi+k - xi |
fi+k |
Da auch p
i,...,i+k(x
i+k) = f
i+k gilt, ist die
Gleichung (1.8) für x = x
i+k wahr.
Da es keine weiteren Fälle gibt, ist die Gleichung (1.8) wahr.
QED
Aus Gleichung (1.8) folgt
| pi,...,i+k(x) = |
(x - xi)pi+1,...,i+k(x)
- (x - xi+k + xi - xi)pi,i+1,...,i+k-1(x)
xi+k - xi |
| Þ
pi,...,i+k(x) = pi,...,i+k-1(x) + |
(x - xi)(pi+1,...,i+k(x)
- pi,...,i+k-1(x))xi+k - xi |
|
(1.9) |
Gleichung (1.9) ist die rekursive Bildungsvorschrift des NEVILLE-Algorithmusses zur Berechnung
eines Funktionswertes, wenn weiterhin pi(x) = fi und x fest gesetzt
wird. Der NEVILLE-Algorithmus ist dem Steigungsschema ähnlich.
Satz 1.2:
| |
Seien (xq, fq), q = 0, 1, ..., n, mit paarweise verschiedenen
xq gegeben.
Dann ist pi, i+1, ..., i+k = f[xi]
+ f[xi, xi+1](x - xi) + ...
+ f[xi, xi+1, ..., xi+k]
(x - xi)(x - xi+1).....(x - xi+k-1),
0 ≤ i ≤ i + k ≤ n.
Als Spezialfall ist p0, 1, ..., n = f[x0]
+ f[x0,x1](x - x0) + ...
+ f[x0,x1,...,xn]
(x - x0)(x - x1).....(x - xn-1)
das Polynom n-ten Grades, das für i = 0, 1, ..., n in den Punkten xi den Wert
fi annimmt.
|
Beweis 1.4:
Induktionsanfang: Satz 1.2 gilt für k = 0, denn p
i = f
i und
f[x
i] = f
i.
Induktionsvoraussetzung: Satz 1.2 gilt f�r alle Polynome vom Grad < k.
Induktionsbehauptung: Satz 1.2 gilt f�r Polynome vom Grad k.
Induktionsbeweis:
Nach Gleichung (1.9) gilt
| pi,...,i+k(x) = pi,...,i+k-1(x) + |
(x - xi)(pi+1,...,i+k(x)
- pi, i+1, ..., i+k-1(x))
xi+k - xi |
Nach Induktionsvoraussetzung ist p
i,...,i+k-1(x) = f[x
i]
+ f[x
i,x
i+1](x - x
i) + ...
+ f[x
i,x
i+1,...,x
i+k-1]
(x - x
i)(x - x
i+1)
....
.(x - x
i+k-2),
somit ist nur noch folgende Gleichung zu zeigen:
| f[xi,xi+1,...,xi+k]
(x - xi)(x - xi+1).....(x - xi+k-1) = |
(x - xi)(pi+1,...,i+k(x)
- pi,...,i+k-1(x))xi+k - xi |
p
i,...,i+k(x) lässt sich wie folgt darstellen
p
i,...,i+k(x) = p
i,...,i+k-1(x)
+ c(x - x
i)
....
.(x - x
i+k-1)
Dabei ist c der Koeffizent bei x
k des Polynoms p
i,...,i+k(x). Nach
Induktionsvoraussetzung ist
f[xi,xi+1,...,xi+k-1]
Koeffizient bei x
k-1 für das Polynom p
i,i+1,...,i+k-1(x) und
Koeffizient bei x
k-1 für das Polynom p
i+1,...,i+k(x), da beide
Polynome (k - 1)-ten Grades sind.
| Þ c = |
f[xi+1,xi+2,...,xi+k]
- f[xi,xi+1,...,xi+k-1]
xi+k - xi |
= f[xi, xi+2, ..., xi+k] |
Aus Induktionsanfang und Induktionsschritt folgt nach dem Satz der vollständigen Induktion,
dass Satz 1.2. für alle nichtnegativen, ganzen Zahlen k wahr ist.
QED
Demzufolge erhält man für die NEWTONsche Darstellung folgenden Term:
| |
pn(x) = f[x0] + f[x0,x1](x - x0)
+ f[x0,x1,x2](x - x0)(x - x1)
+ ... + f[x0,x1,...,xn]
(x - x0)(x - x1).....(x - xn-1) |
(1.10) |
Falls die Sortierung der Stützwerte und -stellen in umgekehrter Reihenfolge erfolgt, so
erhält man
| |
pn(x) = f[xn]
+ f[xn-1,xn](x - xn)
+ f[xn-2,xn-1,xn](x - xn)(x - xn-1)
+ ... + f[x0,x1,...,xn]
(x - xn)(x - xn-1).....(x - x1) |
(1.11) |
LEIBNIZ-Regel:
Eine gegebene Funktion f(x) sei als Produkt zweier anderer Funktionen g(x) und h(x)
darstellbar: f(x) = g(x)h(x).
Dann gilt die LEIBNIZ-Regel
f[x0,x1,...,xk] =
k i=0
g[x0,x1,...,xi]
h[xi,xi+1,...,xk] | (1.12) |
Beweis 1.5:
Induktionsanfang: Gleichung (1.12) gilt für k = 0, denn f[x
0]
= f(x
0) und
0 i=0
g[x
0,x
1,...,x
i]
h[x
i,x
i+1,...,x
0] = g[x
0]h[x
0]
= g(x
0)h(x
0) = f(x
0).
Induktionsvoraussetzung: Gleichung (1.12) gilt für k = q.
Induktionsbehauptung: Gleichung (1.12) gilt für k = q + 1.
Induktionsbeweis:
(x
q+1 - x
0)f[x
0,x
1,...,x
q+1]
= f[x
1,...,x
q+1] - f[x
0,...,x
q]
=
q+1 i=1
g[x
1,...,x
i]h[x
i,...,x
q+1]
-
q< i=0
g[x
0,...,x
i]h[x
i,...,x
q]
=
q+1 i=1
g[x
1,...,x
i]h[x
i,...,x
q+1]
-
q< i=0
g[x
0,...,x
i]h[x
i,...,x
q]
+
q i=0
g[x
0,...,x
i]h[x
i+1,...,x
q+1]
-
q++1 i=1
g[x
0,...,x
i-1]h[x
i,...,x
q+1]
=
q+1 i=1
(x
i - x
0)g[x
0,...,x
i]
h[x
i,...,x
q+1]
+
q i=0
(x
q+1 - x
i)g[x
0,...,x
i]
h[x
i,...,x
q+1]
=
q i=1
(x
i - x
0)g[x
0,...,x
i]
h[x
i,...,x
q+1]
+ (x
q+1 - x
0)g[x
0,...,x
q+1]h[x
q+1]
+ (x
q+1 - x
0)g[x
0]h[x
0,...,x
q+1]
+
q i=1
(x
q+1 - x
i)g[x
0,...,x
i]
h[x
i,...,x
q+1]
= (x
q+1 - x
0)g[x
0]h[x
0,...,x
q+1]
+
q i=1
((x
i-x
0) + (x
q+1-x
i))
g[x
0,...,x
i]h[x
i,...,x
q+1]
+ (x
q+1 - x
0)g[x
0,...,x
q+1]h[x
q+1]
= (x
q+1 - x
0)
q+1 i=0
g[x
0,...,x
i]h[x
i,...,x
q+1]
Aus Induktionsanfang und Induktionsschritt folgt nach dem Satz der vollständigen Induktion,
dass Gleichung (1.12) für alle k gilt.
QED
Bemerkung 1.6: Die NEWTONsche Interpolationsdarstellung hat gegenüber der
LAGRANGEschen Interpolationsdarstellung den Vorteil, dass beim Hinzunehmen einer weiteren
Stützstelle die bekannten c0, c1, ..., cn weiterverwendet
werden und nur cn+1 neu berechnet werden muss.
Inhalt
LAGRANGE-Interpolation
NEWTON-Interpolation mit äquidistanten Stützstellen