<<

. 21
( 31 .)



>>


• Trigonometrische Interpolation (Es gilt ’1 = i2 , eix = cos x + i sin x)
n n n
ijx
¦(x) = aj e = a0 + aj cos(jx) + i aj sin(jx)
j=0 j=1 j=1


• Kubische Spline“Interpolation

¦(x) ∈ C 2 [x0 , xn ] und ¦(x) ∈ C 3 [xj , xj+1 ]

91
92 Interpolation




Beispiel 5.2. (Nichtlineare Interpolationsprobleme)
• Rationale Interpolation
n
aj xj
j=0
¦(x) = m
bj xj
j=0

• Interpolation durch Exponentialsummen
n
aj e»j x
¦(x) =
j=0


In diesem Kapitel werden wir uns mit linearen Interpolationsproblemen beschafti-
¨
gen.


5.2 Polynominterpolation
5.2.1 Existenz und Eindeutigkeit der Polynominterpola-
tion
Polynominterpolation ist eine einfache und e¬ziente M¨glichkeit der Interpolati-
o
on. Es bezeichne Πn die Menge aller reellen oder komplexen Polynome vom Grade
¤ n. Es gilt der
Satz 5.3 (Eindeutigkeit). Zu beliebigen n+1 Stutzstellen (xj , fj ), j = 0, . . . , n,
¨
xj = xk fur j = k gibt es genau ein Polynom P ∈ Πn
¨
P (x) = a0 + a1 x + . . . + an xn

mit

(5.2) P (xj ) = fj , j = 0, . . . , n.

Beweis: Die Zerlegung von (5.2) ergibt das LGS
n
ak xk = fj , j = 0, . . . , n,
j
k=0

d.h.
« « « 
1 x0 · · · xn a0 f0
0
¬. . . . ·¬ . · = ¬ .·
¬. . .. . · ¬ . · ¬ .·
(5.3) . . .  .   .
1 xn · · · xn an fn
n
Polynominterpolation 93




Die Determinante der sogenannten Vandermonde“Matrix in (5.3) ist
n n
(xi ’ xj )
i=1 j=i+1

und damit ungleich Null, wenn die xi paarweise verschieden sind. Also ist die
Matrix invertierbar und das Gleichungssystem eindeutig l¨sbar.
o
Bemerkung 5.4. Prinzipiell ist es somit m¨glich aus dem LGS die Koe¬zienten
o
zu bestimmen, jedoch mit dem Wissen eines Aufwandes von O(n3 ) Operationen
recht teuer.
Aus diesem Grund betrachten wir andere Techniken.

5.2.2 Interpolationsformel von Lagrange
Fur die n + 1 Lagrange“Polynome vom Grad n
¨
n
x ’ xj
Li (x) :=
xi ’ xj
j=0
j=i

gilt o¬ensichtlich
1, fur i = j
¨
Li (xj ) =
0, fur i = j
¨
Damit ist unser gesuchtes Polynom gegeben durch
n
P (x) = fi Li (x), da P (xj ) = fj .
i=0

Beispiel 5.5. Wir betrachten die Daten (3, 68), (2, 16), (5, 352). Die Lagrange“
Polynome sind gegeben durch
(x ’ 2)(x ’ 5) 1
L0 (x) = = ’ (x ’ 2)(x ’ 5)
(3 ’ 2)(3 ’ 5) 2
(x ’ 3)(x ’ 5) 1
L1 (x) = = (x ’ 3)(x ’ 5)
(2 ’ 3)(2 ’ 5) 3
(x ’ 2)(x ’ 3) 1
L2 (x) = = (x ’ 2)(x ’ 3)
(5 ’ 2)(5 ’ 3) 6
Damit erhalten wir
P (x) = ’68 · 1 (x ’ 2)(x ’ 5) + 16 · 1 (x ’ 3)(x ’ 5) + 352 · 1 (x ’ 2)(x ’ 3)
2 3 6
= 30x2 ’ 98x + 92
94 Interpolation




Bemerkung 5.6. Ein Abz¨hlen der notwendigen Operationen ergibt den Auf-
a
wand O(n2 ).
Die Lagrange“Darstellung ist praktisch, wenn man Messwerte fi nachtr¨glich
a
ver¨ndern will, da diese explizit in der Polynomdarstellung auftauchen. Sie ist
a
aber i.A. unpraktisch, wenn man Datenpunkte hinzufugen will, da man alle Li
¨
neu berechnen muss.

5.2.3 Der Algorithmus von Aitken und Neville
Gesucht ist ein numerisch sparsamer Algorithmus zur Berechnung von P (x) an
einigen wenigen Stellen (z.B. nur einmalig) x.
Fur i0 , . . . , ik ∈ {0, 1, . . . , n} sei Pi0 ,...,ik ∈ Πk das Interpolationspolynom zu
¨
xi0 , . . . , xik ; insbesondere
Pi (x) ≡ fi , P0,...,n (x) = P (x).

