Interpolation

Nadine Losert

Ausarbeitung zum Vortrag im Proseminar Analysis(Wintersemester 2008/09, Leitung PD Dr. Gudrun Thäter)

Zusammenfassung: Nachdem wir in den vorherigen Vorträgen verschiedene geometrische

Themen besprochen haben, kommen wir nun zum ersten numerischen Thema. Es handelt sich

hier um das Problem der Interpolation. Hierbei möchten wir n+1 vorgegebene Punkte durch

eine Funktion verbinden. Dabei stellen wir fest, dass es mehrere ganz verschiedene Ansätze

gibt, eine solche Funktion zu �nden. Alle diese Ansätze haben Vor- und Nachteile, und es

hängt von der Situation ab, welche Methode man am besten verwendet. In meinem Vortrag

und somit auch in dieser Ausarbeitung gehe ich hauptsächlich auf die Polynominterpolation

ein, bei der wir ein eindeutig bestimmtes Polynom n-ten Grades �nden, das durch die Stütz-

punkte verläuft. Ich werde zwei verschiedene Arten vorstellen, dieses Polynom zu bestimmen.

Anschlieÿend werden wir die Restabschätzung der Polynominterpolation betrachten. In einem

Sonderfall werden wir sehen, dass das aus der Analysis I und II bereits bekannte Taylorpo-

lynom genau genommen ein Spezialfall des Interpolationspolynoms ist. Am Ende werde ich

noch einen kurzen Ausblick auf die so genannte Spline-Interpolation geben, die ein Problem,

das bei der Polynominterpolation vieler Stützstellen entsteht, löst.

Inhaltsverzeichnis

1 Einleitung 3

2 Interpolation 32.1 Benötigte De�nitionen und Sätze . . . . . . . . . . . . . . . . . . . . . 3

2.1.1 Der Di�erenzenoperator . . . . . . . . . . . . . . . . . . . . . . 42.1.2 Satz von Rolle in der allgemeinen Form . . . . . . . . . . . . . . 6

2.2 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Nahe liegende Ansätze und deren Schwächen . . . . . . . . . . . . . . . 8

2.3.1 Stückweise lineare Interpolation . . . . . . . . . . . . . . . . . . 82.3.2 Stückweise konstante Interpolation . . . . . . . . . . . . . . . . 9

2.4 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Interpolationspolynom nach Lagrange . . . . . . . . . . . . . . . . . . . 102.6 Interpolationspolynom nach Newton . . . . . . . . . . . . . . . . . . . 12

2.6.1 Die Idee hinter der Newtonmethode . . . . . . . . . . . . . . . . 122.6.2 Newtonpolynom bei äquidistanten Stützstellen . . . . . . . . . . 132.6.3 Direkte Berechnung des Newtonpolynoms . . . . . . . . . . . . 13

2.7 Restabschätzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.8 Sonderfall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.8.1 Newtonpolynom im Sonderfall . . . . . . . . . . . . . . . . . . . 162.8.2 Restglied im Sonderfall . . . . . . . . . . . . . . . . . . . . . . . 16

2.9 Schwächen der Polynominterpolation . . . . . . . . . . . . . . . . . . . 172.9.1 Runges Phänomen . . . . . . . . . . . . . . . . . . . . . . . . . 172.9.2 Spline-Interpolation: Ein Ausblick . . . . . . . . . . . . . . . . . 18

3 Resümee 19

Abbildungsverzeichnis

1.1 Malen nach Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1 Satz von Rolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Lösung durch stückweise lineare Interpolation . . . . . . . . . . . . . . 92.4 Lösung durch stückweise konstante Interpolation . . . . . . . . . . . . . 92.5 Lösung durch Polynominterpolation . . . . . . . . . . . . . . . . . . . . 112.6 Runges Phänomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.7 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.8 Spline-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2

1 Einleitung

Aus unserer Kindheit ist uns das Spiel �Malen nach Zahlen� bekannt, bei dem num-merierte Punkte vorgegeben sind, die man verbinden muss, damit ein hübsches Bildentsteht. Hierfür genügt es, die Punkte durch mehr oder weniger gerade Linien zu ver-binden und schon kann man das Bild erkennen.Ähnlich sieht unser Problem bei der Interpolation aus: Wir haben n + 1 Punkte, diewir beispielsweise durch eine physikalische Messung gewonnen haben, im Koordina-tensystem vorgegeben und möchten sie verbinden, um auch Zwischenwerte bestimmenzu können, ohne für jeden Wert eine neue Messung vornehmen zu müssen. Allerdingsverbinden wir die Punkte nicht mit einem Bleistift, sondern mit Hilfe einer Funktion,die durch unsere Punkte verlaufen und dabei die wirklichen Zwischenwerte möglichstgut annähern soll. Zusätzlich stellen wir hier den Anspruch, eine möglichst �glatte�Funktion zu �nden, also eine Funktion, die sich möglichst oft ableiten lässt.

Abbildung 1.1: Malen nach Zahlen

2 Interpolation

2.1 Benötigte De�nitionen und Sätze

Für die Berechnung einer der Interpolationsformeln werden wir später eine Abbildung,nämlich den Di�erenzenoperator, mit einigen daraus abgeleiteten Formeln sowie denSatz von Rolle in der allgemeinen Form benötigen. Um die Schlussfolgerungen bei derHerleitung der Formeln später nicht unterbrechen zu müssen, führen wir beides vorherein.

3

2.1.1 Der Di�erenzenoperator

Der Di�erenzenoperator ist eine Abbildung, die zwar nicht direkt mit dem ThemaInterpolation zusammenhängt, jedoch für das Herleiten und Verstehen der wichtigenFormeln unerlässlich ist.

De�nition 2.1. Bezeichne (s) die Menge aller Zahlenfolgen. Der Di�erenzenoperator

ist die Abbildung

D : (s) → (s)

y := (y0, y1, y2, . . .) 7→ (y1 − y0, y2 − y1, y3 − y2, . . .)

Lemma 2.2. D ist ein Endomorphismus von (s).

Beweis. Für y, z ∈ (s) mit y = (y0, y1, y2, . . .), z = (z0, z1, z2, . . .) und α ∈ R gilt:

D(y + z) = ((y1 + z1)− (y0 + z0), (y2 + z2)− (y1 + z1), (y3 + z3)− (y2 + z2), . . .)

= ((y1 − y0) + (z1 − z0), (y2 − y1) + (z2 − z1), (y3 − y2) + (z3 − z3), . . .)

= (y1 − y0, y2 − y1, y3 − y2, . . .) + (z1 − z0, z2 − z1, z3 − z2, . . .)

= D(y) +D(z)

D(αy) = (αy1 − αy0, αy2 − αy1, αy3 − αy2, . . .)

= α(y1 − y0, y2 − y1, y3 − y2, . . .)

= αD(y)

⇒ Behauptung

Wir betrachten nun die k-fache Hintereinanderausführung von D:Für k = 0, 1, 2, 3 können wir berechnen

D0(y) = id(y) = (y0, y1, . . .)

D1(y) = (y1 − y0, y2 − y1. . . .)

D2(y) = (y2 − 2y1 + y0, y3 − 2y2 + y1, . . .)

D3(y) = (y3 − 3y2 + 3y1 − y0, y4 − 3y3 + 3y2 − y1, . . .)

4

Da die sukzessive Berechnung der Folgen Dk schnell mühsam wird, suchen wir eineMethode, sie direkt anzugeben. Dafür führen wir eine Schreibweise ein, mit deren Hilfewir die Folgenglieder von Dk direkt ausdrücken können.De�niere:

∆0yν := yν und ∆kyν := ∆k−1yν+1 −∆k−1yν für ν ∈ N0, k ∈ N

Wir können schreiben:

D(y) = (∆y0,∆y1,∆y2, . . .)

D2(y) = (∆2y0,∆2y1,∆

2y2, . . .)

D3(y) = (∆3y0,∆3y1,∆

3y2, . . .)

...

Lemma 2.3. (id+D)k(y) = (yk, yk+1, yk+2, . . .) fur k ∈ N

Beweis.

(id+D)(y) = y+D(y) = (y0, y1, y2, . . .) + (y1−y0, y2−y1, y3−y2, . . .) = (y1, y2, y3, . . .)

⇒ Behauptung

Wir können direkt ausdrücken:

Lemma 2.4. ∆ky0 =k∑ν=0

(−1)ν(kν

)yk−ν

Beweis.

Dk = [−id+ (id+D)]kBin. Satz

=k∑ν=0

(−1)ν(kν

)(id+D)k−ν

⇒ (∆ky0,∆ky1, . . .) = Dk(y) =

