The Algorithm for Doolittle's Method for LU Decompositions

Recall from the Doolittle's Method for LU Decompositions page that we can factor a square $n \times n$ matrix into an $LU$ decomposition, $A = LU$ (where $L$ is an $n \times n$ lower triangular matrix whose main diagonal consists of $1$'s and where $U$ is an $n \times n$ upper triangular matrix) using Doolittle's method. Doolittle's method provides an alternative way to factor $A$ into an $LU$ decomposition without going through the hassle of Gaussian Elimination.

Recall that for a general $n \times n$ matrix $A$, we assume that an $LU$ decomposition exists, and write the form of $L$ and $U$ explicitly. We then systematically solve for the entries in in $L$ and $U$ from the equations that result from the multiplications necessary for $A = LU$.

We will now give the general algorithm for Doolittle's method.

Doolittle's Method Algorithm

For each $k = 1, 2, ..., n$:

• $u_{k, m} = a_{k, m} - \sum_{j=1}^{k-1} l_{k,j} u_{j,m}$ for $m = k, k+1, ..., n$ produces the $k^{\mathrm{th}}$ row of $U$.

• $l_{i, k} = \frac{(a_{i, k} - \sum_{j=1}^{k-1} l_{i,j} u_{j, k})}{u_{kk}}$, for $i = k+1, k+2, ..., n$ and $l_{i, i} = 1$ produces the $k^{\mathrm{th}}$ column of $L$.

Example 1

For $n = 3$, verify the algorithm given above for Doolittle's method.

Let $A = \begin{bmatrix}a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}$. We construct $U$ and $L$ systematically.

For $k = 1$ we have that:

(1)

\begin{align} \quad u_{1, 1} = a_{1, 1} - \sum_{j=1}^{0} l_{1,j} u_{j, 1} = a_{1, 1} \quad ( m = 1 ) \\ \quad u_{1, 2} = a_{1, 2} - \sum_{j=1}^{0} l_{1,j}u_{j, 2} = a_{1,2} \quad ( m = 2 ) \\ \quad u_{1, 3} = a_{1, 3} - \sum_{j=1}^{0} l_{1, j} u_{j, 3} = a_{1, 3} \quad ( m = 3 ) \end{align}

(2)

\begin{align} \quad l_{1, 1} = 1 \\ \quad l_{2, 1} = \frac{a_{2, 1} - \sum_{j=1}^{0} l_{2,j}u_{j,1}}{u_{1,1}} = \frac{a_{2, 1}}{u_{1, 1}} \quad (i = 2) \\ \quad l_{3, 1} = \frac{a_{3, 1} - \sum_{j=1}^{0} l_{3,j}u_{j,1}}{u_{1, 1}} = \frac{a_{3, 1}}{u_{1, 1}} \quad (i = 3) \end{align}

For $k = 2$ we have that:

(3)

\begin{align} \quad u_{2, 2} = a_{2, 2} - \sum_{j=1}^{1} l_{2,j} u_{j,2} = a_{2, 2} - l_{2, 1}u_{1, 2} \quad (m = 2) \\ \quad u_{2, 3} = a_{2, 3} - \sum_{j=1}^{1} l_{2, j} u_{j, 3} = a_{2, 3} - l_{2, 1} u_{1, 3} \quad (m = 3) \end{align}

(4)

\begin{align} \quad l_{2, 2} = 1 \\ \quad l_{3, 2} = \frac{a_{3, 2} - \sum_{j=1}^{1} l_{3,j} u_{j, 2}}{u_{2, 2}} = \frac{a_{3, 2} - l_{3, 1} u_{1, 2}}{u_{2, 2}} \end{align}

For $k = 3$ we have that:

(5)

\begin{align} \quad u_{3, 3} = a_{3, 3} - \sum_{j=1}^{2} l_{3, j} u_{j, 3} = a_{3, 3} - l_{3, 1} u_{1, 3} - l_{3, 2} u_{2, 3} \quad (m = 3) \end{align}

(6)

\begin{align} \quad l_{3, 3} = 1 \\ \end{align}

The algorithm terminates at this step.

We get the following equations for the entries in $U$:

(7)

\begin{align} \quad u_{1, 1} = a_{1, 1} \\ \quad u_{1, 2} = a_{1, 2} \\ \quad u_{1, 3} = a_{1, 3} \\ \quad u_{2, 2} = a_{2, 2} - l_{2, 1} u_{1, 2} \\ \quad u_{2, 3} = a_{2, 3} - l_{2, 1} u_{1, 3} \\ \quad u_{3, 3} = a_{3, 3} - l_{3, 1} u_{1, 3} - l_{3, 2} u_{2, 3} \end{align}

And we get the following equations for the entries in $L$:

(8)

\begin{align} \quad l_{2, 1} = \frac{a_{2, 1}}{u_{1, 1}} \\ \quad l_{3, 1} = \frac{a_{3, 1}}{u_{1, 1}} \\ \quad l_{3, 2} = \frac{a_{3, 2} - l_{3, 1} u_{1, 2}}{u_{2, 2}} \end{align}

Furthermore, $l _{1, 1} = l_{2, 2} = l_{3, 3} = 1$.

If you compare these equations with those on the Doolittle's Method for LU Decompositions page, you'll see they're equivalent.