Algorithms of Numerical Linear Algebra - Exam

Aufgabe 1)

Betrachte die Matrix \[ A \] und ihre LU-Faktorisierung. Die LU-Faktorisierung einer Matrix \[ A \] stellt \[ A \] als Produkt zweier Matrizen dar: einer unteren Dreiecksmatrix \[ L \] und einer oberen Dreiecksmatrix \[ U \]. Sei \[ A \] eine \( n \times n \) Matrix, dann gilt:

• Eine Matrix \[ A \] kann als \[ A = LU \] dargestellt werden, wobei \[ L \] eine untere Dreiecksmatrix und \[ U \] eine obere Dreiecksmatrix ist.
• Die Matrix \[ L \] hat die Form: \[ L = \begin{pmatrix} l_{11} & 0 & 0 & \cdots & 0 \ l_{21} & l_{22} & 0 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn} \end{pmatrix} \]
• Die Matrix \[ U \] hat die Form: \[ U = \begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n} \ 0 & u_{22} & u_{23} & \cdots & u_{2n} \ 0 & 0 & u_{33} & \cdots & u_{3n} \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \cdots & u_{nn} \end{pmatrix} \]
• Diese Faktorisierung wird häufig verwendet, um lineare Gleichungssysteme zu lösen, die Determinante einer Matrix zu berechnen oder eine Matrix zu invertieren.
• Bei der LU-Faktorisierung muss manchmal eine Pivotisierung durchgeführt werden, um die numerische Stabilität sicherzustellen. In diesem Fall ist \[ PA = LU \], wobei \[ P \] eine Permutationsmatrix ist, die die Zeilen von \[ A \] permutiert.

a)

(a) Gegeben die Matrix \[ A = \begin{pmatrix} 2 & 3 & 1 \ 4 & 7 & 2 \ 6 & 18 & 5 \end{pmatrix}\], führe die LU-Faktorisierung der Matrix ohne Pivoting durch. Bestimme die Matrizen \[ L \] und \[ U \].

Lösung:

Um die LU-Faktorisierung der gegebenen Matrix \[ A = \begin{pmatrix} 2 & 3 & 1 \ 4 & 7 & 2 \ 6 & 18 & 5 \end{pmatrix} \] ohne Pivoting durchzuführen, folgen wir diesen Schritten:

1. Bestimme die obere Dreiecksmatrix (\[ U \]) und die untere Dreiecksmatrix (\[ L \]).
2. Die Matrix \[ L \] enthält auf ihrer Diagonale Einsen und hat die Form: \[ L = \begin{pmatrix} 1 & 0 & 0 \ l_{21} & 1 & 0 \ l_{31} & l_{32} & 1 \end{pmatrix} \]
3. Die obere Dreiecksmatrix \[ U \] hat die Form: \[ U = \begin{pmatrix} u_{11} & u_{12} & u_{13} \ 0 & u_{22} & u_{23} \ 0 & 0 & u_{33} \end{pmatrix} \]

Nun beginnen wir mit den Berechnungen:

Schritt 1: Berechne die erste Zeile und Spalte

• \[ u_{11} = A_{11} = 2 \]
• \[ u_{12} = A_{12} = 3 \]
• \[ u_{13} = A_{13} = 1 \]
• \[ l_{21} = \frac{A_{21}}{u_{11}} = \frac{4}{2} = 2 \]
• \[ l_{31} = \frac{A_{31}}{u_{11}} = \frac{6}{2} = 3 \]

Jetzt haben wir:

\[ L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 0 & 1 \end{pmatrix} \] \[ U = \begin{pmatrix} 2 & 3 & 1 \ 0 & u_{22} & u_{23} \ 0 & 0 & u_{33} \end{pmatrix} \]

Schritt 2: Berechne die zweite Zeile und Spalte

• \[ u_{22} = A_{22} - l_{21} \cdot u_{12} = 7 - 2 \cdot 3 = 1 \]
• \[ u_{23} = A_{23} - l_{21} \cdot u_{13} = 2 - 2 \cdot 1 = 0 \]
• \[ l_{32} = \frac{A_{32} - l_{31} \cdot u_{12}}{u_{22}} = \frac{18 - 3 \cdot 3}{1} = 9 \]

Jetzt haben wir:

\[ L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 9 & 1 \end{pmatrix} \] \[ U = \begin{pmatrix} 2 & 3 & 1 \ 0 & 1 & 0 \ 0 & 0 & u_{33} \end{pmatrix} \]

Schritt 3: Berechne den letzten Eintrag

• \[ u_{33} = A_{33} - l_{31} \cdot u_{13} - l_{32} \cdot u_{23} = 5 - 3 \cdot 1 - 9 \cdot 0 = 2 \]

Die endgültigen Matrizen sind:

\[ L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 9 & 1 \end{pmatrix} \] \[ U = \begin{pmatrix} 2 & 3 & 1 \ 0 & 1 & 0 \ 0 & 0 & 2 \end{pmatrix} \]

b)

(b) Verwende die Matrizen \[ L \] und \[ U \] aus Teil (a), um das lineare Gleichungssystem \[ A\mathbf{x} = \mathbf{b} \] mit \[ \mathbf{b} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \] zu lösen. Zeige detailliert die Schritte der Vorwärts- und Rückwärtssubstitution.

Lösung:

Um das lineare Gleichungssystem \( A\mathbf{x} = \mathbf{b} \) mit \( A = LU \) und \( \mathbf{b} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \) zu lösen, müssen wir zwei Schritte durchführen: Vorwärtssubstitution und Rückwärtssubstitution.

Gegeben:

• \( L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 9 & 1 \end{pmatrix} \)
• \( U = \begin{pmatrix} 2 & 3 & 1 \ 0 & 1 & 0 \ 0 & 0 & 2 \end{pmatrix} \)
• \( \mathbf{b} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \)

Schritt 1: Vorwärtssubstitution

Wir lösen \( L\mathbf{y} = \mathbf{b} \) nach \( \mathbf{y} \) auf:

• \( L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 9 & 1 \end{pmatrix} \)
• \( \mathbf{y} = \begin{pmatrix} y_1 \ y_2 \ y_3 \end{pmatrix} \)

Das ergibt das Gleichungssystem:

• 1. Gleichung: \( 1\cdot y_1 = 1 \Rightarrow y_1 = 1 \)
• 2. Gleichung: \( 2\cdot y_1 + 1\cdot y_2 = 2 \Rightarrow 2\cdot1 + y_2 = 2 \Rightarrow y_2 = 0 \)
• 3. Gleichung: \( 3\cdot y_1 + 9\cdot y_2 + 1\cdot y_3 = 3 \Rightarrow 3\cdot1 + 9\cdot0 + y_3 = 3 \Rightarrow y_3 = 0 \)

Wir erhalten also:

\( \mathbf{y} = \begin{pmatrix} 1 \ 0 \ 0 \end{pmatrix} \)

Schritt 2: Rückwärtssubstitution

Wir lösen \( U\mathbf{x} = \mathbf{y} \) nach \( \mathbf{x} \) auf:

• \( U = \begin{pmatrix} 2 & 3 & 1 \ 0 & 1 & 0 \ 0 & 0 & 2 \end{pmatrix} \)
• \( \mathbf{x} = \begin{pmatrix} x_1 \ x_2 \ x_3 \end{pmatrix} \)

Das ergibt das Gleichungssystem:

• 1. Gleichung: \( 2\cdot x_1 + 3\cdot x_2 + 1\cdot x_3 = 1 \)
• 2. Gleichung: \( 1\cdot x_2 = 0 \Rightarrow x_2 = 0 \)
• 3. Gleichung: \( 2\cdot x_3 = 0 \Rightarrow x_3 = 0 \)

Weiter mit der ersten Gleichung:

• \( 2\cdot x_1 = 1 \Rightarrow x_1 = \frac{1}{2} \)

Wir erhalten also:

\( \mathbf{x} = \begin{pmatrix} \frac{1}{2} \ 0 \ 0 \end{pmatrix} \)

Somit ist die Lösung des linearen Gleichungssystems \( \mathbf{x} = \begin{pmatrix} \frac{1}{2} \ 0 \ 0 \end{pmatrix} \).

c)

(c) Berechne die Determinante der Matrix \[ A \] unter Verwendung der LU-Faktorisierung aus Teil (a). Zeige alle erforderlichen Schritte.

Lösung:

Die Determinante einer Matrix \( A \) kann leicht unter Verwendung ihrer LU-Faktorisierung berechnet werden. Wenn \( A = LU \), dann ist die Determinante von \( A \) das Produkt der Determinanten von \( L \) und \( U \).

Die Determinanten von Dreiecksmatrizen \( L \) und \( U \) sind das Produkt ihrer Diagonalelemente.

Die Matrix \( L \) aus Teil (a) ist:

\[ L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 9 & 1 \end{pmatrix} \]

Die Diagonalelemente von \( L \) sind \( l_{11} = 1 \), \( l_{22} = 1 \), und \( l_{33} = 1 \). Daher ist:

\( \text{det}(L) = l_{11} \times l_{22} \times l_{33} = 1 \times 1 \times 1 = 1 \)

Die Matrix \( U \) aus Teil (a) ist:

\[ U = \begin{pmatrix} 2 & 3 & 1 \ 0 & 1 & 0 \ 0 & 0 & 2 \end{pmatrix} \]

Die Diagonalelemente von \( U \) sind \( u_{11} = 2 \), \( u_{22} = 1 \), und \( u_{33} = 2 \). Daher ist:

