Diese Präsentation ist unfertig. Sie zeigt einige Möglichkeiten des TEX-Formelsatzes in mathGUIde (unter Verwendung von jsMath).
Wir gliedern die quadratische n·n-Matrix
in vier Teilmatrizen:
Die Elemente dieser Zerlegung (statt A' schreiben wir A1
)
können wir in mathGUIde so schreiben:
v = A.submatrix(1,0, n-1,1)
w = A.submatrix(0,1, 1,n-1)
A1 = A.submatrix(1,1, n-1,n-1)
Zum Verständnis: Die Matrizen-Indizes zählen in mathGUIde nicht ab 1 sondern
ab Null (um mit den Python-Listen kompatibel zu bleiben).
Der submatrix
-Methode übergibt man in den ersten beiden Parametern
die Zeile und Spalte des linken oberen Elements der Untermatrix, dann die
Anzahl der zu übernehmenden Zeilen und Spalten.
Durch Ausmultiplizieren sieht man, dass diese Matrix in folgendes Produkt zerlegt werden kann, vorausgesetzt, dass a11 von Null verschieden ist:
Wir ziehen uns jetzt an den eigenen Haaren aus dem Sumpf, indem wir das Problem auf eine kleinere Matrix abwälzen, nämlich auf die gelb unterlegte (n-1)·(n-1)-Matrix. Nehmen wir also einmal an, dass wir die als Produkt einer unteren (linken) und einer oberen (rechten) Dreiecksmatrix darstellen können:
Damit erhalten wir
Man sieht leicht, dass die rötlich unterlegte Matrix eine untere Dreiecksmatrix ist und die grün unterlegte eine obere Dreiecksmatrix.
Vorausgesetzt, dass wir nicht auf eine Division durch Null stoßen
(das ist ein wunder Punkt, den wir noch klären müssen),
können wir also durch rekursive Anwendung dieser Zerlegung eine
n·n-Matrix in eine untere und eine obere Dreiecksmatrix zerlegen.
Wir müssen nur dafür sorgen, dass die Rekursion abbricht. Dazu behandeln wir
die 1·1-Matrizen separat: Jede 1·1-Matrix ist ja immer gleichzeitig eine
untere und auch eine obere Dreiecksmatrix, da sie nur aus der Hauptdiagonale
besteht.
Wir können dann einfach schreiben:
Diese Rekursion können wir nun fast direkt in eine mathGUIde-Funktion übernehmen. Die farbig unterlegten Programmzeilen entsprechen den farbigen Unterlegungen in den Formeln:
def luRecursive(A): n = A.height() if n == 1: # Rekursionsabbruch: 1·1-Matrix return Matrix.identity(1), A.copy() v = A.submatrix(1,0, n-1,1) w = A.submatrix(0,1, 1,n-1) A1 = A.submatrix(1,1, n-1,n-1) B = A1 - (1/A[0,0]) * v * w L1, U1 = luRecursive(B) # Rekursiver Aufruf für (n-1)·(n-1)-Matrix L_top = Matrix.identity(1).joinRight(Matrix.null(1,n-1)) L_btm = ((1/A[0,0]) * v).joinRight(L1) L = L_top.joinBottom(L_btm) U_top = A.submatrix(0,0, 1,1).joinRight(w) U_btm = Matrix.null(n-1,1).joinRight(U1) U = U_top.joinBottom(U_btm) return L,U
Wir testen den Algorithmus mit einer 3·3-Matrix:
A = Matrix.fromString("5,4,2; 1,9,7; 3,0,6") L, U = luRecursive(A) print(L, U)
Zur Kontrolle vergleichen wir nun die Originalmatrix mit dem Produkt der beiden Dreiecksmatrizen:
print(A, L*U)
Fortsetzung: 3. Umformung in eine Iteration