Crouts Algorithmus ist ein Vorgehen zur Ermittlung der LU-Zerlegung eine Matrix.
Herzogs Algorithmus
Herzog spricht zwar von Crouts Algorithmus, seine Erklärung deckt sich aber nicht, mit anderen Ressourcen, die ich online gefunden habe. Daher stelle ich Herzogs Ansatz hier separat vor:
LaTeX-Code
\begin{algorithm} \caption{Crouts Algorithmus (Herzog)} \begin{algorithmic} \Input Quadratische Matrix $A$ \Output Permutationsmatrix $P$ \Output Untere Dreiecksmatrix $L$ \Output Obere Dreiecksmatrix $U$ \State \Comment{$\ $ Initialisierung:} \State $P=I_n$; \State $L=\mathbf{0}$; \State $U=\mathbf{0}$; \State \State \Comment{$\ $ Zunächst ermitteln wir $L$ und $P$.} \State \Comment{$\ $ Hierzu ermitteln wir auch die obere Dreiecksmatrix $A'$.} \State $A'=A$ \For{$i\in \{1,\ldots, n\}$} \If{$i$-te Spalte benötigt Zeilenflip $P_{ij}$} \State \Comment{$\ $ Bei Zeilenflips direkt $P$ erweitern.} \State Setze $A'=P_{ij}A'$. \State Setze $P=P_{ij}P$ \EndIf \State \If{$i$-te Spalte hat ein Pivot-Element} \State Eliminiere andere Einträge in der Spalte von $A'$ per Elementarmatrix $T_{ij}(s)$. \State Setze den Eintrag $l_{ij}=-s$ in der Matrix $L$. \EndIf \EndFor \State \State Fülle die Hauptdiagonale von $L$ mit Einsen auf, also $l_{ii}=1$. \State \State \Comment{$\ $ Jetzt ermitteln wir noch $U$, das ist aber sehr simpel:} \State Setze $U=A'$, also die per Gaußalgorithmus ermittelte obere Dreiecksmatrix. \State Setze alle Einträge von $U$ unterhalb der Hauptdiagonalen $0$, also $\forall i,j\in \{1,\ldots, n\}\colon i> j \implies u_{ij}=0$. \State \Return $P, L, U$ \end{algorithmic} \end{algorithm}
