Page 95 - Compact Numerical Methods For Computers

Chapter 7

THE CHOLESKI DECOMPOSITION

7.1. THE CHOLESKI DECOMPOSITION
When the matrix A is symmetric and positive definite (see discussion below for
definition), it is possible to perform (without pivoting) the symmetric decomposi-
tion
T T
A = LL = R R (7.1)
where
T
L = R (7.2)
is a lower-triangular matrix. In fact, it is also possible to perform Gauss elimina-
tion in a symmetric fashion for symmetric positive definite matrices without
pivoting for stability (see Dahlquist and Björck 1974, pp 162-4).
The Choleski algorithm (Wilkinson 1965) is derived directly from (7.1), that is

(7.3)

Note that the summation runs only from 1 to the minimum of i and j due to the
triangular nature of L. Thus we have

(7.4)
so that
½
L 11 = (A ) . (7.5)
11
Furthermore
A i1 = L L (7.6)
il 11
so that we obtain
L i1 = A /L . (7.7)
11
i1
Consider now the mth column of L which is defined for i > m by

(7.8)

with the diagonal element determined first by setting i = m. It is straightforward to
see that every element in the right-hand side of equation (7.8) comes from
columns 1, 2, . . . , (m – 1) of L or from column m of A. Since (7.5) and (7.7)
define the first column of L, we have a stepwise procedure for computing its
remaining columns, and furthermore this can be arranged so that L overwrites A
84