The Mathematical Garden

Doolittle's LU Factorization

Using the tridiagonal linear system as example, we present the Doolittle's LU factorization as follows.

The idea here is that, we assume A can be factorized as follows:

Therefore by expanding the factorization, we get

By comparing coefficients with A we have

u₁ = u₂ = ... = u_n-1 = -1

and

a₁ = 2,    a_i = 2 + l_i-1,   l₁ = -1/2,   a_i = -1/a_i  

Hence we get

By using Mathematical Induction, one can prove that

This indicates that the Doolittle's LU factorization exists for the tridiagonal matrixA.

Theorem 1: For a n x n matrix B, if B is diagonally dominant, i.e.

then its Doolittle's LU factorization exists. Moreover, the computational cost for the Doolittle's LU factorization is O(n³) and the computational cost of solving Ly = b and Uf = f are both O(n²). The proof can be found in the book listed in Reference section.

Remark:

1. Theorem 1 gives a sufficient condition for the existence of Doolittle's LU factorization, the condition is not necessary.

2. We note that the tridiagonal matrix A is not diagonally dominant but its Doolittle's LU factorization exists.

3. Moreover, for the tridiagonal linear system, we see that the computational cost of the Doolittle's LU factorization is only O(n).

4. The computational cost of solving Ly = b and Uf = f are both O(n).

A Small Size Example

Let us look at the following example: