3.6 Direct Factorization
In Exercises 1 – 6, determine the Crout decomposition of the given matrix, and
then solve the system Ax=bfor each of the given right-hand side vectors.
1. A=
2 7 5
6 20 10
4 3 0
b1=
0
4
1
,b2=
−4
−16
−7
,b3=
−3
−12
6
The Crout decomposition will consist of the matrices
Forming the product of each row of Lwith the first column of Uand equating the
result with the corresponding element from Adetermines the elements in the first
column of L:
2Section 3.6
Solving for u23, we find u23 = 5. Finally, multiplying the third row of Lwith the
third column of Ugenerates the equation
With b1=041T, forward substitution applied to the system Lz=b1
yields
Now, back substitution applied to the system Ux=zgives
Direct Factorization 3
With b3=−3−12 6 T, forward substitution applied to the system Lz=b3
Now, back substitution applied to the system Ux=zgives
2. A=
112
−1 0 2
3 2 −1
b1=
3
−1
4
,b2=
−9
−10
7
,b3=
−2
−1
0
The Crout decomposition will consist of the matrices
The first row of Uis obtained by multiplying the first row of Lwith the second and
third columns of Uand then equating the result with the corresponding element
from A. This yields the equations
4Section 3.6
Substituting the values obtained during the first pass and solving for the elements
in the second column of Lgives
Substituting the values determined from the previous passes, we find l33 =−3.
Thus,
With b1=3−1 4 T, forward substitution applied to the system Lz=b1
yields
Now, back substitution applied to the system Ux=zgives
Now, back substitution applied to the system Ux=zgives
Direct Factorization 5
3. A=
−3 2 −1
681
427
b1=
7
3
−33
,b2=
−12
1
1
,b3=
17
−19
−35
The Crout decomposition will consist of the matrices
6Section 3.6
3.
Next, multiply the second row of Linto the third column of Uto derive the equation
Substituting the values determined from the previous passes, we find l33 =109
18 .
Thus,
Now, back substitution applied to the system Ux=zgives
Direct Factorization 7
Now, back substitution applied to the system Ux=zgives
With b3=17 −19 −35 T, forward substitution applied to the system Lz=
4. A=
1 4 5
2 6 4
−1−2 3
b1=
−15
−14
−7
,b2=
−10
−10
−10
,b3=
−21
−14
−17
8Section 3.6
Substituting the values obtained during the first pass and solving for the elements
in the second column of Lgives
Substituting the values determined from the previous passes, we find l33 = 2. Thus,
With b2=−10 −10 −10 T, forward substitution applied to the system
Lz=b2yields
Direct Factorization 9
Now, back substitution applied to the system Ux=zgives
With b3=−21 −14 −17 T, forward substitution applied to the system
Lz=b3yields
Now, back substitution applied to the system Ux=zgives
5. A=
1 2 3 4
−1 1 2 3
1−112
−1 1 −1 5
b1=
10
5
3
4
,b2=
−4
−5
−3
−4
,b3=
−2
−3
1
−8
The Crout decomposition will consist of the matrices
l11 0 0 0
1u12 u13 u14
The first row of Uis obtained by multiplying the first row of Lwith the second,
third and fourth columns of Uand then equating the result with the corresponding
element from A. This yields the equations
10 Section 3.6
whose solutions are
Substituting the values obtained during the first pass and solving for the elements
in the second column of Lgives
from which we find l44 = 7. Thus,
Direct Factorization 11
Now, back substitution applied to the system Ux=zgives
Now, back substitution applied to the system Ux=zgives
12 Section 3.6
6. A=
1 3 1 −2
2 4 −1 2
3 1 1 5
4 2 6 −1
b1=
1
−5
−2
9
,b2=
−5
−3
6
−5
,b3=
5
5
−2
1
The Crout decomposition will consist of the matrices
The first row of Uis obtained by multiplying the first row of Lwith the second,
third and fourth columns of Uand then equating the result with the corresponding
element from A. This yields the equations
Direct Factorization 13
from which we find u23 =3
2and u24 =−3. Next, multiplying the third and fourth
rows of Lwith the third column of Ugenerates the equations
With b1=1−5−2 9 T, forward substitution applied to the system Lz=
b1yields
Now, back substitution applied to the system Ux=zgives
14 Section 3.6
Now, back substitution applied to the system Ux=zgives
Now, back substitution applied to the system Ux=zgives
x4=z4=−1;
7. Show that computing the Crout decomposition of an n×nmatrix requires
2
Direct Factorization 15
and the calculation of each ukj (j=k+ 1, k + 2, k + 3, . . . , n) requires 2k−1
operations. Thus, the entire algorithm requires
8. (a) Construct an algorithm to compute the Doolittle decomposition of an n×n
matrix.
(b) Show that computing the Doolittle decomposition of an n×nmatrix re-
quires 2
3n3−1
2n2−1
6narithmetic operations.
(a) Because the Doolittle decomposition is defined by placing ones along the main
STEP 1: for jfrom 1 to n
(b) The first step of the algorithm from part (a) does not require any arithmetic
operations, whereas the second step requires n−1operations and the last step
16 Section 3.6
In Exercises 9 – 14, determine the Doolittle decomposition (see Exercise 8) of
the given matrix, and then solve the system Ax=bfor each of the given right-
hand side vectors.
9. Use the matrix and right-hand side vectors from Exercise 1.
The Doolittle decomposition will consist of the matrices
The first column of Lis obtained by multiplying the second and third rows of Lwith
the first column of Uand then equating the result with the corresponding element
Direct Factorization 17
Substituting the values obtained during the first pass and solving for the elements
Substituting the values determined from the previous passes, we find u33 = 45.
Thus,
100
2 7 5
Now, back substitution applied to the system Ux=zgives
18 Section 3.6
Now, back substitution applied to the system Ux=zgives
10. Use the matrix and right-hand side vectors from Exercise 2.
The Doolittle decomposition will consist of the matrices
Direct Factorization 19
whose solutions are
Substituting the values determined from the previous passes, we find u33 =−3.
20 Section 3.6
Now, back substitution applied to the system Ux=zgives
Now, back substitution applied to the system Ux=zgives
11. Use the matrix and right-hand side vectors from Exercise 3.
The Doolittle decomposition will consist of the matrices