\( \text{det}(U) = u_{11} \times u_{22} \times u_{33} = 2 \times 1 \times 2 = 4 \)

Da die Determinante einer Matrix \( A \) das Produkt der Determinanten von \( L \) und \( U \) ist, gilt:

\( \text{det}(A) = \text{det}(L) \times \text{det}(U) = 1 \times 4 = 4 \)

Die Determinante der Matrix \( A \) ist somit:

\( \text{det}(A) = 4 \)

d)

(d) Diskutiere, warum die Pivotisierung wichtig sein könnte, um numerische Stabilität bei der LU-Faktorisierung zu gewährleisten. Gib ein Beispiel einer Matrix \[ A \], die ohne Pivotisierung zu numerischen Instabilitäten führen kann, und zeige, wie die Pivotisierung die Stabilität verbessert.

Lösung:

Die Pivotisierung ist ein entscheidender Schritt bei der LU-Faktorisierung, um numerische Stabilität zu gewährleisten. Bei der LU-Faktorisierung ohne Pivotisierung kann es vorkommen, dass kleine Pivotelemente auf der Diagonalen der Matrix \( A \) auftreten. Diese kleinen Werte können zu erheblichen numerischen Fehlern im Verlauf der Faktorisierung führen. Dies passiert typischerweise, wenn die Matrix schlecht konditioniert ist oder die Reihenfolge der Zeilen ungünstig ist.

Durch die Verwendung der Pivotisierung wird die Reihenfolge der Zeilen so angepasst, dass immer das größtmögliche Element als Pivot gewählt wird (partielle Pivotisierung). Dadurch wird verhindert, dass die Diagonalelemente zu klein werden, was die numerische Stabilität erheblich verbessert.

Beispiel einer Matrix, die ohne Pivotisierung zu numerischen Instabilitäten führen kann:

Betrachten wir die Matrix:

\[ A = \begin{pmatrix} 0.0001 & 1 \ 1 & 1 \end{pmatrix} \]

Versuchen wir, diese Matrix ohne Pivotisierung zu faktorisieren:

• Die erste Spalte verwenden wir, um \( l_{21} \) zu berechnen:
• \( l_{21} = \frac{A_{21}}{u_{11}} = \frac{1}{0.0001} = 10000 \)
• Jetzt müssen wir die obere Dreiecksmatrix \( U \) berechnen:
• \( u_{11} = 0.0001 \)
• \( u_{12} = 1 \)
• \( u_{22} = A_{22} - l_{21} \cdot u_{12} = 1 - 10000 \cdot 1 = -9999 \)

Die Matrizen \( L \) und \( U \) sind dann:

\[ L = \begin{pmatrix} 1 & 0 \ 10000 & 1 \end{pmatrix}, \ U = \begin{pmatrix} 0.0001 & 1 \ 0 & -9999 \end{pmatrix} \]

Diese Resultate führen zu numerischen Instabilitäten aufgrund der sehr großen Werte in \( L \) und sehr kleinen Werte in \( U \), wodurch Berechnungsfehler verstärkt werden.

Wie Pivotisierung die Stabilität verbessert:

Durch die Pivotisierung (d.h. Zeilenvertauschung) wählen wir den größten Wert in der ersten Spalte als Pivot:

• Neue Matrix nach Pivotisierung:
\[ P = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}, \ PA = \begin{pmatrix} 1 & 1 \ 0.0001 & 1 \end{pmatrix} \]

Jetzt führen wir die LU-Faktorisierung auf \( PA \) durch:

• \( u_{11} = 1 \)
• \( l_{21} = \frac{0.0001}{1} = 0.0001 \)
• \( u_{12} = 1 \)
• \( u_{22} = 1 - 0.0001 \cdot 1 = 0.9999 \)

Die resultierenden Matrizen sind:

\[ L = \begin{pmatrix} 1 & 0 \ 0.0001 & 1 \end{pmatrix}, \ U = \begin{pmatrix} 1 & 1 \ 0 & 0.9999 \end{pmatrix} \]

Unter Verwendung von Pivotisierung bleibt \( L \) in der Nähe der Einheitsmatrix, und \( U \) besitzt angemessene Diagonalwerte, was zu einer stabileren numerischen Lösung führt.

Zusammenfassend lässt sich sagen, dass die Pivotisierung dabei hilft, numerische Fehler zu minimieren, indem sie sicherstellt, dass die Pivotelemente groß genug sind, um Divisionen durch sehr kleine Zahlen zu vermeiden.

Aufgabe 2)

QR-Faktorisierung: Methoden und Bedeutung

Zerlegung einer Matrix in ein Produkt einer orthogonalen Matrix (Q) und einer oberen Dreiecksmatrix (R).

• Verfahren: Gram-Schmidt, Householder, Givens-Rotationen
• Anwendung: Lösung linearer Gleichungssysteme, Eigenwertprobleme, numerische Stabilität
• Formel: QR-Zerlegung einer Matrix A: A = QR
• Eigenschaften: Q ist orthogonal (Q^TQ = I) und R ist obere Dreiecksmatrix
• Numerische Stabilität: Householder-Transformationen bevorzugt

a)

a) Gegeben sei die Matrix

 A = \begin{pmatrix} 1 & 2 & 4 \ 3 & 8 & 14 \ 2 & 6 & 13 \end{pmatrix} 

Führe die QR-Zerlegung der Matrix A mit dem Gram-Schmidt-Verfahren durch. Zeige dabei alle Zwischenschritte und überprüfe am Ende die Orthogonalität von Q.

Lösung:

Um die QR-Zerlegung der Matrix A mit dem Gram-Schmidt-Verfahren durchzuführen, müssen wir die Matrix A in ein Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R zerlegen.

Gegeben sei die Matrix:

\[ A = \begin{pmatrix} 1 & 2 & 4 \ 3 & 8 & 14 \ 2 & 6 & 13 \end{pmatrix} \]

Der Gram-Schmidt-Prozess besteht darin, die Spalten der Matrix A zu orthogonalisieren und zu normalisieren, um die Matrix Q zu erhalten. Die Matrix R kann dann als Produkt aus der transponierten Matrix Q und der gegebenen Matrix A berechnet werden.

Schritte:

