Differences between revisions 3 and 13 (spanning 10 versions)
⇤ ← Revision 3 as of 2022-03-19 20:58:04 →
Size: 3312
Editor: DominicRicottone
Comment:
← Revision 13 as of 2024-01-27 20:35:43 → ⇥
Size: 2975
Editor: DominicRicottone
Comment: Style and added links
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. '''''LU'' decomposition''' is another approach to [[LinearAlgebra/Elimination|Gauss-Jordan elimination]]. It is generalized as '''''A''' = '''LU'''''.

<<TableOfContents>>

----
Line 7: Line 11:
== Introduction == == Elimination Matrices ==
Line 9: Line 13:
Consider the below system of equations: Using the same problem as seen [[LinearAlgebra/Elimination#Introduction|here]]:
Line 17: Line 21:


== Formulation ==

The first step of elimination involves the elimination of the cell at row 2 column 1 ''(henceforward cell '''(2,1)''')''.		 The Gauss-Jordan approach begins with identifying the pivot and transforming this:
Line 24: 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│
└ ┘
Line 29: Line 31:
This can instead be formulated in matrices: ...into this:
Line 32: Line 34:
┌      ┐┌ ┐ ┌ ┐
│  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] 2 1│
│ 0 2 -2│
│ 0 4 1│
└ ┘
Line 39: Line 41:
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.

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.		 This transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices.
Line 44: Line 44:
[1] 2 1 [1] 2 1
 0 [2] -2 -> 0 [2] -2
 0 4 1 0 0 5		 julia> A = [1 2 1; 3 8 1; 0 4 1]
3×3 Matrix{Int64}:
 1 2 1
 3 8 1
 0 4 1
Line 48: Line 50:
   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│
└ ┘└ ┘└ ┘ └ ┘		 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 56: Line 62:

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.

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

----
Line 59: Line 85:
== Factorization == == Decomposition ==
Line 61: Line 87:
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 In this specific example, elimination can be written out as ''('''E''',,3 2,,'''E''',,2 1,,)'''A''' = '''U'''''.

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^''.

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 64: Line 94:
                  ┌ ┐
            -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 103: Line 112:
In particular, cell (3,1) is a 0 in L but is 6 in E,,3 2,, E,,2 1,,. 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.

Contents

  1. LU Decomposition
    1. Elimination Matrices
    2. Decomposition

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

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.

CategoryRicottone

LinearAlgebra/LUDecomposition (last edited 2026-01-07 01:54:41 by DominicRicottone)