The Algorithm for Doolittle's Method for LU Decompositions

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License