5.2.3.1 Rekursionsformel von Aitken
Es gilt die Rekursionsformel von Aitken
(x’xi0 )Pi1 ,...,ik (x)’(x’xik )Pi0 ,...,ik’1 (x)
(5.4) Pi0 ,...,ik (x) = xik ’xi0

Beweis: Das Polynom Q(x) ∈ Πk auf der rechten Seite von (5.4) erfullt
¨
Q(xi0 ) = Pi0 ,...,ik’1 (xi0 ) = fi0
Q(xik ) = Pi1 ,...,ik (xik ) = fik
Q(xij ) = fij , j = 1, . . . , k ’ 1.

Wegen der Eindeutigkeit der Polynom-Interpolation folgt dann (5.4).

5.2.3.2 Variante von Neville
Es sei x fest. Erzeuge die Werte Pi’k,...,i (x) (k ¤ i) nach dem Schema

k=0 1 2 3
x0 f0 = P0 (x)
P0,1 (x)
x1 f1 = P1 (x) P0,1,2 (x)
P1,2 (x) P0,1,2,3 (x)
x2 f2 = P2 (x) P1,2,3 (x)
P2,3 (x)
x3 f3 = P3 (x)
Polynominterpolation 95




Bei Hinzunahme von weiteren Stutzstellen wird das Schema einfach erweitert,
¨
ohne dass die bereits berechneten Ergebnisse ungultig werden.
¨
Fur festes x gilt mit der Bezeichnung
¨

Pi,k := Pi’k,...,i (x) (k ¤ i) :

Startwerte: Pi,0 := fi , i = 0, . . . , n,
Rekursion:
(x’xi’k )Pi,k’1 ’(x’xi )Pi’1,k’1
Pi,k = ,
xi ’xi’k
P ’Pi’1,k’1
= Pi,k’1 + i,k’1 i’k , k = 1, . . . , i,
(5.5) x’x
’1
x’x i
i = 1, 2, . . .

(Durch die Umformulierung wird eine e¬ziente Berechnung erm¨glicht, da die
o
Berechnungen xi ’ xi’k beim Hinzufugen einer Stutzstelle nicht mehr ausgewer-
¨ ¨
tet werden mussen.) Resultat: Pn,n = P (x).
¨
Das obige Schema lautet dann

x0 f0 = P0,0
P1,1
x1 f1 = P1,0 P2,2
P2,1 P3,3
x2 f2 = P2,0 P3,2
P3,1
x3 f3 = P3,0
Diese Variante wird speziell fur x = 0 bei sogenannten Extrapolationsalgorithmen
¨
angewandt.
Wird der Wert von f bis zu einer bestimmten Genauigkeit gesucht, dann werden
einfach weitere Stutzstellen solange hinzugefugt, bis der berechnete Wert mit der
¨ ¨
gewunschten Genauigkeit ubereinstimmt.
¨ ¨

5.2.4 Die Newton™sche Interpolationsformel, Dividierte Dif-
ferenzen
Es sollen die Koe¬zienten des Interpolationspolynoms P (x) berechnet werden.
Fur P = P0,...,n macht man den Ansatz
¨

P (x) = a0 + a1 (x ’ x0 ) + a2 (x ’ x0 )(x ’ x1 ) + · · ·
(5.6)
+an (x ’ x0 ) · · · (x ’ xn’1 ).
96 Interpolation




Die Auswertung dieses Ausdrucks fur festes x geschieht mit dem Horner-Schema:
¨

P (x) = [. . . (an (x ’ xn’1 ) + an’1 )(x ’ xn’2 ) + . . . + a1 ](x ’ x0 ) + a0

d.h. rekursiv
bn = a n ,
bi = bi+1 (x ’ xi ) + ai , i = n ’ 1, . . . , 0,
P (x) = b0 .

Fur die Abschnittspolynome
¨
k i’1
Qk (x) = ai (x ’ xj )
i=0 j=0

folgt

(a) Qk (x) = P0,1...,k (x), k = 0, . . . , n,

(b) ak ist Koe¬zient von xk in P0,1,...,k (x).

Die Koe¬zienten ak werden nicht mittels der Bedingung P (xj ) = fj berechnet,
sondern mit Hilfe des Di¬erenzenschemas:
x0 [f0 ]
[f0 , f1 ]
x1 [f1 ] [f0 , f1 , f2 ]
[f1 , f2 ]
x2 [f2 ]
Die hier auftretenden ”Dividierten Di¬erenzen“ [fi , . . . , fk ] sind rekursiv de¬niert
durch

<<

. 21
( 31 .)



>>