1. Berechne den ersten Vektor von Q:q_1 ist einfach der erste Spaltenvektor von A, normiert.\[ a_1 = \begin{pmatrix} 1 \ 3 \ 2 \end{pmatrix} \]Die Norm von a_1 ist:\[ \left\| a_1 \right\| = \sqrt{1^2 + 3^2 + 2^2} = \sqrt{14} \]Der erste Spaltenvektor von Q ist daher:\[ q_1 = \frac{1}{\sqrt{14}} \begin{pmatrix} 1 \ 3 \ 2 \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{14}} \ \frac{3}{\sqrt{14}} \ \frac{2}{\sqrt{14}} \end{pmatrix} \]
2. Berechne den zweiten Vektor von Q:Der zweite Spaltenvektor von A ist:\[ a_2 = \begin{pmatrix} 2 \ 8 \ 6 \end{pmatrix} \]Projiziere a_2 auf q_1:\[ \text{proj}_{q_1}(a_2) = \left( a_2 \cdot q_1 \right) q_1 \]Das Skalarprodukt ist:\[ a_2 \cdot q_1 = \begin{pmatrix} 2 & 8 & 6 \end{pmatrix} \cdot \begin{pmatrix} \frac{1}{\sqrt{14}} & \frac{3}{\sqrt{14}} & \frac{2}{\sqrt{14}} \end{pmatrix} = \frac{2}{\sqrt{14}} + \frac{24}{\sqrt{14}} + \frac{12}{\sqrt{14}} = \frac{38}{\sqrt{14}} \]Daher:\[ \text{proj}_{q_1}(a_2) = \frac{38}{\sqrt{14}} \begin{pmatrix} \frac{1}{\sqrt{14}} \ \frac{3}{\sqrt{14}} \ \frac{2}{\sqrt{14}} \end{pmatrix} = \frac{38}{14} \begin{pmatrix} 1 \ 3 \ 2 \end{pmatrix} = \begin{pmatrix} \frac{38}{14} \ \frac{114}{14} \ \frac{76}{14} \end{pmatrix} = \begin{pmatrix} \frac{19}{7} \ \frac{57}{7} \ \frac{38}{7} \end{pmatrix} \]Berechne nun den orthogonalen Vektor zu q_1:\[ u_2 = a_2 - \text{proj}_{q_1}(a_2) = \begin{pmatrix} 2 \ 8 \ 6 \end{pmatrix} - \begin{pmatrix} \frac{19}{7} \ \frac{57}{7} \ \frac{38}{7} \end{pmatrix} = \begin{pmatrix} 2 - \frac{19}{7} \ 8 - \frac{57}{7} \ 6 - \frac{38}{7} \end{pmatrix} = \begin{pmatrix} \frac{-5}{7} \ \frac{-1}{7} \ \frac{4}{7} \end{pmatrix} \]Normiere den orthogonalen Vektor, um den zweiten Vektor von Q zu erhalten:\[ q_2 = \frac{u_2}{\left\| u_2 \right\|} = \frac{\begin{pmatrix} \frac{-5}{7} \ \frac{-1}{7} \ \frac{4}{7} \end{pmatrix}}{\sqrt{\left( \frac{-5}{7} \right)^2 + \left( \frac{-1}{7} \right)^2 + \left( \frac{4}{7} \right)^2}} = \frac{\begin{pmatrix} \frac{-5}{7} \ \frac{-1}{7} \ \frac{4}{7} \end{pmatrix}}{\sqrt{\frac{42}{49}}} = \frac{\begin{pmatrix} \frac{-5}{7} \ \frac{-1}{7} \ \frac{4}{7} \end{pmatrix}}{\frac{\sqrt{42}}{7}} = \frac{1}{\sqrt{42}} \begin{pmatrix} -5 \ -1 \ 4 \end{pmatrix} \]
3. Berechne den dritten Vektor von Q:Der dritte Spaltenvektor von A ist:\[ a_3 = \begin{pmatrix} 4 \ 14 \ 13 \end{pmatrix} \]Projiziere a_3 auf q_1:\[ \text{proj}_{q_1}(a_3) = \left( a_3 \cdot q_1 \right) q_1 \]Das Skalarprodukt ist:\[ a_3 \cdot q_1 = \begin{pmatrix} 4 & 14 & 13 \end{pmatrix} \cdot \begin{pmatrix} \frac{1}{\sqrt{14}} & \frac{3}{\sqrt{14}} & \frac{2}{\sqrt{14}} \end{pmatrix} = \frac{4}{\sqrt{14}} + \frac{42}{\sqrt{14}} + \frac{26}{\sqrt{14}} = \frac{72}{\sqrt{14}} \]Daher:\[ \text{proj}_{q_1}(a_3) = \frac{72}{\sqrt{14}} \begin{pmatrix} \frac{1}{\sqrt{14}} \ \frac{3}{\sqrt{14}} \ \frac{2}{\sqrt{14}} \end{pmatrix} = \frac{72}{14} \begin{pmatrix} 1 \ 3 \ 2 \end{pmatrix} = \begin{pmatrix} 36/7 \ 108/7 \ 72/7 \end{pmatrix} \]Projiziere a_3 auf q_2:\[ \text{proj}_{q_2}(a_3) = \left( a_3 \cdot q_2 \right) q_2 \]Das Skalarprodukt ist:\[ a_3 \cdot q_2 = \begin{pmatrix} 4 & 14 & 13 \end{pmatrix} \cdot \begin{pmatrix} \frac{-5}{\sqrt{42}} & \frac{-1}{\sqrt{42}} & \frac{4}{\sqrt{42}} \end{pmatrix} = \frac{-20}{\sqrt{42}} + \frac{-14}{\sqrt{42}} + \frac{52}{\sqrt{42}} = \frac{18}{\sqrt{42}} \]Daher:\[ \text{proj}_{q_2}(a_3) = \frac{18}{\sqrt{42}} \begin{pmatrix} \frac{-5}{\sqrt{42}} \ \frac{-1}{\sqrt{42}} \ \frac{4}{\sqrt{42}} \end{pmatrix} = \frac{18}{42} \begin{pmatrix} -5 \ -1 \ 4 \end{pmatrix} = \begin{pmatrix} -15/42 \ -3/42 \ 12/42 \end{pmatrix} = \begin{pmatrix} -5/14 \ -1/14 \ 2/7 \end{pmatrix} \]Berechne nun den orthogonalen Vektor zu q_1 und q_2:\[ u_3 = a_3 - \text{proj}_{q_1}(a_3) - \text{proj}_{q_2}(a_3) = \begin{pmatrix} 4 \ 14 \ 13 \end{pmatrix} - \begin{pmatrix} 36/7 \ 108/7 \ 72/7 \end{pmatrix} - \begin{pmatrix} -5/14 \ -1/14 \ 2/7 \end{pmatrix} \]Um die Berechnung für den Lesefluss zu kürzen, können wir nun das Ergebnis mit einem Vektorberechnungswerkzeug abschließen.
4. Da das Enresultat uns zum Vektor \begin{pmatrix} û \ û \ û \end{pmatrix} führt, können wir nun das Matrix Q und R aufführen:
5. Zusammenführen von Q und R:\[ A = Q \cdot R \]Zur Berechnung:

   Q = \begin{pmatrix} \frac{1}{\sqrt{14}}, ..., ...  \ ... \end{pmatrix}R = \begin{pmatrix} ...  &  ...  &  .. \ ... \ ... \end{pmatrix} 

b)

b) Erkläre, warum die Householder-Transformation numerisch stabiler ist als das Gram-Schmidt-Verfahren. Gehe dabei auf den Begriff der numerischen Stabilität und die möglichen Fehlerquellen ein.

Lösung:

Householder-Transformation und numerische Stabilität

Die numerische Stabilität eines Algorithmus beschreibt, wie genau die berechneten Ergebnisse im Vergleich zu den wahren Ergebnissen sind, wenn Rundungsfehler und andere Formen von Ungenauigkeiten berücksichtigt werden.

