CS计算机代考程序代写 algorithm Gauss Elimination

Gauss Elimination
CS/SE 4X03
Ned Nedialkov McMaster University January 28, 2021

Outline

Gauss elimination
 a1,1 a1,2 ··· a1,n b1 
a􏰭a ···a b
 2,1 2,2 2,n 2  􏰭
a􏰭a ···a b  3,1 3,2 3,n
3  [A | b] =  􏰭 
. . . . . 
a􏰭a···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)􏰘=2􏰄k2 +􏰄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
2􏰄k2 +􏰄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
.  .   .  aaxb
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
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)
=2􏰄k+n=2 2 +n k=1
=n2 −n+n=n2
Copyright © 2021 N. Nedialkov. All rights reserved. 13/1

Related Posts