Page 53 - Numerical Methods for Chemical Engineering

42 1 Linear algebra

For further discussion of LU factorization with pivoting, consult Quateroni et al.
(2000).

Cholesky decomposition
Since the transpose of a lower triangular matrix L is an upper triangular matrix, we might
wonder if it is possible for some matrix A, that in the LU decomposition, we can set U = L T
to obtain
A = LL T (1.207)

First, by taking the transpose of this equation, we see that any A that can be written in this
T
manner must be symmetric, A = A ,
T
T T
T
A = (LL ) = LL = A (1.208)
N
T
Also, for A to be nonsingular, L and L must be nonsingular, so that for any v ∈ , v = 0,
T T
L v · L v > 0 (1.209)
From
T
T
T
T
T
T
T
T

v Av = v LL v = L v L v = L v · L v (1.210)
T
we see that a matrix A could be written as A = LL only if it were symmetric and positive-
definite; i.e.,
N
T
v Av > 0 ∀v ∈ , v = 0 (1.211)
While only a subset of all matrices are symmetric, positive-definite, they in fact form
T
an important subset, especially in numerical optimization. Thus A = LL , known as a
Cholesky decomposition, is used frequently.
The special structure of a positive-definite matrix allows us to perform Cholesky factor-
T
ization more quickly than LU decomposition. We start by writing A = LL explicitly,
   
a 11 a 21 a 31 ... a N1 L 11
 a 21 a 22 a 32 ... a N2   L 21 L 22 
   
a 31 a 32 a 33 L 31 L 32 L 33
 ...   
 a N3  =  
 . . . . .   . . . . 
 . . . . . . . . . .   . . . . . . . . 
a N1 a N2 a N3 ... a NN L N1 L N2 L N3 ... L NN
 
L 11 L 21 L 31 ... L N1
 L 22 L 32 ... L N2 
 
...
L 33 L N3  (1.212)
 
× 
. .
 . 
 . . . 
L NN
From the (1, 1) element we obtain
L 11 = (a 11 ) 1/2 (1.213)
a 11 = L 11 × L 11