k∑ν=0

(−1)ν(kν

)[(id+D)k−ν(y)]

2.3=

k∑ν=0

(−1)ν(kν

)(yk−ν , yk−ν+1 . . .) = (

k∑ν=0

(−1)ν(kν

)yk−ν ,

k∑ν=0

(−1)ν(kν

)yk−ν+1, . . .)

⇒ ∆ky0 =k∑ν=0

(−1)ν(kν

)yk−ν

5

Zuletzt betrachten wir noch

Lemma 2.5.k−1∑ν=0

(kν

)∆νy0 = yk −∆ky0

Beweis.k−1∑ν=0

(kν

)Dν(y) =

k∑ν=0

[(kν

)1k−νDν(y)

]−Dk(y)

Bin. Satz= (id+D)k(y)−Dk(y)

2.3⇒k−1∑ν=0

(kν

)∆νy0 = yk −∆ky0

2.1.2 Satz von Rolle in der allgemeinen Form

Diesen Satz benötigen wir, um später eine korrekte Restabschätzung vornehmen zukönnen.

Lemma 2.6. (Satz von Rolle) Sei φ stetig im Intervall [a, b] und di�erenzierbar in

(a, b) und gelte φ(a) = φ(b) ⇒ ∃ξ ∈ (a, b) : φ′(ξ) = 0.

Beweis.φ ist stetig in [a, b]

Mittelwertsatz⇒ ∃ξ ∈ (a, b) : φ′(ξ) = f(b)−f(a)b−a

f(a)=f(b)⇒ φ′(ξ) = 0

⇒ Behauptung

Dies bedeutet, dass bei einer stetigen Funktion zwischen zwei Stellen mit gleichemFunktionswert immer eine Stelle liegen muss, an der die Kurve die Steigung 0 besitzt(s. Abb. 2.1).

Dieser Satz gilt natürlich insbesondere auch für f(a) = f(b) = 0, das heiÿt zwi-schen zwei Nullstellen einer di�erenzierbaren Funktion gibt es immer eine Stelle ξ mitf ′(ξ) = 0.

6

Abbildung 2.1: Satz von Rolle

Wir verallgemeinern diesen Satz folgendermaÿen:

Lemma 2.7. Besitze f im Intervall [a, b] mindestens n− 1 und in (a, b) mindestens nstetige Ableitungen.

Sei f(xi) = 0, i = 0, 1, . . . , n mit xi ∈ [a, b], xi < xi+1∀i ∈ {0, 1, . . . , n− 1}.⇒ ∃ξ ∈ (a, b) : D(n)(ξ) = 0

Beweis.

f n-mal di�erenzierbar, f(xi) = 0, i = 1, . . . , n mit xi ∈ [a, b]

2.6⇒ ∃ξ0.0 ∈ (x0, x1), ξ0.1 ∈ (x1, x2), . . . , ξ0.(n−1) ∈ (xn−1, xn) : f ′(ξ0.i) = 0

2.6⇒ ∃ξ1.0 ∈ (ξ0.0, ξ0.1), ξ1.1 ∈ (ξ0.1, ξ0.2), . . . , ξ1.(n−2) ∈ (ξ0.(n−2), ξ0.(n−1)) : f ′′(ξ1.i) = 0

... (iteriere diesen Schluss)

2.6⇒ ∃ξn.0 ∈ (ξ(n−1).0, ξ(n−1).1), ξn.1 ∈ (ξ(n−1).1, ξ(n−1).2) : f (n−1)(ξn.i) = 0

2.6⇒ ∃ξ(n+1).0 =: ξ ∈ (ξn.0, ξn.1) : f (n)(ξ) = 0

7

2.2 Problemstellung

Die Ausgangssituation einer Interpolation besteht immer darin, dass für n + 1 Stütz-stellen xi mit i = 0, 1, · · · , n die (nicht unbedingt verschiedenen) Stützwerte φ(xi) = yigegeben sind. Diese Stützwerte stammen meist aus Messungen oder von einer Funktion,deren Werte sich nur aufwendig, beispielsweise durch eine Reihenentwicklung, berech-nen lassen. Um nun weitere Werte zu berechnen, suchen wir eine Funktion, die an denStützstellen xi genau die zugehörigen Stützwerte yi annimmt und somit zwischen denStützstellen eine gute Annäherung an die wirkliche Funktion darstellt.Der Einfachkeit halber setzen wir im Folgenden o.B.d.A voraus, dass x0 < x1 < x2 <· · · < xn gilt.

