3.5 LU Decomposition
1. (a) Show that the algorithm to obtain an LU decomposition based on Gaussian
elimination requires 2
3n3−1
2n2−1
6narithmetic operations.
(b) Show that the solve step – forward substitution followed by backward sub-
stitution – requires 2n2−narithmetic operations.
(c) Suppose A−1has been calculated. Show that the multiplication A−1b
requires 2n2−narithmetic operations.
(a) To obtain an LU decomposition based on Gaussian elimination, we perform
the following calculations:
This algorithm requires
(b) The following pseudocode performs forward substitution on the system Lz=b
and then back substitution on the system Ux=z.
2Section 3.5
Forward substitution requires
arithmetic operations and back substitution requires an additional
(c) Let (a−1)ij denote the element in row i, column jof the matrix A−1. We can
perform the multiplication A−1bwith the following calculations:
The number of arithmetic operations needed to calculate A−1bis therefore
2. Let Abe an n×nmatrix, and suppose that we need to solve mlinear systems
Ax=bifor i= 1,2,3, …, m. Consider constructing an n×(n+m) augmented
matrix which contains all of the right-hand side vectors and performing Gaussian
elimination with back substitution on this matrix. Show that this algorithm
requires 2
3n3+2m−1
2n2−m+1
6narithmetic operations.
LU Decomposition 3
=
n−1
X
(2n+ 2m−2pass + 1)(n−pass)
3. Show that
1 0 0 0 0
0 1 0 0 0
0m3,2100
0m4,2010
0m5,2001
−1
=
1 0 0 0 0
0 1 0 0 0
0−m3,2100
0−m4,2010
0−m5,2001
.
Carrying out the matrix multiplication, we find
and
1 0 0 0 0
1 0 0 0 0
4. Let
A=1 2
3 4 .
Verify that each of the following pairs forms an LU decomposition of A, and
then use the decomposition to solve the system Ax=4 6 T.
(a) L1=1 0
3 1 , U1=1 2
0−2
(b) L2=1 0
3−2, U2=1 2
0 1
4Section 3.5
(c) L3=−1 0
−3−2, U3=−1−2
0 1
(a)
Performing forward substitution on the system L1z=4 6 T, we find
Now, back substitution on the system U1x=zyields
(b)
Performing forward substitution on the system L2z=4 6 T, we find
Now, back substitution on the system U2x=zyields
LU Decomposition 5
(c)
L3U3=−1 0
−3−2 −1−2
0 1
Performing forward substitution on the system L3z=4 6 T, we find
z1=4
−1=−4; and
5. Let
A=
2 7 5
6 20 10
4 3 0
.
Verify that each of the following pairs forms an LU decomposition of A, and
then use the decomposition to solve the system Ax=041T.
(a) L1=
100
310
2 11 1
, U1=
2 7 5
0−1−5
0 0 45
(b) L2=
1 0 0
3−1 0
2−11 45
, U2=
275
015
001
(c) L3=
2 0 0
6−1 0
4−11 45
, U3=
1 7/2 5/2
0 1 5
0 0 1
6Section 3.5
(a)
L1U1=
100
310
2 7 5
0−1−5
Performing forward substitution on the system L1z=041T, we find
z1= 0;
Now, back substitution on the system U1x=zyields
x3=z3
3
9−43
45 T.
(b)
L2U2=
1 0 0
3−1 0
2−11 45
275
015
001
(1)(2) + (0)(0) + (0)(0) (1)(7) + (0)(1) + (0)(0) (1)(5) + (0)(5) + (0)(1)
LU Decomposition 7
Now, back substitution on the system U2x=zyields
x3=z3
1=−43
45;
x2=z2−5x3
1=7
9;and
x1=z1−7x2−5x3
2=−1
3.
Thus, the solution of the system Ax=041Tis x=−1
3
7
9−43
45 T.
(c)
2 0 0
1 7/2 5/2
Performing forward substitution on the system L3z=041T, we find
45 =−43
45.
Now, back substitution on the system U3x=zyields
6. Let
A=
1 3 1 −2
2 4 −1 2
3 1 1 5
4 2 −1 6
.
8Section 3.5
(a) L1=
1000
2100
3410
4511
, U1=
1 3 1 −2
0−2−3 6
0 0 10 −13
0 0 0 −3
(b) L2=
1 0 0 0
2−1 0 0
3−4 10 0
4−5 10 −3
, U2=
131 −2
023 −6
001−13/10
0 0 0 1
(a)
1000
1 3 1 −2
Performing forward substitution on the system L1z=3 7 10 11 T,
we find
Now, back substitution on the system U1x=zyields
x4=z4
LU Decomposition 9
Thus, the solution of the system Ax=3 7 10 11 Tis x=1111T.
(b)
Performing forward substitution on the system L2z=3 7 10 11 T,
we find
z1= 3;
Now, back substitution on the system U2x=zyields
x4=z4
1= 1;
7. (a) Show that the matrix
0 1
1 1
has no LU decomposition. (Hint: write out the equations corresponding
to l11 0
l21 l22 u11 u12
0u22 =0 1
1 1
10 Section 3.5
and show that the resulting system is inconsistent.)
(b) Reverse the order of the rows of Aand show that the resulting matrix does
have an LU decomposition.
(a) Suppose
Then,
l11u11 = 0;
(b) If we reverse the order of the rows in the given matrix, we find
1 1
8. (a) Show that the matrix
001
010
101
has no LU decomposition.
(b) Rearrange the rows of Aso that the resulting matrix does have an LU
decomposition.
LU Decomposition 11
(a) Suppose
001
010
=
l11 0 0
l21 l22 0
u11 u12 u13
0u22 u23
.
(b) If we interchange the first and third rows in the given matrix, we find
9. Repeat Exercise 8 for the matrix
A=
1 1 1
1 1 2
−102
(a) Let
l11 0 0
u11 u12 u13
12 Section 3.5
and l31u11 =−1. Thus,
u11 =u12 =u13 =1
l11
, l21 =l11,
which is not equal to the element in the second row, third column of A.
Similarly, if u22 = 0, then the element in the third row, second column of B
becomes
−l11
1
l11
+l32 ·0 = −1,
which is not equal to the element in the third row, second column of A. Thus,
Adoes not have an LU decomposition.
(b) After one pass of Gaussian elimination, the matrix Abecomes
1 1 1
1 1 1
To proceed further with Gaussian elimination, we need to interchange the
second and third rows. Consequently, the matrix
1 1 1
10. Consider the matrix
A=
112
−1 0 2
3 2 −1
.
LU Decomposition 13
(a) Find a lower triangular matrix Lwith ones along its diagonal and an upper
triangular matrix Usuch that A=LU.
(b) Find matrices L,Dand Usuch that A=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.
(c) Find a lower triangular matrix Land an upper triangular matrix Uwith
ones along its diagonal such that A=LU.
(a) Gaussian elimination with no pivoting applied to the matrix Ayields
112
1 1 2
Thus,
(b) Observe that the upper triangular matrix from part (a) can be written as the
product
of a diagonal matrix and an upper triangular matrix with ones along its di-
agonal. Thus, A=LDU, where Lis the lower triangular matrix from part
(a),
(c) The product of the lower triangular matrix from parts (a) and (b) with the
diagonal matrix from part (b) is the lower triangular matrix
1 0 0
14 Section 3.5
For Exercises 11 – 15:
(a) Using scaled partial pivoting during the factor step, find matrices L,Uand
Psuch that LU =P A.
(b) Solve the system Ax=bfor each of the given right-hand side vectors.
11. 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
(a) Initialize the row vector to r=1234T. Since
Among the values
the largest corresponds to r3. We therefore interchange the first and third
entries in the row vector to obtain
The first pass of Gaussian elimination transforms the coefficient matrix to
Now, the largest value among
corresponds to r3, so we interchange the second and third entries in the row
LU Decomposition 15
The larger value corresponds to r3, so there is no need to modify the contents of
the row vector. Moreover, as ar4,3= 0, the third pass of Gaussian elimination
is already complete. Finally, we see that LU =P A, where
(b) With b1=10 5 3 4 T, we find Pb1=3 10 5 4 T. Now,
forward substitution applied to Lz=Pb1yields
Next, back substitution applied to Ux=zgives
x4=z4
7= 1;
Next, back substitution applied to Ux=zgives
x4=z4
16 Section 3.5
Next, back substitution applied to Ux=zgives
12. A=
1 0 2 0
−1 4 3 6
0−2 5 −3
3 1 1 0
b1=
3
12
0
5
,b2=
−1
−6
−4
3
,b3=
3
−8
10
2
(a) Initialize the row vector to r=1234T. Since
the largest corresponds to r4. We therefore interchange the first and fourth
entries in the row vector to obtain
The first pass of Gaussian elimination transforms the coefficient matrix to
(1/3) −1/3 5/3 0
Now, the largest value among
corresponds to r2, so there is no need to modify the contents of the row vector.
The second pass of Gaussian elimination transforms the coefficient matrix to
(1/3) (−1/13) 25/13 6/13