Differences between revisions 1 and 15 (spanning 14 versions)

LU Decomposition

LU decomposition is another approach to Gauss-Jordan elimination. It is generalized as A = LU.

Contents

LU Decomposition

Example

LU decomposition is a strategy for simplifying math with A.

julia> using LinearAlgebra

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> lu(A, NoPivot())
LU{Float64, Matrix{Float64}, Vector{Int64}}
L factor:
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 3.0  1.0  0.0
 0.0  2.0  1.0
U factor:
3×3 Matrix{Float64}:
 1.0  2.0   1.0
 0.0  2.0  -2.0
 0.0  0.0   5.0

Note that NoPivot() must be specified because Julia wants to do a more efficient factorization.

Computation of Elimination Matrices

Gauss-Jordan elimination 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 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.

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 as LU

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 lower triangular matrix. In this specific example, L = E_{2 1}^-1E_{3 2}^-1.

See below how E_{3 2}E_{2 1} is messier than E_{2 1}^-1E_{3 2}^-1 despite needing to compute inverses:

julia> E3_2 * E2_1
3×3 Matrix{Int64}:
  1   0  0
 -3   1  0
  6  -2  1

julia> convert(Matrix{Int64}, inv(E2_1) * inv(E3_2))
3×3 Matrix{Int64}:
 1  0  0
 3  1  0
 0  2  1

Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended.

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 15 as of 2024-01-29 03:13:41 → ⇥
  Size: 3111
  Editor: DominicRicottone
  Comment: Factorization
-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.
+'''''LU'' decomposition''' is another approach to [[LinearAlgebra/Elimination|Gauss-Jordan elimination]]. It is generalized as '''''A''' = '''LU'''''.

<<TableOfContents>>

----
-Line 7:
+Line 11:
-== Introduction ==
+== Example ==
-Line 9:
+Line 13:
-Consider the below system of equations:
+'''''LU''''' decomposition is a strategy for simplifying math with '''''A'''''.
-Line 12:
+Line 16:
-x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2
+julia> using LinearAlgebra

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> lu(A, NoPivot())
LU{Float64, Matrix{Float64}, Vector{Int64}}
L factor:
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 3.0  1.0  0.0
 0.0  2.0  1.0
U factor:
3×3 Matrix{Float64}:
 1.0  2.0   1.0
 0.0  2.0  -2.0
 0.0  0.0   5.0
-Line 16:
+Line 37:
+Note that `NoPivot()` must be specified because [[Julia]] wants to do a more efficient factorization.

----
-Line 19:
+Line 44:
-== Formulation ==
+== Computation of Elimination Matrices ==
-Line 21:
+Line 46:
-The first step of elimination involves the elimination of the cell at row 2 column 1 ''(henceforward cell '''(2,1)''')''.
+[[LinearAlgebra/Elimination|Gauss-Jordan elimination]] begins with identifying the pivot and transforming this:
-Line 24:
+Line 49:
-[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 56:
-This can instead be formulated in matrices:
+...into this:
-Line 32:
+Line 59:
-┌       ┐┌      ┐   ┌       ┐
│  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 66:
-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 transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices.
-Line 41:
+Line 68:
-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.
+{{{
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.

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 as LU ==

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]]:

{{{
julia> E3_2 * E2_1
3×3 Matrix{Int64}:
  1   0  0
 -3   1  0
  6  -2  1

julia> convert(Matrix{Int64}, inv(E2_1) * inv(E3_2))
3×3 Matrix{Int64}:
 1  0  0
 3  1  0
 0  2  1
}}}

Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended.

Diff for "LinearAlgebra/LUDecomposition"

LU Decomposition

Example

Computation of Elimination Matrices

Decomposition as LU