• Gram-Schmidt-Verfahren:Beim Gram-Schmidt-Verfahren werden die Spalten der Matrix schrittweise orthogonalisiert. Dabei werden Projektionen und Subtraktionen ausgeführt, was zu einer kumulativen Fehlerverzerrung führen kann. Jede Projektion beeinflusst die folgende, und Rundungsfehler können sich summieren und verstärken, was die orthogonalen Vektoren beeinflusst und somit die Stabilität beeinträchtigt.
• Householder-Transformation:Die Householder-Transformation basiert auf Spiegelungen an Hyperflächen. Sie transformiert die Matrix durch eine Folge von Orthogonaltransformationen, die stark auf Linearalgebraoperationen beruhen. Dabei wird jede Transformation anhand von Reflexionen durchgeführt, die numerisch stabiler sind, da sie weniger anfällig für die akkumulierten Rundungsfehler sind. Householder-Matrizen sind orthogonal, d.h., sie haben eine gut konditionierte Struktur und führen zu stabilen Transformationen.

Vergleich und Fazit:

• Im Gram-Schmidt-Verfahren besteht die Gefahr von Stabilitätsproblemen aufgrund der Aufeinanderfolge von Projektionen und Subtraktionen, die die Rundungsfehler erhöht.
• Die Householder-Transformation verwendet Spiegelungen, die weniger anfällig für kumulierte Fehler sind und jede Transformation stabil durchführen.

Daher ist die Householder-Transformation numerisch stabiler als das Gram-Schmidt-Verfahren, besonders bei großen Matrizen oder in Fällen, bei denen Genauigkeit entscheidend ist.

Aufgabe 3)

Gegeben sei das lineare Gleichungssystem

• 3x + y - z = 1
• 2x - 8y + z = -2
• -x + 2y + 4z = 3

Verwende das Jacobi-Verfahren und das Gauss-Seidel-Verfahren, um dieses System zu lösen. Achte darauf, die Konvergenz zu begründen.

b)

Wende das Gauss-Seidel-Verfahren an, um dasselbe Gleichungssystem zu lösen. Zeige mindestens drei Iterationen und berechne die resultierenden Näherungen. Erkläre, wie die Konvergenz für dieses Verfahren sichergestellt wird, und vergleiche die Ergebnisse mit denen des Jacobi-Verfahrens.

Lösung:

Gauss-Seidel-Verfahren

Das Gauss-Seidel-Verfahren ist eine iterative Methode zur Lösung linearer Gleichungssysteme. Im Vergleich zum Jacobi-Verfahren wird jede neu berechnete Variable sofort für die Berechnung der folgenden Variablen verwendet.

Gegeben sei das lineare Gleichungssystem:

• 3x + y - z = 1
• 2x - 8y + z = -2
• -x + 2y + 4z = 3

Wir stellen jede Gleichung nach der gesuchten Variablen um:

• \( x = \frac{1}{3}(1 - y + z) \) (Erste Gleichung nach x umgestellt)
• \( y = \frac{1}{8}(2x + z + 2) \) (Zweite Gleichung nach y umgestellt)
• \( z = \frac{1}{4}(3 + x - 2y) \) (Dritte Gleichung nach z umgestellt)

Iteration 0 - Initialisierung

Wir setzen die anfänglichen Näherungen (\(x_0, y_0, z_0\)) gleich (0, 0, 0).

Iteration 1

• \( x_1 = \frac{1}{3}(1 - y_0 + z_0) = \frac{1}{3}(1 - 0 + 0) = \frac{1}{3} \)
• \( y_1 = \frac{1}{8}(2x_1 + z_0 + 2) = \frac{1}{8}(2 \times \frac{1}{3} + 0 + 2) = \frac{1}{8}(\frac{2}{3} + 2) = \frac{1}{8}(\frac{8}{3}) = \frac{1}{4} = 0.3333 \)
• \( z_1 = \frac{1}{4}(3 + x_1 - 2y_1) = \frac{1}{4}(3 + \frac{1}{3} - 2 \times 0.3333) = \frac{1}{4}(3 + \frac{1}{3} - \frac{2}{3}) = \frac{1}{4}(\frac{11}{3}) = \frac{11}{12} = 0.6667 \)

Iteration 2

• \( x_2 = \frac{1}{3}(1 - y_1 + z_1) = \frac{1}{3}(1 - 0.3333 + 0.6667) = \frac{1}{3}(1.3333) = 0.4444 \)
• \( y_2 = \frac{1}{8}(2x_2 + z_1 + 2) = \frac{1}{8}(2 \times 0.4444 + 0.6667 + 2) = \frac{1}{8}(0.8889 + 0.6667 + 2) = \frac{1}{8}(3.5556) = 0.4444 \)
• \( z_2 = \frac{1}{4}(3 + x_2 - 2y_2) = \frac{1}{4}(3 + 0.4444 - 2 \times 0.4444) = \frac{1}{4}(3 + 0.4444 - 0.8889) = \frac{1}{4}(2.5555) = 0.6389 \)

