|
Size: 3526
Comment:
|
Size: 2975
Comment: Style and added links
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Elimination Matrices = | = LU Decomposition = |
| Line 3: | Line 3: |
| See [[LinearAlgebra/Elimination|Elimination]] for a walkthrough of '''elimination'''. This regards the computation of '''elimination matrices''', which are a method of computing elimination. | '''''LU'' decomposition''' is another approach to [[LinearAlgebra/Elimination|Gauss-Jordan elimination]]. It is generalized as '''''A''' = '''LU'''''. |
| Line 11: | Line 11: |
| == Introduction == | == Elimination Matrices == |
| Line 13: | Line 13: |
| Consider the below system of equations: | Using the same problem as seen [[LinearAlgebra/Elimination#Introduction|here]]: |
| Line 21: | Line 21: |
== Formulation == The first step of elimination involves the elimination of the cell at row 2 column 1 ''(henceforward cell '''(2,1)''')''. |
The Gauss-Jordan approach begins with identifying the pivot and transforming this: |
| Line 28: | Line 24: |
| [1] 2 1 [1] 2 1 3 8 1 -> 0 2 -2 0 4 1 0 4 1 |
┌ ┐ │ [1] 2 1│ │ 3 8 1│ │ 0 4 1│ └ ┘ |
| Line 33: | Line 31: |
| This can instead be formulated in matrices: | ...into this: {{{ ┌ ┐ │ [1] 2 1│ │ 0 2 -2│ │ 0 4 1│ └ ┘ }}} This transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices. |
| Line 55: | Line 63: |
| This elimination matrix is called E,,2 1,, because is eliminated cell (2,1). An elimination matrix is always the identity matrix with the negative of the multiplier in the elimination position. | This '''elimination matrix''' is called '''''E''',,2 1,,'' because it eliminated cell (2,1), the '''elimination cell'''. An elimination matrix is always the [[LinearAlgebra/SpecialMatrices#Identity_Matrix|identity matrix]] with the negated multiplier in the elimination cell. |
| Line 57: | Line 65: |
| Completing the elimination process: {{{ [1] 2 1 [1] 2 1 0 [2] -2 -> 0 [2] -2 0 4 1 0 0 5 }}} This can be formulated as E,,3 2,, (E,,2 1,, A) = U. Note that this is equivalent to (E,,3 2,, E,,2 1,,) A = U. |
The Gauss-Jordan approach continues with subtracting two of row 2 from row 3. Formulated as matrices instead: |
| Line 85: | Line 85: |
| == Factorization == | == Decomposition == |
| Line 87: | Line 87: |
| It is preferable to refactor (E,,3 2,, E,,2 1,,) A = U into A = L U. L can be trivially solved to be E,,2 1,,^-1^ E,,3 2,,^-1^. Furthermore, because elimination matrices are modifications of the inverse matrix, their inverses are also trivial to solve. Note that these are simply the identity matrix with the (normal, non-negative) multiplier in the elimination position | In this specific example, elimination can be written out as ''('''E''',,3 2,,'''E''',,2 1,,)'''A''' = '''U'''''. A preferable form is '''''A''' = '''LU''''', where '''''L''''' takes on the role of all elimination matrices. '''''L''''' may be a [[LinearAlgebra/SpecialMatrices#Lower_Triangular_Matrices|lower triangular matrix]]. In this specific example, '''''L''' = '''E''',,2 1,,^-1^'''E''',,3 2,,^-1^''. See below how '''''E''',,3 2,,'''E''',,2 1,,'' is messier than '''''E''',,2 1,,^-1^'''E''',,3 2,,^-1^'' despite needing to compute [[LinearAlgebra/MatrixInversion|inverses]]: |
| Line 90: | Line 94: |
| ┌ ┐ -1 │ 1 0 0│ E E = │ 0 1 0│ 2,3 2,3 │ 0 0 1│ └ ┘ ┌ ┐ ┌ ┐ │ 1 0 0│ -1 │ 1 0 0│ │ -3 1 0│ E = │ 0 1 0│ │ 0 0 1│ 2,3 │ 0 0 1│ └ ┘ └ ┘ ┌ ┐ -1 │ 1 0 0│ E = │ 3 1 0│ 2,3 │ 0 0 1│ └ ┘ }}} The fundamental reason for factorization is that the singular product of E,,3 2,, E,,2 1,, is messier than that of E,,2 1,,^-1^ E,,3 2,,^-1^ {{{ |
|
| Line 129: | Line 112: |
| In particular, cell (3,1) is a 0 in L but is 6 in E,,3 2,, E,,2 1,,. ---- == Permutation == If a zero pivot is reached, rows must be exchanged. This can be expressed with matrices as P A = L U. See [[LinearAlgebra/PermutationMatrices|Permutation Matrices]] for more information on these matrices and their properties. |
Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended. |
LU Decomposition
LU decomposition is another approach to Gauss-Jordan elimination. It is generalized as A = LU.
Elimination Matrices
Using the same problem as seen here:
x + 2y + z = 2 3x + 8y + z = 12 4y + z = 2
The Gauss-Jordan approach begins with identifying the pivot and transforming this:
┌ ┐ │ [1] 2 1│ │ 3 8 1│ │ 0 4 1│ └ ┘
...into this:
┌ ┐ │ [1] 2 1│ │ 0 2 -2│ │ 0 4 1│ └ ┘
This transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices.
julia> A = [1 2 1; 3 8 1; 0 4 1]
3×3 Matrix{Int64}:
1 2 1
3 8 1
0 4 1
julia> E2_1 = [1 0 0; -3 1 0; 0 0 1]
3×3 Matrix{Int64}:
1 0 0
-3 1 0
0 0 1
julia> E2_1 * A
3×3 Matrix{Int64}:
1 2 1
0 2 -2
0 4 1This elimination matrix is called E2 1 because it eliminated cell (2,1), the elimination cell. An elimination matrix is always the identity matrix with the negated multiplier in the elimination cell.
The Gauss-Jordan approach continues with subtracting two of row 2 from row 3. Formulated as matrices instead:
julia> E3_2 = [1 0 0; 0 1 0; 0 -2 1]
3×3 Matrix{Int64}:
1 0 0
0 1 0
0 -2 1
julia> E3_2 * E2_1 * A
3×3 Matrix{Int64}:
1 2 1
0 2 -2
0 0 5
Decomposition
In this specific example, elimination can be written out as (E3 2E2 1)A = U.
A preferable form is A = LU, where L takes on the role of all elimination matrices. L may be a lower triangular matrix. In this specific example, L = E2 1-1E3 2-1.
See below how E3 2E2 1 is messier than E2 1-1E3 2-1 despite needing to compute inverses:
E E = ?
3,2 2,1
┌ ┐┌ ┐ ┌ ┐
│ 1 0 0││ 1 0 0│ │ 1 0 0│
│ 0 1 0││ -3 1 0│ = │ -3 1 0│
│ 0 -2 1││ 0 0 1│ │ 6 -2 1│
└ ┘└ ┘ └ ┘
-1 -1
E E = L
2,1 3,2
┌ ┐┌ ┐ ┌ ┐
│ 1 0 0││ 1 0 0│ │ 1 0 0│
│ 3 1 0││ 0 1 0│ = │ 3 1 0│
│ 0 0 1││ 0 2 1│ │ 0 2 1│
└ ┘└ ┘ └ ┘Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended.