Page 160 - Matrix Analysis & Applied Linear Algebra

154 Chapter 3 Matrix Algebra
Example 3.10.6

The LDU factorization. There’s some asymmetry in an LU factorization be-
cause the lower factor has 1’s on its diagonal while the upper factor has a nonunit
diagonal. This is easily remedied by factoring the diagonal entries out of the up-
per factor as shown below:

    
u 11 u 12 ··· u 1n u 11 0 ··· 0 1 u 12 /u 11 ··· u 1n /u 11
 0 u 22 ··· u 2n   0 u 22 ··· 0  0 1 ··· u 2n /u 22 
=
 . . . .   . . . .  . . . .  .
 . . . .   . . . .  . . . . 
. . . . . . . . . . . .
0 0 ··· u nn 0 0 ··· u nn 0 0 ··· 1
Setting D = diag (u 11 ,u 22 ,...,u nn ) (the diagonal matrix of pivots) and redefin-
ing U to be the rightmost upper-triangular matrix shown above allows any LU
factorization to be written as A = LDU, where L and U are lower- and upper-
triangular matrices with 1’s on both of their diagonals. This is called the LDU
factorization of A. It is uniquely determined, and when A is symmetric, the
LDU factorization is A = LDL T (Exercise 3.10.9).

Example 3.10.7
22
The Cholesky Factorization. A symmetric matrix A possessing an LU fac-
torization in which each pivot is positive is said to be positive definite.
Problem: Prove that A is positive definite if and only if A can be uniquely
T
factored as A = R R, where R is an upper-triangular matrix with positive
diagonal entries. This is known as the Cholesky factorization of A, and R is
called the Cholesky factor of A.
Solution: If A is positive definite, then, as pointed out in Example 3.10.6,
it has an LDU factorization A = LDL T in which D = diag (p 1 ,p 2 ,...,p n )
is the diagonal matrix containing the pivots p i > 0. Setting R = D 1/2 L T
√ √ √
where D 1/2 = diag p 1 , p 2 ,..., p n yields the desired factorization because
T
T
A = LD 1/2 D 1/2 L = R R, and R is upper triangular with positive diagonal
22
This is named in honor of the French military officer Major Andr´e-Louis Cholesky (1875–
1918). Although originally assigned to an artillery branch,Cholesky later became attached to
the Geodesic Section of the Geographic Service in France where he became noticed for his
extraordinary intelligence and his facility for mathematics. From 1905 to 1909 Cholesky was
involved with the problem of adjusting the triangularization grid for France. This was a huge
computational task,and there were arguments as to what computational techniques should be
employed. It was during this period that Cholesky invented the ingenious procedure for solving
a positive definite system of equations that is the basis for the matrix factorization that now
bears his name. Unfortunately,Cholesky’s mathematical talents were never allowed to flower.
In 1914 war broke out,and Cholesky was again placed in an artillery group—but this time
as the commander. On August 31,1918,Major Cholesky was killed in battle. Cholesky never
had time to publish his clever computational methods—they were carried forward by word-
of-mouth. Issues surrounding the Cholesky factorization have been independently rediscovered
several times by people who were unaware of Cholesky,and,in some circles,the Cholesky
factorization is known as the square root method.