Algorithms of Numerical Linear Algebra - Cheatsheet

LU-Faktorisierung: Prinzip und Anwendung

Definition:

LU-Faktorisierung zerlegt eine Matrix in eine untere Dreiecksmatrix (L) und eine obere Dreiecksmatrix (U).

Details:

• Gegeben eine Matrix A: \[A = LU\]
• L ist eine untere Dreiecksmatrix (alle Einträge oberhalb der Hauptdiagonalen sind Null)
• U ist eine obere Dreiecksmatrix (alle Einträge unterhalb der Hauptdiagonalen sind Null)
• Verwendung: Lösen von linearen Gleichungssystemen, Berechnung der Determinante, Invertierung von Matrizen
• Anwendung: Gaussian Elimination ohne den Schritt der Rückwärts-Substitution
• Stabilität: Partielle Pivotisierung (\[PA = LU\], wobei P eine Permutationsmatrix ist) kann erforderlich sein, um die numerische Stabilität zu gewährleisten

QR-Faktorisierung: Methoden und Bedeutung

Definition:

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

Details:

• 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

Iterative Verfahren: Jacobi- und Gauss-Seidel-Verfahren

Definition:

Iterative Verfahren zur Lösung linearer Gleichungssysteme. Jacobi und Gauss-Seidel sind zwei beliebte Methoden.

Details:

• Jacobi-Verfahren: Trennt Diagonalelemente und iteriert Lösung durch \[ x^{(k+1)} = D^{-1}(b - (L + U)x^{(k)}) \]
• Gauss-Seidel-Verfahren: Verwendet neueste Werte für Iterationen \[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{ji} a_{ij}x_j^{(k)} \right) \]
• Konvergenz: Beide Methoden konvergieren sicher für strikt diagonaldominante Matrizen

Konjugiertes Gradientenverfahren (CG)

Definition:

Iteratives Verfahren zur Lösung großer, symmetrischer, positiv definierter linearer Gleichungssysteme.

Details:

• Optimiert für spärlich besetzte Matrizen.
• Reduziert den Fehler im Quadrat des Frobenius-Schrittes.
• Zeitkomplexität: \(O(kn^2)\)
• Anfangsvektor: \(x_0\)
• Iteration: \(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}\)
• Beendet, wenn \(\|r_k\| < \text{Toleranz}\)

QR-Algorithmus für Eigenwertprobleme

Definition:

Iteratives Verfahren zur Bestimmung der Eigenwerte einer Matrix.

Details:

• Startmatrix A in Hessenbergform reduzieren für Effizienz.
• Jeder Iterationsschritt: Matrixtqzerlegung A_k = Q_k R_k durchführen, dann A_{k+1} = R_k Q_k.
• Ergebnisse konvergieren zu einer oberen Dreiecksform, deren Diagonalelemente die Eigenwerte von A enthalten.
• Konvergenz durch Shifttechnik beschleunigen.
• Ergebnis: Approximation der Eigenwerte von A.

Numerische Stabilität: Rundungs- und Trunkierungsfehler

Definition:

Untersucht Verhalten von Algorithmen unter Rundungs- und Trunkierungsfehlern; wichtig für Zuverlässigkeit und Genauigkeit numerischer Berechnungen.

Details:

• Rundungsfehler: Entstehen durch begrenzte Genauigkeit der Darstellung von Zahlen im Computer.
• Besonders problematisch bei Subtraktion nahe beieinanderliegender Zahlen.
• Kann akkumulieren und signifikante Abweichungen verursachen.
• Trunkierungsfehler: Entstehen durch Abbrechen einer unendlichen Reihe oder Approximation einer kontinuierlichen Funktion.
• Zum Beispiel bei numerischer Integration und Differenzierung.
• Abhängig von der Schrittweite und dem verwendeten Verfahren.
• Stabilität: Numerische Stabilität bedeutet, dass kleine Fehler im Input nur kleine Fehler im Output erzeugen.
• Ein algorithmus ist numerisch stabil, wenn Fehler nicht exponentiell anwachsen.
• Vorwärtsfehler: Differenz zwischen dem berechneten Wert und dem exakten Wert.
• Rückwärtsfehler: Änderung des Inputs, die notwendig wäre, um das exakte Ergebnis zu erhalten.

Konditionierung und numerische Tests

Definition:

Maß für Empfindlichkeit einer Funktion bezüglich Eingangsfehler; wichtig für Stabilität und Genauigkeit numerischer Algorithmen.

Details:

• Konditionszahl: \ \( \text{cond}(A) = \|A\| \cdot \|A^{-1}\| \)
• Konditionszahl von Matrixproblemen: \ Hohe Konditionszahl -> Problemlösung empfindlich gegenüber Rundungsfehlern.
• Typen von Konditionszahlen: Gleichungen, Eigenwertprobleme, Least-Squares
• Numerische Tests: Überprüfung von Algorithmen hinsichtlich Genauigkeit, Stabilität und Effizienz.
• Beispiele numerischer Tests: Relative Fehler, Residuen, Forward/Backward-Error Analysis.

Praktische Implementierung und Optimierung in MATLAB/Python

Definition:

Praktische Implementierung und Optimierung von Algorithmen der numerischen linearen Algebra in MATLAB und Python

Details:

• Effiziente Speicher- und Rechenzeitnutzung beachten
• MATLAB: Matrixoperationen mit nativen Befehlen (\texttt{mldivide}, \texttt{eig}, \texttt{svd})
• Python: Nutzung von Bibliotheken wie NumPy und SciPy
• Parallelisierung und Vektorisierung zur Performance-Steigerung
• Profiling-Tools zur Identifizierung von Flaschenhälsen
• Pseudocode als Planungsbasis vor der Implementierung