Doolittle's Method with Row Interchanges - Electrical Engineering (EE) PDF Download

 Page 1


 
42
1.7 DOOLITTLE’S METHOD WITH ROW INTERCHANGES  
 We have seen that Doolittle factorization of a matrix A may fail the moment 
at stage i we encounter a 
ii
u which is zero.  This occurrence corresponds to the 
occurrence of zero pivot at the i
th
 stage of simple Gaussian elimination method.  
Just as we avoided this problem in the Gaussian elimination method by 
introducing partial pivoting we can adopt this procedure in the modified Doolittle’s 
procedure.  The Doolittle’s method which is used to factorize A as LU is used 
from the point of view of reducing the system 
Ax = y 
to two triangular systems 
Lz = y 
Ux = z 
as already mentioned on page 19. 
 Thus instead of actually looking for a factorization A = LU we shall be 
looking for a system, 
A*x = y* 
and for which A* has LU decomposition. 
 We illustrate this by the following example:  The basic idea is at each stage 
calculate all the u
ii
 that one can get by the permutation of rows of the matrix and 
choose that matrix which gives the maximum absolute value for u
ii
. 
 As an example consider the system 
  Ax = y 
where 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
- -
-
- -
=
3 2 1 3
1 4 5 1
3 2 2 2
1 2 1 3
A
  y = 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
1
3
8
3
 
We want LU decomposition for some matrix that is obtained from A by row 
interchanges. 
We keep 1  
ii
l = for all i . 
Stage 1: 
1
st
 diagonal of U.  By Doolittle decomposition, 
u
11
 = a
11
 = 3 
If we interchange 2
nd
 or 3
rd
 or 4
th
 rows with 1
st
 row and then find the u
11
 for the 
new matrix we get respectively u
11
 = 2 or 1 or 3.  Thus interchange of rows does 
Page 2


 
42
1.7 DOOLITTLE’S METHOD WITH ROW INTERCHANGES  
 We have seen that Doolittle factorization of a matrix A may fail the moment 
at stage i we encounter a 
ii
u which is zero.  This occurrence corresponds to the 
occurrence of zero pivot at the i
th
 stage of simple Gaussian elimination method.  
Just as we avoided this problem in the Gaussian elimination method by 
introducing partial pivoting we can adopt this procedure in the modified Doolittle’s 
procedure.  The Doolittle’s method which is used to factorize A as LU is used 
from the point of view of reducing the system 
Ax = y 
to two triangular systems 
Lz = y 
Ux = z 
as already mentioned on page 19. 
 Thus instead of actually looking for a factorization A = LU we shall be 
looking for a system, 
A*x = y* 
and for which A* has LU decomposition. 
 We illustrate this by the following example:  The basic idea is at each stage 
calculate all the u
ii
 that one can get by the permutation of rows of the matrix and 
choose that matrix which gives the maximum absolute value for u
ii
. 
 As an example consider the system 
  Ax = y 
where 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
- -
-
- -
=
3 2 1 3
1 4 5 1
3 2 2 2
1 2 1 3
A
  y = 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
1
3
8
3
 
We want LU decomposition for some matrix that is obtained from A by row 
interchanges. 
We keep 1  
ii
l = for all i . 
Stage 1: 
1
st
 diagonal of U.  By Doolittle decomposition, 
u
11
 = a
11
 = 3 
If we interchange 2
nd
 or 3
rd
 or 4
th
 rows with 1
st
 row and then find the u
11
 for the 
new matrix we get respectively u
11
 = 2 or 1 or 3.  Thus interchange of rows does 
 
43
not give any advantage at this stage as we have already got 3, without row 
interchange, for u
11
. 
 
So we keep the matrix as it is and calculate 1
st
 row of U, by Doolittle’s method. 
