|
Size: 3890
Comment: Fixed link
|
Size: 2975
Comment: Style and added links
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| A fundamental step to solving systems of equation is [[LinearAlgebra/Elimination|elimination]]. A mathematical approach grounded in the same methods, but further generalized for automated compuation, is '''LU Decomposition'''. | '''''LU'' decomposition''' is another approach to [[LinearAlgebra/Elimination|Gauss-Jordan elimination]]. It is generalized as '''''A''' = '''LU'''''. |
| Line 11: | Line 11: |
| == Linear Algebra == | == 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: |
| The normal step of elimination proceeds like: | The Gauss-Jordan approach begins with identifying the pivot and transforming this: |
| Line 29: | Line 29: |
| }}} ...into this: {{{ |
|
| Line 36: | Line 41: |
| Critically, note that this elimination step involved subtracting 3 of row 1 from row 2. This can instead be formulated with matrices: |
This transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices. |
| Line 60: | Line 63: |
| 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. | 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 62: | Line 65: |
| Note that the next elimination step will involve subtracting 2 of row 2 from row 3, to the effect of eliminating cell (3,2). Therefore: | The Gauss-Jordan approach continues with subtracting two of row 2 from row 3. Formulated as matrices instead: |
| Line 82: | Line 85: |
| == Simplification with Factorization == | == Decomposition == |
| Line 84: | Line 87: |
| It is generally advantageous to refactor ''(E,,3 2,, E,,2 1,,) A = U'' into ''A = L U'', where ''L'' takes on the role of all elimination matrices. The notation ''L'' is a parallelism to the ''U'' notation for '''upper triangle matrices'''; ''L'' will be a '''lower triagle matrix'''. | In this specific example, elimination can be written out as ''('''E''',,3 2,,'''E''',,2 1,,)'''A''' = '''U'''''. |
| Line 86: | Line 89: |
| ''L'' can be trivially solved to be ''E,,2 1,,^-1^ E,,3 2,,^-1^''. | 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^''. |
| Line 88: | Line 91: |
| As a demonstration of how ''E,,3 2,, E,,2 1,,'' is messier than ''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 109: | Line 112: |
| Furthermore, additional elimination matrices had to be prepended to the previous computation. With this factorization, they instead are appended. This does introduce a step of calculating [[LinearAlgebra/MatrixInversion|inverses]] of the elimination matrices, but this is categorically simple to do. {{{ -1 E E = I 2,3 2,3 ┌ ┐ -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│ └ ┘ }}} ---- == Permutation == If a zero pivot is reached, rows must be exchanged. This can be expressed with matrices as P A = L U. See [[LinearAlgebra/SpecialMatrices#Permutation_Matrices|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.