|
⇤ ← Revision 1 as of 2021-09-14 15:25:30
Size: 1185
Comment:
|
Size: 3300
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 39: | Line 39: |
| 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. | 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. |
| Line 42: | Line 42: |
{{{ [1] 2 1 [1] 2 1 0 [2] -2 -> 0 [2] -2 0 4 1 0 0 5 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│ └ ┘└ ┘└ ┘ └ ┘ }}} == Factorization == 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 {{{ ┌ ┐ -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^ {{{ 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 E,,3 2,, E,,2 1,,. |
Elimination Matrices
See LinearAlgebra/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:
┌ ┐┌ ┐ ┌ ┐ │ 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│ └ ┘└ ┘ └ ┘
This 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.
The full elimination process can be formulated as E3 2 (E2 1 A) = U. This is equivalent to (E3 2 E2 1) A = U.
[1] 2 1 [1] 2 1
0 [2] -2 -> 0 [2] -2
0 4 1 0 0 5
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│
└ ┘└ ┘└ ┘ └ ┘
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.