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}