Differences between revisions 1 and 8 (spanning 7 versions)

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

LU Decomposition

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 E_{2 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 (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:

   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│
└      ┘└      ┘   └      ┘

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)

-  ⇤ ← Revision 1 as of 2021-09-14 15:25:30 → 
  Size: 1185
  Editor: DominicRicottone
  Comment:
+   ← Revision 8 as of 2023-07-09 04:25:47 → ⇥
  Size: 3724
  Editor: DominicRicottone
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-= Elimination Matrices =
+= LU Decomposition =
 Line 3:
-See [[LinearAlgebra/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'''.

<<TableOfContents>>

----
-Line 7:
+Line 11:
-== Introduction ==
+== Linear Algebra ==
-Line 17:
+Line 21:
+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 ''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.

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
}}}

----
-Line 19:
+Line 81:
-== Formulation ==
-Line 21:
+Line 82:
-The first step of elimination involves the elimination of the cell at row 2 column 1 ''(henceforward cell '''(2,1)''')''.
+== Simplification with Factorization ==

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 24:
+Line 91:
-[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 109:
-This can instead be formulated in matrices:
+This does introduce a step of calculating [[LinearAlgebra/MatrixInversion|inverses]] of the elimination matrices, but this is categorically simple to do.
-Line 32:
+Line 112:
-┌       ┐┌      ┐   ┌       ┐
│  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│
└       ┘└      ┘   └       ┘
+            -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 39:
+Line 132:
-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 134:
-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.
+== Permutation ==

If a zero pivot is reached, rows must be exchanged. This can be expressed with matrices as P A = L U.

See [[LinearAlgebra/PermutationMatrices|Permutation Matrices]] for more information on these matrices and their properties.

Diff for "LinearAlgebra/LUDecomposition"

LU Decomposition

Linear Algebra

Simplification with Factorization

Permutation