aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2017-02-18 18:32:49 +0100
committerAdrian Kummerlaender2017-02-18 20:59:48 +0100
commitcd962351df5ed08a8dd6f29cda92853d08fce9fe (patch)
tree1fe1f683a06fda087d2138b480606ac53862da0e /content
parent12a983378135d0e78c709041b4c43722d10b5b3b (diff)
downloadmath_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar.gz
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar.bz2
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar.lz
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar.xz
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.tar.zst
math_reference_sheets-cd962351df5ed08a8dd6f29cda92853d08fce9fe.zip
Expand CG-iteration section
Diffstat (limited to 'content')
-rw-r--r--content/numerik_1.tex45
1 files changed, 20 insertions, 25 deletions
diff --git a/content/numerik_1.tex b/content/numerik_1.tex
index a4659c2..ee64871 100644
--- a/content/numerik_1.tex
+++ b/content/numerik_1.tex
@@ -273,7 +273,7 @@ Givens-Rotationen sind orthogonal, $G(l,k)A$ unterscheidet sich von $A$ nur in d
\vspace{-4mm}
$$(G(l,k)x)_i = \begin{cases}
- cx_l + sx_k & i=l \\
+ cx_l + sx_k & i=l \\
-sx_l + cx_k & i=k \\
x_i & \text{sonst}
\end{cases}$$
@@ -392,7 +392,7 @@ Ein Krylov-Raum-Verfahren bzgl. einer Norm $\|\cdot\|_\star$ ist nur dann sinnvo
\vspace{-2mm}
$$u^{k+1} = u^k + N(b-Au^k)$$
-$u^k$ wird in jeder Iteration entsprechend der jeweiligen Charakterisierung minimiert.
+$u^k$ wird in jeder Iteration entsprechend der jeweiligen Charakterisierung minimiert.
\subsection*{Vorkonditionierer}
@@ -407,6 +407,24 @@ $$u^k = argmin\{\|v-A^{-1}b\|_A : v \in V_k\}$$
Für positiv definite $A, N \in \R^{n \times n}$ sowie $b \in \R^n$ liefert das CG-Verfahren nach spätestens $n$ Schritten $A^{-1}b$. Eigentlich ist es bei exakter Arithmetik also ein direkter Verfahren, wird aber durch früheren Abbruch als iteratives Verfahren verwendet.
+\subsubsection*{Umsetzung}
+
+Minimum $\hat x$ von $f(x)=\frac{1}{2} x^TAx - b^Tx$ ist $A\hat x = b$.
+
+$\nabla f(x) = Ax - b \overset{!}{=} 0$ ergibt Minimum da nach oben geöffnete Parabel wg. $A > 0$.
+
+Initiale Suchrichtung $p_0$ ist $r_0 = b - Ax_0$. Folgende $p_{k+1}$ ergeben sich aus $p_{k+1} = r_{k+1} - \beta_k p_k$.
+
+$p_k$ und $x_k$ sind $A$-konjugiert. $f(x_k + \alpha_k p_k)$ wird via $\alpha_k$ entlang dieser Richtung minimiert mittels:
+
+\vspace{-4mm}
+\begin{align*}
+\alpha_k &= \frac{\skp{r_k,p_k}_2}{\|p_k\|_A^2} = \frac{\skp{r_k,r_k}_2}{\|p_k\|_A^2} \\
+\beta_k &= \frac{\skp{r_{k+1},p_k}_A}{\|p_k\|_A^2} = \frac{\skp{r_{k+1},r_{k+1}}_2}{\|r_k\|_2^2}
+\end{align*}
+
+Es gilt also $x_{k+1} = x_k + \alpha_k p_k$.
+
\subsection*{GMRES-Verfahren}
Das Verfahren des verallgemeinerten minimalen Residuum liefert die Lösung $Ax=b$ für $A \in GL_n(\R)$ und ist charakterisiert durch:
@@ -622,26 +640,3 @@ function [A, L, R] = lr(A)
R = triu(A);
end
\end{lstlisting}
-
-
-\subsection*{Beispiel: Vorwärtssubstitution}
-
-\begin{lstlisting}[frame=single,language=Matlab]
-function z = forwardSubstitution(L, b)
- [w,h] = size(L);
-
- if w ~= h
- error('L is not a square matrix')
- end
-
- if length(b) ~= w
- error('Size of b != size of L')
- end
-
- z = zeros(h,1);
-
- for i = 1:h
- z(i) = ( b(i) - L(i,:)*z ) / L(i,i);
- end
-end
-\end{lstlisting}