Lineare Ausgleichsrechnung:QR und Normalgleichungen
 
  • In der linearen Ausgleichsrechnung wird die euklidische Länge des Residuenvektors
    r = Ax - b
    zu gegebener Matrix A und rechter Seite b bezüglich x minimiert. Häufig entsteht diese Aufgabe so: es ist eine Ansatzfunktion F(x;p)=p0phi0(x)+...+pnphin(x) gesucht, die einen gegebenen Datensatz von N "Meßpunkten" (xi,yi) im Sinne der Methode der kleinsten Fehlerquadrate möglichst gut approximiert. Die phii sind dabei fest vorgegeben. Es wird also Summe(F(xi;p)-yi)2 bezüglich p minimiert. Setzt man die Elemente einer N*(n+1) Matrix Ai,j gleich phij(xi), dann lautet die Lösung mit Hilfe der sogenannten Normalgleichungen (das Gleichungssystem, das man erhält, wenn man den Gradienten der Summe gleich null setzt)
    A'Ap = A'y
    Dabei ist .' die Transposition und y der Vektor der Werte yi. Mit der QR-Methode wird A zerlegt in das Produkt einer orthonormalen Matrix Q' und einer oberen Dreiecksmatrix R mit N-n-1 angehängten Nullzeilen und man erhält p direkt aus einem System der Form Rp=(Qy)1,...,n .
  • Dabei müssen mindestens so viele "Meßpunkte" wie Koeffizienten vorliegen (N >= n+1), sonst kann die Lösung nicht eindeutig sein.
  • Bestimmt werden die Koeffizienten p0,...,pn der Ansatzfunktion F, die linear von diesen Koeffizienten abhängt.
  • Die beiden gängigsten Verfahren der linearen Ausgleichsrechnung sind die Lösung der Normalgleichungen und das QR-Verfahren.
  • Das QR-Verfahren nach Householder ist numerisch stabiler als das Aufstellen und Lösen des Gauß'schen Normalgleichungssystems.
  • Hier haben Sie die Möglichkeit entweder Matrix und rechte Seite vorzugeben oder aber aus einer Liste von vorgegebenen Ansatzfunktionen sich ein Problem konstruieren zu lassen.
  • Wenn Sie mit eigenen Ansatzfunktionen arbeiten wollen, können Sie das Gauss-Newton-Verfahren (-> nichtlineare Gleichungen) benutzen, das im linearen Fall nur einen Schritt benötigt und in der hiesigen Variante die Householderzerlegung benutzt.
 

Die Eingaben
    Version eigene Matrix und rechte Seite:
 
  • Zeilen- und Spaltenzahl der Matrix
  • Matrix und rechte Seite gemeinsam, zeilenweise
    Version Problemgenerierung:
 
  • Um sinnvolle Ausgleichsprobleme künstlich zu erzeugen, wird hier zunächst eine Ansatzfunktion mit exakten Koeffizienten p vorgegeben.
  • Aus dieser Funktion wird in einem Intervall [a,b] eine Menge von N "Meßpunkten" durch Störung mit einem anzugebenden Fehlerlevel errlev erzeugt. Mit diesen künstlichen "Meßpunkten" werden dann neue Koeffizienten zu den Ansatzfunktionen bestimmt.
  • Die "Meßpunkte" werden im Intevall [a,b] äquidistant erzeugt mit y = F(x;p0,...)+2·(½-r)·errlev·y_max_abs. Dabei ist r = r(x) eine Zufallszahl aus (0,1) und y_max_abs ist der betragsmäßig größte errechnete Funktionswert von F .
  • Zur Auswahl stehen vier verschiedene Ansatzfunktionen mit 5 bzw. 6 Koeffizienten.
    1. Polynomansatz mit Standardmonomen 1, x, x2, ..., x5 als Ansatzfunktionen. Wahlweise kann hier das anzugebende Intervall linear auf [-1:1] tranformiert werden.
    2. Polynomansatz mit den Legendrepolynomen L0(x),...,L5(x) als Ansatzfunktionen. Diese Polynome lauten
      L0(x) = 1, L1(x) = x, L2(x) = ½(3x2-1),...
    3. Trigonometrischer Ansatz mit den Ansatzfunktionen 1, sin(pi·x), cos(pi·x), sin(2·pi·x), cos(2·pi·x).
    4. Exponentialansatz mit den Ansatzfunktionen 1,e-x,e-1.1 x, e-4 x,e-10 x.
  • Die exakten Koeffizienten zu dem gewählten Ansatz. Eine Trennung der Zahlen kann durch Leerzeichen bzw. Kommata erfolgen. Erlaubt sind die Zahldarstellungen der Programmiersprache FORTRAN.
  • Das Intervall [a,b], in dem die "Meßpunkte" bestimmt werden sollen.
  • Die Anzahl der zu bestimmenden "Meßpunkte" (N <= 1000).
  • Maximaler Fehlerlevel (0 <= errlev <= 1), mit dem eine Punktauswertung der Ansatzfunktion gestört werden soll, um einen "Meßpunkt" zu erhalten.
 

Die Ausgaben
 
  • Wurde eine eigene Matrix mit rechter Seite eingegeben, dann nur der Lösungsvektor x und die Norm des Residuums.
  • Andernfalls:
  • Die vorgegebenen Koeffizienten p0,...,pn.
  • Die mit dem QR-Verfahren errechneten Koeffizienten.
  • Die mit den Normalgleichungen bestimmten Koeffizienten.
  • Eine Graphik, die die "Meßpunkte" und die Ansatzfunktion mit den Koeffizienten aus der QR-Zerlegung wiedergibt.
 

Fragen ?!
 
  • Was bedeuten große Abweichungen zu den Ausgangskoeffizienten für die Sensitivität der linearen Ausgleichsrechnung ?
  • Wann gibt es Unterschiede zwischen den Resultaten mit dem QR-Verfahren und den Normalgleichungen und warum?
  • Welche Rolle spielt die Transformation auf [-1,1] im Falle des Polynomansatzes ?
  • Wie unterscheiden sich die Polynomansätze mit den Standardmonomen und den Legendrepolynomen ?
  • Welche Rolle spielt die Lage des Intervalles [a,b] und warum ?
 

Das Eingabeformular
 
 

Zurück: Lineare Gleichungssysteme
 Back to the top!

07.01.2009