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)
\begin{align} \quad a_{11} = u_{11} \quad , \quad a_{12} = u_{12} \quad , \quad a_{13} = u_{13} \end{align}

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

(3)
\begin{align} \quad a_{21} = m_{21}u_{11} \quad , \quad a_{22} = m_{21}u_{12} + u_{22} \quad , \quad a_{23} = m_{21}u_{13} + u_{23} \end{align}

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)
\begin{align} \quad a_{31} = m_{31}u_{11} \quad , \quad a_{32} = m_{31}u_{12} + m_{32}u_{22} \quad , \quad a_{33} = m_{31}u_{13} + m_{32}u_{23} + u_{33} \end{align}

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)
\begin{align} \quad 2 = u_{11} \quad , \quad 3 = u_{12} \quad , \quad 2 = u_{13} \end{align}

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

(7)
\begin{align} \quad 1 = m_{21}(2) \quad , \quad 3 = m_{21}(3) + u_{22} \quad , \quad 2 = m_{21}(2) + u_{23} \end{align}

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:

(8)
\begin{align} \quad 3 = m_{31}(2) \quad , \quad 4 = m_{31}(3) + m_{32}\left ( \frac{3}{2} \right ) \quad , \quad 1 = m_{31}(2) + m_{32}(1) + u_{33} \end{align}

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:

(9)
\begin{align} \quad A = \begin{bmatrix} 2 & 3 & 2\\ 1 & 3 & 2\\ 3 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ \frac{1}{2} & 1 & 0\\ \frac{3}{2} & -\frac{1}{3} & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 & 2\\ 0 & \frac{3}{2} & 1\\ 0 & 0 & -\frac{5}{3} \end{bmatrix} = LU \end{align}