Tools

LU Decomposition

LU decomposition is a method of factoring a square matrix \( A \) into the product of a lower triangular matrix \( L \) and an upper triangular matrix \( U \). It is a fundamental technique in linear algebra that simplifies:

  • Solving systems of linear equations \( Ax = b \) efficiently
  • Computing determinants, since \(\det(A) = \det(L) \cdot \det(U)\)
  • Inverting matrices, since triangular matrices are easier to invert

Mathematically, for a square matrix \( A \in \mathbb{R}^{n \times n} \), LU decomposition finds matrices \( L \) and \( U \) such that:

\( A = L \cdot U \)

Where:

  • \( L \) is a lower triangular matrix with ones on the diagonal (unit lower triangular), and entries below the diagonal representing elimination multipliers.
  • \( U \) is an upper triangular matrix containing the resulting pivots after Gaussian elimination.

Pivot: In LU decomposition, a pivot is the number in the matrix used to eliminate other numbers in the same column during the elimination process. It is usually chosen from the diagonal of the current column. Picking a pivot with a larger value helps avoid errors in calculations. If the pivot is zero or too small, the rows of the matrix can be swapped to select a better pivot. This process, called pivoting, ensures that the decomposition works correctly and calculations remain accurate.

Example

Matrix A

\( A = \begin{bmatrix} 2 & 4 & 3 & 5 \\ -4 & -7 & -5 & -8 \\ 6 & 8 & 2 & 9 \\ 4 & 9 & -2 & 14 \end{bmatrix} \)

Step 1: First Column Elimination

We start with the first pivot element (2 in row 1) and eliminate all entries below it using appropriate multipliers. Each multiplier is stored in the corresponding position in L:

  • \( R_2 \leftarrow R_2 - (-4/2) \cdot R_1 = R_2 + 2 \cdot R_1 \) → Multiplier = -2 → stored in L(2,1)
  • \( R_3 \leftarrow R_3 - (6/2) \cdot R_1 = R_3 - 3 \cdot R_1 \) → Multiplier = 3 → stored in L(3,1)
  • \( R_4 \leftarrow R_4 - (4/2) \cdot R_1 = R_4 - 2 \cdot R_1 \) → Multiplier = 2 → stored in L(4,1)

Note on R1, R2, R3, ...: These represent the rows of the matrix. Row operations update U and fill L with multipliers.

Updated upper triangular matrix U:

\( U_1 = \begin{bmatrix} 2 & 4 & 3 & 5 \\ 0 & 1 & 1 & 2 \\ 0 & -4 & -7 & -6 \\ 0 & 1 & -8 & 4 \end{bmatrix} \)

Partial lower triangular matrix L:

\( L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \end{bmatrix} \)

Step 2: Second Column Elimination

Pivot element: 1 (row 2, column 2). Eliminate entries below pivot in column 2:

  • \( R_3 \leftarrow R_3 - (-4/1) \cdot R_2 = R_3 + 4 \cdot R_2 \) → Multiplier = -4 → stored in L(3,2)
  • \( R_4 \leftarrow R_4 - (1/1) \cdot R_2 = R_4 - 1 \cdot R_2 \) → Multiplier = 1 → stored in L(4,2)

Updated U:

\( U_2 = \begin{bmatrix} 2 & 4 & 3 & 5 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & -3 & 2 \\ 0 & 0 & -9 & 2 \end{bmatrix} \)

Updated L:

\( L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & -4 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{bmatrix} \)

Step 3: Third Column Elimination

Pivot element: -3 (row 3, column 3). Eliminate entry below pivot:

  • \( R_4 \leftarrow R_4 - (-9/-3) \cdot R_3 = R_4 - 3 \cdot R_3 \) → Multiplier = 3 → stored in L(4,3)

Final upper triangular matrix U:

\( U = \begin{bmatrix} 2 & 4 & 3 & 5 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & -3 & 2 \\ 0 & 0 & 0 & -4 \end{bmatrix} \)

Final lower triangular matrix L (all multipliers included, diagonal = 1):

\( L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & -4 & 1 & 0 \\ 2 & 1 & 3 & 1 \end{bmatrix} \)

Step 4: Example Solving \( Ax = b \)

Let’s solve \( Ax = b \) with:

\( b = \begin{bmatrix} 3 \\ -1 \\ -5 \\ 20 \end{bmatrix} \)

Step 4a: Forward Substitution (\( Ly = b \))

We solve for \( y \) using the lower triangular matrix L:

\( L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & -4 & 1 & 0 \\ 2 & 1 & 3 & 1 \end{bmatrix}, \quad Ly = b \)

Row by row:

  • \( y_1 = b_1 / L_{11} = 3 / 1 = 3 \)
  • \( y_2 = b_2 - L_{21} y_1 = -1 - (-2)(3) = -1 + 6 = 5 \)
  • \( y_3 = b_3 - L_{31} y_1 - L_{32} y_2 = -5 - (3)(3) - (-4)(5) = -5 - 9 + 20 = 6 \)
  • \( y_4 = b_4 - L_{41} y_1 - L_{42} y_2 - L_{43} y_3 = 20 - (2)(3) - (1)(5) - (3)(6) = 20 -6 -5 -18 = -9 \)
\( y = \begin{bmatrix} 3 \\ 5 \\ 6 \\ -9 \end{bmatrix} \)

Step 4b: Backward Substitution (\( Ux = y \))

Now solve for \( x \) using upper triangular matrix U:

\( U = \begin{bmatrix} 2 & 4 & 3 & 5 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & -3 & 2 \\ 0 & 0 & 0 & -4 \end{bmatrix}, \quad Ux = y \)

Start from last row upward:

  • \( x_4 = y_4 / U_{44} = -9 / (-4) = 2.25 \)
  • \( x_3 = (y_3 - U_{34} x_4) / U_{33} = (6 - 2*2.25)/(-3) = (6 -4.5)/(-3) = 1.5/-3 = -0.5 \)
  • \( x_2 = (y_2 - U_{23} x_3 - U_{24} x_4) / U_{22} = (5 - 1*(-0.5) - 2*2.25)/1 = (5 +0.5 -4.5)/1 = 1 \)
  • \( x_1 = (y_1 - U_{12} x_2 - U_{13} x_3 - U_{14} x_4)/U_{11} = (3 -4*1 -3*(-0.5) -5*2.25)/2 = (3 -4 +1.5 -11.25)/2 = (-10.75)/2 = -5.375 \)
\( x = \begin{bmatrix} -5.375 \\ 1 \\ -0.5 \\ 2.25 \end{bmatrix} \)

Thus, the solution \( x \) satisfies \( Ax = b \) using LU decomposition efficiently, without computing the inverse of A.