Differences between revisions 1 and 17 (spanning 16 versions)

LU Decomposition

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

Contents

LU Decomposition

Description

If a matrix A can be decomposed into lower and upper triangular matrices L and U, the system can generally be solved by:

Let y = Ux.
Reformulate the original system as Ly = b. This system's first equation simply states the value of y₁. The second equation gives y₂ in terms of y₁, which can be can be solved by substitution. And so on.
Solve for y.
Reformulate the original problem as Ux = y. As before, this system's last equation simply states the value of x_n. And so on.
Solve for x.

Furthermore, note that the inverse matrix A^-1 can be calculated as U^-1L^-1.

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 2026-01-07 01:54:41 by DominicRicottone)

-  ⇤ ← Revision 1 as of 2021-09-14 15:25:30 → 
  Size: 1185
  Editor: DominicRicottone
  Comment:
+   ← Revision 17 as of 2026-01-07 01:54:41 → ⇥
  Size: 3907
  Editor: DominicRicottone
  Comment: Details
-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 ==
+== Description ==
-Line 9:
+Line 13:
-Consider the below system of equations:
+If a matrix '''''A''''' can be decomposed into [[LinearAlgebra/SpecialMatrices#Lower_Triangular_Matrices|lower]] and [[LinearAlgebra/SpecialMatrices#Upper_Triangular_Matrices|upper triangular matrices]] '''''L''''' and '''''U''''', the system can generally be solved by:
 1. Let ''y = '''U'''x''.
 2. Reformulate the original system as '''''L'''y = b''. This system's first equation simply states the value of ''y,,1,,''. The second equation gives ''y,,2,,'' in terms of ''y,,1,,'', which can be can be solved by substitution. And so on.
 3. Solve for ''y''.
 4. Reformulate the original problem as '''''U'''x = y''. As before, this system's last equation simply states the value of ''x,,n,,''. And so on.
 5. Solve for ''x''.

Furthermore, note that the [[LinearAlgebra/Invertibility|inverse]] matrix '''''A'''^-1^'' can be calculated as '''''U'''^-1^'''L'''^-1^''.
-Line 12:
+Line 23:
-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 44:
+Note that `NoPivot()` must be specified because [[Julia]] wants to do a more efficient factorization.

----
-Line 19:
+Line 51:
-== Formulation ==
+== Computation of Elimination Matrices ==
-Line 21:
+Line 53:
-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 56:
-[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 63:
-This can instead be formulated in matrices:
+...into this:
-Line 32:
+Line 66:
-┌       ┐┌      ┐   ┌       ┐
│  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 73:
-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 75:
-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/Invertibility|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

Description

Computation of Elimination Matrices

Decomposition as LU