LU Decomposition using Crout’s Method

LU Decomposition using Crout’s Method

Procedure-

1. Choose a matrix (m X n) (e.g., 3X 3, 3 X 4, 4 X 4, etc.,)

2. The Crout’s matrix decomposition algorithm differs slightly from the Doolittle method. Doolittle's method returns a unit lower triangular matrix and an upper triangular matrix, while the Crout’s method returns a lower triangular matrix and a unit upper triangular matrix.

3. Initialize the L and U matrices. L matrix size will be (m X m). The values of matrix elements below the main diagonal can be assigned to l₂₁, l₃₁, etc., and so on. And the matrix elements above the diagonal are zeroes.

$$\ \begin{bmatrix} l11 & 0 & 0 & 0 \\ l21 & l22 & 0 & 0 \\ l31 & l32 & l33 & 0 \\ l41 & l42 & l43 & l44 \end{bmatrix} $$

l₂₁, l₃₁, etc. are unknown

4. For matrix U, take a matrix with all diagonal elements assigned to 1, and the matrix elements below the diagonal are zeroes. Size of matrix U will be as same as matrix A (or, m X n). Matrix U can be written as

$$\begin{bmatrix} 1 & u12 & u13 & u14 \\ 0 & 1 & u23 & u24 \\ 0 & 0 & 1 & u34 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

u₁₁, u₁₂, u₁₃, u₁₄, u₂₂, etc. are unknown.

5. For a given example,

$$\mathbf{A\ =}\begin{bmatrix} \mathbf{1} & \mathbf{2} & \mathbf{3} \\ \mathbf{2} & \mathbf{5} & \mathbf{2} \\ \mathbf{3} & \mathbf{2} & \mathbf{5} \end{bmatrix}$$

Now, $\begin{bmatrix} \mathbf{1} & \mathbf{2} & \mathbf{3} \\ \mathbf{2} & \mathbf{5} & \mathbf{2} \\ \mathbf{3} & \mathbf{2} & \mathbf{5} \end{bmatrix}$= L * U = $\begin{bmatrix} \mathbf{l}\mathbf{11} & \mathbf{0} & \mathbf{0} \\ \mathbf{l}\mathbf{21} & \mathbf{l}\mathbf{22} & \mathbf{0} \\ \mathbf{l}\mathbf{31} & \mathbf{l}\mathbf{32} & \mathbf{l}\mathbf{33} \end{bmatrix}$ * $\begin{bmatrix} \mathbf{1} & \mathbf{u}\mathbf{12} & \mathbf{u}\mathbf{13} \\ \mathbf{0} & \mathbf{1} & \mathbf{u}\mathbf{23} \\ \mathbf{0} & \mathbf{0} & \mathbf{1} \end{bmatrix}$

=$\mathbf{\ }\begin{bmatrix} \mathbf{l}\mathbf{11} & \mathbf{(l}\mathbf{11*u}\mathbf{12)} & \mathbf{(l}\mathbf{11*u}\mathbf{13)} \\ \mathbf{l}\mathbf{21} & \mathbf{(l}\mathbf{21*u}\mathbf{12 + l}\mathbf{22)} & \mathbf{(l}\mathbf{21*u}\mathbf{13 + l}\mathbf{22*u}\mathbf{23)} \\ \mathbf{l}\mathbf{31} & \mathbf{(l}\mathbf{31*u}\mathbf{12}\mathbf{+ l}\mathbf{32)} & \mathbf{(l}\mathbf{31*u}\mathbf{13 + l}\mathbf{32*u}\mathbf{23 + l}\mathbf{33)} \end{bmatrix}$

Next, resolve the basic matrix multiplication equations from above,

l₁₁ = 1

l₁₁*u₁₂ = 2

l₁₁*u₁₃ = 3

l₂₁ = 2

l₂₁*u₁₂+l₂₂ = 5

l₂₁*u₁₃+l₂₂*u₂₃ = 2

l₃₁ = 3

l₃₁*u₁₂+l₃₂ = 2

l₃₁*u₁₃+l₃₂*u₂₃+l₃₃=5

We obtain matrices L and U by solving the aforementioned equations.