<<

. 22
( 31 .)



>>

(a) [fi ] = fi ,
[fi+1 ,··· ,fk ]’[fi ,...,fk’1 ]
(b) [fi , . . . , fk ] = ,
xk ’xi

z.B.
f1 ’f0
[f0 , f1 ] = x1 ’x0
[f1 ,f2 ]’[f0 ,f1 ]
[f0 , f1 , f2 ] = .
x2 ’x0

Satz 5.7. Es gilt:
k i’1
P0,...,k (x) = [f0 , . . . , fi ] (x ’ xj ).
i=0 j=0
Polynominterpolation 97




Beweis: Durch Induktion bzgl. k: Fur k = 0 ist die Behauptung o¬ensichtlich
¨
richtig: Die Aussage gelte fur k ’ 1 ≥ 0.
¨
P0,...,k (x) = P0,...,k’1 (x) + a(x ’ x0 ) · · · (x ’ xk’1 ).

Zu zeigen ist a = [f0 , . . . , fk ].
Koe¬zient von xk in P0...,k (x) :a
Koe¬zient von xk’1 in P0...,k’1 (x) : [f0 , . . . , fk’1 ]
Koe¬zient von xk’1 in P1...,k (x) : [f1 , . . . , fk ]
(nach Induktionsvoraussetzung)
Nach der Formel von Aitken (5.4) ist
(x ’ x0 )P1,...,k (x) ’ (x ’ xk )P0,...,k’1 (x)
P0,...,k (x) = .
xk ’ x0
Der Koe¬zient von xk auf der rechten Seite ist
[f1 , . . . , fk ] ’ [f0 , . . . , fk’1 ]
a= = [f0 , . . . , fk ].
xk ’ x0

De¬nition
Beispiel 5.8. (vgl. Lagrange-Form)
Das Di¬erenzenschema lautet
[f0 ] = 68
16’68
[f0 , f1 ] = = 52
2’3
52’112
[f1 ] = 16 [f0 , f1 , f2 ] = = 30
3’5
16’352
[f1 , f2 ] = = 112
2’5
[f2 ] = 352
Damit erhalten wir das Interpolationspolynom (vgl. (5.5))

P (x) = P0,2 (x) = 68 + 52(x ’ 3) + 30(x ’ 3)(x ’ 2) = 30x2 ’ 98x + 92

Satz 5.9. Fur eine beliebige Permutation i0 , . . . , in von 0, . . . , n gilt
¨
[fi0 , . . . , fin ] = [f0 , . . . , fn ].

Bemerkung 5.10. Die Berechnung der dividierten Di¬erenzen kann o¬ensicht-
lich mit O(n2 ) Rechenoperationen erfolgen. Die Bestimmung des Polynoms P
hingegen ben¨tigt nur O(n) Operationen, wenn man zur Auswertung das Horner“
o
Schema verwendet.
98 Interpolation




Mit dem Newton“Schema konnen leicht zusatzliche Datenpunkte mit in die In-
¨ ¨
terpolation aufgenommen werden. Außerdem erlaubt das Horner“Schema eine
e¬ziente Berechnung des Polynoms, wenn selbiges sehr oft fur verschiedene x
¨
auszuwerten ist.

5.2.5 Interpolationsfehler
Wir betrachten den Fehler f (x) ’ P (x) zwischen einer Funktion f und dem In-
terpolationspolynom P zu den Stutzstellen (xj , fj ), fj = f (xj ), j = 0, . . . , n. Es
¨
gilt der
Satz 5.11. Sei f ∈ C n+1 [a, b] und x, x0 , . . . , xn ∈ [a, b]. Dann gibt es ein ξ ∈ [a, b]
¯
mit
f (n+1) (ξ)
(5.7) f (¯)’P (¯) =
x x L(¯),
x L(x) := (x’x0 )(x’x1 ) . . . (x’xn )
(n + 1)!
Beweis: Betrachte fur x = xj die Funktion
¨¯
f (¯) ’ P (¯)
x x
L(x) ∈ C n+1 [a, b]
F (x) := f (x) ’ P (x) ’
L(¯)
x
F hat die n+2 Nullstellen x, x0 , . . . , xn in [a, b]. Nach dem Satz von Rolle (Zwi-
¯
schen zwei Nullstellen einer Funktion F (x) liegt (mindestens) eine Nullstelle ihrer
Ableitung F (x)) hat F (n+1) (x) mindestens eine Nullstelle ξ ∈ [a, b]:
f (¯) ’ P (¯)
x x
0 = F (n+1) (ξ) = f (n+1) (ξ) ’ (n + 1)!
L(¯)
x
’ Behauptung.
Bemerkung 5.12. Fur den Interpolationsfehler erhalten wir somit die Absch¨tzung
a
¨
f (n+1) (y)
(5.8) |f (x) ’ P (x)| ¤ max L(x) .
y∈[a,b] (n + 1)!

