Herleitung der Ausgleichsrechnung
Wenn man den Ausgleichskreis anhand von n gegebenen Punkten direkt bestimmen wollte, wäre folgendermaßen
zu verfahren:
Die Summe S(x,y,r) = f1²(x,y,r) + f2²(x,y,r) + ... + fn²(x,y,r)
der Abstandsquadrate soll minimiert werden, also müssen die partiellen Ableitungen
δS/δx, δS/δy, δS/δr
jeweils den Wert 0 annehmen. Das ergibt ein nichtlineares Gleichungssystem in den Unbekannten x, y, r :
Abgesehen von einfachen (meist zu Übungszwecken konstruierten) Fällen kann man
solche Gleichungssysteme nicht unmittelbar lösen. Hier hilft aber ein fundamentales mathematisches Prinzip
weiter - die Linearisierung von Problemstellungen. Damit lassen sich Lösungen näherungsweise
ermitteln, deren exakte Berechnung nicht oder nur mit großer Mühe möglich ist.
Wir wollen jetzt begründen, warum die Berechnung von Ausgleichskreisen funktioniert - diese Herleitung lässt sich übrigens leicht verallgemeinern. Zur Vermeidung langer Terme definieren wir f:= (f1,...,fn)T, daraus folgt: f1²(x,y,r) + ... + fn²(x,y,r) = ||f(x,y,r)||², wobei ||f(x,y,r)||² genau dann minimal ist, wenn ||f(x,y,r)|| minimal ist. A sei die Funktionalmatrix von f bezüglich der Startwerte x0, y0, r0 - der Taylorsche Satz liefert:
f1·δf1/δx | + f1·δf1/δx | + f2·δf2/δx | + ... + fn·δfn/δx | = 0 |
f1·δf1/δy | + f1·δf1/δy | + f2·δf2/δy | + ... + fn·δfn/δy | = 0 |
f1·δf1/δr | + f1·δf1/δr | + f2·δf2/δr | + ... + fn·δfn/δr | = 0 |
Wir wollen jetzt begründen, warum die Berechnung von Ausgleichskreisen funktioniert - diese Herleitung lässt sich übrigens leicht verallgemeinern. Zur Vermeidung langer Terme definieren wir f:= (f1,...,fn)T, daraus folgt: f1²(x,y,r) + ... + fn²(x,y,r) = ||f(x,y,r)||², wobei ||f(x,y,r)||² genau dann minimal ist, wenn ||f(x,y,r)|| minimal ist. A sei die Funktionalmatrix von f bezüglich der Startwerte x0, y0, r0 - der Taylorsche Satz liefert:
f(x,y,r) = f(x0,y0,r0) + A·(x-x0,y-y0,r-r0)T + „Rest”
und es gibt x, y, r mit: ||f(x0,y0,r0) + A·(x-x0,y-y0,r-r0)T|| ≤ ||f(x0,y0,r0)||. Es ist eine vernünftige Strategie, nach einer Optimallösung (x1,y1,r1) von min(x,y,r)||f(x0,y0,r0)A + A·(x-x0,y-y0,r-r0)T|| zu suchen, weil in der Regel gilt:||f(x1,y1,r1)|| < ||f(x0,y0,r0)||.
Sei u:= x-x0, v:= y-y0, w:= r-r0 und b:= f(x0,y0,r0); damit haben wir das lineare Ausgleichsproblem(*) min(u,v,w) ||A·(u,v,w)T + b||
zu lösen. Es reicht, die Minimalstelle von g(u,v,w):= ||A·(u,v,w)T + b||² = (u,v,w)·AT·A·(u,v,w)T + 2·bT·A·(u,v,w)T + bT·b zu bestimmen. Aus den notwendigen Bedingungen δg/δu = δg/δv = δg/δw = 0 ergeben sich direkt die Normalgleichungen:AT·A·(u,v,w)T + AT·b = 0.
Wir setzen voraus, dass die Spalten von A linear unabhängig sind, folglich ist die symmetrische Matrix AT·A positiv definit und daher invertierbar. Wir erhalten:(u,v,w)T = -(AT·A)-1·AT·b.
Die Lösung (u,v,w) - exakt müsste man (u0,v0,w0) schreiben - ist somit eindeutig bestimmt und bildet auch wirklich die Minimalstelle von g, weil die positiv definite Matrix 2·AT·A die zugehörige Hesse-Matrix ist. Folglich ist unser lineares Ausgleichsproblem (*) gelöst und mit den Näherungswerten x1:= x0 + u, y1:= y0 + v, r1:= r0 + w kann die nächste Schleife starten.