ws-numerik/TASK.md

N01 Aufgabe 10

Portfolio-Pruefung zur Vorlesung Numerik und Optimierung I Wintersemester 25/26 Prof. Dr. Anne Wald, Bjoern Ehlers, Imke Claußen

Abgabe: Bis Sonntag, 15.03.2026, bis 18:00 Uhr

Hinweise zur Bearbeitung

• Ihre Codes muessen ausfuehrbar sein. • Die Codes sollten ausfuehrlich kommentiert sein, sodass jemand, der den Code nicht selbst implementiert hat, diesen leicht verstehen kann. • Ein Portfolio sollte nicht mehr als 15.000 Zeichen beinhalten. Ihre Ausarbeitungen sollten also kompakt und zielfuehrend sein. • Ihre Loesungen muessen bis 15.03.2026, 18:00 Uhr, abgegeben werden. • Numpy oder Aehnliches ist erlaubt zum Generieren von Vektoren und Matrizen sowie zum direkten Rechnen mit diesen, das heißt, Multiplikation und Addition. Anderweitig sind keine bereits in Bibliotheken implementierte Funktionen erlaubt, um Algorithmen zu implementieren, es sei denn, dies ist explizit angegeben. • Zum Plotten und Praesentieren der Loesungen ist die Benutzung von Bibliotheken wie Matplotlib oder Aehnlichem natuerlich erlaubt. • Wenn Sie Software-Bibliotheken verwenden, schreiben Sie bitte die Version sowie Ihre verwendete Python-Version dazu, damit dies bei der Korrektur der Loesungen beruecksichtigt werden kann. • Bei Fragen kontaktieren Sie bitte Bjoern Ehlers oder Anne Wald.

Loesen linearer Gleichungssysteme

In Kapitel 7 im Skript haben wir die QR-Zerlegung behandelt, bei der eine Matrix A in das Produkt QR mit einer unitaeren Matrix Q und einer (verallgemeinerten) rechten oberen Dreiecksmatrix R zerlegt wird. Der Vorteil ist, dass die Konditionszahl durch diese Zerlegung, anders als beim Uebergang zur Normalengleichung, nicht erhoeht wird. Fuer die Berechnung der Matrix Q haben wir im Skript das Gram-Schmidt-Orthogonalisierungsverfahren verwendet. In der Praxis wird jedoch haeufig das Householder-Verfahren zur Berechnung einer Zerlegung A = QS verwendet, wobei auch hier die Matrix Q eine Orthogonalmatrix ist und S eine verallgemeinerte obere Dreiecksmatrix.

Aufgaben

1. Das Householder-Verfahren wird beispielsweise im Buch Numerische Mathematik kompakt von Robert Plato beschrieben (in der zweiten Auflage in Abschnitt 4.8.3). Erlaeutern Sie zunaechst knapp und ohne Beweise, wie das Householder-Verfahren funktioniert.

2. Berechnen Sie die QS-Zerlegung mithilfe von Householder-Transformationen fuer die Matrix A = (0, 1; 0, 0; 1, 1)

3. Implementieren Sie das Householderverfahren zur Berechnung der Zerlegung A = QS. Das Programm soll als Eingabe eine Matrix A ∈Rm×n mit m ≥n ≥1 erhalten und die Matrizen Q und S ausgeben.

4. Wie loesen Sie ein lineares Gleichungssystem mithilfe der Zerlegung A = QS? Ergaenzen Sie ihr Programm so, dass es lineare Gleichungssysteme Ax = b mit A ∈Rn×n mithilfe der Zerlegung A = QS loest. Als Eingabe soll das Programm also die Matrix A und den Vektor b erhalten und die Loesung x ausgeben.

5. Fuehren Sie Ihr Programm aus d) fuer A = (d, 0, ..., 0, 1; -1, d, ..., ..., 1; -1, ..., ..., 0, 1; ..., ..., ..., d, 1; -1, -1, ..., -1, 1) in RR^(n times n) und b = (1 + d, d, -1 + d, ..., 3 - n + d, 2 - n) in RR^n mit n = 20 und d = 0.1 aus. Geben sie den Loesungsvektor x aus.