|
Size: 1185
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]] 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'''''. <<TableOfContents>> ---- |
| Line 7: | Line 11: |
| == Introduction == | == Elimination Matrices == |
| Line 9: | Line 13: |
| Consider the below system of equations: | Using the same problem as seen [[LinearAlgebra/Elimination#Introduction|here]]: |
| Line 17: | Line 21: |
| 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 1 }}} 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. 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 }}} ---- |
|
| Line 19: | Line 84: |
| == Formulation == | |
| Line 21: | Line 85: |
| The first step of elimination involves the elimination of the cell at row 2 column 1 ''(henceforward cell '''(2,1)''')''. | == Decomposition == 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 24: | Line 94: |
| [1] 2 1 [1] 2 1 3 8 1 -> 0 2 -2 0 4 1 0 4 1 |
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│ └ ┘└ ┘ └ ┘ |
| Line 29: | Line 112: |
| This can instead be formulated in matrices: | Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended. |
| Line 31: | Line 114: |
| {{{ ┌ ┐┌ ┐ ┌ ┐ │ 1 0 0││ 1 2 1│ │ 1 2 1│ │ -3 1 0││ 3 8 1│ = │ 0 2 -2│ │ 0 0 1││ 0 4 1│ │ 0 4 1│ └ ┘└ ┘ └ ┘ }}} |
|
| Line 39: | Line 115: |
| This elimination matrix is called E,,2 1,, because is eliminated cell (2,1). An elimination matrix is always the identity matric with the negative of the multiplier in the elimination position. | |
| Line 41: | Line 116: |
| The full elimination process can be formulated as E,,3 2,, (E,,2 1,, A) = U. This is equivalent to (E,,3 2,, E,,2 1,,) A = U. |
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.