Robert Sedgewick: Algorithmen

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


38. Kurvenanpassung



Methode der kleinsten Quadrate

Häufig liegt der Fall vor, daß unsere Daten zwar nicht exakt sind, wir jedoch eine Vorstellung von der Form der Funktion haben, die an die Daten angepaßt werden muß. Die Funktion könnte von einigen Parametern abhängen:

f(x) = f(c1, c2, ..., cM, x),

Die Prozedur der Kurvenanpassung hat dann die Aufgabe, diejenigen Parameter zu finden, für die in den gegebenen Punkten die Übereinstimmung mit den beobachteten Werten »am besten« ist. Falls die Funktion ein Polynom wäre (mit den Koeffizienten als Parameter) und die Werte exakt wären, wäre dies eine Interpolation. Doch nunmehr betrachten wir allgemeinere Funktionen und ungenaue Daten. Um die Diskussion zu vereinfachen, konzentrieren wir uns auf die Anpassung an Funktionen, die als Linearkombinationen einfacherer Funktionen dargestellt sind, wobei die Koeffizienten die unbekannten Parameter sind:

f(x) = c1f1(x) + c2f2(x) + ... + cMfM(x).

Hierzu gehören die meisten Funktionen, die für uns von Interesse sind. Nach der Untersuchung dieses Falls werden wir allgemeinere Funktionen betrachten.

Ein gebräuchliches Verfahren, mit dem gemessen wird, wie gut eine Funktion angepaßt ist, ist das Kriterium der kleinsten Quadrate. Hierbei wird der Fehler berechnet, indem die Quadrate der Fehler in den einzelnen Beobachtungspunkten addiert werden:

E =
Summe
1<=j<=N
(f(xj)-yi)2.

Dies ist ein sehr natürliches Maß; die Quadrierung wird ausgeführt, um zu verhindern, daß Fehler mit unterschiedlichen Vorzeichen sich gegenseitig ausgleichen. Offensichtlich ist es wünschenswert, die Wahl der Parameter so zu treffen, daß E minimiert wird. Es zeigt sich, daß diese Wahl der Parameter effizient berechnet werden kann; dies ist die sogenannte Methode der kleinsten Quadrate.

Das Verfahren ergibt sich praktisch unmittelbar aus der Definition. Um die Herleitung zu vereinfachen, betrachten wir den Fall M = 2, N = 3, doch die allgemeine Methode läßt sich ebenso herleiten. Angenommen, es seien drei Punkte x1, x2, x3 und entsprechende Werte y1, y2, y3 gegeben, an die eine Funktion der Form f(x) = c1f1(x) + c2f2(x) angepaßt werden soll. Unsere Aufgabe besteht darin, diejenigen Koeffizienten c1, c2 zu finden, für die der kleinste quadratische Fehler

E =(c1f1(x1) + c2f2(x1) - y1)2
+ (c1f1(x2) + c2f2(x2) - y2)2
+ (c1f1(x3) + c2f2(x3) - y3)2

realisiert wird. Um die Werte von c1 und c2 zu bestimmen, für die dieser Fehler minimal wird, brauchen wir nur die Ableitungen dE/dc1 und dE/dc2 gleich null zu setzen. Für c1 erhalten wir:

dE/dc1 = 2(c1f1(x1) + c2f2(x1) - y1)f1(x1)
+ 2(c1f1(x2) + c2f2(x2) - y2)f1(x2)
+ 2(c1f1(x3) + c2f2(x3) - y3)f1(x3).

Indem wir die Ableitung gleich null setzen, erhalten wir eine Gleichung, der die Variablen c1 und c2 genügen müssen (f1(x1) usw. sind »Konstanten« mit bekannten Werten):

c1(f1(x1)f1(x1) + f1(x2)f1(x2) + f1(x3)f1(x3))
+ c2(f2(x2)f1(x2) + f2(x3)f1(x3))
= y1f1(x1) + y2f1(x2) + y3f1(x3).

Wir erhalten eine ähnliche Gleichung, wenn wir die Ableitung dE/dc2 gleich null setzen. Diese recht kompliziert aussehenden Gleichungen können beträchtlich vereinfacht werden, wenn man die Vektorschreibweise und die Operation des Skalarprodukts benutzt. Wenn wir die Vektoren x = (x1,x2,x3) und y = (y1,y2,y3) einführen, so ist das Skalarprodukt von x und y die reelle Zahl, die durch