11 12 12 13 13 14
3; 1 ; 2; 1 uu a u a u = = = = =- =- 
The first column of L: 
. 1
3
3
;
3
1
;
3
2
; 1
11
41
41
11
31
31
11
21
21 11
= = = = = = = =
u
a
l
u
a
l
u
a
l l 
Thus 
L is of the form 
32
42 43 44
10 0 0
2
10 0
3
1
10
3
1
l
ll l
??
??
??
??
??
??
??
??
; and 
 
U is of the form 
22 23 24
33 34
44
31 2 1
0
00
00 0
uuu
uu
u
-- ??
??
??
??
??
??
; A and Y remaining unchanged. 
 
Stage 2 
 
We now calculate the second diagonal of U:  By Doolittle’s method we have 
 
12 21 22 22
u l a u - =
 
        ()
3
8
1
3
2
2 - = ?
?
?
?
?
?
- - = 
Suppose we interchange 2
nd
 row with 3
rd
 row of A and calculate u
22
 : our new a
22
 
is 5. 
But note that 
21
l and 
31
l get interchanged.  Therefore new 
21
l is 1/3. 
Suppose instead of above we interchange 2
nd
 row with 4
th
 row of A: 
New a
22
 = 1   and    new l
21
 = 1   and    therefore new u
22
 = 1 – (1) (1) = 0 
Page 3


 
42
1.7 DOOLITTLE’S METHOD WITH ROW INTERCHANGES  
 We have seen that Doolittle factorization of a matrix A may fail the moment 
at stage i we encounter a 
ii
u which is zero.  This occurrence corresponds to the 
occurrence of zero pivot at the i
th
 stage of simple Gaussian elimination method.  
Just as we avoided this problem in the Gaussian elimination method by 
introducing partial pivoting we can adopt this procedure in the modified Doolittle’s 
procedure.  The Doolittle’s method which is used to factorize A as LU is used 
from the point of view of reducing the system 
Ax = y 
to two triangular systems 
Lz = y 
Ux = z 
as already mentioned on page 19. 
 Thus instead of actually looking for a factorization A = LU we shall be 
looking for a system, 
A*x = y* 
and for which A* has LU decomposition. 
 We illustrate this by the following example:  The basic idea is at each stage 
calculate all the u
ii
 that one can get by the permutation of rows of the matrix and 
choose that matrix which gives the maximum absolute value for u
ii
. 
 As an example consider the system 
  Ax = y 
where 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
- -
-
- -
=
3 2 1 3
1 4 5 1
3 2 2 2
1 2 1 3
A
  y = 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
1
3
8
3
 
We want LU decomposition for some matrix that is obtained from A by row 
interchanges. 
We keep 1  
ii
l = for all i . 
Stage 1: 
1
st
 diagonal of U.  By Doolittle decomposition, 
u
11
 = a
11
 = 3 
If we interchange 2
nd
 or 3
rd
 or 4
th
 rows with 1
st
 row and then find the u
11
 for the 
new matrix we get respectively u
11
 = 2 or 1 or 3.  Thus interchange of rows does 
 
43
not give any advantage at this stage as we have already got 3, without row 
interchange, for u
11
. 
 
So we keep the matrix as it is and calculate 1
st
 row of U, by Doolittle’s method. 
11 12 12 13 13 14
3; 1 ; 2; 1 uu a u a u = = = = =- =- 
The first column of L: 
. 1
3
3
;
3
1
;
3
2
; 1
11
41
41
11
31
31
11
21
21 11
= = = = = = = =
u
a
l
u
a
l
u
a
l l 
Thus 
L is of the form 
32
42 43 44
10 0 0
2
10 0
3
1
10
3
1
l
ll l
??
??
??
??
??
??
??
??
; and 
 
U is of the form 
22 23 24
33 34
44
31 2 1
0
00
00 0
uuu
uu
u
-- ??
??
??
??
??
??
; A and Y remaining unchanged. 
 
Stage 2 
 
We now calculate the second diagonal of U:  By Doolittle’s method we have 
 
12 21 22 22
u l a u - =
 
        ()
