Chapter 3 Homework Solving Requires Divisions Thus The Entire Solve

Direct Factorization 21

For the second pass, we multiply the second row of Lwith the second and third

columns of U. Equating each product with the corresponding element from Agen-

erates the equations

Substituting the values determined from the previous passes, we find u33 =109

18 .

Thus,

Now, back substitution applied to the system Ux=zgives

22 Section 3.6

Now, back substitution applied to the system Ux=zgives

With b3=17 −19 −35 T, forward substitution applied to the system Lz=

b3yields

12. Use the matrix and right-hand side vectors from Exercise 4.

The Doolittle decomposition will consist of the matrices

Direct Factorization 23

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

from A. This yields the equations

For the second pass, we multiply the second row of Lwith the second and third

columns of U. Equating each product with the corresponding element from Agen-

erates the equations

Solving for l32, we find l32 =−1. Finally, multiplying the third row of Lwith the

third column of Ugenerates the equation

24 Section 3.6

With b2=−10 −10 −10 T, forward substitution applied to the system

With b3=−21 −14 −17 T, forward substitution applied to the system

Lz=b3yields

13. Use the matrix and right-hand side vectors from Exercise 5.

The Doolittle decomposition will consist of the matrices



1 0 0 0





u11 u12 u13 u14



Direct Factorization 25

whose solutions are

For the second pass, we multiply the second row of Lwith the second, third and

fourth columns of U. Equating each product with the corresponding element from

Agenerates the equations

Multiplying the third and fourth rows of Linto the second column of Uderives the

whose solution for l43 is l43 =−1. Finally, multiplying the fourth row of Lwith the

fourth column of Uyields

26 Section 3.6

Now, back substitution applied to the system Ux=zgives

x4=z4

7= 1;

x3=z3−5x4

3= 1;

x2=z2−5x3−7x4

3= 1; and

x1=z1−2x2−3x3−4x4= 1.

Hence, x=1111T.

With b2=−4−5−3−4T, forward substitution applied to the system

Lz=b2yields

z1=−4;

z2=−5 + z1=−9;

z3=−3−z1+z2=−8; and

z4=−4 + z1−z2+z3=−7.

Now, back substitution applied to the system Ux=zgives

x4=z4

7=−1;

x3=z3−5x4

3=−1;

x2=z2−5x3−7x4

3= 1; and

x1=z1−2x2−3x3−4x4= 1.

Hence, x=1 1 −1−1T.

With b3=−2−3 1 −8T, forward substitution applied to the system

Lz=b3yields

z1=−2;

z2=−3 + z1=−5;

z3= 1 −z1+z2=−2; and

Direct Factorization 27

Hence, x=1−1 1 −1T.

14. Use the matrix and right-hand side vectors from Exercise 6.

The Doolittle decomposition will consist of the matrices

The first column of Lis obtained by multiplying the second, third and fourth rows

For the second pass, we multiply the second row of Lwith the second, third and

fourth columns of U. Equating each product with the corresponding element from

Agenerates the equations

Multiplying the third and fourth rows of Linto the second column of Uderives the

28 Section 3.6

from which we find u44 =−9

10 . Thus,

With b1=1−5−2 9 T, forward substitution applied to the system Lz=

b1yields

With b2=−5−3 6 −5T, forward substitution applied to the system

Lz=b2yields

Direct Factorization 29

With b3=5 5 −2 1 T, forward substitution applied to the system Lz=b3

yields

Now, back substitution applied to the system Ux=zgives

15. (a) Construct an algorithm to factor an n×nmatrix into the product LDU ,

where Lis a lower triangular matrix with ones along its diagonal, Dis a

diagonal matrix and Uis an upper triangular matrix with ones along its

diagonal.

(b) Suppose the matrix Ahas been factored into the product LDU , where the

matrices L,Dand Uhave the form specified in part (a). Construct an

algorithm to use this factorization to solve the system Ax=b.

(c) How many arithmetic operations are required to compute the factorization

in part (a)? How does this total compare to the number of operations

needed to compute an LU decomposition?

(d) How many arithmetic operations are required by the algorithm in part (b)

to solve a system given an LDU decomposition of the coefficient matrix?

How does this total compare to the number of operations needed by forward

and backward substitution?

(e) How does the total number of arithmetic operations needed to solve a

system of equations using an LDU decomposition compare to the number

of operations needed to solve a system using an LU decomposition?

30 Section 3.6

(a) One approach is to determine a Crout decomposition and then factor the diag-

triangular matrix.

(b) Suppose the matrix Ahas been factored into the product LDU, where Lis a

of D. Finally, solve the system Ux=yfor xby back substitution.

(c) Starting from either a Crout decomposition or a Doolittle decomposition re-

(d) Because the matrices Land Uhave ones along the diagonal, forward and

In Exercises 16 – 21, determine the LDU decomposition (see Exercise 15) of the

given matrix, and then solve the system Ax=bfor each of the given right-hand

side vectors.

16. Use the matrix and right-hand side vectors from Exercise 1.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices 

2 0 0



1 7/2 5/2



Direct Factorization 31

Factoring the diagonal elements from the lower triangular matrix produces the LDU

decomposition consisting of

Solving Dy=z, we find

Finally, back substitution applied to the system Ux=ygives

Solving Dy=z, we find

32 Section 3.6

Solving Dy=z, we find

17. Use the matrix and right-hand side vectors from Exercise 2.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices 

1 0 0



112



Factoring the diagonal elements from the lower triangular matrix produces the LDU

decomposition consisting of

1 0 0



1 0 0



112



Solving Dy=z, we find

Direct Factorization 33

Solving Dy=z, we find

Finally, back substitution applied to the system Ux=ygives

x3=y3=−5;

18. Use the matrix and right-hand side vectors from Exercise 3.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices



−3 0 0



1−2/3 1/3



Factoring the diagonal elements from the lower triangular matrix produces the LDU

decomposition consisting of

1 0 0



−3 0 0



34 Section 3.6

With b1=7 3 −33 T, forward substitution applied to the system Lz=b1

yields

Solving Dy=z, we find

Direct Factorization 35

Finally, back substitution applied to the system Ux=ygives

19. Use the matrix and right-hand side vectors from Exercise 4.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices 

1 0 0



145



With b1=−15 −14 −7T, forward substitution applied to the system Lz=

b1yields

Finally, back substitution applied to the system Ux=ygives

36 Section 3.6

Solving Dy=z, we find

20. Use the matrix and right-hand side vectors from Exercise 5.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices









Factoring the diagonal elements from the lower triangular matrix produces the LDU

decomposition consisting of



1 0 0 0





1000



and



1 2 3 4



Solving Dy=z, we find

38 Section 3.6

Hence, x=1 1 −1−1T.

Finally, back substitution applied to the system Ux=ygives

x4=y4=−1;

21. Use the matrix and right-hand side vectors from Exercise 6.

The Crout decomposition of the matrix Aconsists of the lower and upper triangular

matrices









Factoring the diagonal elements from the lower triangular matrix produces the LDU

decomposition consisting of



1 0 0 0





1 0 0 0



Direct Factorization 39

Solving Dy=z, we find

Finally, back substitution applied to the system Ux=ygives

x4=y4= 9;

40 Section 3.6

With b3=5 5 −2 1 T, forward substitution applied to the system Lz=b3

yields