Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

1 Lineare Gleichungssysteme, LR- und Cholesky-Zerlegung, iterative Verfahren
2 Approximation im quadratischen Mittel
- 2.1 Normalengleichungen
- 2.2 Householder-Verfahren
3 Nichtlineare Gleichungssysteme
- 3.1 Banachscher Fixpunktsatz
- 3.2 Newton Verfahren (klassisch) / Newton Iteration
4 Interpolation, Integration und Differentiation
5 Gewöhnliche und (wenige) partielle Differentialgleichungen, numerische Methoden
6 Unsortiert

Lineare Gleichungssysteme, LR- und Cholesky-Zerlegung, iterative Verfahren

Ziel: Residuum $\|Ax - b\|_2$ minimieren

Gauß-Algorithmus

Mit Spaltenpivotisierung stabil
spd-Matrix oder diagonaldominante Matrix -> Spaltenpivotisierung nicht sinnvoll
$| a i k |$ betragsmäßig sehr unterschiedlich -> Zeilenäquilibrierung

LR- und Cholesky-Zerlegung

s.p.d Matrix -> es ex. eine LR-Zerlegung
s.p.d MAtrix -> Einzelschnitterfahren konvergiert

LR-Zerlegung

Spalten-Pivotisierung: Zeilen tauschen. Betragsmäßig größtes Element nach oben
Aufwand: $n 3$
$P \cdot A = L \cdot R$ , P = Permutationsmatrix -> Speichert Zeilenvertauschung zu Stabilisierungszwecken
$Ax = b \Leftrightarrow LR x = b$

Cholesky-Zerlegung (Satz 1.3)

$A = L D L t$
Aufwand: Hälfte des Gauß-Algorithmus
$a_{ik} = \sum_{j=1}^{k} l_{ij} r_{jj} l_{kj}$

$r_{kk} = a_{kk} - \sum_{j=1}^{k-1} r_{jj} l^2_{kj} \ \ \big \} D$
$l_{ik} = (a_{ik} - \sum_{j=1}^{k-1} l_{ij} r_{jj} l_{kj}) \frac{1}{r_{kk}}, i > k \ \ \big \} L$

A ist spd, wenn $r k k > 0$

Maschinengenauigkeit / Stabilität eines Algorithmus

Kondition einer Matrix (Def. 1.2)

$K(A) = cond_{\|\cdot\|}(A) := \|A\| \cdot \|A^{-1}\|$
Schlecht konditioniert, wenn $cond_{\|\cdot\|}(A) >> 1$

Iterative Verfahren

$\|x\|_{1} = \sum_{i=1}^{n} |x_i|$

$\|A\|_{1} = \max_{1 \le k \le n} \sum_{i=1}^{n} |a_{ik}|$ , Spaltensummennorm

$\|x\|_{2} = \left( \sum_{i=1}^{n} |x_i|^2 \right)^{\frac{1}{2}}$

$\left\| A \right\|_2 = \sqrt{\lambda_{{\rm max}}(A^{t}A)}$ , Spektralnorm

$\|x\|_{\infty} = \max_{i=1,\dots,n} |x_i|$

$\left\| A \right\|_\infty = \max_{1 \le i \le n}{\sum_{j=1}^n \left| a_{ij} \right|}$ , Zeilensummennorm

$\|A\|=n \cdot \max_{i,j\in\{1,\dots,n\}}|a_{ij}|$ , Gesamtnorm

Spektralradius: $\rho(A) := \max \limits_{1 \le i \le n} |\lambda_i(A)|$ , für jede induzierte Matrixnorm: $\rho(A)=\lim_{n\to\infty}\sqrt[n]{\|A^n\|}$

Konvergenzkriterium: Iterationsverfahren konvergiert genau dann, wenn $p (T) < 1$

Gesamtschrittverfahren

Zeilensummenkriterium: $\|T_{GS}\|_\infty = \max_{1 \le i \le n} \sum_{k=1, k \ne i} \left | \frac{a_{ik}}{a_{ii}} \right | < 1$

Spaltensummenkriterium: $\|T_{GS}\|_1 = \max_{1 \le k \le n} \sum_{i=1, i \ne k} \left | \frac{a_{ik}}{a_{kk}} \right | < 1$