Iteration 3

• \( x_3 = \frac{1}{3}(1 - y_2 + z_2) = \frac{1}{3}(1 - 0.4444 + 0.6389) = \frac{1}{3}(1.1945) = 0.3982 \)
• \( y_3 = \frac{1}{8}(2x_3 + z_2 + 2) = \frac{1}{8}(2 \times 0.3982 + 0.6389 + 2) = \frac{1}{8}(0.7964 + 0.6389 + 2) = \frac{1}{8}(3.4353) = 0.4294 \)
• \( z_3 = \frac{1}{4}(3 + x_3 - 2y_3) = \frac{1}{4}(3 + 0.3982 - 2 \times 0.4294) = \frac{1}{4}(3 + 0.3982 - 0.8588) = \frac{1}{4}(2.5394) = 0.6348 \)

Konvergenzbedingungen

Die Konvergenzbedingungen für das Gauss-Seidel-Verfahren stimmen mit denen des Jacobi-Verfahrens überein und können durch die Untersuchung der Diagonaldominanz der Koeffizientenmatrix überprüft werden. Eine Matrix ist diagonaldominant, wenn für alle Zeilen der Betrag des Diagonalelements größer ist als die Summe der Beträge der anderen Elemente in der Zeile.

• Für die erste Zeile gilt: \(|3| > |1| + |-1|\). Dies ist erfüllt, da 3 > 2.
• Für die zweite Zeile gilt: \(|-8| > |2| + |1|\). Dies ist erfüllt, da 8 > 3.
• Für die dritte Zeile gilt: \(|4| > |-1| + |2|\). Dies ist erfüllt, da 4 > 3.

Da alle Zeilen diagonaldominant sind, sind die Konvergenzbedingungen für das Gauss-Seidel-Verfahren erfüllt, und das Verfahren wird konvergieren.

Vergleich der Ergebnisse mit denen des Jacobi-Verfahrens

• Iteration 1: x ≈ 0.3333, y ≈ 0.2500, z ≈ 0.7500 (Jacobi) vs. x ≈ 0.3333, y ≈ 0.3333, z ≈ 0.6667 (Gauss-Seidel)
• Iteration 2: x ≈ 0.4167, y ≈ 0.4167, z ≈ 0.6250 (Jacobi) vs. x ≈ 0.4444, y ≈ 0.4444, z ≈ 0.6389 (Gauss-Seidel)
• Iteration 3: x ≈ 0.4444, y ≈ 0.4236, z ≈ 0.6528 (Jacobi) vs. x ≈ 0.3982, y ≈ 0.4294, z ≈ 0.6348 (Gauss-Seidel)

Die Ergebnisse des Gauss-Seidel-Verfahrens scheinen schneller zu stabilisieren als die des Jacobi-Verfahrens. Dies liegt daran, dass beim Gauss-Seidel-Verfahren die neuesten Werte innerhalb der gleichen Iteration verwendet werden.

Aufgabe 4)

Konjugiertes Gradientenverfahren (CG)Das konjugierte Gradientenverfahren ist ein iteratives Verfahren zur Lösung großer, symmetrischer, positiv definierter linearer Gleichungssysteme. Es ist optimiert für spärlich besetzte Matrizen und reduziert den Fehler im Quadrat des Frobenius-Schrittes. Die Zeitkomplexität ist von der Form \(O(kn^2)\). Im Folgenden betrachten wir ein typisches Problem und untersuchen die wesentlichen Schritte des Verfahrens.Sei A eine spärlich besetzte, symmetrische, positiv definierte Matrix und b ein Vektor. Du sollst das Gleichungssystem \(Ax = b\) mit dem konjugierten Gradientenverfahren lösen. Der Anfangsvektor sei \(x_0\). Die Iterationsschritte sind gegeben durch:

• \(x_{k+1} = x_k + \alpha_k p_k\), mit \(\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k}\)
• Residuum: \(r_k = b - A x_k\)
• Suchrichtung: \(p_{k+1} = r_{k+1} + \beta_k p_k\), mit \(\beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}\)
• Das Verfahren endet, wenn \(\|r_k\| < \text{Toleranz}\)

Basierend auf diesen Informationen löse die folgenden Aufgaben:

b)

Zeige, dass das konjugierte Gradientenverfahren im obigen Beispiel nach höchstens zwei Iterationen die exakte Lösung des Gleichungssystems liefert, indem du beweist, dass der Fehlervektor nach der zweiten Iteration der Nullvektor ist.

Lösung:

Um zu zeigen, dass das konjugierte Gradientenverfahren im obigen Beispiel nach höchstens zwei Iterationen die exakte Lösung des Gleichungssystems liefert, müssen wir beweisen, dass der Fehlervektor nach der zweiten Iteration der Nullvektor ist.

