LU-Decomposition Row/Col-Pivot Solved by Substitution
Notes
| | Generate row transformations (Gaussian algorithm)
to convert A into an upper-right triangular matrix R.
Li is a matrix for row additions that generates zeros in column i of A. |
LE(A,i): generates elementary matrices for column i aki=0, k>i (zeros in column i below aii)
- performs a Gaussian elimination step for column i of matrix A
- Row operations summarized in matrix Li = Product( LE(A,i) ), i=1..3!
Pivot Search(Swapping rows and columns to do this) aii = element with the largest absolute value
SPvt(A,i) search for a column pivot
pi := PivotZ(A, i), qi := PivotS(A, i) complete pivot search across rows AND columns starting from row/column i
Pi = T(i, pi) - row-swap matrices for row i row pi (pivot) (Multiplication from the left)
Qi = T(i, qi) - column swap matrices for column i column qi (pivot) (Multiplication from the right)
Pivot Selection Button
Pivot := (2 Row/Column Pivot), (1 Column Pivot), ( 0 no pivot search - T(i,ki) = identity matrix )
If a pivot is deselected, the corresponding swap matrices T(i,ki) become the identity matrix.
(3)...(9) User functions for elementary matrices and pivot search
The row-swap matrices Pi = T(i, pi) and column-swap matrices Qi = T(i, qi) are self-inverse: T(i, j) T(i, j) = En!
Once R is computed (4x4 matrix),
R := (L3 P3 L2 P2 L1) P1 A (Q1 Q2 Q3)
requires an adjustment to the row swaps to ensure that the column permutation matrix P contains the matrices of all component steps.
P A Q → P3 P2 P1 A Q1 Q2 Q3
the exchange matrices Pi can be combined into P:
R = L3 || P3 L2 P3 || P3 P2 L1 P2 P3 || P3 P2 P1 || A || Q1 Q2 Q3 =
R = L3 || L2 || L1 || P || A || Q
R = (L3 L2 L1) P A Q L = (L3 L2 L1)-1
The self-inverse applications of the permutation matrices are highlighted in bold to summarize the row operations at the intermediate steps Ai in row correction into Li. In particular, the permutation matrices P and Q are orthogonal matrices, i.e., their inverses are their transposes: P-1 = PT and Q-1 = QT!
Insertion (RED = id)
→ Permutation matrices P arranged in the correct order, left hand of A!
Using the permutation matrix P and property of orthogonal matrices:
→ L := 2*Identity(5) - Product(Reverse({ L3 ,P3 ,L2 ,P2 ,L1 ,P2, P3 ,P4 })); 4x4
→L:=(2 identity(5) - P P1 L1 P2 L2 P3 L3 P4 L4 ); 5x5
L:=2*Identity(5) - Product(Reverse({ L4 ,P4 ,L3 ,P3 ,L2 ,P2 ,L1 ,P2, P3 ,P4 })); 5x5 German version 4x4 - Further information
