Page 122 - Applied Numerical Methods Using MATLAB

PROBLEMS 111
Table P2.6.2 Comparison of Several Methods for Solving a System of Linear
Equations
LU QR gauss(A,b) A\b

||Ax i − b|| 7.8505e-016 8.7419e-016
# of flops 453 327 1124 785

equations whose coefficient matrix is the 10-dimensional Hilbert
matrix (see Example 2.3) and fill in the corresponding blanks of
Table P2.6.2 with the results.
(ii) Apply the QR decomposition to solve the system of linear equations
given by Eq. (P2.6.4) and fill in the corresponding blanks of
Table P2.6.2 with the results.
(cf) This problem illustrates that QR decomposition is quite useful for solving
a system of linear equations, where the coefficient matrix A is square and
nonsingular or rectangular with the row dimension greater than the column
dimension and no rank deficiency.

2.7 Cholesky Factorization of a Symmetric Positive Definite Matrix:
If a matrix A is symmetric and positive definite, we can find its LU
decomposition such that the upper triangular matrix U is the transpose of
the lower triangular matrix L, which is called Cholesky factorization.
Consider the Cholesky factorization procedure for a 4 × 4matrix

     
0 0 0
a 11 a 12 a 13 a 14 u 11 u 11 u 12 u 13 u 14
 a   u 12 u 22 0 0   0 
 12 a 22 a 23 a 24  =    u 22 u 23 u 24 
 a 13 a 23 a 33 a 34   u 13 u 23 u 33 0   0 0 u 33 u 34 
0 0 0
a 14 a 24 a 34 a 44 u 14 u 24 u 34 u 44 u 44
 2 
u u 11 u 12 u 11 u 13 u 11 u 14
11
2
 u 12 u 11 u + u 2 22 u 12 u 13 + u 22 u 23 u 12 u 14 + u 22 u 24 
12
=  2 2 2 
u 13 u 11 u 13 u 12 + u 23 u 22 u 13 u 14 + u 23 u 24 + u 33 u 34
13 23 33
 u + u + u 
2
2
2
u 14 u 11 u 14 u 12 + u 24 u 22 u 14 u 13 + u 24 u 23 + u 34 u 33 u + u + u + u 2
14 24 34 44
(P2.7.1)
Equating every row of the matrices on both sides yields
√
u 11 = a 11 , u 12 = a 12 /u 11 ,u 13 = a 13 /u 11 ,u 14 = a 14 /u 11 (P2.7.2.1)

2
u 22 = a 22 − u , u 23 = (a 23 − u 13 u 12 )/u 22 ,u 24 = (a 24 − u 14 u 12 )/u 22
12
(P2.7.2.2)

2
2
u 33 = a 33 − u − u , u 34 = (a 43 − u 24 u 23 − u 14 u 13 )/u 33 (P2.7.2.3)
23 13

2
2
u 44 = a 44 − u − u − u 2 (P2.7.2.4)
34 24 14