[WS] Polynominterpolation - Theorie

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Polynominterpolation - Theorie
Gliederung

  1. Lagrange-Interpolations-Aufgabe

  2. Eindeutigkeit und Existenz

  3. Horner-Schema
    3a. Abspaltung einer Nullstelle

  4. Polynom vom Grad n mit (n+1) Nullstellen ist gleich dem Nullpolynom

  5. Taylor-Polynom-Darstellung
    5a. Koeffizientenberechnung mittels vollst. Horner-Schema

  6. Monom-Darstellung

  7. Lagrange-Darstellung

  8. Newton-Darstellung
    8a. Dividierte Differenzen - Definition
    8b. Dividierte Differenzen - Berechnung
    8c. Neville-Schema

  9. Interpolationsfehler
    9a. Darstellung 2
    9b. Darstellung 3
    9c. Abschätzungen

  10. Approximation
    10a. Tschebyscheffknoten
    10b. Konvergenz
    10c. Approximationssatz von Weierstraß
    10d. Fehlerempfindlichkeit und Extrapolation

  11. Weitere Darstellung der Dividierten Differenzen
    11a. Integraldarstellung der dividierten Differenzen
    11b. Integraldarstellung des Interpolationsfehlers
    11c. Mehrfachknoten


  12. Hermitsche-Interpolations-Aufgabe
    12a. Eindeutigkeit
    12b. Existenz (Neville-Hermite-Schema)
    12c. Dividierte Differenzen (Neville-Hermite)
    12d. Hermite-Darstellung
    12e. Interpolationsfehler



Im Anhang habe ich ein Schaubild dieses Themas beigefügt. Dabei kann es bei der Nummerierung zu Abweichungen von obiger Gliederung kommen. Jedoch sollte es über die Titel möglich sein, den Zusammenhang herzustellen.

Rechenbeispiele befinden sich in einem eigenen Workshop.

Fragen & Anregungen bitte hier posten.
tigerbine Auf diesen Beitrag antworten »
1. Lagrange-Interpolations-Aufgabe
In diesem Workshop wollen wir uns mit der Lösung der Lagrange'schen Interpolationsaufgabe beschäftigen. Dazu müssen wir sie zunächst formulieren:

LIPA

Bestimme zu (n+1) paarweise verschiedenen Knoten und zugehörigen Knotenwerten ein Polynom mit:



 
 
tigerbine Auf diesen Beitrag antworten »
2. Eindeutigkeit der Lösung
Seien zwei Lösungen der LIPA. Dann hat das Polynom (n+1) Nullstellen.

Mit (4) folgt dann und damit .
tigerbine Auf diesen Beitrag antworten »
3. Horner-Schema
Klassischer Weise ist ein Polynom in der Monom-Darstellung gegeben:

Jedoch ist diese Darstellung zur Auswertung an einer Stelle eher ungeeignet, sind doch:





durchzuführen. Deswegen schreibt man es wie folgt um:

Und werten die Klamern von innen(rechts) nach außen (links) aus. Das führt dann auf die Berechnungsvorschrift des Hornerschemas:







Das Polynom mit den Koeffizienten bezeichnen wir mit:



Auch dieses Polynom könnten wir wieder an der Stelle auswerten. Wiederholte Anwendung liefert das vollständige Hornerschema:











tigerbine Auf diesen Beitrag antworten »
3a - Abspalten einer Nullstelle
Es gilt der folgende Zusammenhäng zwischen und die in (3) eingeführt wurde. Beweis ist durch Nachrechnen führbar.




Lehrer
Es muss natürlich nicht unbedingt eine Nullstelle von sein, die Titelwahl erklärt sich mit den nächsten post.
tigerbine Auf diesen Beitrag antworten »
4. Polynom vom Grad n mit (n+1) Nullstellen ist gleich dem Nullpolynom
Nun können wir die in (2) verwendete Behauptung beweisen. Sei und besitze (n+1) Nullstellen. Dann können wir folgende vollst. Induktion führen:









Aus (IV) wissen wir, dass n Nullstellen hat. Es muss also noch eine weitere Nullstelle haben. Sei diese Nullstelle nun mit bezeichnet, dann folgt:



fertig.
tigerbine Auf diesen Beitrag antworten »
5. Taylor-Polynom-Darstellung
Hier wollen wir uns die Taylorpolynom-Darstellung des Polynoms anschauen. Entwickeln wir diese um , so gilt offensichtlich:



Denn es gilt für das Restglied (hier in der Lagransche-Form):



Somit haben wir eine weitere Darstellung des Interpolationspolynoms. Die Koeffizienten lassen sich aus dem vollständigen Hornerschema ablesen, siehe (5a).
tigerbine Auf diesen Beitrag antworten »
5a. Koeffizientenberechnung mittels vollst. Horner-Schema
In diesem Abschnitt soll gezeigt werden, dass in der letzten Diagonale des vollst. Horner-Schemas die gesuchten Koeffizienten stehen, also dass gilt:




Beweis


(1) j-maliges Differenzieren von in der Darstellung (3a)












Zürückführen auf (n-j)







tigerbine Auf diesen Beitrag antworten »
6. Monom-Darstellung
Wie bereits erwähnt, können wir das gesuchte Interpolationspolynom (IP) in der Monom-Schreibweise wie folgt angeben:



Da es Lösung der LIPA (siehe 1) ist, gilt folglich für alle i = 0,...,n:



Dieses können wir dann als Lineares Gleichungssystem schreiben:



Diese Matrix nennt man Vandermonde-Matrix. Aus ihrer Regularität folgt die Existenz und Eindeutigkeit des Koefizientenvektors a und damit des IPs.

Man kann dies aber auch ohne ihre Kenntnis beweisen. Dazu betrachten wir den Spezialfall , also das homogene LGS:



Lesen wir dies zeilenweise, so steht im Grunde a, dass das gesuchte IP (n+1) Nullstellen hat. Mit (4) folgt, dass es sich dann eindeutig um das Nullpolynom handelt. Daher ist die einzige Lösung, somit der Kern nur der Nullvektor, also die Matrix regulär. Wieder folgt daraus die Existenz und Eindeutigkeit des Interpolationspolynoms
tigerbine Auf diesen Beitrag antworten »
7. Lagrange-Darstellung
Leider ist die Monom-Darstellung zur praktischen Bestimmung des IPs nur bedingt geeignet, muss doch ein inhomogenes LGS einer meist vollbesetzten (nxn)-Matrix gelöst werden. Hier eine weitere Darstellung des IPs, die Lagrange-Darstellung:



Der Nachweis der Erfüllung der LIPA erfolgt durch Rechnung. Mit dieser Form sind wir also jetzt in der Lage, das IP direkt aus den Knoten und zug. Werten zu bestimmen. Anwendung findet diese Darstellung unter anderem beim Thema Numerische Integration. Um der Kritik in Punkt 8 vorzugreifen, empfehle ich das PDF über die baryzentrische Darstellung aus diesem Thread. Sie spielt vor allem unter dem Gesichtspunkt eine Rolle, dem wir uns in Punkt 10a. (Tschebyscheffknoten) dieses Workshops widmen.
tigerbine Auf diesen Beitrag antworten »
8. Newton-Darstellung
Ein Nachteil der Lagrange-Darstellung ist jedoch, dass man bei der Hinzunahme eines weiteren Knotens die bisherigen Ergebnisse verwerfen muss. Gesucht ist nun eine Darstellung von , die einfach zu bei der Hinzunahme eines weiteren Knotens, zu erweitern ist. Da einen Vektorraum bildet, besitzt eine eindeutige Darstellung bzgl. jeder Basis dieses Vektorraums. In (6) wurde das IP z.B. als Linearkombination der Monom-Basis ausgedrückt. Eine andere Basis erhält man durch die Basisfunktion N:

-

-

Die Newton-Darstellung des IPs sieht dann wie folgt aus:



Das die LIPA wiederspiegelnde LGS sieht dann wie folgt aus:



Da die Knoten paarweise verschieden sind, erkennt man sofort die Regularität der Matrix und damit wieder die Existenz und Eindeutigkeit des IPs. Des weiteren können die gesuchten Koeffizienten mittels der weniger aufwändigen Vorwärtssubstitution berechnet werden.







Dies kann man nun schematisch darstellen. Dazu verwendet man das Schema der dividierten Differenzen.
tigerbine Auf diesen Beitrag antworten »
8a. Dividierte Differenzen - Definition
Die dividierten Differenzen sind wie folgt definiert:






Es ist dann zunächst der Nachweis zu führen, dass das daraus erhalte Polynom:




die LIPA erfüllt. Dies geschieht durch vollständige Induktion, wobei man die Behauptung sogar noch etwas allgemeiner fast:




interpoliert die Punkte


Beweis über k = (i+k)-i:







Denn wegen diesem Zusammenhang hat man ja die Newton-Darstallung eingeführt. Es bleibt also zu zeigen, dass gilt:



Dies geschieht Mittels des Polynoms (Nevillesches Polynom)



durch:
  • Nachweis, dass q die LIPA erfüllt
  • Eindeutigkeit des IPs
  • Koeffizientenvergleich von
tigerbine Auf diesen Beitrag antworten »
8b. Dividierte Differenzen - Berechnung
So gut wie in jedem Buch ist eine andere Nomenklatur zu diesem Thema zu finden. Ich habe mich für diese entschieden, weil die Index-Vergabe analog zu der Bezeichnung der Einträge einer Matrix ist (wenn wir dort die erste Zeile mit 0 bezeichnen würden Augenzwinkern )





Schema dividierte Differenzen für n=3










Um nun die benötigten Koeffizienten des IPs zu berechnen (erste Zeile) müssen wir die in (8) definierte Rekursionsformel anwenden. Aber auch hier gibt es eine Eselsbrücke.
tigerbine Auf diesen Beitrag antworten »
8c. Neville Schema
Hier wollen wir uns das in (8a) eingeführte Polynom q noch einmal etwas genauer ansehen. Wenn man den dortigen Beweis geführt hat, liefert dieser gerade, dass q eine weitere Darstellung des IP ist. Die bezeichnen wir als Neville-Darstellung.




Diese interpoliert wie gesagt die (k+1) Knoten und man kann das letztlich gesuchte IP der (n+1) Knoten rekursiv berechnen. Schreibt man diese Rekursion wieder tabellarisch auf, so erkennt man sofort die Ähnlichkeit zum Schema der dividierten Differenzen.

Neville- Schema für n=3











Verwendet man die Formel in einem Algorithmus, so stellt man die zunächst auf folgende Darstellung um. So sind weniger wesentliche Operationen nötig.

tigerbine Auf diesen Beitrag antworten »
9. Interpolationsfehler
Bezweckte man mit der Berechnung des IPs eine Funktion f zu approximieren, so ist natürlich von Interesse zu wissen, wie gut das durch die Polynominterpolation gelingt. Deswegen definiert man den Interpolationsfehler wie folgt:



Desweiteren ist es von Interesse zu wissen, ob die Approximation für größe n immer besser wird, ob also gilt:

tigerbine Auf diesen Beitrag antworten »
9a. Darstellung 2
Das können wir aber aus der Definition (9) nicht beantworten. Deswegen betrachtet man eine weitere Darstellung des Interpolationsfehlers, mittels dividierter Differenzen.



Beweis:

Sei für j=0,...,n. Dann hat das IP durch die Knoten die Newton-Form:



Setzt man nun , dann folgt:





Setzte . Fertig.
tigerbine Auf diesen Beitrag antworten »
9b. Darstellung 3
Was wir jetzt schon aus dieser Darstellung erkennen, ist dass sich der Interpolationsfehler aus 2 Faktoren zusammensetzt.

  • Knotenpolynom
  • dividierter Differenz


Letzteren wollen wir noch etwas genauer untersuchen. Dazu werden wir den Satz von Rolle benötigen.

Seien paarweise verschiedene Knoten in einem Intervall I=[a,b] und . Dann gibt es ein mit

Beweis:

interpoliere . Dann hat die Funktion (n+2) Nullstellen in I.

hat (n+1) Nullstellen



hat 1 Nullstelle und es ist





tigerbine Auf diesen Beitrag antworten »
9c. Abschätzungen
Mit (9a), (9b) erhält man erhält man:



Da nun aber nicht explizit bekannt ist und auch von x abhängt, schätz man weiter ab:



für alle
tigerbine Auf diesen Beitrag antworten »
10. Approximation
Aus der Darstellung des Interpolationsfehlers wissen wir, dass er von 2 Faktoren abhängt. Diese sollen im Folgenden einzeln betrachtet werden.