x · y = x1y1 + x2y2 + x3y3

definiert ist. Wenn wir nun die Vektoren f1 = (f1(x1), f1(x2), f1(x3)) und f2 = (f2(x1), f2(x2), f2(x3)) einführen, können unsere Gleichungen für die Koeffizienten c1 und c2 sehr einfach ausgedrückt werden:

c1f1 · f1 + c2f1 · f2 = y · f1,
c1f2 · f1 + c2f2 · f2 = y · f2.

Diese Gleichungen können mit Hilfe des Gaußschen Eliminationsverfahrens gelöst werden, wodurch man die gesuchten Koeffizienten erhält.

Nehmen wir zum Beispiel an, daß wir wissen, daß an die gegebenen Punkte

(1,0; 2,05) (2,0; 1,53) (4,0; 1,26) (5,0; 1,21) (8,0; 1,13) (10,0; 1,1)

eine Funktion der Form c1 + c2/x angepaßt werden soll. (Diese Punkte sind gegenüber den exakten Werten für 1 + 1/x leicht gestört.) In diesem Falle ist f1 eine Konstante (f1 = (1,0; 1,0; 1,0; 1,0; 1,0; 1,0)), und es ist f2 = (1,0; 0,5; 0,25; 0,2; 0,125; 0,1), so daß wir das Gleichungssystem

Formel

zu lösen haben; die Lösung lautet c1 = 0,998 und c2 = 1,054 (was beides, wie erwartet, nahe bei eins liegt).

Das oben skizzierte Verfahren läßt sich leicht auf die Bestimmung von mehr als zwei Koeffizienten verallgemeinern. Um die Konstanten c1, c2, ..., cM in

f(x) = c1f1(x) + c2f2(x) + ... + cMfM(x)

zu ermitteln, für die der kleinste quadratische Fehler für die Vektoren der Punkte bzw. Beobachtungen

x = (x1,x2,...,xN),
y = (y1,y2,...,yN)

realisiert wird, berechne man zuerst die mit den Funktionswerten als Komponenten gebildeten Vektoren

f1 = (f1(x1),f1(x2),...,f1(xN)),
f2 = (f2(x1),f2(x2),...,f2(xN)),
:
fM = (fM(x1),fM(x2),...,fM(xN)).

Dann erzeuge man ein lineares Gleichungssystem A c = b von der Dimension M mal M mit

aij = fi · fj,
b = fj · y.

Die Lösung dieses Gleichungssystems liefert die gesuchten Koeffizienten.

Dieses Verfahren kann leicht implementiert werden, indem man für die Vektoren f ein zweidimensionales Feld vorsieht und dabei y als den (M+1)-ten Vektor betrachtet. Dann kann ein Feld a[1..M,1..M+1] wie folgt gefüllt werden:

    for i:=1 to M do
      for j:=1 to M+1 do
        begin
        t:= 0.0;
        for k:=1 to N do t:=t+f[i,k]*f[j,k];
        a[i,j]:=t;
        end;

Die Lösung kann unter Benutzung der Gaußschen Elimination aus Kapitel 37 erfolgen.

Die Methode der kleinsten Quadrate kann zur Behandlung nichtlinearer Funktionen (zum Beispiel einer Funktion von der Art f(x) = c1e-c2x sin c3x) verallgemeinert werden, und sie wird für diesen Typ von Anwendungen oft benutzt. Die Idee ist im Prinzip die gleiche; das Problem dabei ist, daß sich die Ableitungen möglicherweise nicht mehr leicht berechnen lassen. In einem solchen Fall kann ein Iterationsverfahren zur Anwendung kommen: Verwende eine Schätzung für die Koeffizienten, benutze diese dann bei der Methode der kleinsten Quadrate zur Berechnung der Ableitungen, wodurch eine bessere Schätzung für die Koeffizienten gewonnen wird. Dieses grundlegende Verfahren, welches heutzutage vielfach angewandt wird, wurde um 1820 von Gauss beschrieben.


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