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.