Zero Pivots Clearly,zero pivots prevent forward elimination Attention:zero pivots can appear along the way Later:Where guaranteed no zero pivots? ●All pivots≠0→？we are safe Experiment with system with known solution. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 12
Zero Pivots • Clearly, zero pivots prevent forward elimination • Attention: zero pivots can appear along the way • Later: Where guaranteed no zero pivots? • All pivots 6= 0 ⇒? we are safe Experiment with system with known solution. Copyright c 2011, NA Yin Last Modification: Oct. 2011 12
Vandermonde Matrix 71 2 4 8 2n-1 1 3 9 27 3n-1 1 x 16 64 4n-1 1 n+1 (n+1)2 (n+1)3 (n+1)n-1 :emn521+普 .We obtain bi,for row i=1,...,n +- 、2 aij 6 System is ready to be tested. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 13
Vandermonde Matrix 1 2 4 8 · · · 2 n−1 1 3 9 27 · · · 3 n−1 1 4 16 64 · · · 4 n−1 ... ... ... ... ... ... 1 n + 1 (n + 1)2 (n + 1)3 · · · (n + 1)n−1 • What row sums on RHS ⇒ xi = 1, i = 1, . . . , n • Geometric series: 1 + t + t 2 + · · · + t n−1 = t n−1 t−1 • We obtain bi , for row i = 1, . . . , n X n j=1 (1 + i) j−1 | {z } aij · 1 |{z} xj = (1 + i) n − 1 (1 + i) − 1 = 1 i [(1 + i) n − 1] | {z } bi System is ready to be tested. Copyright c 2011, NA Yin Last Modification: Oct. 2011 13
Vandermonde Test Platform with 7 significant (decimal)digits *n 1,...,8=expected results *n=9:error>16,000% ●Question: What happened? Why so sudden? Can anything be done? Answer:matrix is "ill-conditioned" Sensitivity to roundoff errors Leads to error propagation and magnification First,how to assess vector errors. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 14
Vandermonde Test • Platform with 7 significant (decimal) digits ∗ n = 1, . . . , 8 ⇒ expected results ∗ n = 9: error > 16, 000%!! • Question: ∗ What happened? ∗ Why so sudden? ∗ Can anything be done? • Answer: matrix is ”ill-conditioned” ∗ Sensitivity to roundoff errors ∗ Leads to error propagation and magnification First, how to assess vector errors. Copyright c 2011, NA Yin Last Modification: Oct. 2011 14
Errors Given system:Ax =b and solution estimate ·Residual(error):r≡At-b ●Absolute error(if x is known:e≡c-x Norm taken of r or e:vector->scalar quantity (more on norms later) Relative errors:l/and lel/l Back to ill-conditioning,.. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 15
Errors • Given system: Ax = b and solution estimate x˜ • Residual (error): r ≡ Ax˜ − b • Absolute error (if x is known): e ≡ x − x˜ • Norm taken of r or e: vector → scalar quantity (more on norms later) • Relative errors: krk/kbk and kek/kxk Back to ill-conditioning, ... Copyright c 2011, NA Yin Last Modification: Oct. 2011 15
Ill-conditioning 。 0x1+x2=11 c1+x2=2 }→0piot 。General rule:if 0 is problematic→ numbers near 0 are problematic 十2}=nd1=之 x1+x2=2 .e small (e.g.,e=10-9 with 8 significant digits)=x2=1 and z1=0-wrong! what can be done? Copyright©2011，NA⊙Yin Last Modification:Oct.2011 16
Ill-conditioning • 0 · x1 + x2 = 1 x1 + x2 = 2 ⇒ 0 pivot • General rule:if 0 is problematic ⇒ numbers near 0 are problematic • x1 + x2 = 1 x1 + x2 = 2 . . . x2 = 2−1/ 1−1/ and x1 = 1−x2 • small (e.g., = 10−9 with 8 significant digits)⇒ x2 = 1 and x1 = 0–wrong! what can be done? Copyright c 2011, NA Yin Last Modification: Oct. 2011 16