Abbildung 2.2: Problemstellung

2.3 Nahe liegende Ansätze und deren Schwächen

2.3.1 Stückweise lineare Interpolation

Der vermutlich nächstliegende Ansatz besteht darin, die Punkte einfach durch geradeLinien zu verbinden, also die Funktion zwischen zwei Punkten xi und xi+1 durch dielineare Funktion, die diese Punkte verbindet, anzunähern.Daraus ergibt sich die Formel

S(x) = φ(xi) +φ(xi+1)− φ(xi)

xi+1 − xi(x− xi), x ∈ [xi, xi+1)

Die Werte dieser Funktion sind o�ensichtlich sehr leicht zu berechnen. Die Funktionhat jedoch den groÿen Nachteil, dass sie an den Stützstellen nicht di�erenzierbar ist.

8

Abbildung 2.3: Lösung durch stückweise lineare Interpolation

2.3.2 Stückweise konstante Interpolation

Bei der stückweise konstanten Interpolation, auch bekannt als Nearest-Neighbour-Interpolation, sucht man sich für jede Stelle x die nächstliegende Stützstelle xi undsetzt dann K(x) = yi. Wir erhalten so die Funktion

K(x) = φ(xi), x ∈[xi −

xi − xi−1

2, xi +

xi+1 − xi2

)

Auch hier fällt die Berechnung der Werte nicht schwer, jedoch ist die Funktion vorallem bei weit auseinanderliegenden Stützwerten yi meist eine schlechte Annäherung.Weiterhin besteht hier das Problem, dass K nicht an allen Stellen stetig ist.

Abbildung 2.4: Lösung durch stückweise konstante Interpolation

9

2.4 Polynominterpolation

Eine weitere Lösung des Interpolationsproblems ist die Polynominterpolation. Hier be-stimmen wir ein Polynom n-ten Grades, das genau durch die n+1 Stützpunkte verläuft.Der Vorteil besteht nun darin, dass Polynome bekanntlich beliebig oft di�erenzierbarsind. Weiterhin sind uns Polynome sehr vertraut, wir werden also keine Probleme imUmgang mit ihnen haben.

Lemma 2.8. Es existiert höchstens ein Polynom ψ n-ten Grades, für das gilt: ψ(xi) =yi, i = 0, 1, 2, . . . , n.

Beweis. Seien γ und ψ zwei Polynome n-ten Grades, für die gilt: γ(xi) = ψ(xi) =yi ∀i ∈ {0, 1, . . . , n}

Sei F (x) := γ(x)− ψ(x) = cnxn + cn−1x

n−1 + · · ·+ c1x+ c0

⇒ F (xi) = 0 ∀i ∈ 1, . . . , n

⇒ F (x) = cn(x− x1)(x− x2) · · · (x− xn)

aber : 0 = F (x0) = cn (x0 − x1)(x0 − x2) · · · (x0 − xn)︸ ︷︷ ︸6=0, da xi paarweise verschieden

⇒ cn = 0

⇒ F (x) = 0

⇒ γ = ψ

⇒ Es existiert höchstens ein Polynom ψ, das die geforderten Eigenschaften erfüllt.

2.5 Interpolationspolynom nach Lagrange

Die Idee dieser Methode besteht darin, ein Interpolationspolynom der Form

L(x) = y0L0(x) + y1L1(x) + . . .+ ynLn(x)

zu �nden mit

Lk(xj) = δkj :=