tigerbine Auf diesen Beitrag antworten »
10a. Tschebyscheffknoten
In diesem Abschnitt wollen wir den Fehleranteil verursacht durch das Knotenpolynom minimieren.

Aufgabe: min!

Lösung:

Wähle als Knoten die Nullstellen des Tschebyscheff-Polynoms (Mehr dazu im Workshop Orthogonale Polynome
):







Beweis:

Sei das Knotenpolynom mit obigen Tschebyscheff-Knoten. Sei nun eine bessere Knotenwahl, d.h. für das zugehörige Knotenpolynom gelte:



Mit dem Workshop orth. Polynom weiß man aus (1e), dass dieselben Nullstellen haben. Da sie sich nur um den konstanten Faktor unterscheiden, liegt auch das gleiche oszillierende Verhalten vor (siehe 1f)

  • Es ist , da beide Polynome den gleichen Höchstkoeffizienten (1 bei ) besitzen.

  • Wegen(*) sind die beiden Polynome aber verschieden und es gilt

  • Seien zwei aufeinanderfolgende Extremstellen von . Dann gilt wegen der Oszillation und derselben Ausschlaghöhe:



    und





  • und




    Also haben dann und verschiedene Vorzeichen.

    Somit liegt zwischen und nach dem ZWS für stetige Funktion eine Nullstelle von p.

    Somit hat p(n+1)-Nullstellen

    p ist das Nullpolynom, Widerspruch zu .


Veranschaulichung

  • äquidistante Knoten






  • Tschebyscheff-Knoten

    Nullstellen von :

    Nullstellen von :






tigerbine Auf diesen Beitrag antworten »
10b. Konvergenz
Hat man die Knoten nun optimal gewählt, hängt die Frage ob für von der zu approximierenden Funktion f ab.



Dabei gilt:

  • für
  • wird umso kleiner, je enger die Knoten zusammenliegen.


Somit ist der ausschlaggebende Faktor . Sind also die Ableitungen von f beschränkt auf [a,b] und f genügend oft differenzierbar, so gilt für . Dies ist jedoch i.A. - bei beliebiger Stützstellenwahl - nicht zu erwarten. Für vernünftige Verwendung wird man auch gleichmäßige Konvergenz fordern.

Beispiel von Runge
Satz von Faber + Konvergenzsatz mit Tschebyscheff
tigerbine Auf diesen Beitrag antworten »
10c. Approximationssatz von Weierstraß
Zu jeder stetigen Funktion f auf einem kompakten Intervall [a,b] gibt es eine Folge von Polynomen, die auf [a,b] gleichmäßig gegen f konvergieren.

Achtung:

Dieser Satz besagt nicht, dass man diese Folge durch die Lagrangeschen Interpolationspolynome erhält! Siehe auch Satz von Faber.
tigerbine Auf diesen Beitrag antworten »
10d. Fehleranfälligkeit und Extrapolation
Liegen fehlerhafte Daten vor, so verändert dies stark die Gestalt des IPs im gesamten Intervall. Konstruieren wir mal ein einfaches Beispiel.

Auf dem Intervall [-1,1] wollen wir die Nullfunktion approximieren. Dazu wählen wir die äquidistanten Stützstellen





Und vergeben folgende Funktionswerte:





Nun berechnen wir das IP in der Lagrange-Darstellung ():





Beispiel








__________________________________________________________






__________________________________________________________








Man erkennt auch deutlich, dass sich das IP mit steigender Knotenzahl ausserhalb von [-1,1] immer schneller von der Funktion f entfernt. Deswegen ist das IP i.A. auch nicht zur Extrapolation geeignet.

Lehrer
Achtung, denn trifft man diese Aussage generell, so tappt man leicht in eine Falle. Das IP so wie es hier bestimmt wurde hat ja das Ziel die Funktion f auf dem Intervall [a,b] möglichst gut zu approximieren. Daher ist es bei dieser Konstruktion auch nicht von Interesse, wie sich das IP außerhalb des Intervalls verhält. Dennoch wird man Interpolationspolynome auch zur Extrapolation verwenden, jedoch mit anders gestalteter Knotenwahl. Mehr dazu steht im [WS] Extrapolation
tigerbine Auf diesen Beitrag antworten »
11a. Integraldarstellung der Dividierten Differenzen
Zunächst noch eine Notation






Satz von Hermite-Genocchi

