# 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)For $k = 2$ we have that:

(3)For $k = 3$ we have that:

(5)The algorithm terminates at this step.

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

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

(8)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.