Robert Sedgewick: Algorithmen

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


38. Kurvenanpassung



Der Begriff Kurvenanpassung (oder Datenanpassung) wird verwendet, um das allgemeine Problem der Bestimmung einer Funktion zu beschreiben, die in einer Menge von gegebenen Punkten eine Menge von gegebenen Werten annimmt. Das hießt, wenn die Punkte

x1, x2,..., xN

und die zugehörigen Werte

y1, y2,..., yN

gegeben sind, besteht das Ziel darin, eine Funktion (vielleicht von einem vorgegebenen Typ) zu finden, so daß

f(x1) = y1, f(x2) = y2,..., f(xN) = yN,

gilt

und daß f(x) in anderen Punkten »sinnvolle« Werte annimmt. Es könnte der Fall vorliegen, daß die x-Werte und y-Werte durch eine gewisse unbekannte Funktion miteinander verknüpft sind. Dann besteht unser Ziel darin, diese Funktion zu finden; im allgemeinen hängt die Definition dessen, was »sinnvoll« ist, jedoch von der Anwendung ab. Wir werden sehen, daß es oft einfach ist, »nicht sinnvolle« Funktionen zu identifizieren.

Die Kurvenanpassung besitzt offensichtliche Anwendungen bei der Analyse experimentell gewonnener Daten, kann aber auch für viele andere Zwecke verwendet werden. Zum Beispiel kann sie in der Computergrafik benutzt werden, um Kurven zu erzeugen, die »gut aussehen«, ohne daß zusätzlicher Aufwand für die Speicherung einer großen Zahl darzustellender Punkte erforderlich ist. Eine ähnliche Anwendung ist die Verwendung der Kurvenanpassung, um einen schnellen Algorithmus zur Berechnung des Wertes einer bekannten Funktion in einem beliebigen Punkt bereitzustellen: Es wird eine kurze Tabelle von exakten Werten gespeichert, und andere Werte werden mittels Kurvenanpassung bestimmt.

Um dieses Problem zu lösen, kommen zwei prinzipielle Methoden zur Anwendung. Die erste ist die Interpolation: Es ist eine glatte Funktion zu finden, die in den gegebenen Punkten exakt die gegebenen Werte annimmt. Das zweite Verfahren, Datenanpassung mit Hilfe der Methode der kleinsten Quadrate, wird benutzt, wenn die gegebenen Werte möglicherweise nicht exakt sind und eine Funktion gesucht wird, die so gut wie möglich mit ihnen übereinstimmt.


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