3
8
1
3
2
2 - = ?
?
?
?
?
?
- - = 
Suppose we interchange 2
nd
 row with 3
rd
 row of A and calculate u
22
 : our new a
22
 
is 5. 
But note that 
21
l and 
31
l get interchanged.  Therefore new 
21
l is 1/3. 
Suppose instead of above we interchange 2
nd
 row with 4
th
 row of A: 
New a
22
 = 1   and    new l
21
 = 1   and    therefore new u
22
 = 1 – (1) (1) = 0 
 
44
Of these 14/3 has largest absolute value.  So we prefer this.  Therefore we 
interchange 2
nd
 and 3
rd
 row. 
 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
- -
- -
=
1
8
3
3
;
3 2 1 3
3 2 2 2
1 4 5 1
1 2 1 3
Newy NewA 
1 000
31 2 1
1
10 0 14
0**
3
3
;
2
*10 00 * *
3
00 0 *
1 **1
NewL NewU
??
-- ??
??
??
??
??
==
??
??
??
??
??
??
??
??
??
 
 
Now we do the Doolittle calculation for this new matrix to get 2
nd
 row of U and 2
nd
 
column of L. 
 
13 21 23 23
u l a u - = 
         
() ()
3
10
2
3
1
4 - = - ?
?
?
?
?
?
- - =
 
14 21 24 24
u l a u - = 
          
() ()
3
2
1
3
1
1 - = - ?
?
?
?
?
?
- - =
 
2
nd
 column of L: 
[]
22 12 31 32 32
u u l a l ÷ - =
 
       () ()
3
14
1
3
2
2 ÷
?
?
?
?
?
?
?
?
?
?
?
?
- - = 
       
7
4
- = 
[]
11 12 41 42 42
u u l a l ÷ - = 
       ()() []
3
14
1 1 3 ÷ - = 
        = 0 
Page 4


 
42
1.7 DOOLITTLE’S METHOD WITH ROW INTERCHANGES  
 We have seen that Doolittle factorization of a matrix A may fail the moment 
at stage i we encounter a 
ii
u which is zero.  This occurrence corresponds to the 
occurrence of zero pivot at the i
th
 stage of simple Gaussian elimination method.  
Just as we avoided this problem in the Gaussian elimination method by 
introducing partial pivoting we can adopt this procedure in the modified Doolittle’s 
procedure.  The Doolittle’s method which is used to factorize A as LU is used 
from the point of view of reducing the system 
Ax = y 
to two triangular systems 
Lz = y 
Ux = z 
as already mentioned on page 19. 
 Thus instead of actually looking for a factorization A = LU we shall be 
looking for a system, 
A*x = y* 
and for which A* has LU decomposition. 
 We illustrate this by the following example:  The basic idea is at each stage 
calculate all the u
ii
 that one can get by the permutation of rows of the matrix and 
choose that matrix which gives the maximum absolute value for u
ii
. 
 As an example consider the system 
  Ax = y 
where 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
- -
-
- -
=
3 2 1 3
1 4 5 1
3 2 2 2
1 2 1 3
A
  y = 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
1
3
8
3
 
We want LU decomposition for some matrix that is obtained from A by row 
interchanges. 
We keep 1  
ii
l = for all i . 
Stage 1: 
1
st
 diagonal of U.  By Doolittle decomposition, 
u
11
 = a
11
 = 3 
If we interchange 2
nd
 or 3
rd
 or 4
th
 rows with 1
st
 row and then find the u
11
 for the 
new matrix we get respectively u
11
 = 2 or 1 or 3.  Thus interchange of rows does 
 
43
not give any advantage at this stage as we have already got 3, without row 
interchange, for u
11
. 
 
So we keep the matrix as it is and calculate 1
st
 row of U, by Doolittle’s method. 
