CS计算机代考程序代写 Gauss Elimination with Partial Pivoting

Gauss Elimination with Partial Pivoting
CS/SE 4X03
Ned Nedialkov McMaster University January 29, 2021

Outline
Example
GE with partial pivoting Scaled partial pivoting

Example GE with partial pivoting Scalled PP Example
Example 1. Consider
Solution is
10−5×1 + x2 = 1 x1 + x2 = 2
x1 = 1 ≈ 1+10−5 = 1.00001 1−10−5
x2 = 2−x1 ≈ 1−10−5 = 0.99999
Solve by Gauss elimination (GE) in 4-digit decimal floating-point arithmetic
Copyright © 2021 N. Nedialkov. All rights reserved. 3/16

Example GE with partial pivoting Scalled PP Example cont.
Example 1. cont.
• Multiply first row by 1/10−5 = 105 and subtract from second
10−5×1 + x2 = 1 (1−105)x2 =2−105
• Pivot 10−5
• Inthisarithmetic1−105 =2−105 =−105
• Second equation is −105×2 = −105
• Backward substitution gives
x􏰔 2 = 1 , x􏰔 1 = 1 − x􏰔 2 = 0 10−5
Solution is x1 ≈ 1.00001, x2 ≈ 0.99999
Copyright © 2021 N. Nedialkov. All rights reserved. 4/16

Example GE with partial pivoting Scalled PP Example cont.
Example 1. cont. • Error in x􏰔2 is
δ=x􏰔2−x2 ≈1−0.99999=10−5 • From 10−5×1 + x2 = 1,
x􏰔1 = 1−x􏰔2 = 1−(x2 +δ) 10−5 10−5
=1−x2− δ 10−5 10−5
= x1 − 105δ • Error in x􏰔1 is −105δ ≈ −1
• Error in x􏰔2 is multiplied by −105 in x􏰔1
Copyright © 2021 N. Nedialkov. All rights reserved. 5/16

Example GE with partial pivoting Scalled PP Example cont.
Example 1. cont. • Swap rows
x1 + x2 = 2 10−5×1 + x2 = 1
• Multiply first row by 10−5/1 and subtract from second x1 + x2 = 2
x2(1−10−5) = 1−2×10−5
• Inthisarithmetic1−10−5 =1−2×10−5 =1
• Second equation is x2 = 1
Copyright © 2021 N. Nedialkov. All rights reserved. 6/16
• Pivot 1

Example GE with partial pivoting Scalled PP Example cont.
Example 1. cont.
• Backward substitution gives
x􏰞 2 = 1
x􏰞 1 = 2 − x􏰞 2 = 1
• Error in x􏰞2 = 1 same as before
• From x1 + x2 = 2 and x􏰞2 = x2 + δ,
x􏰞1 =2−x􏰞2 =2−x2 −δ = x1 − δ
• Error δ in x􏰞2 is not magnified in x􏰞1
Copyright © 2021 N. Nedialkov. All rights reserved. 7/16

Example GE with partial pivoting Scalled PP GE with partial pivoting
GE with partial pivoting
• Choose the row with the largest (in magnitude) entry
Copyright © 2021 N. Nedialkov. All rights reserved. 8/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting
Example 2. Consider
2×1 + 2cx2 = 2c x1 + x2 = 2
c > 1 is a constant
• Partial pivoting: first row as pivot row (2 > 1)
• GE gives
2×1 + 2cx2 = 2c (1−c)x2 =2−c
• Forcsufficientlylarge,1−c≈−c,2−c≈−c
Copyright © 2021 N. Nedialkov. All rights reserved. 9/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 2. cont.
• Backward substitution gives
x􏰔2≈1, x􏰔1=2c−2cx􏰔2 ≈0 2
If δ = x􏰔2 − x2,
x􏰔1=2c−2cx􏰔2 =c−c(x2+δ)=c−cx2−cδ=x1−cδ
2
• Error is multiplied by c • True solution
x2 = c − 2 ≈ 1, x1 = c c−1 c−1
≈ 1
Copyright © 2021 N. Nedialkov. All rights reserved.
10/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 2. cont.
Chose the row with the largest entry with respect to the entries in
this row
2×1 + 2cx2 = 2c 1×1 + 1×2 = 1
• Scale vector s = (2c, 1), 2c largest in first row, 1 largest in second row
• Ratio vector
􏰅2 1􏰆 r= 2c,1
• Chose row with largest ratio as pivot row
• Eliminate with second row
Copyright © 2021 N. Nedialkov. All rights reserved.
11/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 2. cont.
• GE gives
x1 + x2 = 2 2×1 + 2cx2 = 2c
x1 + x2 = 2 (2c−2)x2 = 2c−4
• Backward substitution (when c sufficiently large) x􏰞 2 ≈ 1
x􏰞 1 ≈ 1
Copyright © 2021 N. Nedialkov. All rights reserved.
12/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 3.
Ax=−6 4 1 −18x2= 34 =b
3 −139 3x1 −19 6 −2 2 4 x3 16
12 −8 6 10 x4 26 • Scale vector s = (13, 18, 6, 12)
si = max{|aij| | j = 1,2,3,4}
• Ratio vector
􏰅3 6 6 12􏰆 r= 13,18,6,12
• Select index in r with largest ratio: 3 or 4
• Pick 3 and eliminate with row 3
Copyright © 2021 N. Nedialkov. All rights reserved.
13/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 3. cont.
0 −12 8 1 x1 −27
• Ratio vector
􏰅122 4􏰆 r = 13, 18,−, 12
0 2 3 −14x2=50  
6 −2 2 4x3 16 0−422×4 −6
• Scale vector s = (13, 18, 6, 12)
− means entry does not matter
• Select index from 1,2,4 with largest ratio: 1
• Eliminate with row 1
Copyright © 2021 N. Nedialkov. All rights reserved.
14/16

Example GE with partial pivoting Scalled PP Scaled partial pivoting cont.
Example 3. cont.
With rounding to 4 decimal places
0 −12 8
1 x1 −27 −13.8333 x2 = 45.5
0 0 6 −2 0 0
4.3333 2 −0.6667
4 1.6667
x3  16 
• Scale vector s = (13, 18, 6, 12) • Ratio vector
0.6667 􏰆 r= −, 18 ,−, 12
• Select index from 2,4 with largest ratio: 2 • Eliminate with row 2
􏰅 4.3333
x4
3
Copyright © 2021 N. Nedialkov. All rights reserved.
15/16

Example GE with partial pivoting Scalled PP Example 3. cont.
0 −12 8
1 x1 −27
−13.8333 x2 = 45.5 4 x3  16 
0 6
0
0 4.3333 −2 2
0 −0
−0.4615 x4
10
x4 = −21.6667
x3 = (45.5 − (−13.8333) ∗ (−21.6667))/(4.3333)
= −58.6671
x2 = (−27 − 8 ∗ (−58.6671) − 1 ∗ (−21.6667))/(−12)
= −38.6667
x1 = (16 − (−2) ∗ (−38.6667) − 2 ∗ (−58.6671) − 4 ∗ (−21.6667))/6
= 23.7779
Copyright © 2021 N. Nedialkov. All rights reserved. 16/16