{1 für k = j0 für k 6= j

,

dann folgt bei Einsetzen der Stützstellen xi o�ensichtlich

L(xi) = Li(xi)yi = yi.

Nun suchen wir Polynome Lk, die die Bedingung Lk(xj) = δkj erfüllen.

10

Hierbei erreichen wir die Bedingung Lk(xj) = 0 ∀j 6= k durch den Term

Lk(x) :=∏i 6=k

0≤i≤n

(x− xi)

Um nun auch die Bedingung Lk(xk) = 1 zu erreichen, de�nieren wir

Lk(x) :=Lk(x)

Lk(xk)=∏i 6=k

0≤i≤n

x− xixk − xi

Mit dem Lagrangeschen Interpolationspolynom

L(x) =n∑ν=0

yν∏i 6=ν

0≤i≤n

x− xixν − xi

ist also das Interpolationsproblem gelöst, denn es gilt L(xi) = yi ∀i ∈ {0, 1, 2, . . . , n}.Die Schwäche des Lagrangeschen Polynoms liegt darin, dass bei Hinzunahme weitererStützstellen eine völlig neue Berechnung des Polynoms notwendig ist.

Abbildung 2.5: Lösung durch Polynominterpolation

11

2.6 Interpolationspolynom nach Newton

Einen Ausweg bietet das Interpolationspolynom nach Newton, das sich die bei Hinzu-nahme weiterer Stützstellen sukzessive erweitern lässt.

2.6.1 Die Idee hinter der Newtonmethode

Bei der Newtonmethode bilden wir zuerst ein konstantes Polynom, das überall - alsoinsbesondere auch an der ersten Stützstelle x0 - den ersten Stützwert y0 annimmt.Dieses Polynom muss natürlich N0(x) = y0 := α0 sein. Um nun auch an der zweitenStützstelle x1 den zugehörigen Stützwert y1 zu erreichen, addieren wir zu N0 einenTerm, der für x = x0 verschwindet, also den Faktor (x − x0) enthält. Diese Methodeiterieren wir für die restlichen Stützstellen und erhalten somit:

N0(x) = α0

N1(x) = α0 + α1(x− x0)N2(x) = α0 + α1(x− x0) + α2(x− x0)(x− x1)

...Nn(x) = α0 + α1(x− x0) + α2(x− x0)(x− x1)

+ · · ·+ αn(x− x0)(x− x1) · · · (x− xn−1)

O�ensichtlich löst das Polynom N(x) := Nn(x) mit geeignet gewählten αi das Inter-polationsproblem.

Um die αi zu bestimmen, rufen wir uns unser ursprüngliches Problem N(xi)!

= yi inErinnerung. Durch Einsetzen erhalten wir:

y0 = α0

y1 = α0 + α1(x1 − x0)y2 = α0 + α1(x2 − x0) + α2(x2 − x0)(x2 − x1)

...yn = α0 + α1(xn − x0) + α2(xn − x0)(xn − x1)

+ · · ·+ αn(xn − x0)(xn − x1) · · · (xn − xn−1)

und können somit die Faktoren αi durch sukzessives Au�ösen der Gleichungen bestim-men.Das Newtonpolynom

N(x) = y0 +n∑i=1

αi(x− x0)(x− x1) · · · (x− xi−1)

mit

yk = α0 +n∑i=1

αi(xk − x0)(xk − x1) · · · (xk − xi−1)

12

löst also ebenfalls das Interpolationsproblem und ist somit aufgrund der Eindeu-tigkeit des Interpolationspolynoms identisch mit dem Lagrangeschen Interpolations-polynom. O�ensichlich ist es bei Hinzunahme einer weiteren Stützstelle xn+1 lediglicherforderlich, mithilfe einer weiteren Gleichung den Faktor αn+1 zu bestimmen und denTerm αn+1(x− x0)(x− x1) · · · (x− xn) zum Newtonpolynom zu addieren.

2.6.2 Newtonpolynom bei äquidistanten Stützstellen

Wir betrachten nun den besonders häu�gen Fall von äquidistanten Stützstellen, dasheiÿt

xi+1 − xi = h ∀i ∈ {0, 1, 2, . . . , n− 1}

Wie betrachten die Formel zur Berechnung der αi:

yk = α0 +∑n

i=1 αi (xk − x0)︸ ︷︷ ︸=kh

(xk − x1)︸ ︷︷ ︸=(k−1)h

· · · (xk − xi−1)︸ ︷︷ ︸=(k−i+1)h

= α0 +∑n

i=1 αihik(k − 1) · · · (k − i+ 1)

= α0 +∑n

i=1 αihi k!k−i!

Wir sehen also, dass die Berechnung des Newtonpolynoms bei äquidistanten Stützstel-len sehr einfach wird.

2.6.3 Direkte Berechnung des Newtonpolynoms

Nun wäre es wünschenswert, eine Formel zu �nden, mit der wir die αi direkt - alsoohne ein Gleichungssystem lösen zu müssen - berechnen können. Mithilfe des in 2.1.1eingeführten Di�erenzenoperators ist dies möglich.

Lemma 2.9. Es gilt: αk = ∆ky0k!hk für k = 0, 1, . . . , n

Beweis. Induktionsanfang für k = 0

∆0y0

0!k0= y0 = α0

InduktionsvoraussetzungEs gelte für ein k < n

αi =∆iy0

i!hi∀i = 0, 1, . . . , k

13

Induktionsschritt k → k + 1

yk+12.6.2= α0 +

∑ni=1 αih

i k+1!k+1−i!

= α0 + α1h1(k+1)!

k!+ α2

h2(k+1)!(k−1)!

+ · · ·+ αkhk(k+1)!

1!+ αk+1h

k+1(k + 1)!

IV= ∆0y0

0!h0 + ∆1y0h1(k+1)!h11!k!

+ ∆2y0h2(k+1)!h22!(k−1)!

+ · · ·+ ∆ky0(k+1)!hkk!1!

+ αk+1hk+1(k + 1)!

= ∆0y0 + ∆1y0k+1!

1!((k+1)−1)!+ ∆2y0

k+1!2!((k+1)−2)!

+ · · ·+ ∆ky0k+1!

k!((k+1)−k)!+ αk+1h

k+1(k + 1)!

=(k+1

0

)∆0y0 +

(k+1

1

)∆1y0 +

(k+1

2

)∆2y0 + · · ·+

(k+1k

)∆ky0 + αk+1h

k+1(k + 1)!

=k∑ν=1

[(k+1ν

)∆νy0

]+ αk+1h

k+1(k + 1)!

2.5= yk+1 −∆k+1y0 + αk+1h

k+1(k + 1)!

⇒ αk+1 = ∆k+1y0(k+1)!hk+1

⇒ Behauptung

Durch Einsetzen in N(x) erhalten wir die direkte Gleichung für das Newtonpoly-nom:

N(x) = y0 +n∑i=1

∆iy0

i!hi(x− x0)(x− x1) · · · (x− xi−1)

Falls wir unsere Stützwerte durch eine Messung gewonnen haben, also nichts überdie ursprüngliche Funktion wissen, ist das Problem der Interpolation durch Polynomehiermit vollständig gelöst.

2.7 Restabschätzung

Gehen wir jedoch von einer ursprünglichen Funktion φ aus, die wir annähern möchten,so müssen wir uns natürlich nach dem Interpolationsfehler fragen, also eine Restab-schätzung vornehmen. Hierfür benötigen wir die Bedingung, dass φ im Intervall min-destens n+ 1 stetige Ableitungen besitzt.

De�niere: R(x) := φ(x)−N(x)

⇒ R(xi) = 0 ∀i ∈ {0, 1, . . . , n}

De�niere: K(x) := R(x)− c(x− x0)(x− x1) · · · (x− xn)

⇒ K(xi) = 0 ∀i ∈ {0, 1, . . . , n}

14

Wähle nun y 6= xi ∀i ∈ {0, 1, . . . , n} beliebig und de�niere:

c := R(x)(y−x0)(y−x1)···(x−xn)

⇒ K(y) = R(y)−R(y) (y−x0)(y−x1)···(y−xn)(y−x0)(y−x1)···(x−xn)

= 0,

K hat also n+ 2 Nullstellen

2.7⇒ ∃ξ ∈ (min{x0, y},max{xn, y}) : Kn+1(ξ) = 0

⇒ 0 = φ(n+1)(ξ)−N (n+1)(ξ)︸ ︷︷ ︸=0

−c(n+ 1)!

⇒ 0 = φ(n+1)(ξ)− c(n+ 1)!

⇒ c = φ(n+1)(ξ)(n+1)!

K(y)=0⇒ 0 = R(y)− φ(n+1)(ξ)(n+1)!

(y − x0)(y − x1) · · · (y − xn)

⇒ R(y) = (y−x0)(y−x1)···(y−xn)(n+1)!

φ(n+1)(ξ)

y beliebig⇒ R(x) = (x−x0)(x−x1)···(x−xn)(n+1)!

φ(n+1)(ξ) ∀x

Somit erhalten wir die vollständige Lösung unseres Problems durch:

φ(x) = N(x) +R(x)

= y0 +n∑i=1

[∆iy0i!hi (x− x0)(x− x1) · · · (x− xi−1)

]+ (x−x0)(x−x1)···(x−xn)

(n+1)!φ(n+1)(ξ)

mitξ ∈ (min{x0, y},max{xn, y}).

2.8 Sonderfall

Wir betrachten den Fall, dass alle Stützstellen xi zusammenfallen, also h = 0 ist. Wiesodies sinnvoll ist, werden wir später sehen. Wir bestimmen einen allgemeinen Limes:

Lemma 2.10. limh→0∆kyi

hk = φ(k)(xi), i = 0, ..., n

Beweis. Induktionsanfang für k = 0

limh→0

∆0yih0

= limh→0

yi = yi = φ(xi) = φ(0)(xi)

15

InduktionsvoraussetzungGelte die Behauptung für ein festes k

Induktionsschritt k → k + 1

limh→0

∆k+1yi

hk+1 = limh→0

∆kyi+1−∆kyi

hkh

= limh→0

1h

(∆kyi+1

hk − ∆kyi

hk

)IV= lim

h→0

φ(k)(xi+1)−φ(k)(xi)h

= limh→0

φ(k)(xi+h)−φ(k)(xi)h

= φ(k+1)(xi)

⇒ Behauptung

Somit gilt natürlich insbesondere

limh→0

∆ky0

hk= φ(k)(x0)

2.8.1 Newtonpolynom im Sonderfall

Schauen wir uns nun den Grenzwert des Newtonpolynoms im Sonderfall an:

limh→0

N(x) = limh→0

[y0 +n∑i=1

∆iy0i!hi (x− x0)(x− x1) · · · (x− xi−1)]

= y0 +n∑i=1

(limh→0

∆iy0hi

)1i!(x− x0)(x− x1) · · · (x− xi−1)

2.10= φ(x0) +

n∑i=1

φ(i)(x0)i!

(x− x0)(x− x1) · · · (x− xi−1)

xi=x0∀i= φ(x0) +n∑i=1

φ(i)(x0)i!

(x− x0)i

Dieser Ausdruck entspricht dem Taylorpolynom zu φ vom Grad n entwickelt um x0.

2.8.2 Restglied im Sonderfall

Betrachten wir nun das Restglied:

R(x) = (x−x0)(x−x1)···(x−xn)(n+1)!

φ(n+1)(ξ)

xi=x0∀i= (x−x0)n+1

(n+1)!φ(n+1)(ξ)

für ein ξ ∈ (x, x0).

16

Dies entspricht dem Taylorrestglied in der Darstellung nach Lagrange. Wir sehen also,dass die Taylorformel ein Spezialfall der Newtonschen Interpolationsformel ist.Hierbei ist zu beachten, dass im Falle des Zusammenfalls der Stützstellen xi auch dieStützwerte yi zusammenfallen müssen, da es keine Funktion gibt, die an einer Stellex verschiedene Werte y annimmt. Die Informationen, die uns durch den Wegfall derStützstellen x1, x2, . . . , xn verloren gehen, werden im Fall der Taylorformel also durchdie Werte der Ableitungen φ(1)(x0), φ(2)(x0), . . . , φ(n)(x0) ersetzt. Diese Werte habenwir, wie wir gesehen haben, für die Berechnung des Grenzwertes des Newtonpolynomsbenötigt.Streng genommen handelt es sich beim Taylorpolynom nicht mehr um ein Interpolati-onspolynom, da keine Werte zwischen Stützstellen angenähert werden, sondern um einvollständiges Extrapolationspolynom, mit dem wir Werte auÿerhalb der Stützstellen,genauer gesagt einer einzigen Stützstelle, annähern können. Hierbei wird die Annähe-rung bekanntlich umso schlechter, je weiter wir uns von der Stützstelle xi entfernen.

2.9 Schwächen der Polynominterpolation

Wie wir gesehen haben, erfüllt die Polynominterpolation den Anspruch, eine Interpo-lationsfunktion mit beliebig vielen Ableitungen zu �nden. Sie hat jedoch die Schwäche,dass Polynome höheren Grades stark zum Überschwingen neigen, die Annäherung imFall sehr vieler Stützstellen also schnell sehr schlecht wird.

2.9.1 Runges Phänomen

Dieses Überschwingen sehen wir anschaulich anhand der Runge-Funktion:

f(x) =1

1 + (5x)2

Betrachten wir nun die Interpolationspolynome (in rot) für 6 und 11 Stützstellen:

Abbildung 2.6: Runges Phänomen

17

Hier wird klar, dass die Annäherung im Falle n = 10 an den Rändern sehr schlechtist. Eine mögliche Lösung für dieses Problem besteht darin, die Abstände der Stütz-stellen an den Rändern kleiner zu wählen.

2.9.2 Spline-Interpolation: Ein Ausblick

In der Praxis wird im Falle von sehr vielen Stützstellen jedoch meist die Spline-Interpolation verwendet. Hierbei handelt es sich um eine Art stückweise Polynomin-terpolation. Die Interpolationsfunktion wird jeweils zwischen zwei Stützstellen durchPolynome niedrigen Grades de�niert, wobei man an die Funktion den Anspruch stellt,dass sie an den Stützstellen zweimal di�erenzierbar ist. Schauen wir uns für ein Beispielmit n = 7 die Polynom- und die Spline-Interpolation im Vergleich an:

Abbildung 2.7: Polynominterpolation

Abbildung 2.8: Spline-Interpolation

Hier ist gut zu sehen, dass die groÿen Schwingungen des Polynoms bei der Spline-Interpolation verschwinden.

Dennoch ist die Polynominterpolation in der Mathematik sehr wichtig zur Annähe-rung von Funktionen zwischen wenigen Stützpunkten und als Grundlage bestimmterIntegrationsverfahren.

18

3 Resümee

Während der Arbeit an diesem Thema �el mir auf, wie kompliziert sich ein anfangseinfach erscheinendes Problem mathematisch lösen lässt. So scha�t man zum Beispieldurch die Verbesserung der stückweise linearen Interpolation auf die di�erenzierbarePolynominterpolation wiederum das neue Problem des Überschwingens.Besonders interessant fand ich, dass es fast zu jeder Situation und zu jedem Anspruch,den ich an die interpolierende Funktion stelle, eine Lösung gibt. So werde ich zumBeispiel meist stückweise linear interpolieren, wenn es nur um die Bestimmung derZwischenwerte geht. Lege ich dagegen Wert auf die Di�erenzierbarkeit, wende ich diePolynominterpolation an. Suche ich hingegen einen Kompromiss zwischen �Glätte� derFunktion und Exaktheit der Zwischenwerte, so wähle ich die Spline-Interpolation.Mich würde im Anschluss an diese Arbeit das Prinzip der Spline-Interpolation genauerinteressieren. Lesern, denen es genauso geht, empfehle ich für den ersten WissensdurstWikipedia, für fundiertere und ausführlichere Informationen jedoch das entsprechendeonline verfügbare Skript der Uni Göttingen1, das jedoch meiner Erfahrung nach ohneweitere numerische Kenntnisse sehr schwierig nachzuvollziehen ist.

1https://lp.uni-goettingen.de/get/text/1232

19

Literatur

[1] Richard Courant: Vorlesung über Di�erential- und Integralrechung 1Springer Verlag, Berlin - Heidelberg - New York, 4.Au�age, 1971

[2] Harro Heuser: Lehrbuch der Analysis 1Teubner, Stuttgart, 4. durchgesehene Au�age, 1986

[3] http://de.wikipedia.org (25.10.2008)

[4] http://en.wikipedia.org (25.10.2008)

Abbildungen

(1.1) http://www.kigo-tipps.de/images/bildmaterial/zb_eichhoernchen.jpg (4.11.2008)(2.1) http://upload.wikimedia.org/wikipedia/de/0/0c/Satz_von_Rolle.png (4.11.2008)(2.2) http://en.wikipedia.org/wiki/Image:Interpolation_Data.svg (4.11.2008)(2.3) http://en.wikipedia.org/wiki/Image:Interpolation_example_linear.svg (4.11.2008)(2.4) http://en.wikipedia.org/wiki/Image:Piecewise_constant.svg (4.11.2008)(2.5) http://en.wikipedia.org/wiki/Image:Interpolation_example_polynomial.svg (4.11.2008)(2.6) http://upload.wikimedia.org/wikipedia/commons/4/4d/Interpolation

_runge_funktion_5_stuetzstellen.png (4.11.2008)und http://de.wikipedia.org/wiki/Bild:Interpolation

_runge_funktion_10_stuetzstellen.png (4.11.2008)(2.7) http://upload.wikimedia.org/wikipedia/de/6/6e/Polynom_interpolation.png (4.11.2008)(2.8) http://de.wikipedia.org/w/index.php?title=

Bild:Spline_interpolation.svg&�letimestamp=20071210125345 (4.11.2008)

20