11 12 12 13 13 14
3; 1 ; 2; 1 uu a u a u = = = = =- =- 
The first column of L: 
. 1
3
3
;
3
1
;
3
2
; 1
11
41
41
11
31
31
11
21
21 11
= = = = = = = =
u
a
l
u
a
l
u
a
l l 
Thus 
L is of the form 
32
42 43 44
10 0 0
2
10 0
3
1
10
3
1
l
ll l
??
??
??
??
??
??
??
??
; and 
 
U is of the form 
22 23 24
33 34
44
31 2 1
0
00
00 0
uuu
uu
u
-- ??
??
??
??
??
??
; A and Y remaining unchanged. 
 
Stage 2 
 
We now calculate the second diagonal of U:  By Doolittle’s method we have 
 
12 21 22 22
u l a u - =
 
        ()
3
8
1
3
2
2 - = ?
?
?
?
?
?
- - = 
Suppose we interchange 2
nd
 row with 3
rd
 row of A and calculate u
22
 : our new a
22
 
is 5. 
But note that 
21
l and 
31
l get interchanged.  Therefore new 
21
l is 1/3. 
Suppose instead of above we interchange 2
nd
 row with 4
th
 row of A: 
New a
22
 = 1   and    new l
21
 = 1   and    therefore new u
22
 = 1 – (1) (1) = 0 
 
44
Of these 14/3 has largest absolute value.  So we prefer this.  Therefore we 
interchange 2
nd
 and 3
rd
 row. 
 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
- -
- -
=
1
8
3
3
;
3 2 1 3
3 2 2 2
1 4 5 1
1 2 1 3
Newy NewA 
1 000
31 2 1
1
10 0 14
0**
3
3
;
2
*10 00 * *
3
00 0 *
1 **1
NewL NewU
??
-- ??
??
??
??
??
==
??
??
??
??
??
??
??
??
??
 
 
Now we do the Doolittle calculation for this new matrix to get 2
nd
 row of U and 2
nd
 
column of L. 
 
13 21 23 23
u l a u - = 
         
() ()
3
10
2
3
1
4 - = - ?
?
?
?
?
?
- - =
 
14 21 24 24
u l a u - = 
          
() ()
3
2
1
3
1
1 - = - ?
?
?
?
?
?
- - =
 
2
nd
 column of L: 
[]
22 12 31 32 32
u u l a l ÷ - =
 
       () ()
3
14
1
3
2
2 ÷
?
?
?
?
?
?
?
?
?
?
?
?
- - = 
       
7
4
- = 
[]
11 12 41 42 42
u u l a l ÷ - = 
       ()() []
3
14
1 1 3 ÷ - = 
        = 0 
 
45
Therefore new L has form 
10 00
1
10 0
3
24
10
37
10 *1
??
??
??
??
-??
??
??
??
 
 
New U has form 
31 2 1
10 14 2
0
33 3
00 * *
00 0 *
-- ??
??
--
??
??
??
??
??
 
 
This completes the 2
nd
 stage of our computation. 
 
Note:  We had three choices of u
22
 
to be calculated, namely –8/3, 14/3, 0 before 
we chose 14/3.  It appears that we are doing more work than Doolittle.  But this is 
not really so.  For, observe, that the rejected u
22
 namely – 8/3 and 0 when divided 
by the chosen u
22
 namely 14/3 give the entries of L below the second diagonal. 
 
3
rd
 Stage: 
3
rd
 diagonal of U: 
23 32 13 31 33 33
u l u l a u - - =
 
         ()
?
?
?
?
?
?
- ?
?
?
?
?
?
- - - ?
?
?
?
?
?
- =
3
10
7
4
2
3
2
2 
         
7
10
= 
Suppose we interchange 3
rd
 row and 4
th
 row of new A obtained in 2
nd
 stage.  We 
get new a
33
 = 2. 
But in L also the second column gets 3
rd
 and 4
th
 row interchanges 
Therefore new l
31
 = 1   and   new l
32
 = 0 
Therefore new u
33
 = a
33
 – l
31
 u
13
 – l
