Pivoting Switch order of equations,moving offending element off diagonal x1+x2=2 x1+x2=1∫ →2=and1=2-2= This is correct,even for small e(or even e=0) Compare size of diagonal (pivot)elements to e Ratio of first row of Vandermonde matrix =1:2T-1 Issue is relative size,not absolute size. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 17
Pivoting • Switch order of equations,moving offending element off diagonal • x1 + x2 = 2 x1 + x2 = 1 ⇒ x2 = 1−2 1− and x1 = 2 − x2 = 1 1− • This is correct,even for small (or even = 0) • Compare size of diagonal (pivot) elements to • Ratio of first row of Vandermonde matrix = 1 : 2n−1 Issue is relative size,not absolute size. Copyright c 2011, NA Yin Last Modification: Oct. 2011 17
Scaled Partial Pivoting Also called row pivoting (vs.column pivoting) Instability source:subtracting large values: .Find rowsi columnsj1:minimize O(n3)calculations!..simplify (remove k),imagine:ak1=1 。∴.findi3廿columnsj>1:minl Still 1)O(n2)calculations,2)how to minimize each row? ·Find:min,.orm Copyright©2011，NA⊙Yin Last Modification:Oct.2011 18
Scaled Partial Pivoting • Also called row pivoting (vs. column pivoting) • Instability source: subtracting large values: akj = aij aki aii • Find i 3 ∀ rows k 6= i,∀ columns j > 1:minimize |aij ak1 ai1 | • O(n 3 ) calculations!∴ simplify (remove k),imagine:ak1 = 1 • ∴ find i 3 ∀ columns j > 1 : mini | aij ai1 | • Still 1)O(n 2 )calculations,2)how to minimize each row? • Find i : mini maxj |aij| |ai1| ,or:maxi |ai1| maxj |aij| Copyright c 2011, NA Yin Last Modification: Oct. 2011 18