Linear Systems

LU Decomposition

Factor a matrix A into a lower triangular L and upper triangular U such that L·U = A. Example: A=[[2,1],[4,3]] gives L=[[1,0],[2,1]], U=[[2,1],[0,1]].

The multipliers L(i,j) = a(i,j) / U(j,j) are computed during forward elimination; the Schur complement gives U(i,i).

lu-decomposition LU decomposition factors A = L·U where L has ones on its diagonal and U is upper triangular.

Example

Factor a matrix into lower and upper triangular matrices.

highlighted = computed this step

Step 1 — Set up

Start with the matrix A.

A=[2143]A= \left[\begin{array}{cc}2&1\\4&3\end{array}\right]

Step 2 — First multiplier

Compute the first multiplier.

U11=2L21=4/2=2U_{11}= 2 \quad L_{21}= 4 / 2 = \hl{2}

Step 3 — Schur complement

Use the Schur complement for the lower-right entry.

U12=1U22=3−2⋅1=1U_{12}= 1 \quad U_{22}= 3 - 2 \cdot 1 = \hl{1}

Step 4 — Factors

Display the L and U factors.

L=[1021]U=[2101]L= \left[\begin{array}{cc}1&0\\\hlmath{2}&1\end{array}\right] \quad U= \left[\begin{array}{cc}2&1\\0&\hlmath{1}\end{array}\right]

Step 5 — Verify product

Multiply L and U to verify the entries.

LU=[2143]L U= \left[\begin{array}{cc}\hlmath{2}&\hlmath{1}\\\hlmath{4}&\hlmath{3}\end{array}\right]

Step 6 — Result

State that the product L U equals A.

A=LU[2143]A=L U \quad \left[\begin{array}{cc}\hlmath{2}&\hlmath{1}\\\hlmath{4}&\hlmath{3}\end{array}\right]