Bemerkung 5.13. Wegen |x ’ xi | ¤ b ’ a folgt sofort
(b ’ a)n+1
(n+1)
(5.9) |f (x) ’ P (x)| ¤ max f (y) .
(n + 1)!
y∈[a,b]

Beispiel 5.14. Es sei f (x) = sin(x) auf [0, 2π]. Aus
f (1) (x) = cos(x), f (2) (x) = ’ sin(x), f (3) (x) = ’ cos(x), . . .
folgt |f (k) (y)| ¤ 1, ∀y ∈ IR. Mit den ¨quidistanten Stutzstellen xi = 2πi/n folgt
a ¨
aus (5.9)
(2π)n+1
|f (x) ’ P (x)| ¤ .
(n + 1)!
¨
Man sieht leicht, daß bereits fur kleine n eine sehr gute Ubereinstimmung der
¨
Funktionen erwartet werden kann.
Polynominterpolation 99




5.2.6 Konvergenz
Sei
(m) (m)
< . . . < x(m) = b},
∆m := {a = x0 < x1 m = 0, 1, . . . ,
nm

eine Folge von Intervallteilungen von [a, b].
(m) (m)
∆m = max |xi+1 ’ xi | .
i

P∆m (x) bezeichne das interpolierende Polynom von f bzgl. ∆m .
Problem: Gilt lim P∆m (x) = f (x) fur
¨
m’∞

lim ∆m = 0 ?
m’∞

Antwort: i.A. nicht richtig.


Beispiel 5.15. (Beipiel von Runge)
f (x) = (1 + 25x2 )’1 in [’1, 1]
f (x) ist bzgl. x ∈ C keine ganze Funktion: vgl. Satz 5.17.
I
f wird an den Stellen xj = ’1 + 2j , j = 0, . . . , n, interpoliert durch ein Polynom
n
1


0.9


0.8


0.7


0.6


0.5


0.4


0.3


0.2


0.1


0
’1 ’0.8 ’0.6 ’0.4 ’0.2 0 0.2 0.4 0.6 0.8 1




Abbildung 5.1: Beispiel von Runge.

Pn .

n f ’ Pn ∞
1 0.96
5 0.43
13 1.07
19 8.57
100 Interpolation




Wir w¨hlen nun die Knoten x0 , . . . , xn so, dass L
a = max |L(x)| m¨glichst
o

’1¤x¤1
klein wird, vgl. (5.8). Man erh¨lt
a

L(x) = 2’n Tn+1 (x) , x ∈ [’1, 1],

wobei die Tschebysche¬-Polynome Tn wie folgt de¬niert sind:

Tn (x) = cos nθ, x = cos θ, 0 ¤ θ ¤ 2π.

¤ 1 und die Nullstellen von L(x) = 2’n Tn+1 (x) sind
Es gilt Tn ∞

1
(j + 2 )π
xj = cos , j = 0, . . . , n.
n+1
Bei dieser Wahl der Knoten ergibt sich die Fehlerabsch¨tzung
a
n f ’ Pn ∞
1 0.93
5 0.56
13 0.12
19 0.04
Die Verbesserung ist erheblich, die Approximation aber immer noch unbefriedi-
gend.

Ohne Beweis geben wir noch an:

Satz 5.16. Zu jeder Folge {∆m } gibt es f ∈ C[a, b], so dass {P∆m } nicht gleichm¨ßig
a
gegen f konvergiert.

Satz 5.17. Sei f eine ganze Funktion. Dann gilt P∆m ’ f gleichm¨ßig fur alle
a ¨
{∆m } mit ∆m ’ 0.

Bemerkung 5.18. P (x) = P0,...,n (x) oszilliert i.A. stark fur großes n; die Inter-
¨
polation ist dann unbrauchbar. Diese Schwierigkeiten werden bei der Spline-Interpolation
vermieden.


5.3 Trigonometrische Interpolation
5.3.1 Diskrete Fouriertransformation

<<

. 22
( 31 .)



>>