Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


38. Kurvenanpassung



Interpolation mit Hilfe von Polynomen

Wir haben bereits ein Verfahren zur Lösung des Problems der Datenanpassung kennengelernt: Falls bekannt ist, daß f ein Polynom vom Grad N - 1 ist, so liegt das Problem der Polynom-Interpolation aus Kapitel 36 vor. Selbst wenn wir keine speziellen Informationen über f haben, könnten wir das Problem der Datenanpassung lösen, indem wir für f(x) das Interpolationspolynom vom Grad N - 1 für die gegebenen Punkte und Werte wählen. Dieses könnte unter Anwendung der in Kapitel 36 umrissenen Methoden berechnet werden. Es gibt allerdings viele Gründe, um für die Datenanpassung keine Interpolation mit Hilfe von Polynomen zu benutzen. Zum einen ist ein beträchtlicher Rechenaufwand erforderlich (es stehen weiterentwickelte Methoden mit einer zu N(log N)2 proportionalen Laufzeit zur Verfügung, doch elementare Verfahren sind quadratisch). Die Berechnung eines Polynoms (zum Beispiel) vom Grad 100 zur Interpolation einer durch 100 Punkte verlaufenden Kurve dürfte ein bei weitem übertriebener Aufwand sein.

Der hauptsächliche Nachteil der Polynom-Interpolation besteht jedoch darin, daß Polynome von einem hohen Grad relativ komplizierte Funktionen sind, die unerwartete Eigenschaften haben können, die nicht gut mit der anzupassenden Funktion in Einklang zu bringen sind. Ein Ergebnis aus der klassischen Mathematik (der Approximationssatz von Weierstraß) besagt, daß es möglich ist, jede beliebige sinnvolle Funktion mit Hilfe eines Polynoms (von genügend hohem Grad) zu approximieren. Leider weisen Polynome von sehr hohem Grad eine Tendenz zu wilden Schwankungen auf. Es erweist sich, daß selbst dann, wenn die meisten Funktionen auf einem abgeschlossenen Intervall durch ein Interpolationspolynom fast überall gut approximiert werden, immer bestimmte Stellen existieren, wo die Approximation sehr schlecht ist. Außerdem wird bei dieser Theorie von der Voraussetzung ausgegangen, daß es sich bei den vorliegenden Daten um exakte Werte einer gewissen unbekannten Funktion handelt. Oft jedoch liegt der Fall vor, daß die gegebenen Daten nur Näherungswerte sind. Falls die y-Werte Näherungswerte für ein gewisses unbekanntes Polynom von niedrigem Grad sind, so wäre es wünschenswert, daß die Koeffizienten der Glieder von hohem Grad in dem Interpolationspolynom den Wert null haben. Doch gewöhnlich ergibt sich etwas anderes; das Interpolationspolynom versucht stattdessen, die Glieder von hohem Grad zu benutzen, um eine exakte Anpassung zu erreichen. Diese Effekte sind die Ursache dafür, daß Interpolationspolynome für viele Anwendungen der Kurvenanpassung ungeeignet sind.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]