Gauss Elimination
CS/SE 4X03
Ned Nedialkov McMaster University January 28, 2021
Outline
Gauss elimination
a1,1 a1,2 ··· a1,n b1
aa ···a b
2,1 2,2 2,n 2
aa ···a b 3,1 3,2 3,n
3 [A | b] =
. . . . .
aa···ab n,1 n,2 n,n n
• Multiply first row by a2,1/a1,1 and subtract from second row • Multiply first row by a3,1/a1,1 and subtract from third row
• ···
• Multiply first row by an,1/a1,1 and subtract from nth row
Copyright © 2021 N. Nedialkov. All rights reserved. 3/1
Gauss elimination cont.
Example 1.
1 −1 3×1 ×3 A=110↓
3 −2 1
1−1 3 A(1)=0 2−3
0 1 −8
↓
Copyright © 2021 N. Nedialkov. All rights reserved.
4/1
Gauss elimination cont.
aaa···ab 1,1 1,2 1,3 1,n 1
0 a(1) a(1) ··· a(1) b(1)
2,2 2,3 2,n 2
0 a(1) a(1) ··· a(1) b(1)
A
| b
= 0 a(1) a(1) · · · a(1) b(1)
(1) (1)
3,2 3,3 3,n
3
• Multiply second row by a(1)/a(1) 3,2 2,2
• Multiply second row by a(1)/a(1) 4,2 2,2
• ···
• Multiply second row by a(1) /a(1)
and subtract from third row and subtract from forth row
4,2 4,3 4,n 4
….. . . . . .
(1) (1) (1) (1)
0 a a ··· an,n bn
n,2
n,3
and subtract from nth row
Copyright © 2021 N. Nedialkov. All rights reserved. 5/1
n,2 2,2
(2) (2)
A |b =
3,3 0 0 a(2)
4,n4
aaa···ab
2,2 2,3 0 0 a(2)
··· a(1) b(1)
2,n 2
··· a(2) b(2)
3,n 3
··· a(2) b(2)
1,1 1,2 1,3 0 a(1) a(1)
1,n 1
4,3
. . . . .
(2) (2)(2) 0 0 an,3 ··· an,n bn
• Keep eliminating until upper triangular system
…..
Copyright © 2021 N. Nedialkov. All rights reserved. 6/1
Gauss elimination cont.
1−1 3 A(1)=0 2 −3 ×1/2
01−8 ↓
1−1 3 A(2) = 0 2 −3
0 0 −6.5
Copyright © 2021 N. Nedialkov. All rights reserved. 7/1
Gauss elimination
Algorithm
Algorithm 1.1 (Gauss elimination). for k = 1 : n − 1
for i = k + 1 : n mik = aik/akk % update row for j = k + 1 : n
aij =aij −mikakj bi = bi − mikbk
% for each row % for each row below kth % multiplier
Copyright © 2021 N. Nedialkov. All rights reserved.
8/1
% update bi
Gauss elimination
Cost
• We do not count the operations for updating b
• The third nested for loop executes n − k times
◦ n − k multiplications ◦ n − k additions
• The work per one iteration of the second nested for loop is 2(n − k) + 1, the 1 comes from the division
• This loop executes n − k times
• The total work for the second nested for loop is
2(n−k)2 +(n−k)
• The work for the outermost for loop is
n−1 n−1 n−1 2(n−k)2 +(n−k)=2k2 +k k=1 k=1 k=1
Copyright © 2021 N. Nedialkov. All rights reserved.
9/1
Gauss elimination
Cost
Since12+22+32+···+n2 =n(n+1)(2n+1)/6
n−1
k2 = (n−1)(n−1+1)(2(n−1)+1)/6 k=1
= n3/3 − n2/2 + n/6 Using the above and n−1 k = (n−1)n ,
n−1 n−1
2k2 +k=2n3/3−2n2/2+2n/6+n2/2−n/2
k=1 k=1
= 2n3/3 − n2/2 − n/6 = 2n3/3 + O(n2)
Total work for Gauss elimination is 2/3n3 + O(n2)
Copyright © 2021 N. Nedialkov. All rights reserved. 10/1
k=1 2
Backward substitution
• After GE, we have
a1,1 a1,2 a1,3 ···
a1,n x1 b1
a2,n x2 b2
a3,n x3 b3
..=.
a2,2 a2,3 ··· a3,3 ···
• xn = bn/an,n
• an−1,n−1xn−1 + an−1,nxn = bn−1
xn−1 = (bn−1 − an−1,nxn)/an−1,n−1 •x=b−n a x/a
k k j=k+1 k,j j k,k
. . . aaxb
n−1,n−1 n−1,n n−1
n−1 bn
Copyright © 2021 N. Nedialkov. All rights reserved.
11/1
an,n
xn
Backward substitution
Algorithm
Algorithm 2.1 (Backward substitution). for k = n : −1 : 1
x=b−n a x/a
k k j=k+1 k,j j k,k
Copyright © 2021 N. Nedialkov. All rights reserved. 12/1
Backward substitution
Cost
• The work per iteration is ◦ n − k multiplications
◦ (n−k−1)+1 additions
◦ 1 division
◦ total 2(n − k) + 1 operations
• Total work is
nnn
(2(n − k) + 1) = 2 (n − k) + 1
k=1
k=1 k=1
n−1 n(n − 1)
=2k+n=2 2 +n k=1
=n2 −n+n=n2
Copyright © 2021 N. Nedialkov. All rights reserved. 13/1
Total cost
• GE: 2n3/3−n2 +n/6
• Backward substitution: n2
• Total cost for solving Ax = b is
2n3/3 + n2/2 + n/6 = 2n3/3 + O(n2) = O(n3)
Copyright © 2021 N. Nedialkov. All rights reserved. 14/1