Differences between revisions 5 and 12 (spanning 7 versions)
⇤ ← Revision 5 as of 2023-07-03 05:09:15 →
Size: 3526
Editor: DominicRicottone
Comment:
← Revision 12 as of 2024-01-21 17:53:30 → ⇥
Size: 3890
Editor: DominicRicottone
Comment: Fixed link
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. 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'''.
Line 11: Line 11:
== Introduction == == Linear Algebra ==
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 normal step of elimination proceeds like:
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│
└ ┘
┌ ┐
│ [1] 2 1│
│ 0 2 -2│
│ 0 4 1│
└ ┘
Line 33: Line 36:
This can instead be formulated in matrices: Critically, note that this elimination step involved subtracting 3 of row 1 from row 2.

This can instead be formulated with matrices:
Line 55: Line 60:
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 62:
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.		 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:
Line 85: Line 82:
== Factorization == == Simplification with Factorization ==
Line 87: Line 84:
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 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'''.

''L'' can be trivially solved to be ''E,,2 1,,^-1^ E,,3 2,,^-1^''.

As a demonstration of how ''E,,3 2,, E,,2 1,,'' is messier than ''E,,2 1,,^-1^ E,,3 2,,^-1^'':
Line 90: Line 91:
                  ┌ ┐
            -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 109:
In particular, cell (3,1) is a 0 in L but is 6 in E,,3 2,, E,,2 1,,. 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│
                  └ ┘
}}}
Line 139: Line 142:
See [[LinearAlgebra/PermutationMatrices|Permutation Matrices]] for more information on these matrices and their properties. See [[LinearAlgebra/SpecialMatrices#Permutation_Matrices|Permutation Matrices]] for more information on these matrices and their properties.

LU Decomposition

A fundamental step to solving systems of equation is elimination. A mathematical approach grounded in the same methods, but further generalized for automated compuation, is LU Decomposition.

Contents

  1. LU Decomposition
    1. Linear Algebra
    2. Simplification with Factorization
    3. Permutation

Linear Algebra

Consider the below system of equations: 

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

The normal step of elimination proceeds like: 

┌        ┐
│ [1] 2 1│
│  3  8 1│
│  0  4 1│
└        ┘
┌         ┐
│ [1] 2  1│
│  0  2 -2│
│  0  4  1│
└         ┘

Critically, note that this elimination step involved subtracting 3 of row 1 from row 2.

This can instead be formulated 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 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.

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: 

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

Simplification with Factorization

It is generally advantageous to refactor (E3 2 E2 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.

L can be trivially solved to be E2 1-1 E3 2-1.

As a demonstration of how E3 2 E2 1 is messier than 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│
└      ┘└      ┘   └      ┘

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 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 Permutation Matrices for more information on these matrices and their properties.

CategoryRicottone

LinearAlgebra/LUDecomposition (last edited 2024-01-29 03:13:41 by DominicRicottone)