Polynominterpolation

Suche eines Polynoms anhand vorgegebener Punkte

In der numerischen Mathematik versteht man unter Polynominterpolation die Suche nach einem Polynom, welches exakt durch vorgegebene Punkte (z. B. aus einer Messreihe) verläuft. Dieses Polynom wird Interpolationspolynom genannt und man sagt, es interpoliere die gegebenen Punkte.

Interpolationspolynom 7. Grades

Anwendungen

Bearbeiten

Polynome lassen sich sehr leicht integrieren und ableiten. Deswegen tauchen interpolierende Polynome an vielen Stellen in der numerischen Mathematik auf, beispielsweise bei der numerischen Integration und entsprechend bei Verfahren zur numerischen Lösung gewöhnlicher Differentialgleichungen.

Problemstellung

Bearbeiten

Für   gegebene Wertepaare   mit paarweise verschiedenen Stützstellen   wird ein Polynom   maximal  -ten Grades gesucht, das alle Gleichungen

 

erfüllt. Ein solches Polynom existiert stets und ist eindeutig bestimmt, wie im Folgenden gezeigt wird.

Beim Interpolationsproblem ist also   im Vektorraum   der Polynome mit Grad   oder kleiner zu suchen, kurz  . Ist   eine Basis von  , so ergeben die Gleichungen   ein lineares Gleichungssystem für die Koeffizienten der Basisdarstellung  . Da sich ein und dasselbe Polynom aber unterschiedlich darstellen lässt, je nachdem welche Basis für den Vektorraum   gewählt wird, kann man ganz verschiedene Gleichungssysteme erhalten. Wählt man für   die Standardbasis  , also für   die Darstellung  , so erhält man ein Gleichungssystem mit der Vandermonde-Matrix:

 .

Diese ist regulär, wenn die Stützstellen   paarweise verschieden sind, das Gleichungssystem lässt sich dann eindeutig lösen. Somit ist die Existenz und Eindeutigkeit des gesuchten Polynoms   immer sichergestellt. Trotz der theoretischen einfachen Darstellung wird dieses Gleichungssystem in der Praxis nicht zur Berechnung des Interpolationspolynoms verwendet, da seine Lösung aufwendig ist und es zudem im Allgemeinen schlecht konditioniert ist.

Lösungsverfahren

Bearbeiten

Obiges Gleichungssystem ließe sich beispielsweise mit dem Gaußschen Eliminationsverfahren lösen. Der Aufwand dafür wäre mit   (siehe Landau-Symbole) allerdings vergleichsweise groß. Bei Wahl einer anderen Basis als der Standardbasis zur Beschreibung des Polynoms   kann der Aufwand verringert werden.

Lagrangesche Interpolationsformel

Bearbeiten
 
Beispielhafte lagrangesche Basisfunktionen für x0 = 0, x1 = 1, x2 = 2, x3 = 3 (n = 3)

Eher für theoretische Betrachtungen günstig ist eine Darstellung in der Lagrange-Basis. Die Basisfunktionen sind die Lagrange-Polynome

 

die so definiert sind, dass

 

gilt, wobei   das Kronecker-Delta darstellt. Damit entspricht die Matrix   genau der Einheitsmatrix. Die Lösung des Interpolationsproblems lässt sich dann einfach angeben als

 

mit den Stützwerten  . Dies wird häufig benutzt, um die Existenz der Lösung des Interpolationsproblems zu beweisen. Ein Vorteil der Lagrange-Basis ist somit, dass die Basisfunktionen   von den Stützwerten   unabhängig sind. Dadurch lassen sich verschiedene Sätze von Stützwerten   mit gleichen Stützstellen   schnell interpolieren, wenn die Basisfunktionen   einmal bestimmt worden sind. Ein Nachteil dieser Darstellung ist jedoch, dass alle Basisvektoren bei Hinzunahme einer einzelnen Stützstelle komplett neu berechnet werden müssen, weshalb dieses Verfahren für die meisten praktischen Zwecke zu aufwendig ist. In der digitalen Signalverarbeitung wird die Lagrange-Interpolation unter dem Namen „Farrow Filter“ für adaptives Resampling eingesetzt.

Baryzentrische Interpolationsformel

Bearbeiten

Die Lagrangesche Interpolationsformel kann umgeformt werden in die praktisch relevantere Baryzentrische Interpolationsformel

 

für  , wobei die Baryzentrischen Gewichte wie folgt definiert sind

 

Für vorgegebene Stützstellen   können die Gewichte   vorberechnet werden, sodass der Aufwand für die Auswertung von   nur noch bei   liegt. Beim Hinzufügen einer neuen Stützstelle müssen die Gewichte neu bestimmt werden. Dies hat einen Aufwand von   im Vergleich zum Neubestimmen der Lagrangepolynome von  .

