Numerik I für Maschinenbauer - SS 2019

Infos zur aktuellen Woche

Woche 11

In Woche 11 behandeln wir die Interpolation mit Polynomen.


Wir betrachten die Darstellungen des Interpolationspolynoms in den verschiedenen Basen und die Berechnung der Koeffizienten mit Hilfe der dividierten Differenzen, sowie das Neville-Aitken-Schema zur direkten Auswertung des Interpolationspolynoms an einem gegebenen Punkt. Für die Auswertung der Darstellung in der Newton-Basis verwenden wir das Horner-Schema.
Über eine weitere Diagonale zu (x,f(x)) im Newton-Schema erhalten wir mit der Interpolationseigenschaft und der Eigenschaft der dividierten Differenzen (Satz 8.21 (iv)) die Fehlerdarstellung
f(x)-P(f|x0,...,xn)(x) = (x-x0)...(x-xn)f(n+1)(ξ)/(n+1)!
Da wir ξ nicht explizit kennen, muss die (n+1). Ableitung betragsmäßig abgeschätzt werden.
Um möglichst gute Fehlerabschätzungen für gegebene Auswertungspunkte zu erhalten, versuchen wir die Knoten/Stützstellen gegebenenfalls möglichst so zu wählen, dass der Anteil des Knotenpolynoms in der Abschätzung/Darstellung minimiert wird.

Wir wollen die Eigenschaften der verschiedenen Darstellungen vergleichen:
Für die Lagrange-Basis sind die Koeffizienten unmittelbar gegeben, die Auswertung an einem Punkt erfordert aber O(n2) Operationen. Da die Auswertung in dieser Darstellung auch anfällig bezüglich Auslöschung ist, ist diese Basis vor allem für theoretische Zwecke interessant. Zudem können damit später die Gewichte der Quadraturformeln berechnet werden.
Die Auswertung in Monomenbasis (Potenzform) erfordert mit dem Horner-Schema nur jeweils n Additionen und Multiplikationen, allerdings muss zur Aufstellung zunächst ein Gleichungssystem mit (in der Regel sehr schlecht konditionierter) Vandermonde-Matrix gelöst werden, was ca. n3/3 Operationen erfordert. Zudem ist die Auswertung sehr oft schlecht konditioniert (insbesonder bezüglich der Koeffizienten, vgl. A2.17).
Praxisrelevant ist vor allem die Darstellung in Newton-Basis (ca. n2/2 Divisionen und n2 Additionen zur Berechnung der Koeffizienten, n Multiplikationen und 2n Additionen zur Auswertung - Horner).
Ein wichtiger Unterschied zwischen den Darstellungen ist zudem: Bei Hinzunahme eines weiteren Punktes muss bei Lagrange-Basis und Potenzform in der Regel alles neu berechnet werden, während in der sukzessiven Auswertung des Newton-Schemas nur eine Diagonale hinzukommt.
Der grundlegende Unterschied zur direkten Auswertung über Neville-Aitken (Aufwand ca. n2 Multiplikationen/Divisionen und 2n2 Subtraktionen/Additionen für einen gegebenen Auswertungspunkt) besteht darin, dass das Polynom nicht explizit aufgestellt werden muss. Das Verfahren ist in geeigneter Darstellung sehr stabil und lässt sich auch anderweitig verwenden. Effizient ist das Verfahren aber nur für eine oder sehr wenige Auswertungen! Zur Aufstellung des Polynoms ist es nicht geeignet.

Gerechnet werden Hausaufgaben (Vorbereitung für Minitests und Klausur) sind

NuMaMB Letzte Bearbeitung: 18. Juni 2019