LR-Zerlegung mit Pivotsuche (vollständig/teilweise) R4
Hinweise
==>
LE(A,i): generiert Elementar-Matrizen für Spalte i ==> aki=0, k>i (0en Spalte i unterhalb aii)
- setzt einen Gauß-Eliminationsschritt für eine Spalte i der Matrix A um -
Zeilenoperation in Matrix Li = Product( LE(A,i) ) zusammengefasst!
Pivotsuche(Zeilen- und Spaltentausch damit) aii = betragsgrößtes Element
SPvt(A,i) suche Spalten-Pivot
pi:=PivotZ(A,i), qi:=PivotS(A,i) vollständige Pivotsuche über Zeilen UND Spalten ab Zeile/Spalte i
Pi=T(i ,pi ) - Zeilentausch-Matrizen für Zeile i <> Zeile pi (Pivot) (Multiplikation von Links)
Qi=T(i ,qi ) - Spaltentausch-Matrizen Spalte i <> Spalte qi (Pivot) (Multiplikation von Rechts)
Schalter für Pivot-Wahl
Pivot:= (2 Zeilen/Spalten-Pivot), (1 Spalten-Pivot), ( 0 ohne Pivot-Suche - T(i,ki)=Einheitsmatrix )
Wenn ein Pivot abgewählt wird werden die entsprechenden Tauschmatrizen T(i,ki) zur Einheitsmatrix.
(3)...(9) User-Funktionen für Elementarmatrizen und Pivotsuche
Die Zeilentausch-Matrizen Pi=T(i,pi) und Spaltentausch-Matrizen Qi=T(i,qi) sind Selbstinvers T(i, j) T(i, j) = En! Wenn R berechnet ist,
(25) R:=(L3 P3 L2 P2 L1) P1 A (Q1 Q2 Q3)
muss ein Abgleich der Zeilen/Spalten-Austausche eingefügt werden,
R = L' P A Q L'-1R = P A Q , L = L'-1
damit die Zeilen/Spaltenabfolge in L R zu P A Q → P3 P2 P1 A Q1 Q2 Q 3 passt,
die Tauschmatrizen Pi zu P zusammengefasst werden können:
R= L3 || P3 L2 P3 || P3 P2 L1 P2 P3 || P3 P2 P1 || A || Q1 Q2 Q3 =
R= L3 || L2 || L1 || P || A || Q
In Fettschrift ausgezeichnet die selbstinversen Einsätze der Tauschmatrizen um die Zeilenoperationen an den Zwischenschritten Ai in Zeilen/Spalten-Korrekt zusammen zu fassen in Li. Insbesondere sind die Tauschmatrizen und P,Q orthogonale Matrizen, d.h. die Inverse=Transponiert: P-1= PT bzw. Q-1= QT !
(26) Einschub(ROT=id )
→ Permutationsmatrizen P in der richtigen Reihenfolge vor A angeordnet!
Unter Verwendung der Permutationsmatrix P
→ L:=Transpose(L3 P3 L2 P2 L1 P1 Transpose(P))
| | Generiere Zeilenumformungen (Gauß-Algorithmus) um A in eine rechte obere Dreiecksmatrix R zu überführen. Li Matrix für Zeilenadditionen die in A Spalte i 0en erzeugt. |
ElementarMatrizen LR-AllPivotMx
A:={{1, 3, -1 },{2, 5, -1 }, {-1, -6, 3 }}
ggf. wollen Sie auf die Pivotsuchfunktionen verzichten und die Pivotauswahl pi,qi von Hand setzen z.B. P1:=T(1,2),Q1:=T(1,4).
A x = b ===> L R = P A ===> P A x = P b ===> L R x = P b
---
a(i,k):=Sum(Element(L, i, j) Element(R, j,k) , j,1,k)
---
| LR Zerlegung mit Spaltenpivot R3 | LR Zerlegung mit Totalpivot R3 | |
p1:=SPvt(A,1)
P1:=T(1,p1)
A1:=P1 A
L1:=Product(LE(A1,1))
A2:=L1 P1 A
p2:=SPvt(A2,2)
P2:=T(2, p2)
L2:=Product(LE(P2 A2 ,2))
R:=(L2 P2 L1) (P1 A)
"L2 || P2 L1 P2 || P2 P1 A"
L:= L2 P2 L1 P2)^-1
P:= P2 P1
| p1:=PivotZ(A, 1) || q1:=PivotS(A,1)
P1:=T(1,p1) || Q1:=[code]T(1,q1)
A1:=P1 A Q1
L1:=Product(LE(A1,1))
A2:=L1 P1 A Q1
p2:=PivotZ(A2, 2) || q2:=PivotS(A2,2)
P2:=T(2,p2) || Q2:=T(2,q2)
L2:=Product(LE(P2 A2 Q2,2 ))
R:= L2 P2 L1 P1 A Q1 Q2
L:=(L2 P2 L1 (P2))^-1
P:=(P2) P1
Q:=Q1 Q2
| |
L R x = P b
| L R Q^T x = P b
| |
| L y = P b R x = y | L y =P b R QT x = y | |
Arbeits-Vorlage
LR Zerlegung R³ - LU decomposition solve linear equations
LR Zerlegung R4x4 - LU decomposition solve linear equations
Rechnen auf einem Matrixfeld
Aus einer Matrix
generiere ich die Gaußelimationsfaktoren für L1 aus der 1. Spalte
dividiere durch a11, alle Faktoren mal (-1) (alles unter a11) und fülle zur Einheitsmatix auf.
In der 1. Spalte stehen die Faktoren mit denen die 1.Zeile multipliziert wird. Um dann per Matrixprodukt zur Faktorzeile addiert zu werden. Alle Zeilen 2,3,4..n werden geändert mit Nullen in der ersten Spalte. Da ist jetzt Platz um die Eliminationsfaktoren zu parken. Da quasi die Inverse für L benötigt wird, machen wir den Faktor (-1) rückgängig beim Eintrag in das Matrixfeld LR:
Wiederhole Algorithmus auf der Matrix (cij)
Wiederhole Algorithmus auf Matric (uij)
Die Koeffizienen bilden die obere Dreiecksmatrix R und untere Dreiecksmatrix L ergänzt um die Diagonale {1,1,1,1}. Zeilen-Tauschmatrizen Pi zur Pivotsuche in den Einzelschritten müssen natürlich auch auf LR angewendet werden (Li Pi => Pi LR).
In dieser Form wird die Verwaltung der Zeilen/Spaltentausche wesentlich einfacher, oder?