LaTeX-examples/documents/Numerik/Klausur1/Aufgabe2.tex

\section*{Aufgabe 2}
\subsection*{Teilaufgabe a}
\textbf{Aufgabe}
Formulieren Sie einen Algorithmus in Pseudocode zum Lösen des Gleichungssystems
\[Ly = b,\]
wobei $L$ eine invertierbare, untere Dreiecksmatrix ist.

Geben Sie die Formel zur Berechnung von $y_i$ an.

\textbf{Lösung:} 
\[y_i = \frac{b_i - \sum_{k=1}^{i-1} l_{ik} \cdot y_k}{l_{ii}}\]

\begin{algorithm}[H]
    \begin{algorithmic}
    \Require Lower, invertable, triangular Matrix $L \in \mathbb{R}^{n \times n}$, Vektor $b$
	\Procedure{solve}{$L$, $b$}
    	\For{$i \in \Set{1, \dots n}$}
			\State $y_i \gets b_i$
			\For{$k \in \Set{1, \dots, i-1}$}
				\State $y_i \gets y_i - l_{ik} \cdot y_k$
			\EndFor
			\State $y_i \gets \frac{y_i}{l_{ii}}$
		\EndFor
	\EndProcedure
    \end{algorithmic}
\caption{Calculate $y$ in $Ly = b$}
\end{algorithm}

\subsection*{Teilaufgabe b}
\[Ax = b \Leftrightarrow PAx = Pb \Leftrightarrow LRx = Pb \]

\begin{algorithm}[H]
    \begin{algorithmic}
    \Require Matrix $A$, Vektor $b$
	\Procedure{LoeseLGS}{$A$, $b$}
    	\State $P, L, R \gets \Call{LRZer}{A}$
		\State $b^* \gets P \cdot b$
		\State $c \gets \Call{VorSub}{L, b^*}$
		\State $x \gets \Call{RueckSub}{R, c}$
		\State \Return $x$
	\EndProcedure
    \end{algorithmic}
\caption{Löse ein LGS $Ax = b$}
\end{algorithm}

\subsection*{Teilaufgabe c}
Der Gesamtaufwand ist:
\begin{itemize}
	\item LR-Zerlegung, $\frac{1}{3}n^3 - \frac{1}{3} n^2$
	\item Vektormultiplikation, $2n$
	\item Vorwärtssubstitution, $\frac{1}{2} n^2$
	\item Rückwärtssubstitution, $\frac{1}{2} n^2$
\end{itemize}