Doolittle's Method for LU Decompositions

This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

# Doolittle's Method for LU Decompositions

As we have already seen, if we can write a square $n \times n$ matrix $A$ as a product of two matrices, $L$ and $U$ where $L$ is a lower triangular matrix with ones on the main diagonal and $U$ is an upper triangular matrix, then solving the system $Ax = b$ becomes a matter of simply applying forward substitution and backwards substitution.

Thus far though, we have found an $LU$ factorization of a matrix by first applying Gaussian Elimination to $A$ to get $U$, and then examining the multipliers in the Gaussian Elimination process to determine the entries below the main diagonal of $L$. We will now look at another method for finding an $LU$ decomposition of matrix without going through the process of Gaussian Elimination.

Doolittle's Method takes an $n \times n$ matrix $A$ and assume that an $LU$ decomposition exists. We then match the entries of $A$ with the products or necessary entries from $L$ and $U$. Doolittle's Method is best explained with an example. Suppose that $A$ is a $3 \times 3$ matrix and that an $LU$ decomposition exists.

(1)
\begin{align} A = \begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ m_{21} & 1 & 0\\ m_{31} & m_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13}\\ 0 & u_{22} & u_{23}\\ 0 & 0 & u_{33} \end{bmatrix} = LU \end{align}

If we multiply $L$ and $U$ for the first row of $A$ we immediately get that:

(2)

We then multiply $L$ and $U$ for the second row of $A$ and we have that:

(3)

From these equations, we can solve for $m_{21}$, $u_{22}$, and $u_{23}$. Lastly, we then multiply $L$ and $U$ for the third row of $A$ and we have that:

(4)

For a less general example, suppose that we want to find an $LU$ factorization to the matrix $A = \begin{bmatrix} 2 & 3 & 2\\ 1 & 3 & 2\\ 3 & 4 & 1 \end{bmatrix}$. We first assume that an $LU$ factorization exists. Then we have that:

(5)
\begin{align} \quad A = \begin{bmatrix} 2 & 3 & 2\\ 1 & 3 & 2\\ 3 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ m_{21} & 1 & 0\\ m_{31} & m_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13}\\ 0 & u_{22} & u_{23}\\ 0 & 0 & u_{33} \end{bmatrix} = LU \end{align}

We immediately have that:

(6)

Moving onto the second row of $A$, we have that:

(7)
From the first equation we see that $m_{21} = \frac{1}{2}$. Plugging this into the second equation and we have that $u_{22} = \frac{3}{2}$. Plugging $m_{21}$ into the third equation and we have that $u_{23} = 1$. Moving onto the third row of $A$ and we have that:
From the first equation we see that $m_{31} = \frac{3}{2}$. Plugging this into the second equation and we have that $m_{32} = -\frac{1}{3}$. Plugging both of these into the third equation and we have that $u_{33} = -\frac{5}{3}$. So we have all entries for both $L$ and $U$ and so: