Page 96 - Compact Numerical Methods For Computers

The Choleski decomposition 85
within the computer. It remains to be shown that the procedure is stable and that
for i = m the right-hand side of (7.8) is positive, so no square roots of negative
numbers are required.
Firstly, A is positive definite if
T
x A x >0 for all x 0. (7.9)
An equivalent statement is that all the eigenvalues of A are positive. From (7.9) it
follows by setting x to any column of the unit matrix that no diagonal element of
A can be non-positive. Likewise, by taking only x and x non-zero
i
i
(7.10)
which requires that the quadratic equation
2
z A ii + 2zA + A jj = 0 (7.11)
ij
has only complex roots. This occurs if
(7.12)
Consider now the ith step of the Choleski decomposition. For the moment
suppose that only rows 1, 2, . . . , (i - 1) of L have been computed, giving a
submatrix L i-1 which is a decomposition of the submatrix A i-1 of A; hence

(7.13)

Following Kowalik and Osborne (1968), we have

L c = a (7.14)
i - l
or
(7.15)
where L is assumed non-singular. In fact, it is positive definite providing the
i-1
positive square root is chosen in the computation of each of its diagonal elements
via (7.8). Consider now the choice in (7.9) of an x such that the first (i – 1)
elements of x are given by x = -1, and x = 0 for j > i. This choice, using
j
i
(7.13) gives
(7.16)

which reduces to
T
A ii - c c > 0. (7.17)
But a comparison of this with (7.8) shows that it implies the square of each
diagonal element of L is positive, so that all the elements of L are real providing A
is positive definite. Furthermore, an analysis similar to that used in (7.10), (7.11)
and (7.12) demands that
(7.18)