Newtonscher Algorithmus

Bearbeiten

In diesem Verfahren wird das Polynom   in Newton-Basis dargestellt, so dass die Koeffizienten effizient mit dem Schema der dividierten Differenzen bestimmt werden können. Eine effiziente Auswertung des Polynoms kann dann mithilfe des Horner-Schemas erfolgen.

Ansatz: Newton-Basis

Bearbeiten

Als Ansatz für das gesuchte Interpolationspolynom   wählt man die Newton-Basisfunktionen   und   mit  , so dass   dargestellt wird mit der Newtonschen Interpolationsformel

 

Das Gleichungssystem der Gleichungen   hat dann die Form

 

Im Gegensatz zur Vandermonde-Matrix bei Wahl der Standardbasis   erhält man bei Wahl der Newton-Basis also eine einfach strukturierte untere Dreiecksmatrix, und das Gleichungssystem lässt sich einfach lösen.

Bestimmung der Koeffizienten: Schema der dividierten Differenzen

Bearbeiten

Die Koeffizienten   werden aber nicht direkt aus dem obigen Gleichungssystem bestimmt, sondern effizienter mithilfe der dividierten Differenzen. Durch Induktion beweist man mit der Rekursionsformel von Aitken, dass für die Koeffizienten   gilt

 .

Dabei sind für   die dividierten Differenzen   rekursiv definiert durch

 
 .

Die Notation mit angehängtem   erklärt sich dadurch, dass oft eine unbekannte Funktion   angenommen wird, die bei bekannten Funktionswerten   interpoliert werden soll.

Die rekursive Berechnung der dividierten Differenzen lässt sich wie folgt veranschaulichen. Dabei sind die gesuchten Koeffizienten   genau die oberste Schrägzeile:

 

Offensichtlich ist bei Ergänzung der   Wertepaare   um einen weiteren Punkt   in obigem Schema nur eine weitere Zeile hinzuzufügen, um den zusätzlichen Koeffizienten   zu berechnen. Die zuvor bestimmten Koeffizienten   müssen nicht neu berechnet werden.

Alternativ zur obigen rekursiven Definition wird zum Beispiel in einem der Artikel von Marsden[1] die dividierte Differenz   einer hinreichend oft differenzierbaren Funktion   als der eindeutige Koeffizient zur höchsten Potenz von   eines Polynoms  -ten Grads   definiert, das   an den Stellen   interpoliert. Tritt dabei ein Wert in der Sequenz   mit der Vielfachheit   auf, so sollen die Ableitungen des Polynoms die Ableitungen der Funktion   an dieser Stelle bis zur Ordnung   interpolieren. Es gilt somit

 

Eine weitere Möglichkeit, um die dividierten Differenzen unabhängig von der Vielfachheit der Stützstellen auszudrücken ist die Hermite-Genocchi-Formel, welche auf einer Integraldarstellung basiert.

Auswertung des Polynoms: Horner-Schema

Bearbeiten

Wenn die Koeffizienten   des Interpolationspolynoms   einmal bekannt sind, kann man es effizient mithilfe des Horner-Schemas auswerten. Dazu schreibt man   in der Form (einfache Umformung der Newtonschen Interpolationsformel)

 ,

so dass   rekursiv berechnet werden kann durch

 

Dies erfordert einen Aufwand von  .

Algorithmus von Neville-Aitken

Bearbeiten

Ähnlich wie im Newtonschen Algorithmus wird beim Algorithmus von Neville-Aitken die Lösung rekursiv berechnet. Dazu bezeichne   das eindeutig bestimmte Interpolationspolynom  -ten Grades zu den   Stützpunkten  , wobei   ist. Es gilt dann die Rekursionsformel von Aitken:

 

Beweisen lässt sie sich durch Einsetzen von  , wodurch man verifiziert, dass die rechte Seite der Gleichung die Interpolationsbedingung erfüllt. Die Eindeutigkeit des Interpolationspolynoms liefert dann die Behauptung.

Nach der Rekursionsformel von Aitken ergibt sich der eindeutige Koeffizient von   zur Potenz   als Differenz der Koeffizienten von   und   zu   dividiert durch  . Dies zeigt, dass die Diagonalelemente   im Schema der dividierten Differenzen genau die Koeffizienten   des Interpolationspolynoms   nach dem Ansatz von Newton liefern.

Mit dem Schema von Neville kann außerdem die Auswertung von   an einer Stelle   rekursiv erfolgen:

 

Vergleich der Lösungsverfahren

Bearbeiten

Möchte man alle Koeffizienten des Interpolationspolynoms   bestimmen, so bietet der Newtonsche Algorithmus hierfür den geringsten notwendigen Aufwand von  . Das so bestimmte Polynom lässt sich dann mit   Operationen an einer Stelle auswerten. Darum ist der Newtonsche Algorithmus gut geeignet, wenn das Interpolationspolynom an vielen Stellen ausgewertet werden soll. Auch lassen sich effizient weitere Stützpunkte hinzufügen. Liegen die Stützstellen oder die Stützwerte allerdings zu nahe beieinander, so besteht die Gefahr der Auslöschung bei der Bestimmung der dividierten Differenzen.

Der Neville-Aitken-Algorithmus ist dagegen gut geeignet, wenn ein Interpolationspolynom nur an ganz wenigen Stellen ausgewertet werden soll, dabei ist er weniger anfällig gegen Auslöschung. Auch im Neville-Aitken-Algorithmus lassen sich effizient neue Stützpunkte hinzufügen. So kann z. B. eine gewünschte Genauigkeit der Interpolation an einer Stelle durch Hinzufügen immer weiterer Stützstellen erreicht werden.

Beispiel: Interpolation der Tangensfunktion

Bearbeiten
 
Tangensfunktion (blau) und ihre Polynominterpolante dritten Grades (rot)

Interpoliere die Funktion   bei gegebenen Punkten

   
   
   
   
   

Lösung mit Lagrange

Bearbeiten

Die Lagrange-Basisfunktionen sind

 

also ist das Interpolationspolynom

 

Lösung mit Newton

Bearbeiten

Die dividierten Differenzen sind hier

 

und das Interpolationspolynom ist

 

Verwendet man genauere Startwerte  , verschwinden der erste und der dritte Koeffizient.

Interpolationsgüte

Bearbeiten

Fehlerabschätzung

Bearbeiten

Gegeben sei eine Funktion  , deren   Funktionswerte   an den Stellen   durch das Polynom   interpoliert werden. Mit   sei das kleinste Intervall bezeichnet, das die Stützstellen   und eine Stelle   enthält. Ferner sei   ( )-mal stetig differenzierbar auf  . Dann existiert ein  , für das gilt[2]:

 

Insbesondere ist also bezüglich der Maximumsnorm auf   und mit  :

 

Es gibt auch noch eine andere Fehlerformel, welche auf den oben eingeführten dividierten Differenzen beruht[2]:

 

Fehleroptimierung nach Tschebyschow

Bearbeiten
 
Für größere n clustern die Tschebyschow-Punkte an den Intervallrändern.

Der Fehler hängt also von einer Ableitung von   ab und von dem Produkt  , also den Stützstellen  . Manchmal ist man in der Position, dass man sich Stützstellen selbst wählen kann; etwa, wenn man ein physikalisches Experiment durchführt, oder aber auch bei einigen Verfahren zur numerischen Lösung von Differentialgleichungen. In diesem Fall ist die Frage interessant, für welche Stützstellen die Maximumsnorm   minimal wird.[3]

Für einen Beweis betrachtet man normalerweise normierte Stützstellen

 

Nun kann man die Maximumsnorm der Funktion   wie folgt abschätzen

 

Tschebyschow hat gezeigt, dass die Nullstellen der Tschebyschow-Polynome („Tschebyschow-Punkte“) optimale Stützstellen sind. Die Polynome   haben die Nullstellen   für  . So gewählte Stützstellen liefern eine scharfe Grenze der oberen Abschätzung

 

Diese Aussage kann dann mit der Transformation

 

auf den Fall eines allgemeinen Intervalls   übertragen werden. Der Beweis liefert auch die Abschätzung

 
 
Polynom-Interpolation 6 äquidistanter Stützstellen (rote Punkte), die auf der Rungefunktion liegen (blau)
 
Das gleiche mit 11 Stützstellen

Runges Phänomen

Bearbeiten

Verbessert sich die Interpolationsgüte, wenn mehr Stützpunkte hinzugefügt werden? Im Allgemeinen nicht: Bei äquidistanten Stützstellen und hohem Grad des Polynoms kann es vorkommen, dass die Polynomfunktion kaum noch der zu interpolierenden Funktion ähnelt, was auch als Runges Phänomen bekannt ist. Polynome streben im Grenzfall   gegen  . Verhält sich die zu interpolierende Funktion anders, etwa periodisch oder asymptotisch konstant, treten starke Oszillationen in der Nähe der Intervallgrenzen auf. Für solche Funktionen sind Polynominterpolationen über das gesamte Intervall relativ ungeeignet.

Tschebyschow-Stützstellen, die an den Intervallgrenzen dichter liegen, können zwar den Gesamtfehler der Interpolation verkleinern, dennoch empfiehlt sich ein Wechsel des Interpolationsverfahrens, etwa zur Spline-Interpolation. Runge gab für dieses Phänomen ein Beispiel an, die nach ihm benannte Runge-Funktion:

 

Konvergenzverhalten

Bearbeiten

Es gibt aber Bedingungen, unter denen sich die Interpolationsgüte mit steigender Anzahl von Stützpunkten verbessert: Wenn das Stützstellengitter immer „feiner“ wird und eine analytische Funktion interpoliert wird. Genauer: Sei   eine analytische Funktion auf dem Intervall  . Für eine Intervallteilung

 

sei ihre Norm definiert durch

 

Zu jeder Intervallteilung   gibt es ein eindeutig bestimmtes Polynom  , das   an den Stützstellen   interpoliert. Gilt für eine Folge von Intervallteilungen  , so folgt   gleichmäßig.

Allerdings lässt sich zu jeder Folge   auch eine auf   stetige Funktion   finden, so dass   nicht gleichmäßig gegen   konvergiert (Satz von Faber[4]).

Bestapproximation

Bearbeiten

Der Zusammenhang zwischen dem Interpolationpolynom und dem Polynom, welches die Funktion am besten bezüglich der Maximumsnorm   annähert, ist wie folgt gegeben:

Seien dazu folgende Objekte gegeben

  • eine stetige, zu nähernde Funktion:  
  • Stützstellen:  
  • Lebesgue-Konstante:  
  • Interpolationspolynom:   mit  
  • Bestapproximation:   mit  .

Dann gilt die Abschätzung

 

Verallgemeinerung

Bearbeiten

Bisher wurden die Stützstellen   des Interpolationspolynoms   als paarweise verschieden angenommen. Bei der Hermiteinterpolation ist das nicht der Fall. An mehrfach vorkommenden Stützstellen werden dabei nicht nur die Funktionswerte, sondern auch die Werte der Ableitungen des Interpolationspolynoms vorgegeben.

Lebesgue-Konstante

Bearbeiten

Sei der Operator, der einer Funktion   sein Interpolationspolynom   zuordnet, definiert durch

 

wobei   das  -te Lagrange-Polynom ist.

Als Lebesgue-Konstante   wird die Operatornorm von   bezeichnet. Dafür wird eine Norm benötigt, und oft wird hier auf die Maximumsnorm   zugegriffen:

 

Die Norm kann explizit berechnet werden:

 

Literatur

Bearbeiten
  • Hans R. Schwarz, Norbert Köckler: Numerische Mathematik. 5. Aufl. Teubner, Stuttgart 2004, ISBN 3-519-42960-8
  • Stoer, Bulirsch: Numerische Mathematik 1. 10. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2007, ISBN 978-3-540-45389-5, 2.1 Interpolation durch Polynome, S. 39–57 (Behandelt die Verfahren nach Lagrange, Neville-Aitken und Newton, Hermite-Interpolation und Fehlerabschätzung jeweils mit Beispielen und Beweisen.).
  • Press, Teukolsky, Vetterling, Flannery: Numerical Recipes. The Art of Scientific Computing. 3. Auflage. Cambridge University Press, Cambridge 2007, ISBN 978-0-521-88407-5, 3.2 Polynomial Interpolation and Extrapolation, S. 118–120 (Neville-Aitken-Algorithmus mit C++-Implementation).
  • Carl Runge: Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten. In: Zeitschrift für Mathematik und Physik. Band 46. B. G. Teubner, Leipzig 1901, S. 224–243 (hdl:1908/2014 – Runge-Phänomen).
  • Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065765-4.
Bearbeiten
Wikibooks: Dividierte Differenzen & Horner-Schema – Implementierungen in der Algorithmensammlung

Einzelnachweise

Bearbeiten
  1. Martin J. Marsden: An Identity for Spline Functions with Applications to Variation-Diminishing Spline Approximation. In: Journal of Approximation Theory, 3, 1970, S. 7–49.
  2. a b Rolf Rannacher: Numerik 0: Einführung in die Numerische Mathematik. Heidelberg University Publishing. Heidelberg University Publishing, Heidelberg 2017, ISBN 978-3-946054-27-6, 2.1 Polynominterpolation, S. 24–34, doi:10.17885/heiup.206.281.
  3. Jochen Werner: Numerische Mathematik. 1. Auflage. Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6, 10.4.4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch
  4. Andrei Nikolajewitsch Kolmogorow et al.: Mathematics of the 19th Century. 1. Auflage. Birkhäuser, 1998, ISBN 3-7643-5845-9, Kap. 4.books.google.de