Crout’s Method

Definition

Crout’s Method is a specialized form of LU Decomposition used in numerical linear algebra to solve systems of linear equations. It decomposes a square matrix $A$ into the product of two matrices: a lower triangular matrix $L$ (where all diagonal elements are 1, and elements above the diagonal are 0) and an upper triangular matrix $U$ (where elements below the diagonal are 0).

Main Content

1. The LU Decomposition Foundation

Crout’s method is based on the principle that any square matrix $A$ can be represented as $A = LU$.
Unlike Doolittle’s method (where the diagonal of $L$ is 1), Crout’s method sets the diagonal of the $U$ matrix as arbitrary, while forcing the diagonal of the $L$ matrix to be 1.

2. Matrix Structure

The matrix $L$ is lower triangular with $1$s on the main diagonal.
The matrix $U$ is upper triangular.
The system $Ax = b$ becomes $LUx = b$, which is solved in two stages: $Ly = b$ (Forward substitution) and $Ux = y$ (Backward substitution).

3. Representation of Decomposition

The visual structure of the decomposition looks like this:

| a11 a12 a13 |   | 1    0    0   |   | u11 u12 u13 |
| a21 a22 a23 | = | l21  1    0   | * | 0   u22 u23 |
| a31 a32 a33 |   | l31  l32  1   |   | 0   0   u33 |

Working / Process

1. Decomposition of Matrix A

Set up the equations by multiplying $L$ and $U$ and equating the results to elements of $A$.
Calculate the elements of $U$ and $L$ column by column. The formula for $U$ elements is $u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj}$ for $i \leq j$.
The formula for $L$ elements is $l_{ij} = \frac{1}{u_{jj}} (a_{ij} - \sum_{k=1}^{j-1} l_{ik}u_{kj})$ for $i > j$.

2. Forward Substitution

Solve the system $Ly = b$ for $y$ using the lower triangular matrix $L$.
Since $L$ has $1$s on the diagonal, $y_1$ is simply $b_1$, and subsequent values are found easily: $y_i = b_i - \sum_{j=1}^{i-1} l_{ij}y_j$.

3. Backward Substitution

Solve the system $Ux = y$ for the final solution vector $x$.
Start from the last variable $x_n = y_n / u_{nn}$ and move upwards: $x_i = \frac{1}{u_{ii}} (y_i - \sum_{j=i+1}^{n} u_{ij}x_j)$.

Advantages / Applications

It is computationally efficient for solving systems of equations with the same coefficient matrix but different constant vectors ($b$).
It is significantly faster than calculating the inverse of a matrix, requiring approximately $2/3n^3$ operations.
It is widely used in engineering simulations, structural analysis, and finite element methods where large sparse matrices are common.

Summary

Crout’s method is an efficient numerical technique for solving systems of linear equations by decomposing a matrix $A$ into a unit lower triangular matrix $L$ and an upper triangular matrix $U$. By transforming the problem into two sequential steps—forward and backward substitution—it simplifies complex calculations into manageable linear operations. Important terms include LU Decomposition, Triangular Matrices, Forward Substitution, and Backward Substitution.