|
Size: 3569
Comment:
|
Size: 3526
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
<<TableOfContents>> ---- |
|
| Line 32: | Line 36: |
| ┌ ┐┌ ┐ ┌ ┐ │ 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│ └ ┘└ ┘ └ ┘ |
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 |
| Line 41: | Line 57: |
| 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. | Completing the elimination process: |
| Line 47: | Line 63: |
| }}} | |
| Line 48: | Line 65: |
| E E A = U 3,2 1,2 ┌ ┐┌ ┐┌ ┐ ┌ ┐ │ 1 0 0││ 1 0 0││ 1 2 1│ │ 1 2 1│ │ 0 1 0││ -3 1 0││ 3 8 1│ = │ 0 2 -2│ │ 0 -2 1││ 0 0 1││ 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. {{{ 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 56: | Line 80: |
---- |
|
| Line 105: | Line 131: |
| ---- |
Elimination Matrices
See Elimination for a walkthrough of elimination. This regards the computation of elimination matrices, which are a method of computing elimination.
Introduction
Consider the below system of equations:
x + 2y + z = 2 3x + 8y + z = 12 4y + z = 2
Formulation
The first step of elimination involves the elimination of the cell at row 2 column 1 (henceforward cell (2,1)).
[1] 2 1 [1] 2 1 3 8 1 -> 0 2 -2 0 4 1 0 4 1
This can instead be formulated in 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 is eliminated cell (2,1). An elimination matrix is always the identity matrix with the negative of the multiplier in the elimination position.
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 E3 2 (E2 1 A) = U. Note that this is equivalent to (E3 2 E2 1) A = U.
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
Factorization
It is preferable to refactor (E3 2 E2 1) A = U into A = L U. L can be trivially solved to be E2 1-1 E3 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
┌ ┐
-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 E3 2 E2 1 is messier than that of E2 1-1 E3 2-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│
└ ┘└ ┘ └ ┘In particular, cell (3,1) is a 0 in L but is 6 in E3 2 E2 1.
Permutation
If a zero pivot is reached, rows must be exchanged. This can be expressed with matrices as P A = L U.
See Permutation Matrices for more information on these matrices and their properties.