Mathematical Preliminaries And Error Analysis

CHAPTER 1Mathematical Preliminaries and Error Analysis2. Review of CalculusNotation.C(X) — all functions continuous on the set X.C[a, b] — all functions continuous on the interval [a, b].C n(X) — all functions that have n derivatives continuous on X.C 1(X) — all functions that have derivatives of all orders on X.Theorem (Mean Value Theorem). If f 2 C[a, b] and f is di erentiableon (a, b), then a number c in (a, b) exists withf (b) f (a)f 0(c) b aorf (b) f (a) f 0(c)(b a).1

21. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISTheorem (Extreme Value Theorem). If f 2 C[a, b], then c1, c2 2 [a, b]exist with f (c1) f (x) f (c2) for all x 2 [a, b]. In addition, if f isdi erentiable on (a, b), then c1 and c2 occur either at the endpoints of [a, b]or where f 0 is zero.Theorem (Intermediate Value Theorem). If f 2 C[a, b] and K is anynumber between f (a) and f (b), then there exists c 2 (a, b) such that f (c) K.Corollary (Intermediate Value Theorem). If f 2 C[a, b] and f (a)f (b) 0, then there exists c 2 (a, b) such that f (c) 0.Note. This corollary is often used in approximating roots of equations.

2. REVIEW OF CALCULUS3Theorem (Taylor’s Theorem). Let f 2 C n[a, b] with f (n 1) existing on[a, b] and x0 2 [a, b]. For every x 2 [a, b], there exists a number (x)between x0 and x withf (x) Pn(x) Rn(x)where0Pn(x) f (x0) f (x0)(x nXf (k)(x0)k 0andNote.k!(xf 00(x0)x0) (x2!f (n)(x0)x0) · · · (xn!2x0)nx0)kf (n 1)( (x))Rn(x) (x(n 1)!x0)n 1.(1) f is the sum of a Taylor polynomial of order n (also called a Maclaurinpolynomial if x0 0) and a remainder term (or truncation error).(2) The case n 0 is just the Mean Value Theorem (MVT).f (x) P0(x) R0(x) f (x0) f 0( (x))(x {z } {zP0 (x)(3) If f is a polynomial of degree r, then for nRo (x)x0)}r, f (x) Pn(x).Maple. See taylor polynomials.mw and/or taylor polynomials.pdf

41. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISExample. Let f (x) 2x cos(2x)(x2)2, x0 0.(a)Find P3(x) and P4(x) and use them to approximate f (0.4).f 0(x) 2 cos(2x)4x sin(2x)2(x2)f 00(x) 4 sin(2x)8sin(2x)f 000(x) 16 cos(2x) 8 cos(2x) 16x sin(2x)24 cos(2x) 16x sin(2x)4 sin(2x) 8x cos(2x)8x cos(2x) 22f (4)(x) 48 sin(2x) 16 sin(2x) 32x cos(2x) 64 sin(2x) 32x cos(2x)f (5)(x) 128 cos(2x) 32 cos(2x) 64x sin(2x) 160 cos(2x) 64x sin(2x)f (0) P3(x) 4; f 0(0) 6; f 00(0) 2; f 000(0) 2 24 24 6x x x3 26f (0.4) P3(0.4) 24; f (4)(0) 04x32.016Since f (4)(0) 0,P4(x) P3(x) 4x3x2 6x4.x2 6x4

2. REVIEW OF CALCULUS5(b) Use the error formula in Taylor’s Theorem to find an upper bound forthe error f (0.4) P3(0.4) and f (0.4) P4(0.4) .By graphing, for 0 x 0.4, f (4)(x) 55.1 and f (5)(x) 160.Then f (4)( (x)) R3(.4) f (0.4) P3(0.4) .44!by rounding up. Similarly, f (5)( (x)) R4(.4) f (0.4) P4(0.4) .45!a better bound than for R3(.4) .0 4 55.1(.4)4 .05878240 5 160 5(.4) .01366,120The actual absolute error is f (0.4)P3(0.4) (.8 cos(.8)2.56)( 2.016) .01337.Notice that in this problem we are dealing with error at a point.

61. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISExample. Approximate sin(42 ) with error less than or equal to 10 6. 7 x 42 453 4 60 30 Use Taylor polynomial with x0 , so x x0 .4607 (x) ,304 7 f (n 1)( (x)) 7 n 11 n 1 .05236n 1Rn .30(n 1)!30 4(n 1)! 60(n 1)! 7 .052363Then R2 .0000239 and303! 7 .052364R3 .000000313 10 6, so take n 3.304!f (x) sin(x), f 0(x) cos(x), f 00(x) sin(x), f 000(x) cos(x),To find n, with f (x) sin(x) andsofThus 4p2 ,2f0 7 4p2 ,2 7 f 00 4 p2,2f 000 4 p2.2sin(42 ) sin P33030 f 00( 4 )f 000( 4 )02 f f(x x0) (x x0) (x x0)33!p 4 p 4 p 2! p 22 2 22 3 .669130422604601260 7 From the TI-89, sin .6691306,30 7 so sin(42 ) P3 .0000002 2 10 7. 30Maple. See taylor’s error.mw and/or taylor’s error.pdf

3. ROUND-OFF ERROR AND COMPUTER ARITHMETIC73. Round-o Error and Computer ArithmeticMaple. See computernumbers.mw and/or computernumbers.pdfThere are problems in using a finite subset of the reals (rational numbers,actually) to represent all reals.Suppose each machine number can be represented as a k-digit decimal machinenumber in floating-point form as 0.d1d2 · · · dk 10n,1 d1 9,0 di 9,i 2, . . . , k.Suppose y 0.d1d2 · · · dk dk 1dk 2 10n is in the numerical range of the machine.Two methods for getting the floating-point form of k digits f l(y):(1) f l(y) 0.d1d2 · · · dk 10n is chopping.(2) rounding: add 5 10n(k 1)and then chop to get 0.1 2··· k 10m.We refer to both cases as round-o error.Example (of rounding). Suppose we wish to round .372648 103 and.372653 103 with k 4 and n 3, so5 10n.372648 103.000050 103.372698 103Now chop:.3726 103(k 1) 5 102 5 10.372653 103.000050 103.372703 103.3727 103 5 103 .00005 103.

81. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISMeasuring approximation errors:Suppose p? approximates p:absolute error prelative error pp? p? p Problem (p.20, #1a). p ,absolute error relative error 227 227 p? 227. .001264489267. 4.02499434755 10 4. Since 4 is the largest nonnegative value of t for whichrelative error 5 10twe say p? approximates p to 4 significant digits.An approximation to floating-point arithmetic:xy fl(fl(x) fl(y))x y fl(fl(x) fl(y))xy fl(fl(x)x y fl(fl(x) fl(y))fl(y))In Maple, “Digits: t;” causes all arithmetic to be rounded to t digits (10 is thedefault), and, for example,xy corresponds to evalf(evalf(x) evalf(y)).

3. ROUND-OFF ERROR AND COMPUTER ARITHMETIC9There are problems to be noted with subtraction:Example. Use 4 digit choppingfl( ) 3.141relative error 1.89 10fl( 227 ) 3.142relative error 2.73 1044Both representations have 4 significant digits, but227 fl(3.142relative error ( 2273.141) 0.001 with ) ( 2270.001 2.09 10 1, ) yielding a result with only 1 significant digit. Thus subtracting nearly equal numbers cancels significant digits, and these cannot be recovered. We get small absolute error, but large relative error.

101. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSIS4. Errors in Scientific ComputationSequencing of operations can make a di erence:Problem (p.28, #1b). Use four digit rounding to find the roots of1 12392.2554197358 and4 x6 0. Note that the exact roots round to.005419735789.1 23xThe quadratic formula for ax2 bx c 0 givespb b2 4acbx1 and x2 2aas solutions.pb22a4aca .3333, b 30.75, c .1667, b2 945.6, ac .0556, 4ac ppb2 4ac 945.8, b2 4ac 30.75, b b2 4ac 0pbb2 4ac 61.50, and 2a .6666, sox1 061.50 0 and x2 .6666.6666.222492.26, andrelative error 1 and relative error 4.96 10 5.Thus we have no and 5 significant digits. But rationalizing numerators,2c2cppx1 and x2 ,b b2 4acbb2 4acso 2c x1 .3334, b pb24ac 61.5, and b.3334 .005421 and x2 61.5pb24ac 0, giving.3334, undefined.0Relative error for x1 is 2.3 10 4, giving 4 significant digits. Maple. See nested.mw and/or nested.pdf

4. ERRORS IN SCIENTIFIC COMPUTATION11algorithm — a procedure that unambiguously describes a finite, ordered sequence of steps to solve a problem or approximate a solution.stable algorithm — small changes in initial data produce small changes inthe final resultsunstable algorithm — not stableconditionally stable algorithm — stable only for certain choices of initial dataGrowth of round-o error:Suppose an error E0 0 is introduced at some stage of the calculations andthe error after n subsequent operations is En.linear growth of (relative) error — En CnE0, where C is a constantindependent of n. This reflects a stable algorithm.exponential growth of (relative) error — En C nE0 for some C 1. Thisreflects an unstable algorithm.Maple. See convergence.mw and/or convergence.pdf.

121. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISRates of convergence for sequences:Our algorithms often generate sequences of values. Suppose { n} ! andn ! 0. Recall{ n} 1, 2, 3, . . . , n, . . .and{ n} ! means lim n .n!1If there exists K 0 such that n K n for large n,we say { n} converges to with a rate of convergence O( n) (“big oh of n”)1or { n} ! with rate of convergence O( n). Usually, n p for some 1 np 0. We want the largest such value p so that n O p .nn 2n 3 on 2n3 3 oExample. Consider! 2 and! 2.n 7n3 7n1234562n 3n 72n 3n 7.625000.777778.9000001.0000001.0833331.1538462n3 311n3 7nn3.625000 1.000000 1.0000001.266667 .500000 .1250001.676471 .333333 .0370371.845070 .250000 0.156251.916667 .200000 .00800001.950673 .1666687 .0046302n 3 2n 14111111 11 ·( n )n 7n 7n 7nn 1 1 2n 31so 2 Oand the rate of convergence is Osince lim 0.n!1 nn 7nn2

4. ERRORS IN SCIENTIFIC COMPUTATION2n3 32n3 3 2n32 n3 7n3 714 11111 11·n3 7n3 7n313(n 1)n3 1 1 2n3 31so 3 2 O 3 and rate of convergence is O 3 since lim 3 0.n!1 nn 7nn n1oProblem (p.29 #10b). Find the rate of convergence of sin 2 .n1sin hsin k 2We know lim 2 0. From calculus, lim 1 ) lim 1)n!1 nh!0 hk 2 !0 k 2 sin n121 11letting k lim 1 1 2. Then, for large n, sin 2 2 · 2 .n n!1 n2nn 1 1 11Since lim 2 0, sin 2 0 O 2 , so rate of convergence is O 2 . n!1 nnnnWe can also use the big oh notation to show how some divergent sequencesgrow as n becomes large. If positive constants p and K exist with n Knp for all large values of n,we say that { n} ! 1 with rate of convergence O(np).Finally, we can use big oh for functions.Suppose lim G(h) 0 and lim F (h) L. If there is K 0 such thath!0 F (h)h!0L K G(h) for h small enough, then F (h) L O(G(h)).Usually, we like to use G(h) hp, and want the largest p such thatF (h) L O(hp).

141. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSISRecall.h2hne e 1 h ··· hn 12n! (n 1)!hh3 h5 3!5!sin h hcos h 1( 1)nh2n 1 ( 1)n 1 cos 2n 3··· h(2n 1)!(2n 3)!h2 h4 2!4!1 11 h( 1)nh2n ( 1)n 1 cos 2n 2··· h(2n)!(2n 2)!2h h( 1)n 1 n 1· · · ( 1) h h(1 )n 2n nProblem (p.29 #11b). Find the rate of convergence for lime 2e 1 h h ) 12heh1h 1 he cos hh!0cos hcos h1 2 1 4h h224111 h2 h42241 12 h2 h41 12 h2h41124 {z}hcos 6h )720cos 2h )720 {z } O(h2 )1cos 21 2 h h .24720720 1.e h )21 O(h). 1 12 h2and its rate of convergence.h4cos 6h for 0 h )720Looks like Lcos hh!0e 21 ehh h for h small enough. Thus 22hExample. Find limcos h 1he 21 ehh ) 2heh1

4. ERRORS IN SCIENTIFIC COMPUTATIONThus limh!0cos hcos h1 12 h21 with rate of convergence O(h2) or4h241 12 h21 O(h2). 4h2415

Example (of rounding). Suppose we wish to round .372648 103 and.372653 103 with k 4 and n 3, so 5 10n(k 1) 5 102 5 105 103 .00005 103.372648 103.372653 103.000050 103.00005