Numerik I für Maschinenbauer - SS 2019

Infos zur aktuellen Woche

Woche 6

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-Reflektionen. Dann starten wir mit dem linearen Ausgleich. Wir betrachten auch die Kondition der Matrizen bei den einzelnen Lösungswegen:

Normalgleichungen: A^TA x=A^T b (Werden in der Praxis immer (Aufwand halb so groß wie bei Gauß / LR!) mittels L-D-L^T-Zerlegung gelöst.)
||A x-b||₂ → min (genauer: x^* = arg min_x∈Rⁿ||A x-b||₂) 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)²). Dafür ist der Rechenaufwand für m>n etwas größer. Bei den Normalgleichungen ist der größte Aufwand die Berechnung von A^TA (m n²/2). Das Lösen des LGS kostet nur n³/6. Householder: m n²-n³/3 (Givens ist doppelt so teuer.) Für m=n haben wir also für beide Lösungswege den Aufwand 2/3 n³. Hingegen ist für m>>n der Aufwand m n² gegenüber m n²/2.
Das eigentlich Wichtige ist die Zuordnung der Parameter (in x) und das Aufstellen von A und b - danach "Schema F". Es soll aber jede der drei Variante mindestens einmal bearbeitet werden. Es ist wie beim Sport: Um etwas gut zu können, muss man es genügend oft üben. Es gibt die Typen explizit y=f(x) 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 f_j(t) mit Messwerten (t_i,y_i) i=1...m .
	j=1

Daraus ergibt sich A mit a_ij=f_j(t_i) i=1...m, j=1..n, b mit b_i=y_i i=1...m, und x mit x_i=α_i i=1...n . Im Fall der Substitution wird b_i meistens zu b_i=y_i - g(t_i).
Man erhät aber in jedem Fall ein System der Form x^* = arg min_x∈Rⁿ||A x-b||₂ .
Einige Infos und Beispiele zur Vorgehensweise (gab es auch schon letzte Woche):

Infos zu Q-R : Givens, Housholder, Gleichungssysteme und Ausgleich.
Infos zu : Durchführung Housholder .
In der Vorlesung und in der Großübung wurden ja bereits Beispiele zum linearen Ausgleich vorgerechnet. Bei den Hausaufgaben gibt es noch einmal ein Beispiel Grundaufgabe linearer Ausgleich: Zu gegebenen A und b bestimme x^* = arg min_x∈Rⁿ||A x-b||₂ mit allen Verfahren. Hierzu liegt auch bereits jetzt eine Musterlösung auf. Dort kann und sollte man sich die Vorgehensweise schon einmal vorab anschauen.

Gerechnet werden die Aufgaben

die Verständnisfragen Vorlage
Aufgabe 3.26 (nur mit Householder)
Aufgabe 4.6
Aufgabe 4.9

Hausaufgaben (Vorbereitung für Minitests und Klausur) sind die Aufgaben

Die Verständnisfragen
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 x^* = arg min_x∈Rⁿ||A x-b||₂ ü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)

Letzte Bearbeitung: 9. Mai 2019