32
 u
23
 
        ()( ) ( )
?
?
?
?
?
?
- + - - =
3
10
0 2 1 2 
         = 4. 
Page 5


 
42
1.7 DOOLITTLE’S METHOD WITH ROW INTERCHANGES  
 We have seen that Doolittle factorization of a matrix A may fail the moment 
at stage i we encounter a 
ii
u which is zero.  This occurrence corresponds to the 
occurrence of zero pivot at the i
th
 stage of simple Gaussian elimination method.  
Just as we avoided this problem in the Gaussian elimination method by 
introducing partial pivoting we can adopt this procedure in the modified Doolittle’s 
procedure.  The Doolittle’s method which is used to factorize A as LU is used 
from the point of view of reducing the system 
Ax = y 
to two triangular systems 
Lz = y 
Ux = z 
as already mentioned on page 19. 
 Thus instead of actually looking for a factorization A = LU we shall be 
looking for a system, 
A*x = y* 
and for which A* has LU decomposition. 
 We illustrate this by the following example:  The basic idea is at each stage 
calculate all the u
ii
 that one can get by the permutation of rows of the matrix and 
choose that matrix which gives the maximum absolute value for u
ii
. 
 As an example consider the system 
  Ax = y 
where 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
- -
-
- -
=
3 2 1 3
1 4 5 1
3 2 2 2
1 2 1 3
A
  y = 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
1
3
8
3
 
We want LU decomposition for some matrix that is obtained from A by row 
interchanges. 
We keep 1  
ii
l = for all i . 
Stage 1: 
1
st
 diagonal of U.  By Doolittle decomposition, 
u
11
 = a
11
 = 3 
If we interchange 2
nd
 or 3
rd
 or 4
th
 rows with 1
st
 row and then find the u
11
 for the 
new matrix we get respectively u
11
 = 2 or 1 or 3.  Thus interchange of rows does 
 
43
not give any advantage at this stage as we have already got 3, without row 
interchange, for u
11
. 
 
So we keep the matrix as it is and calculate 1
st
 row of U, by Doolittle’s method. 
11 12 12 13 13 14
3; 1 ; 2; 1 uu a u a u = = = = =- =- 
The first column of L: 
. 1
3
3
;
3
1
;
3
2
; 1
11
41
41
11
31
31
11
21
21 11
= = = = = = = =
u
a
l
u
a
l
u
a
l l 
Thus 
L is of the form 
32
42 43 44
10 0 0
2
10 0
3
1
10
3
1
l
ll l
??
??
??
??
??
??
??
??
; and 
 
U is of the form 
22 23 24
33 34
44
31 2 1
0
00
00 0
uuu
uu
u
-- ??
??
??
??
??
??
; A and Y remaining unchanged. 
 
Stage 2 
 
We now calculate the second diagonal of U:  By Doolittle’s method we have 
 
12 21 22 22
u l a u - =
 
        ()
3
8
1
3
2
2 - = ?
?
?
?
?
?
- - = 
Suppose we interchange 2
nd
 row with 3
rd
 row of A and calculate u
22
 : our new a
22
 
is 5. 
But note that 
21
l and 
31
l get interchanged.  Therefore new 
21
l is 1/3. 
Suppose instead of above we interchange 2
nd
 row with 4
th
 row of A: 
New a
22
 = 1   and    new l
21
 = 1   and    therefore new u
22
 = 1 – (1) (1) = 0 
 
44
Of these 14/3 has largest absolute value.  So we prefer this.  Therefore we 
interchange 2
nd
 and 3
rd
 row. 
 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
- -
- -
=
1
8
3
3
;
3 2 1 3
3 2 2 2
1 4 5 1
1 2 1 3
Newy NewA 
1 000
31 2 1
1
10 0 14
0**
3
3
;
2
*10 00 * *
3
00 0 *
1 **1
NewL NewU
??
-- ??
??
??
??
??
==
??
??
??
??
??
??
??
??
??
 
 
Now we do the Doolittle calculation for this new matrix to get 2
nd
 row of U and 2
nd
 
column of L. 
 
13 21 23 23
u l a u - = 
         
() ()
3
10
2
3
1
4 - = - ?
?
?
?
?
?
- - =
 
14 21 24 24
u l a u - = 
          
() ()
3
2
1
3
1
1 - = - ?
?
?
?
?
?
- - =
 
2
nd
 column of L: 
[]
22 12 31 32 32
u u l a l ÷ - =
 
       () ()
3
14
1
3
2
2 ÷
?
?
?
?
?
?
?
?
?
?
?
?
- - = 
       
7
4
- = 
[]
11 12 41 42 42
u u l a l ÷ - = 
       ()() []
3
14
1 1 3 ÷ - = 
        = 0 
 
45
Therefore new L has form 
10 00
1
10 0
3
24
10
37
10 *1
??
??
??
??
-??
??
??
??
 
 
New U has form 
31 2 1
10 14 2
0
33 3
00 * *
00 0 *
-- ??
??
--
??
??
??
??
??
 
 
This completes the 2
nd
 stage of our computation. 
 
Note:  We had three choices of u
22
 
to be calculated, namely –8/3, 14/3, 0 before 
we chose 14/3.  It appears that we are doing more work than Doolittle.  But this is 
not really so.  For, observe, that the rejected u
22
 namely – 8/3 and 0 when divided 
by the chosen u
22
 namely 14/3 give the entries of L below the second diagonal. 
 
3
rd
 Stage: 
3
rd
 diagonal of U: 
23 32 13 31 33 33
u l u l a u - - =
 
         ()
?
?
?
?
?
?
- ?
?
?
?
?
?
- - - ?
?
?
?
?
?
- =
3
10
7
4
2
3
2
2 
         
7
10
= 
Suppose we interchange 3
rd
 row and 4
th
 row of new A obtained in 2
nd
 stage.  We 
get new a
33
 = 2. 
But in L also the second column gets 3
rd
 and 4
th
 row interchanges 
Therefore new l
31
 = 1   and   new l
32
 = 0 
Therefore new u
33
 = a
33
 – l
31
 u
13
 – l
32
 u
23
 
        ()( ) ( )
?
?
?
?
?
?
- + - - =
3
10
0 2 1 2 
         = 4. 
 
46
Of these two choices of u
33
 we have 4 has the largest magnitude.  So we 
interchange 3
rd
 and 4
th
 rows of the matrix of 2
nd
 stage to get 
 
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
-
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
-
- -
- -
=
8
1
3
3
3 2 2 2
3 2 1 3
1 4 5 1
1 2 1 3
NewY NewA
 
 
 
10 00
31 2 1
1
10 0 10 14 2
0
3
33 3
;
10 10
00 4 *
24
*1 00 0 *
37
NewL NewU
??
-- ??
??
??
?? --
??
==
??
??
??
??
??
??
??
-
??
??
 
 
Now for this set up we calculate the 3
rd
 stage entries as in Doolittle’s method: 
24 32 14 31 34 34
u l u l a u - - = 
        ()( ) ( ) 4
3
2
0 1 1 3 = ?
?
?
?
?
?
- - - - = 
()
33 23 42 13 41 43 43
u u l u l a l ÷ - - =
 
       () 4
3
10
7
4
2
3
2
2 ÷
?
?
?
?
?
?
?
?
?
?
?
?
- ?
?
?
?
?
?
- - - ?
?
?
?
?
?
- = 
       = 5/14. 
10 0 0
31 2 1
1
10 0 10 14 2
0
3
33 3
;
10 1 0
00 4 4
5 24
1 00 0 *
37 14
NewL NewU
??
-- ??
??
??
??
--
??
?= =
??
??
??
??
??
??
??
-
??
??
 
 
Note:   The rejected u
33
 divided by chosen u
33
 gives l
43.