Zeilensummernkriterium und Spaltensummenkriterium erfüllt -> GS konvergiert

Einzelschrittverfahren

A spd Matrix -> ES konvergiert

Approximation im quadratischen Mittel

Fehlerquadratsumme (S 2.1): $\sum_{j=1}^m \sum_{l=1}^{\alpha_j} \left | f_j^l - \sum_{i=1}^n \varphi_i(t_j)x_i \right |^2$

Approximationsproblem

Menge G abgeschlossen und beschränkt -> G kompakt

Normalengleichungen

$A t A x * = A t b$

eindeutig lösbar wenn $det A^t A \ne 0 \Leftrightarrow Rg A = n$

$g * = P b, P = A (A t A) - 1 A t$

$\|P\|_2 = 1$

$\frac{\|x- \overline x\|_2}{\|x\|_2} \le \frac{1}{cos \theta} cond_2(A^t A)^{1/2} \frac{\|b-\overline b\|_2}{\|b\|_2}$

Householder-Verfahren

Ausgangspunkt: $Q t A = R$

benutzt Spiegelung / Givens-Rotation

$H (v) = (1 - 2 v v t)$

Nichtlineare Gleichungssysteme

Fixpunktiteration: $x^{k+1} = \varphi(x^k), k = 0,1,\dots$

Banachscher Fixpunktsatz

Bedingungen
- $G$ abgeschlossen
- Funktion $\varphi$ selbstabbildend. $\varphi(G) \subset G$
- $\|\varphi(x)-\varphi(y)\| \le \kappa \|x-y\|, \ x,y \in G, 0 < \kappa < 1$

Newton Verfahren (klassisch) / Newton Iteration

$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$
Lipschitz-Bedingung: $\|f'(z)-f'(x)\| \le L \|z-x\|, x,z \in \overline B_R(\overline x)$

Interpolation, Integration und Differentiation

Stützstellen: $p_{n-1}(x_i) = \sum_{k=0}^{n-1} a_k a_i^k = f_i, i = 1,2,\dots,n$
Lagrange-Polynom: $L_{n-1}(x) = \sum_{j=1}^n l_j(x) f_j$
Vandermonde Matrix

Gewöhnliche und (wenige) partielle Differentialgleichungen, numerische Methoden

Anfangswertproblem
Existenzsatz von Peano
Lipschitzbedingung
lokale Lipschitzbedingung
Eindeutigkeit der Lösung
Picard-Lindelöf
- f stetig und lokale Liptschitzbedingung erfüllt -> Es existiert eine Lösung
Kontraktion
Existenz einer maximalen Lösung

Euler-Cauchy-Verfahren

Verbessertes Euler-Cauchy-Verfahren

Runge-Kutta Verfahren

Klassisches Runge-Kutta Verfahren

Trapezregel

rückwärtiger Euler

Runge-Kutta Gauß

Unsortiert

Lineares Ausgleichsproblem

$| Ax - b |^2_2 \to min$

Einzelschrittverfahren / Gauß-Seidel-Verfahren

$\begin{matrix} a_{1;1}\cdot x_1+\dots+a_{1;n}\cdot x_n&=&b_1\\ a_{2;1}\cdot x_1+\dots+a_{2;n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n;1}\cdot x_1+\dots+a_{n;n}\cdot x_n&=&b_n\\ \end{matrix}$

$x^{(m+1)}_k:=\frac1{a_{k;k}}\left(b_k-\sum_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right)$

konvergiert, wenn Matrix s.p.d.
konvergiert, wenn Spaltensummenkriterium erfüllt wird

Gesamtschrittverfahren / Jacobi-Verfahren

$\begin{matrix} a_{1,1}\cdot x_1+\dots+a_{1,n}\cdot x_n&=&b_1\\ a_{2,1}\cdot x_1+\dots+a_{2,n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n,1}\cdot x_1+\dots+a_{n,n}\cdot x_n&=&b_n\\ \end{matrix}$

$x_i^{(m+1)}:=\frac1{a_{i,i}}\left(b_i-\sum_{j\not=i} a_{i,j}\cdot x_j^{(m)}\right)$

konvergiert wenn A diagonaldominant ist $|a_{ii}| > \sum_{j \ne i} |a_{ij}|$

Kleinkram

Differentialgleichungen und Numerik - Übersicht