LU Decomposition using Doolittle Factorization

LU Decomposition using Doolittle Factorization

We can write an m X n matrix A as a product of two matrices, L and U. And A = L*U

L =$\ \begin{bmatrix} 1 & 0 & 0 & 0 \\ l21 & 1 & 0 & 0 \\ l31 & l32 & 1 & 0 \\ l41 & l42 & l43 & 1 \end{bmatrix}$ ; U = $\begin{bmatrix} u11 & u12 & u13 & u14 \\ 0 & u22 & u23 & u24 \\ 0 & 0 & u33 & u34 \\ 0 & 0 & 0 & u44 \end{bmatrix}$

L= lower triangular matrix; U= upper triangular matrix

Procedure-

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

2. Initialize the L and U matrices. For L matrix, take a matrix with all diagonal elements assigned to 1, and the matrix elements above the diagonal are zeroes. 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.

$$\ \begin{bmatrix} 1 & 0 & 0 & 0 \\ l21 & 1 & 0 & 0 \\ l31 & l32 & 1 & 0 \\ l41 & l42 & l43 & 1 \end{bmatrix} $$

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

3. Size of matrix U will be as same as matrix A (or, m X n). Matrix U can be written as

$$\begin{bmatrix} u11 & u12 & u13 & u14 \\ 0 & u22 & u23 & u24 \\ 0 & 0 & u33 & u34 \\ 0 & 0 & 0 & u44 \end{bmatrix}$$

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

4. For a given example,

$$\mathbf{A\ =}\begin{bmatrix} \mathbf{2} & \mathbf{- 1} & \mathbf{- 2} \\ \mathbf{- 4} & \mathbf{6} & \mathbf{3} \\ \mathbf{- 4} & \mathbf{- 2} & \mathbf{8} \end{bmatrix}$$

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

Next, resolve the basic equations, u₁₁ = 2, u₁₂ = -1, u₁₃ = -2

To get the above equations, take the sum of the multiplications of the elements in row 1 of matrix L and the elements in column 1 of matrix U to obtain the equations above. Then compare the sum with corresponding element of matrix A.

Then follow the same process for matrix L’s row 1 and matrix U’s column 2, then matrix L’s row 1 and matrix U’s column 3.

Then follow the same procedure for matrix L’s row 2 and 3

Apply the same procedure to the first row of matrix L and the second column of matrix U, then to the first row of matrix L and third column of matrix U.

Then repeat these steps for rows 2 and 3 of matrix L.

l₂₁*u₁₁ = -4

l₂₁*u₁₂ + u₂₂ = 6

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

l₃₁*u₁₁ = -4

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

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

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