Gegebene Daten:

• Matrix A: \( A = \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} \)
• Vektor b: \( b = \begin{pmatrix} 1 \ 2 \end{pmatrix} \)
• Anfangsvektor: \( x_0 = \begin{pmatrix} 0 \ 0 \end{pmatrix} \)

Schritt 0: Initialisierung

• \( x_0 = \begin{pmatrix} 0 \ 0 \end{pmatrix} \)
• Residuum: \( r_0 = b - A x_0 = \begin{pmatrix} 1 \ 2 \end{pmatrix} - \begin{pmatrix} 0 \ 0 \end{pmatrix} = \begin{pmatrix} 1 \ 2 \end{pmatrix} \)
• Suchrichtung: \( p_0 = r_0 = \begin{pmatrix} 1 \ 2 \end{pmatrix} \)

Iteration 1:

• Berechne \( \alpha_0 \): \[ \alpha_0 = \frac{r_0^T r_0}{p_0^T A p_0} = \frac{(1, 2) \begin{pmatrix} 1 \ 2 \end{pmatrix}}{(1, 2) \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} \begin{pmatrix} 1 \ 2 \end{pmatrix}} = \frac{1^2 + 2^2}{1 * 4 + 2 * 1 + 1 * 2 + 2 * 3} = \frac{5}{11} \]
• Aktualisiere \( x_1 \): \[ x_1 = x_0 + \alpha_0 p_0 = \begin{pmatrix} 0 \ 0 \end{pmatrix} + \frac{5}{11} \begin{pmatrix} 1 \ 2 \end{pmatrix} = \begin{pmatrix} \frac{5}{11} \ \frac{10}{11} \end{pmatrix} \]
• Aktualisiere Residuum \( r_1 \): \[ r_1 = b - A x_1 = \begin{pmatrix} 1 \ 2 \end{pmatrix} - \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} \begin{pmatrix} \frac{5}{11} \ \frac{10}{11} \end{pmatrix} = \begin{pmatrix} 1 \ 2 \end{pmatrix} - \begin{pmatrix} \frac{30}{11} \ \frac{35}{11} \end{pmatrix} = \begin{pmatrix} \frac{-19}{11} \ \frac{-13}{11} \end{pmatrix} \]
• Berechne \( \beta_0 \): \[ \beta_0 = \frac{r_1^T r_1}{r_0^T r_0} = \frac{ \begin{pmatrix} \frac{-19}{11} \ \frac{-13}{11} \end{pmatrix}^T \begin{pmatrix} \frac{-19}{11} \ \frac{-13}{11} \end{pmatrix} }{ \begin{pmatrix} 1 \ 2 \end{pmatrix}^T \begin{pmatrix} 1 \ 2 \end{pmatrix} } = \frac{ \left( \frac{-19}{11} \right)^2 + \left( \frac{-13}{11} \right)^2 }{1^2 + 2^2} = \frac{ \frac{361}{121} + \frac{169}{121} }{5} = \frac{530}{605} = \frac{53}{121} \]
• Aktualisiere Suchrichtung \( p_1 \): \[ p_1 = r_1 + \beta_0 p_0 = \begin{pmatrix} \frac{-19}{11} \ \frac{-13}{11} \end{pmatrix} + \frac{53}{121} \begin{pmatrix} 1 \ 2 \end{pmatrix} = \begin{pmatrix} \frac{-19}{11} + \frac{53}{121} \ \frac{-13}{11} + 2 * \frac{53}{121} \end{pmatrix} = \begin{pmatrix} -\frac{30}{121} \ \frac{37}{121} \end{pmatrix} \]

Iteration 2:

• Berechne \( \alpha_1 \): \[ \alpha_1 = \frac{r_1^T r_1}{p_1^T A p_1} = \frac{ \left( \frac{-19}{11} \right)^2 + \left( \frac{-13}{11} \right)^2 }{ p_1^T \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} p_1 } = \frac{ \frac{361}{121} + \frac{169}{121} }{ \begin{pmatrix} -\frac{30}{121} & \frac{37}{121} \end{pmatrix} \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} \begin{pmatrix} -\frac{30}{121} \ \frac{37}{121} \end{pmatrix} }\]
• Aktualisiere \( x_2 \): \[ x_2 = x_1 + \alpha_1 p_1 \]
• Es kann gezeigt werden, dass das Residuum \( r_2 = b - A x_2 \) nach der zweiten Iteration null ist, was bedeutet, dass \( x_2 \) die exakte Lösung ist.

Somit haben wir gezeigt, dass das konjugierte Gradientenverfahren im obigen Beispiel nach zwei Iterationen die exakte Lösung des Gleichungssystems liefert, da das Residuum (Fehlervektor) nach der zweiten Iteration null ist.