Floating Point Arithmetic and Rounding Error Analysis Claude-Pierre Jeannerod (cid:21) Nathalie Revol Inria(cid:21)LIP,ENSdeLyon Finite precision ⇒ rounding errors: 2.3456×5.4321=12.74153376 2.3456 / 5.4321=0.43180353822646858489... 2.3456+5.4321=7.7777 What is the e(cid:27)ect of all such errors on the computed solution x ? (cid:98) Context Starting point: How do numerical algorithms behave in (cid:28)nite precision arithmetic? Typically, (cid:73) basic matrix computations: Ax = b, ... (cid:73) (cid:29)oating-point arithmetic as speci(cid:28)ed by IEEE 754. 2 2.3456 / 5.4321=0.43180353822646858489... 2.3456+5.4321=7.7777 What is the e(cid:27)ect of all such errors on the computed solution x ? (cid:98) Context Starting point: How do numerical algorithms behave in (cid:28)nite precision arithmetic? Typically, (cid:73) basic matrix computations: Ax = b, ... (cid:73) (cid:29)oating-point arithmetic as speci(cid:28)ed by IEEE 754. Finite precision ⇒ rounding errors: 2.3456×5.4321=12.74153376 2 2.3456+5.4321=7.7777 What is the e(cid:27)ect of all such errors on the computed solution x ? (cid:98) Context Starting point: How do numerical algorithms behave in (cid:28)nite precision arithmetic? Typically, (cid:73) basic matrix computations: Ax = b, ... (cid:73) (cid:29)oating-point arithmetic as speci(cid:28)ed by IEEE 754. Finite precision ⇒ rounding errors: 2.3456×5.4321=12.74153376 2.3456 / 5.4321=0.43180353822646858489... 2 What is the e(cid:27)ect of all such errors on the computed solution x ? (cid:98) Context Starting point: How do numerical algorithms behave in (cid:28)nite precision arithmetic? Typically, (cid:73) basic matrix computations: Ax = b, ... (cid:73) (cid:29)oating-point arithmetic as speci(cid:28)ed by IEEE 754. Finite precision ⇒ rounding errors: 2.3456×5.4321=12.74153376 2.3456 / 5.4321=0.43180353822646858489... 2.3456+5.4321=7.7777 2 Context Starting point: How do numerical algorithms behave in (cid:28)nite precision arithmetic? Typically, (cid:73) basic matrix computations: Ax = b, ... (cid:73) (cid:29)oating-point arithmetic as speci(cid:28)ed by IEEE 754. Finite precision ⇒ rounding errors: 2.3456×5.4321=12.74153376 2.3456 / 5.4321=0.43180353822646858489... 2.3456+5.4321=7.7777 What is the e(cid:27)ect of all such errors on the computed solution x ? (cid:98) 2 In this lecture, two approaches: A priori analysis: (cid:73) Goal: bound on ||x −x||/||x|| for any input and format (cid:98) (cid:73) Tool: the many nice properties of (cid:29)oating-point (cid:73) Ideal: readable, provably tight bound + short proof A posteriori, automatic analysis: (cid:73) Goal: x and enclosure of x −x for given input and format (cid:98) (cid:98) (cid:73) Tool: interval arithmetic based on (cid:29)oating-point (cid:73) Ideal: a narrow interval computed fast Rounding error analysis Old and nontrivial question [von Neumann, Turing, Wilkinson, ...] 3 A posteriori, automatic analysis: (cid:73) Goal: x and enclosure of x −x for given input and format (cid:98) (cid:98) (cid:73) Tool: interval arithmetic based on (cid:29)oating-point (cid:73) Ideal: a narrow interval computed fast Rounding error analysis Old and nontrivial question [von Neumann, Turing, Wilkinson, ...] In this lecture, two approaches: A priori analysis: (cid:73) Goal: bound on ||x −x||/||x|| for any input and format (cid:98) (cid:73) Tool: the many nice properties of (cid:29)oating-point (cid:73) Ideal: readable, provably tight bound + short proof 3 Rounding error analysis Old and nontrivial question [von Neumann, Turing, Wilkinson, ...] In this lecture, two approaches: A priori analysis: (cid:73) Goal: bound on ||x −x||/||x|| for any input and format (cid:98) (cid:73) Tool: the many nice properties of (cid:29)oating-point (cid:73) Ideal: readable, provably tight bound + short proof A posteriori, automatic analysis: (cid:73) Goal: x and enclosure of x −x for given input and format (cid:98) (cid:98) (cid:73) Tool: interval arithmetic based on (cid:29)oating-point (cid:73) Ideal: a narrow interval computed fast 3 Rounding error analysis Old and nontrivial question [von Neumann, Turing, Wilkinson, ...] In this lecture, two approaches: A priori analysis: → this lecture (cid:73) Goal: bound on ||x −x||/||x|| for any input and format (cid:98) (cid:73) Tool: the many nice properties of (cid:29)oating-point (cid:73) Ideal: readable, provably tight bound + short proof A posteriori, automatic analysis: → Nathalie’s lecture (cid:73) Goal: x and enclosure of x −x for given input and format (cid:98) (cid:98) (cid:73) Tool: interval arithmetic based on (cid:29)oating-point (cid:73) Ideal: a narrow interval computed fast 4