3. Umformung in eine Iteration
Wenn wir die Matrix A so in das Produkt L·R zerlegen,
dass L eine untere Dreiecksmatrix mit Einsen auf der Hauptdiagonalen ist
und R eine obere Dreiecksmatrix, können wir die relevanten Informationen
in eine einzige Matrix packen:
\begin{pmatrix}\green{u_{11}} & \green{u_{12}} & \green{u_{13}} & \ldots & \green{u_{1n}} \cr
\pink{l_{21}} & \green{u_{22}} & \green{u_{23}} & \ldots & \green{u_{2n}} \cr
\pink{l_{31}} & \pink{l_{32}} & \green{u_{33}} & \ldots & \green{u_{2n}} \cr
\vdots & \vdots & \vdots & \ddots & \vdots \cr
\pink{l_{n1}} & \pink{l_{n2}} & \pink{l_{n3}} & \ldots & \green{u_{nn}}
\end{pmatrix}
Daraus lassen sich L und R gewinnen:
L, indem die Diagonalelemente (u_{11}bisu_{nn}) durch 1 und die übrigen grün unterlegten Elemente durch Null ersetzt werden,R, indem alle rötlich unterlegten Elemente durch Null ersetzt werden.
Wir entwerfen nun einen Algorithmus, der die Ausgangsmatrix A
direkt in diese Kompaktdarstellung umformt.
Im letzten Abschnitt haben wir die Matrix so zerlegt:
A = \begin{pmatrix}a_{11} & \textbf{w} \cr
\textbf{v} & A'
\end{pmatrix}
= \begin{pmatrix}1 & \textbf 0 \cr \pink{\frac{1}{a_{11}}} \textbf{v} & I_{n-1}\end{pmatrix}
\begin{pmatrix}\green{a_{11}} & \green{\textbf w} \cr \textbf 0 & \yellow{A' - \frac{1}{a_{11}} \textbf{v w}}\end{pmatrix}
Wenn wir die relevanten Informationen zusammenpacken, erhalten wir:
\begin{pmatrix}\green{a_{11}} & \green{\textbf w} \cr
\pink{\frac{1}{a_{11}} \textbf{v}} & \yellow{A' - \frac{1}{a_{11}} \textbf{v w}}
\end{pmatrix}
Im den rötlichen und grünen Bereichen stehen schon Teile der Dreiecksmatrizen,
der gelb unterlegte Bereich muss weiter zerlegt werden.
Dies bekommen wir durch folgende Operationen aus der Ausgangsmatrix
(machen Sie sich dazu bitte klar, wie das Produkt
vw gebildet wird):
- Die erste Zeile bleibt unverändert.
- Der Rest der ersten Spalte wird durch
a_{11}dividiert. In mathGUIde (Matrizen werden hier ab Null indiziert) sieht das so aus:
for (i of fromTo(1, n-1))
A[i][0] = nDiv(A[i][0], A[0][0]) - Im Rest der Matrix wird von jedem Element
das Produkt aus dem links davon stehenden Element der ersten Spalte
(das schon durch
a_{11}dividiert ist!) und dem darüber stehenden Element der ersten Zeile subtrahiert:
for (i of fromTo(1, n-1))
for (j of fromTo(1, n-1))
A[i][j] = nSub(A[i][j], nMul(A[i][0], A[0][j])))
In mathGUIde (Matrizen werden hier ab Null indiziert!) sieht das so aus:
for (i of fromTo(1, n-1)) {
A[i][0] /= A[0][0]
for (const i of fromTo(1, n-1))
for (const j of fromTo(1, n-1))
A[i][j] -= A[i][0] * A[0][j]
Jetzt ist es nur noch ein kleiner Schritt, dieses Verfahren auf den Rest der Matrix zu erweitern. Dazu führen wir eine äußere Schleifenvariable k für den linken (und oberen) Index der zu bearbeitenden Restmatrix ein. Damit nicht nur Number-Typen (sondern z.B. auch BigInt, Rational) die Matrix besiedeln dürfen, ersetzen wir die Operatoren + usw. durch die polymorphen Funktionen add usw.:
Damit haben wir die im ersten Abschnitt gewonnene Zerlegung bestätigt:
\yellow{\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 10 \\ 3 & 26 & 24 \end{pmatrix}}
=
\pink{\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{pmatrix}}
\cdot \green{\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 10 \\ 3 & 26 & 24 \end{pmatrix}}
Fortsetzung: 4. Beseitigung des Schönheitsfehlers: LRP-Zerlegung
