Herr Reusken hat in der Vorlesung Folgendes behandelt: QR-Zerlegung und
Lösung von linearen Gleichungsystemen über
Houshoulder-Transformation und Ausgleichsprobleme: Problemstellung sowie
Lösung über Normalgleichungen, Householder. und
Givens-Transformationen.
In der 6. Woche behandeln wir zunächst noch einmal
Householder-Reflexionen (für lin. Gleichungssysteme). Dann starten wir
mit dem linearen Ausgleich. Wir betrachten auch die Kondition der Matrizen
bei den einzelnen Lösungswegen:
Normalgleichungen: ATA*x=ATb
(Werden in der Praxis immer (Aufwand halb so groß wie bei Gauß / LR!)
mittels L-D-LT-Zerlegung gelöst.)
||A*x-b||2 → min mittels orthogonaler Transformationen
(Givens und Householder)
Das sind also zwei Lösungswege, wobei wir im 2. Fall noch zwei Verfahren haben.
Die orthogonalen Transformationen sind i.a. wesentlich besser konditioniert
(κ(A)) als die Normalgleichungen (κ(A)2).
Dafür ist der Rechenaufwand für m>n etwas größer.
Bei den Normalgleichungen ist der größte Aufwand die Berechnung von ATA (m*n2/2).
Das Lösen des LGS kostet nur n3/6. Householder: m*n2-n3/3 (Givens ist doppelt so teuer.)
Für m=n haben wir also für beide Lösungswege den Aufwand 2/3*n3. Hingegen ist für m>>n der
Aufwand m*n2 gegenüber m*n2/2.
Das eigentlich Wichtige ist die Zuordnung der Parameter (in x) und das Aufstellen von A und b - danach kommt "Schema F".
Es gibt die Typen explizit y=f(t) und implizit F(X)=0. (implizit nächste Woche)
Ferner muss/kann man mitunter substituieren (A4.9).
Bei explizitem Ansatz haben wir
n
y(t) =
∑
αj fj(t)
mit Messwerten (ti,yi) i=1...m .
j=1
Daraus ergibt sich A mit aij=fj(ti) i=1...m, j=1..n,
b mit bi=yi i=1...m, und x mit xi=αi i=1...n .
Im Fall der Substitution wird bi meistens zu bi=yi - g(ti).
Man erhät aber in jedem Fall ein System der Form ||A*x-b||2 → min .
Einige Infos und Beispiele zur Vorgehensweise (gab es auch schon letzte Woche):
Infos zu Q-R : Givens, Housholder, Gleichungssysteme und Ausgleich.
Aufgabe 3.26 - für x=(3,2,3)T.
(mit Givens und Householder)
Grundaufgabe linearer Ausgleich
Zu unten stehenden A und b löse das lineare Ausgleichsproblem ||A*x-b||2 → min
über Givens-Rotationen und Householder-Reflexionen sowie die Normalgleichungen. Lösung
╭
╮
╭
╮
│
3
7
│
│
10
│
A =
│
0
-12
│
und b =
│
-11
│
│
4
1
│
│
5
│
╰
╯
╰
╯
Aufgabe 4.7 (über Givens und Householder sowie die Normalgleichungen)
Aufgabe 4.8 (über Givens und Householder sowie die Normalgleichungen)