Sei und paarweise verschieden. Dann besitzen die dividierten Differenzen folgende Darstellung:






Beweis: vollst. Induktion

n=0:




Sei die Behauptung wahr für (n-1). Ferner verifiziere man:







Somit folgt für n:







tigerbine Auf diesen Beitrag antworten »
11b. Integraldarstellung des Interpolationsfehlers
Somt kann man den Interpolationsfehler auch wie folgt schreiben:



tigerbine Auf diesen Beitrag antworten »
11c. Mehrfachknoten
Durch die Integraldarstellung der dividierten Differenzen kann man sie stetig fortsetzen für den Fall, dass Knoten zusammenfallen:




Für den Fall folgt dann, da :







Für (k+1)-gleiche Knoten gilt analog:




Nochmal zum Fall (n+1) gleicher Knoten zurück. Es ergibt sich dann in der Newton-Darstellung:







also nichts anderes, als das n-te Taylorpolynom in
tigerbine Auf diesen Beitrag antworten »
12. Hermitsche-Interpolations-Aufgabe
Nun ist aus der Schulzeit noch bekannt, dass ein Polynom n-ten Grades nicht nur durch die Vorgabe von (n+1) Funktionswerten an paarweise verschiedenen Knoten eindeutig bestimmt ist. Oft kommen in dem "Steckbrief" auch Bedingungen für die Ableitungen vor.

Den Beweis, dass man im Falle von Mehrfachknoten auch durch diese Bedingungen, das interpolierende Polynom eindeutig bestimmt ist, soll mit der Hermitschen-Interpolationsaufgabe (HIPA) gezeigt werden.

HIPA

Gegeben sind m-paarweise verschiedene Knoten auf dem Gitter . An den sog. Mehrfachknoten, soll das interpolierende Polynom nicht nur den Wert der Funktion annehmen, sondern auch noch den Wert der Ableitung(en). Somit sieht der Datensatz wie folgt aus:







Gesucht ist nun ein Polynom p von möglichst niedrigem Grad, so dass die Bedingung:



erfüllt ist.
tigerbine Auf diesen Beitrag antworten »
12a. Eindeutigkeit
Sei . Seien zwei Lösungen der HIPA und . Dann hat das Polynom höchstens den Grad N und die Eigenschaft:



D.h. am Knoten hat q eine -fache Nullstelle. Insgesamt hat dann q, Nullstellen. Somit ist und .
tigerbine Auf diesen Beitrag antworten »
12b. Existenz (Neville-Hermite-Schema)
Bei der LIPA haben wir in(8c) das Neville-Schema zur Bestimmung der Newton-Darstellung des Interpolationspolynoms verwendet. Dabei wird im Beweis (den der Leser zu führen hat) gezeigt, dass gilt "q interpoliert . Dies hätte man auch als Existenzbeweis des IPs der LIPA nehmen können. (Beweis durch LGS ist einfacher)

Um auch hier ein Berechnungsschema zu erhalten, überträgt man nun (8c) auf die HIPA:

Neville-Hermitsche-Formel

Die im folgenden Algorithmus bestimmen liegen in und interpolieren die gegebenen Daten an den (k+1), nicht notwendiger Weise verschiedenen, Stellen . Bei Mehrfachknoten sind dann auch die Ableitungen heranzuziehen. Der Algorithmus lautet:





Beweis ist wieder durch vollst. Induktion zu führen.
tigerbine Auf diesen Beitrag antworten »
12c. Dividerte Differenzen (Neville-Hermite)







tigerbine Auf diesen Beitrag antworten »
12d. Hermite-Darstellung
Analog zur Newton-Darstellung:

tigerbine Auf diesen Beitrag antworten »
12e. Interpolationsfehler


tigerbine Auf diesen Beitrag antworten »
Ausblick
Abschließend erkennt man also dass ein Datensatz der Länge (n+1) zwar eindeutig ein IP vom Grad N festlegt, man aber nicht mit wachsendem n (also höherem Aufwand) bessere Resultate erzielen muss. Im [Workshop-Spline-Interpolation-Theorie] soll daher ein anderer Ansatz für eine interpolierende Funktion gezeigt werden.

Einen anderen Ansatz eine Funktion durch die Datenwolke zu legen, verfolgt die Methode der kleinsten Quadrate.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »