Einführung in die Numerik - Cheatsheet

Gauß-Verfahren

Definition:

Verfahren zur Lösung linearer Gleichungssysteme durch Umformung der Koeffizientenmatrix in eine obere Dreiecksform.

Details:

• 3 Schritte: Vorwärtselimination, Rückwärtssubstitution, Pivotisierung.
• Ziel: Matrix in obere Dreiecksform mit Nullen unter der Diagonalen.
• Vorwärtselimination: Subtrahiere passende Vielfache der Zeilen.
• Rückwärtssubstitution: Löse das System von oben nach unten.
• Pivotisierung: Tausche Zeilen, um nullte Diagonalelemente zu vermeiden.
• Kosten: \(O(n^3)\) Operationen für \(n\) Gleichungen

Jacobi-Verfahren und Gauss-Seidel-Verfahren

Definition:

Jacobi-Verfahren und Gauss-Seidel-Verfahren sind iterative Methoden zur Lösung von linearen Gleichungssystemen der Form \( Ax = b \).

Details:

• Jacobi-Verfahren: Update der Lösung erfolgt für jede Variable simultan durch Isolation der Variablen in den Gleichungen.
• Formel: \( x^{(k+1)} = D^{-1} (b - (L + U)x^{(k)}) \)
• Konvergenzbedingung: Matrix \( A \) muss diagonaldominant oder positiv definit sein.
• Gauss-Seidel-Verfahren: Verbesserung basiert auf sukzessive Aktualisierung neuer Werte in den Gleichungen.
• Formel: \( x_i^{(k+1)} = \frac{1}{a_{ii}} \left(b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)}\right) \)
• Schnellere Konvergenz als Jacobi, aber Reihenfolge der Berechnungen wichtig.

LU-, QR- und Cholesky-Zerlegung

Definition:

LU-, QR- und Cholesky-Zerlegung sind wichtige Matrixzerlegungen in der numerischen Mathematik, die zur Lösung von linearen Gleichungssystemen und zur Eigenwertbestimmung verwendet werden.

Details:

• LU-Zerlegung: Zerlegt eine Matrix A in das Produkt zweier Matrizen L (untere Dreiecksmatrix) und U (obere Dreiecksmatrix), sodass gilt: \(A = LU\).
• QR-Zerlegung: Zerlegt eine Matrix A in das Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R, sodass gilt: \(A = QR\).
• Cholesky-Zerlegung: Zerlegt eine symmetrische, positiv definite Matrix A in das Produkt einer unteren Dreiecksmatrix L und deren Transponierte \(L^T\), sodass gilt: \(A = LL^T\).

Polynominterpolation: Newton und Lagrange

Definition:

Polynominterpolation mithilfe von Newton- und Lagrange-Polynomen, um einen gegebenen Datensatz genau zu approximieren.

Details:

• Lagrange-Polynom: \[ P(x) = \sum_{i=0}^{n} y_i \frac{(x-x_0) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i-x_n)} \]
• Newton-Polynom: \[ P(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1) \cdots (x-x_{n-1}) \]
• Interpolationsfehler: \[ f(x) - P(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (x-x_0)(x-x_1) \cdots (x-x_n) \]

Numerische Differentiation: Vorwärts-, Rückwärts- und Zentrale Differenzen

Definition:

Numerische Differentiation verwendet Diskretisierungen, um Ableitungen zu berechnen.

Details:

• Vorwärts-Differenz: \( f'(x) \approx \frac{f(x+h) - f(x)}{h} \)Fehler: \( O(h) \)
• Rückwärts-Differenz: \( f'(x) \approx \frac{f(x) - f(x-h)}{h} \)Fehler: \( O(h) \)
• Zentrale Differenz: \( f'(x) \approx \frac{f(x+h) - f(x-h)}{2h} \)Fehler: \( O(h^2) \)

QR-Algorithmus und Schur-Zerlegung bei Eigenwertproblemen

Definition:

QR-Algorithmus zur Berechnung von Eigenwerten einer Matrix durch wiederholte Anwendung der QR-Zerlegung; Schur-Zerlegung zur Darstellung einer Matrix in obere Dreiecksform durch unitäre Transformation.

Details:

• QR-Zerlegung: \( A = QR \), wobei \(Q\) orthogonal und \(R\) eine obere Dreiecksmatrix ist.
• Iterativer Ablauf des QR-Algorithmus: \( A_{k+1} = R_k Q_k \), die Eigenwerte stehen auf der Diagonalen von \( A_k \) im Limes.
• Schur-Zerlegung: Jede quadratische Matrix \(A\) kann in der Form \( A = UTU^H \) mit unitärer Matrix \(U\) und oberer Dreiecksmatrix \(T\) zerlegt werden.

Adaptive Quadraturverfahren: Romberg-Integration

Definition:

Romberg-Integration ist eine Methode zur numerischen Integration, die Trapezregel und Richardson-Extrapolation kombiniert.

Details:

• Kombiniert Trapezregel mit Richardson-Extrapolation für höhere Genauigkeit.
• Hierarchie von Trapezregel-Näherungen.
• Extrapolationsschema: \( R_{k,j} = \frac{4^j R_{k+1,j-1} - R_{k,j-1}}{4^j - 1} \)
• Matrix von Näherungen \( R_{0,0}, R_{1,0}, R_{0,1}, \text{...} \)
• Erfordert adaptive Kontrolle um Fehler zu minimieren.

Fehlerschranken und Konditionszahlen

Definition:

Fehlerschranken: obere Grenze für den bestehenden Fehler in einer numerischen Berechnung. Konditionszahlen: Maß für die Empfindlichkeit der Lösung einer numerischen Problemstellung gegenüber kleinen Änderungen in den Eingangsdaten.

Details:

• Absolute Fehlerschranke: \[ |E(x)| \leq \text{obere Schranke} \]
• Relative Fehlerschranke: \[ |r(x)| = \frac{|E(x)|}{|x|} \leq \text{obere Schranke} \]
• Konditionszahl bei Funktion f: \[ \kappa(f) = \frac{|f'(x)|}{|f(x)|} |x| \]
• Schlecht konditioniertes Problem: hohe Konditionszahl (empfindlich gegenüber Fehlern)
• Gut konditioniertes Problem: niedrige Konditionszahl (weniger empfindlich gegenüber Fehlern)