Intro Numerical Analysis
Intro Numerical Analysis MATH 441
Popular in Course
Popular in Mathematics (M)
This 88 page Class Notes was uploaded by Alphonso Thompson on Thursday October 29, 2015. The Class Notes belongs to MATH 441 at Western Carolina University taught by Erin McNelis in Fall. Since its upload, it has received 10 views. For similar materials see /class/230961/math-441-western-carolina-university in Mathematics (M) at Western Carolina University.
Reviews for Intro Numerical Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Muller s Method MATH 441541 Numerical Analysis Sixth Meeting Computer Arithmetic Continued amp Root Finding Algorithms Thursday September 27th 1 Given the continuous function x and three reasonable guesses to the root7 m0 m1 and 2 2 A Visual Explanation 3 The Formula for the New Guess for the Root Given three guesses7 m0 m1 and 2 generate the new approximation7 mg as 20 m m 7 3 2 b sgnbb2 7 4m where C 902 b 900 22f901 HM 901 22f900 H902 900 902K951 902K950 901 a 901 22f0 7 f10 22f1 7 mm 900 902K951 902K950 901 4 Strengths and Weaknesses 5 Rates of Convergence for Methodsl Bisection Secant Newton False Position Fixed Point Muller s Oz 2 1 5 a 1 a T f 162 for simple roots a 1 a x 1839 04 l for multiple roots 1For Miiller s Method rate in particular see Michael T Heath Scienti c Computing An Introductory Survey7 2nd Ed McGraw Hill7 2002 Page 234 Interpolation And Polynomial Approximation 0 Section 31 Interpolation and the Lagrange Polynomial The Concept How is this different from similar to regression How is this different from similar to using Taylor Polynomials Reminder of Taylor Polynomials and Their Error Terms Lagrange Polynomial a Deriving the Concept and Terms 139 L m 7 95095 7 1 i 7 MAX 7 k1nim m7L n 9 90090k 901 9 k71k n1 9 m ii The nth degree Lagrange Polynomial Pnz through the points mo fm0 zn is given by Pam P101 39n7 Lofzo L1f1 Lnmf b An Example Find the Second Order Lagrange Polynomial through the points 1 3 4 2 and 6 5 from the function fm and use it to approximate f2 c The Error Term d The Uniqueness of the lnterpolating Polynomial Theorem 32 If m0 m1 mn are n 1 distinct numbers and f is a function whose values are given at these numbers then a unique polynomial Pm of degree at most 71 exists with u Pzk k01n where this polynomial is given by 0 Section 32 Divided Differences H Question What if you had P1m through points mo f0 and x1 fm1 and you wanted to generate P2z which also passes through 2 fm2 How would you do this to New Notations a New way for writing the Lagrange Polynomial of degree n Pnz b Divided Difference Notation Connecting the Lagrange Polynomial and Divided Differences ugtos An Excel Example See Excel DividedDifferencesxls Handout MATH 441541 Numerical Analysis Eighth Meeting Interpolation Thursday October 18th 2007 Interpolation And Polynomial Approximation 0 Section 34 Cubic Spline Interpolation 1 Piecewise Polynomial Approximations 7 Global interpolation versus local interpolation 7 Varying degree piecewise polynomial approximations and associated degrees of freedom a Piecewise Constant Interpolation b Piecewise Linear Interpolation c Piecewise Quadratic Interpolation d Piecewise Cubic Interpolation 2 Cubic Splines The most common piecewise polynomial approximation 7 De nition Cubic Spline Interpolant Given a function 1 de ned on 11 and a set of nodes a mo lt ml lt lt zn b a cubic spline interpolant S for f is a function that satis es where Sm is a cubic polynomial denoted Sjm on the subinterval mg741 for each j O 1 n 7 1 that satis es the following conditions a Interpolation Condition Smj fzj for each j O 1 n Continuity of Interpolant Sj1zj1 Sjzj1 for each j O 1 7 7 2 ET Continuity of the Derivative S1zj1 Szj1 for each j 01 n 7 2 d Continuity of the Second Derivative S z l S mj1 for eachj O 1 n72 Free or Natural Boundary S m0 S zn 0 Natural Spline Clamped Boundary S z0 f z0 and S zn f mn Complete Cubic Spline iii NotaKnot Condition S is linear across 02 and znqmn ie you are tting a cubic polynomial across 0 2 and a cubic polynomial across n iv Parabolic Endpoints S m0 S m1 and S zn1 S zn ie the cubics approach parabolas at their extremities 7 A picture 7 The general formula On each subinterval j j 0 n 7 1 we have 5190 1739 balm 901W 0190 90739 17190 mg 7 Example Problem 12 from Section 34 p 154 Suppose we have a clamped cubic spline 3z for data from some function fz de ned on 13 and given by 7 80m3x712m7127m713 if1 mlt2 S a 31zabz72cm722dx723 if2 x 3 Given f 1 f 3 nd a b c and d 7 Splines in MATLAB 1 Numerical Differentiation 0 Section 41 Numerical Differentiation the Calculus Way Approximating f z0 7 Finding a Bound for the Error 1 Using the Taylor Polynomial 2 Using Lagrange Polynomials 3 A Problem to Be Aware Of When Reducing Size of Error 4 ForwardDifference vs BackwardDifference Formula 7 Higher Order Methods 71 1Point Formulas Derivation DH Three and FivePoint Formulas Examples Problem 9b 9367879 8233241 7180350 6209329 5320305 4513417 7 Higher Order Derivatives 7 Comparing Roundoff Error to Truncation Error 7 When Do We Really Want to Approximate the Derivative Numerically An Example Consider the following boundary value problem 471g 7lmg l3ygz7 0 mlt1 subject to 340 37 341 7 2 Numerical Integration 0 Section 43 Basic Numerical Quadrature Methods 7 What is Numerical Quadrature 7 Integrating the Lagrange Interpolating Polynomial 7 Useful Theorems and De nitions Weighted Mean Value Theorem for Integrals Suppose f E Chub7 the Riemann integral of 9 exists on 11 and gz does not change sign on 11 Then there exists a number 0 in 11 with b b fltzgtgltzgt dz 7a gltzgt dz 1 1 Degree of Accuracy The degree of accuracy7 or precision7 of a quadrature formula is the largest positive integer n such that the formula is exact for x M for each k O7 17 771 So7 look at the error term If it has derivatives of H then all polynomials of degree n 7 1 will vanish by the nth derivative7 f 7 Basic Quadrature Rules 1 Trapezoid Rule Integrating the rst order Lagrange Polynomial 2 Simpson7s Rule Integrating the third order Taylor polynomial about 1 over 07 2 3 n 1Point Open and Closed NewtonCotes Formulas a The n 1point Closed NewtonCotes formula uses nodes xi mo 271 for i b 017 7n where mo a7 zn b and h T approximating 1171435 dm A fx dz z gai xi where ai 50quot b The n 1point open NewtonCotes formula uses nodes xi 0 ih for i 017 7n where mo a 71x b 7 h and h fig approximating dm A dm gai m with the same ai de nition as above 4 Associated Error Values a For n1point Closed NewtonCotes formula Suppose that 20 Ll u denotes the n 1 point closed Newton Cotes formula with 0 a7 zn b and h b 7 an There exists 5 E 071 for which 17 hn3fn2 E n AWE 190 gaifzi t2t71t7ndt if n is even and f E Cnizm7 b7 and b i n I I hn2fn1 n Afmd7alfmlWO tt7lt7ndt if n is odd and f E Cn1ab b For 71 1point open NewtonCotes formula Suppose that 220 Ll u denotes the n 1 point open Newton Cotes formula with 0 a h mn b 7 h and h b 7 an 2 There exists 5 6 11 for which b n hn3fn2 n1 2 AfmdmaifxiW tt71t7ndt 71 if n is even and f E Cnizm7 b7 and b n hn2fn1 E n AfxdxaifmfmJ tt71t7ndt if n is odd and f E Cn1ab a X Xquot I b X Xq WM 3 0 d am d W A Who Le has an quot WWW 0 Mich 4 Hrs Maxims 4 dz wm WM EEqu Z i Q5 21 2e amplequot jll39x quot 25ml 39ljl 843 O Whack d0 Wt mum b a wu onquoto a Mama aka WM 0 W110 hm Walk 05 a mm 9 W110 mane y Need W5 imam 0 work quot vh Wamh al n Le WM m x d H NMEIL fg nd 3 2quot tr Z ax 4 5 13 a soluh39on 0 W dtffqn d p 3 3376 5 di 1 WE 53946 I a e e 14 1 676 6x dZ i Baa 40 M an LJ LS gag vai p Ej 0 4143 Emma wm ordimg duke n5 bL HWL ls M 0M mch6 Vom able Cdquot dmvahws Pav n a dig 24m 7 man RX ma variable j 3 Wf aldtrm va QW om Whanecs imam Jo Solw an ordlmg M n numm 11157 045mm us an vmh al valMk problem 2 dlfhrfnhal abn 0P amigo My 3731 and 33 cl W nd39an n bulwill nd Valle X M art on W wm tgpgu m 43 s w or3 iY 8mdf M Y up kw 1l 91quot 5 65 whm 132quot 79 WW 3 7 MB 90sz 3wa dx relbns mmuf 1le 7 MN man an usduh39on wish s uniltM i 013 i quot Su handou r EMWE a as 3 103 6quot m Wm un s ol mxh d m da Wu 7060 Vm a unl qw Wm verld 4mg 5 Hysm r Le E L mmL Lgl mintd39 l as a in 0439 Zvarmws litz Ii 1 bu Miriam dunk 8 2 DDMm legeez w tquot as andMd 77quot5 l l L K 39 1 0 w hb 3 5 1 3 Michal q i W H Nuke Rea also bud a amid dwim L0 posstbu t Padr WW3 7 COMM cums Z 13 at Husd s mum l kL mL thth amp 21m sm HuSA 9quot a M va 6 Ooan 39 a s h ex v 8 we 003 Swim g Eula395 Mdhod Stmpw quotwhen in solw m h pmbms l a valtu Gwm gzm g 3ao Awnx X ux 5 My tih o a g fty kol s us 0quot m haw y d I sh is A W l 7m akwgi 39 a w a m 39iw quotl y L1 0 A H85 r 39 a t g l Appro oriljna k 390 60le mm 14 w k a a ham Rem Li39s hmbm HM m m k a 339 P I 9ampw 4 L CM S L1 m k a Fmd 6cm 0 Wu M 550 a I fj n c4 anadm MM quot 8quot 393 59 39 KW Em Ltcmgb Sovx l ts r Wmquot 1 m u z M ww 533 m I 9 35H W it fa t 80M DY g 3C 9 g gg Eulers iurmula NM 0W 24 t W 3 4 W 3 Jam 3 391 12 1 QgtSZ q 1895615 uh h lL 52l5 qk in Q quot 4 l o 40 mm 3834 03539 h 10101qu tl o h 239 53 l o Ii Emilia H4 l 1833b 2148 a Wl Maggy ng zznaat MATH 441541 Numerical Analysis Ninth Meeting Interpolation Thursday October 25th 2007 Numerical Differentiation 0 Section 41 Numerical Differentiation the Calculus Way Approximating f z0 7 Finding a Bound for the Error 1 Using the Taylor Polynomial 2 Using Lagrange Polynomials 3 A Problem to Be Aware Of When Reducing Size of Error 4 ForwardDifference vs BackwardDifference Formula 7 Higher Order Methods 71 1Point Formulas 1 Derivation to Three and FivePoint Formulas Examples Problem 9b 7 Higher Order Derivatives 7 Comparing Roundoff Error to Truncation Error 7 When Do We Really Want to Approximate the Derivative Numerically An Example Consider the following boundary value problem m1y zy3y9v 0 1 subject to 340 37 341 7 Numerical Integration 0 Section 43 Basic Numerical Quadrature Methods 7 What is Numerical Quadrature 7 Integrating the Lagrange Interpolating Polynomial 7 Useful Theorems and De nitions Weighted Mean Value Theorem for Integrals Suppose f E Chub7 the Riemann integral of 9 exists on 11 and gz does not change sign on 11 Then there exists a number 0 in 11 with Degree of Accuracy The degree of accuracy7 or precision7 of a quadrature formula is the largest positive integer n such that the formula is exact for x M for each k O7 17 771 S07 look at the error term If it has derivatives of f 7 then all polynomials of degree n 7 1 will vanish by the nth derivative7 f 7 Basic Quadrature Rules NH F Trapezoid Rule Integrating the rst order Lagrange Polynomial Simpson7s Rule Integrating the third order Taylor polynomial about 1 over 0 mg n 1Point Open and Closed NewtonCotes Formulas a The n 1point closed NewtonCotes formula uses nodes xi mo 271 for i 7177nwherez0017znbandh quot1 b7 approximating 1171435 dm A fx dz z gal an where ai fiequot b The n 1point open NewtonCotes formula uses nodes xi 0 ih for i 017 77 where mo a 717 b 7 h and h fig approximating dm A dm gai mi with the same a de nition as above Associated Error Values a For n1point closed NewtonCotes formula Suppose that 20 Ll u denotes the n 1 point closed Newton Cotes formula with 0 a7 zn b and h b 7 an There exists 5 6 11 for which 17 i n I I hn3fn25 n 2 Afmdm7iaifzlWO tt71t7ndt if n is even and f E Cnza7 b7 and m dz fawn i0 if n is odd and f E Cn1ab hw ww n l ntt71t7ndt 0 b For n1 point open NewtonCotes formula Suppose that TL ai xi denotes l 0 the n 1 point open Newton Cotes formula with 0 a h mn b 7 h and h b 7 an 2 There exists 5 6 11 for which 17 i n I I hn3fn25 n1 2 a dmigal z WLl tt71t7n dt if n is even and f E Cnza7 b7 and b 7 n I I hn2fn15 n1 AWdag711z am n1I A tt71t7ndt if n is odd and f E Cn1ab 0 Section 44 Composite Numerical Integration 7 The concept 7 Composite Trapezoid7s Rule Deriving a formula Theorem Let f E C392ozb7 h 17 00717 and mi aj h for eachj 01n There exists a u E 071 for which the Composite Trapezoid rule for n subintervals can be written with it s error term as b h b7 a M dz 5 e 7 m n71 N0 2 Z We N j1 2 Example Use the composite trapezoid rule with h 025 to approximate 257 dm 0 7 Composite Simpson7s Rule Deriving a formula Theorem Let f E C4ab7 n be even7 h 17 00717 and mi aj h for eachj 01n There exists a u E 071 for which the Composite Simpson7s rule for n subintervals can be written with it s error term as b h n271 nZ M c1273 fa2 Z fx21fox2171fb a 71 1 b7a 4 4 77180 h f M 2 Example Use the composite Simpson s rule with h 025 to approximate mze m dz 0 7 Composite Midpoint Rule Theorem Let f E C392ozb7 h 17Ln27 and mi 01j1h7 for eachj 7101n1 There exists a u E 071 for which the Composite Trapezoid rule for n 2 subintervals can be written with it s error term as b nZ b 7 a mg dz 2h 2 mm 6 WW 1 2 Example Use the composite midpoint rule with h 025 to approximate 257 dz 0 7 Error Bounding Example 8 Suppose you wanted to use the Composite Trapezoid Rule to approximate lnz dz correct to within 1041 What is the value of n that you need ie or step size h do you need MATH 441541 Numerical Analysis Third Meeting Root Finding Algorithms Thursday September 6th 2007 Root Finding ie Solving Nonlinear Equations in One Variable 0 Introductory Thoughts 1 How are root nding and solving nonlinear equations the same thing 2 What are the challenges to doing this analytically 0 Section 21 The Bisection Method aka the Binary Search Method 1 The Problem 7 Given Suppose you have a continuous function 1 de ned on 11 with fa and fb having opposite signs 7 Some Conclusions The Intermediate Value Theorem guarantees that f has at least one root on 11 call it p 7 The Big Question How do you go about nding the root p given this information and the formula for f 2 The concept of Bracketing the Root77 3 The Bisection Method Algorithm OBJECTIVE Given the continuous function f on the interval 11 where fa and fb have opposite signs7 nd a solution to x 0 INPUT endpoints a and b tolerance TOL maximum number of iterations N and f OUTPUT approximate solution p or message of failure 4 Other Possible Stopping Criteria 5 Convergence Issues 7 Will it converge 7 How fast will it converge 7 Example The equation zcosm 3 8x 7 3 has a solution on the interval 27 5 How many iterations will you need7 at most7 to nd the solution with an accuracy of 1041 6 Strengths and Weaknesses of the Bisection Method 0 Section 23 Newton7s Method Secant Method and Method of False Position 1 The Problem 7 Given Suppose you have a continuous and possibly continuously differentiable function f and some reasonable guesses as to a root of the function 7 The Big Question How do you go about nding the root p given this information and the formula for f 2 The Secant Method a Given the continuous function x and two reasonable guesses to the root7 p0 and p1 b A Visual Explanation c Deriving the Formula for the New Guess at the Root d The Secant Method Algorithm e An Example Use the Secant Method with initial guesses p0 2 and p1 3 to nd an approximation to the solution to zcosm 3 8x 7 3 correct to three decimal places f What Problems Could Occur g Strengths and Weaknesses of the Secant Method 3 Newton s Method a Given continuously differentiable f and one reasonable guesses to the root p0 b A Visual Explanation c Deriving the Formula for the New Guess at the Root d Newton s Method Algorithm AAA e The Relation to the Secant Method f An Example Use Newton s Method with initial guess p0 2 to nd an approximation to the solution to zcosm 3 8x 7 3 correct to three decimal places g What Problems Could Occur h Strengths and Weaknesses of Newton s Method 4 The Method of False Position a Given continuous function x and two reasonable guesses to the root p0 and p1 that bracket the root b A Visual Explanation c The Formula for the New Guess at the Root d An Example Use the Method of False Position with initial guesses p0 2 and p1 4 to nd an approximation to the solution to zcosm 3 8x 7 3 correct to three decimal places e What Problems Could Occur f Strengths and Weaknesses of Method of False Position A 0 Section 22 FixedPoint Methods 1 The Problem 7 Given Suppose you have a continuous function f and some reasonable guesses as to a xed point of the function 7 The Big Question How do you go about nding the xed point p given this information and the formula for f 2 What is a xed point and how is nding the xed point of a function related to root nding 3 Fixed Point lteration a Given the continuous function x and a reasonable guess to the xed point p0 b A Visual Explanation c Deriving the Formula for the New Guess at the Fixed Point d The Fixed Point Algorithm 4 Existence and Uniqueness Theorems a Existence If g E Ca b and a S g S b for all z 6 11 then 9 has at least one xed point p in 11 b Uniqueness i Contraction Mapping Theorem If there also exists a value 0 lt k lt 1 such that LCM 79yl S W yl for all z and y in 11 ie g is a contraction mapping on 0119 then the xed point p is unique ii Text Theorem If in addition to the existence criteria g m exists on a 1 and a positive constant 1 lt 1 exists with g m k for all z E a 1 then the xed pint in a 1 is unique c Fixed Point Theorem Let g E Ca 1 be such that a S g S 1 for all z E a1 Suppose in addtion tht 9 exists on a 1 and that a constant 0 lt k lt 1 exists with g m k for all z E a 1 Then for any number p0 in a 1 the sequence de ned by pm 9997171 n 21 converges to the unique xed point p in a1 Also the bounds for the error involved in using pn to approximate p are given by 1 7p S k maxpo 7 Mb 7190 and kn 1971719 a P1 P07 7121 d An Example Verify that the function fz e m has a unique xed point on 0 1 Use the Fixed Point lteration Method with initial guess p0 09 to nd an approximation to the true xed point correct to three decimal places e What Problems Could Occur f How are the xed point method and Newton s Method related g Strengths and Weaknesses of the Fixed Point Method A 0 Section 24 Error Analysis for Iterative Methods 1 De nition pn0 converges to p with order of convergence 04 If 1973310 converges to p and positive constants Oz and exist such that hm an1 29 A 71400 pl 7 p04 then 1973310 has order of convergence 4 In particular a If 04 1 the sequence is linearly convergent b If 04 2 the sequence is quadratically convergent 2 Theorem Let g E Ca 1 be such that a S g S 1 for all z E a1 Suppose in addition that g is continuous on a 1 and a positive constant k lt 1 exists with gm k for all z E a 1 If gp 31 0 then for any number p0 in a 1 the sequence pn1 91 for n 2 0 converges only linearly to the unique xed point p in a1 is continuous and 3 Theorem Let p be a xed point of Suppose that g p 0 and g strictly bounded by M on an open interval I containing p Then there exists a 6 gt 0 such that for pg 6 p 7 61 6 the sequence de ned by p1 91 when n 2 O converges at least quadratically to p Moreover for suf ciently large values of n M 2 Pn1 7p1lt 7 2 7p 4 Theorem from 23 Let f E Czab lfp E 071 is such that fp 0 and f p 7 07 then there exists a 6 gt 0 such that Newton s method generates a sequence 1973310 converging to p for any initial approximation po 6 p 7 619 l 6 5 Theorem 1 E 01m7 b has a simple zero at p in 071 if and only if fp 07 but f p 7 O 6 Corollary If f E 01m7 b and has a root7 197 on 11 there exists an interval about p where Newton s method converges quadratically to p for any initial approximation po 6 071 provided that p is not a simple zero D 0 1807 In rvrpd ah ovw IM O duud piLa mu mkxpdahd h Mgr mt 2x0 ampquot we M1x o a Pdgnomlals d4 Sam TLL puuwisc PM Sum Xo x x 5 m X 51 4 1 739 510 XIQK QX Sn NA I h t 5 x L39 in main wam e adrpiwwxa WM 3 Cubic QUM plumm Cubic l 397 39 X11 M d Y X it 3 n1 pbir s Z n owace How mums unknowns L pur cubic 1 n Mics quot1 4n unKnDWnS Vx uwmuMs m mpost Linhrvuml39z 2mm SOL indigo 1 gerbua dms wr am SewnHy n Moms 7 5m mndt n ons 41x r uvolah on Aquot Con nui s m mm abm M5 3 7 sou hs w Q g f S39if x jlss 3 m 9F 5 bag 2amp3 X2 1quot 5 07 7 7 s3 I i uh g fcwil ch 5 CH 3 a 1 quot 16 5mm a 9 5 8 Sim x2 3 z SI 52 LH 11 6mg NH STl x I i J 4 0 41K 4n van abizsunkmums 6m cond x ms x mka nl a l quot Smoo 39 slept n How man WV enmg 4n39l15n43 397 n W Wk FDrUL makhm mwmkj va WNYL Lamas mug Siluin le X ZHB H WW z 9n LnDn 1 n wit mam Nut15 Q algae o4 grudowx W a use Wee om 54er phi Xod XV r5 Oph ons on how An LSL Mu as 0 11 0 Patquot 0v Moduqu sph ne Lbouvxdamg and moms 550920 Ln pDiM air 5quot a O m Ld 0 f CM WW5 loo 0 Kn mmm quot H Law mu 0 bmdalok rod vud Wu Mme tthau rms pk l7 n ch m 0 ends Q03 Maxme CuJofc 661M User 9910M Slept 03v 2 end s 5 U0 112 s at om i39cm I if Clanmud gt nL llU 0 and rod 4 MW slope 6 rod M a NobelKm Common 6 IS lumav across Bo X21 and Xn1 X131 gm 95 0 OO00X3 bOXQKDXMO U3 9quot 61m a zm m 393 OGDX quot lbu y 6 ob Vmbohc axde Squot 09 quot 13 3quotxn SW 7 81 ll rom 54 9164 Cl wlptd um ephru 6m 3 UV 35quot ZbMV X433 la 7 5 m a b 1 6975de Hi5 39 lbw 3 1 HfHQ Find aoc Mi be ox ew usm EEK I ourbwui 39 I qunw z 3 3 3 Soc D 63 2a So 3 q 500 4 5 09 q bcd bIc dampcda 5 24 03 11335333 L5 SJ m 5 4 1D 5Lx U7 8 m 4 ohm 5 m b 2cx 1 74 but s m 2c 4 we x 7 33 MG 50m 4m fr m jg a b2 3 Con nuM B mm2 Sol 2 313 Con nmkj OJr quot4 dth s m arm 13 go Mp1 054 b4 C B 2 U50 3744 24 3d 34vZ rid 153 M m Omar 4 Din ah ml Num meat derenh ah ow nsvms 70 rmuas pr 5 10345 Q w W Van a OlES nsmljlws an iid L39 appv wmake W WS 04w 0 nvahve M3 Me WW 9 mm nd ammo Sm k 075 I05 Cede Divtn 43m o 13er 333 4 am have 00 WQOYMula 1th tr L V 1 quot mn tulier quot teCO m hao D 3 W 4ch vgfLO 3970 Hh quot39 439 03 4 MM m 4m 0 1390 z iC HM 00 Emard h 5 wa md hod ID mm 1 2 42me J4 Locum Wm M 39amp My hiL Ir 1 4 j 10quot k0 X l 3 064de BTW NCWOd 439me Ix g JANM h Can ou uanh how 00d Mus approx 67 Le ca up a bounde QmN K IUD Lfmh1w n W Ta50 s wuwomaxqum 123 Tatgor 39 iL XA H Xb 09x StIr I i Z W 4 i M3 U4Q IHUM n Q s blN WWquot hH 6W Wm imfgvm b mm knot M W mm Tm hw Polxj gm 0 camMud R to 1 Z 4 new 00 6 13km XXL 0 1 70 8ka i mb W 4 Wm 4W0 40on m HS 1quot aquot w m x mm 03 49m imam in m 51 Xoh X0 9quot W h h 4M humin 1 h L h I Q 5 dUrN Forward b W EXH CTL I EQUHL TD 7 rm imam in h 51 Error H rm 330 691 lsx HMDIQ 3 Mm 39 0 AWN 4 03 4 m 5mm Wm 63 error gumMa 0 bound em Q39w x swan 3M3 l 3 QQBBQB BQS U4 N 7 eror 1 quotC 39 m Q M aw 405 6 1er 3 WI 4 5quot 1910058 4 and J WWW 1 mlt 0 Ex 4 1 J L quot quot 30 Pramlm my gig L qawaml 3m g Know mm mm cogm 6M9 1433 I SlnfL I 90 8039 Hm mi x V03 a m z smats 2 f avwE P ggK W f 0 a 1307 N W an S Mdhodl cont Xn X n quot IX39VWB 4 0ch 3me x0 on cex a x A a i tsour musWorm is W roo re ULD D 0Q 0vsgww 7 3 Mess ooh n 39csk K digib n hnh quot xn3lt l0 4 396 5 MSW heatd an x0 XZX z bl o 093 I lt IO am 5 M 3 010 K Mayo 4 N disk WW 00 bad bld tAValutFX MS Wm 14 law had 00 395 M werth 0 a g M S 3 1 3l2 Can mhmt 94 a curve wmd brick Hu MUM no i dismna Z a ff 10 T Posst dt problems LL whg UL 3006 64Wva Valw g V9115 mpm39M Q Cammy 1 WW5 W p x 11 Ind s Nara max md Iw Su x shallow shape We W was New amuqu a show 01 0 w is x W41 g X0 2 09 w an 4 u 050m 0 5YD amp QTTL 39 no I 9 Suppost quu don Know a smer V39 90 Mon uT do know a bruer mkrval 7 S mr r wl Biwh39m rum a shod wh e 47 Uta Us answu as xo M wan Vmsab Cans b4 Mum s Md hoA Egg 6 Mm an i ulgquot WM w Wu Pm 1ava 11er M s approach 30 rLaamp39vd 5 153 5 Achmu Wu lmb a WW 0 shapt amp can Us ng m Approx bwm 5 0w Higbg smslHVL JrD choice 0 nf rvaluz Leap L mam nm a Lormt rl kralcs cu 0 15 assoc wlmax M In amt Wm m0 77 47W X NEVER nkxsds Kl39 X gt 0 i Kn2 005 CD 9 31 0 mes 01 poor emu Xo v 0 C9 Wm 3m MIL know 04 43900 Wu Mus provid prbgrom w hmula 1 Cc 5mm MoHnod Jus v New rm s md nod W ust an sqer 411mb ILXNB 39 39 h igm A ln39l 39 39x39nvL Xn l Xn z So Ncwhm 2 SMM Md hod YNn YNn j Kan A Law x 3 7m Xh l quot i 39Xnb Kiwf xn it 39 1 XII z Sim 40de NoJrL v 00 ow zzr mm vrmula Jaw P m mm Mums ow 0 Donuter 1 Graphm nkwrdra ow 96 Mug ha given hNo mhal Aw XHX OWN CIAUL WI WNquot m NM 7M We 3mmquot Mn 5 0 as aged 0L0 5W h N CuNL a ang n mL Vs can muck our cmuurgna 0 b1 gtower WNw tms N3 in 39 Xv 1 t 1 Can how miav womms N MMWS mus x X9 1 0 GA 21 2 0 59 83 D No onger W 41 jgornrwda 3H asltr Mm biscd39rov 5H mm mm ck momma o r Snap 09 ownL Cong O Slower Mun WW5 4 9 mh al 1536 9H hush mpo am 7 SWIM 22 Fixed Pocm Md nod Wm is a 1M pow of 1 3cm Xquot ls a Warm at 06 Ur 4308 x 7 fit 11 7025 X D 50 txedilas is X 39 9x 99 Fwd X 73 13 XSmOtsV39XX 0 M 3 0 n Qua eaw39i39 of X m0lt3 m 3063 5 Wm 00 nkrsxo W W W fim 54 W i 7C 2 x 6 ID Wh dms a ML 0 d 00 Win37 1 O M Q quotW a Mm hawmuem N D Ox 00 ihndm W4 V avusa p v wd RM C0500 7quot 7L 5L7 Find 19 3 OK as a Q e F 4 m 39 In 7 5 ismb gxq 0 LT lx SWCX 3 M MARS 934 WK xsmbc X Smo 60mg 4m rod Mama 19m 0 h a ixedp v 0Q7c 3x164 50km ur an 39x mm 1Cm0agw Can hm rook 431ml mun m D ham Valid A OLHHQIQMWM jcor MAMj 39w Mfg Given quotWquot OULSS a 7m gum inquot 1 6 PM 5nLX Wi ummb a hcd 5mm gtlt W 39 15 L3ml 311 wt Kg l 1 smoqq3 X1 smLoqqav o l V39U l39 O W Zing xcder mod mo 30 vex codll b CU C50 horfww vallg ro 82X Ier r 3 cum M k f 2 r X39D w X 0RM b 3 EMWUI New m 0W Emb aegoqsb o 39 39 quotfquot OSS max m 9 4 A Ct LS U J 3 b T a b was Lint mes cut all pm 5M4 pus cs m v xe a W is max ka 5 quot mn Once u cxoss 9quot 5mm m cross again MA 0 W amuse 63f b k in 3937 awovuss gt 2 fZL39 Obt XYJie o n HQ Wu 0 15m Lam s 0 mkxvmjmd as web 05 aff m o lquot t 3 ob39mkimio 0 I 0000000000 000 WWWWW 000000 0mMMWWWWWWMWWWWWWWM0 WMWWWWWWWWWWWWWE mes IMWWWWW0WWMWWWMWWWWW 0WWWOMWWWWWWWWMMWWWW 0 0000000000000000000000 0MWWWWWMWOMWWWWWWWO 00 0 me0 TmMMWWW MWMMWWW WWMWWWWWWWWWWWMWWWWW 0WWWMWWWM 000000 I0000000000000300000 00000000 00 00 00000000 00000000000Wm000 00 WWWWWWWWWWWMMWWWWWWO 00000000000 0 I000 00000 0 0 00000000000 00000000 00000 WWWWWWWWMWWWWMMWW 000W00W00000 I00000000000000000 0000000000000000en0 00WWWWWWWWWWWMW MWWWWWWWWWWWWWW 0 0000000000 0 E0000 00 0WWOWWWWWWWWO 000 S0000 0 0 0 00 0000 0000 0 0 0 00 390 K I 00 0 00 0 2 a 4 s a 7 s a 0 16 2 mm Funchnns MATLAE FuncunnReference textA ExampleZ Pm smpes aHhe ends Man mmmm me vames Ma 59001770151000th ave EMDYEEG x 44 y 0 15 112 236 236 146 49 06 0 cs splnex0 y 0 Xx unspaceH ntxyyy n xx 74101 pvalICSyxX n 1 4 3 u 2 6 Examples The wnvedms 1900101990 p 75995 91972 105711 123203 131669 150697 179323 203212 226505 249633 1 wwm The expvessmn sphnE t p 2000 0505070 cum 500770 01 ex vapmate and 079mm 02 pnpmaunn m we yeaVZOOO The 7950 15 ans 10182007 2 52 PM mm FunchnnsMATLAE chunnkefmm textA 2706060 mple4 The statements splmetm w ppvaltpp hnspacemzltpzmm plutlwllywyyy mamaytz25 ux axzs equal marde M n mare vames 0 e Wu mare cums man dues x hence w 1 and w end are used as emsmpes 45 0 as Example5 x 025 1 y 5 le mam xx 11 yy splnelx xx plutlxYU D xx 1 1lrquot plutlx l2 u xxY 1lZr hold on hold off 3 mm 10182007 2 52 PM WWWWWW WW WWWWMMWM I k WWWWWWWWMWW MWWWM WWWWWM WW m n m m m 0 mwmmmm W WWMWWWWWW ReVerences MATH 441541 Introduction to Numerical Analysis Things to Beware with Floating Point Numbers and a Few Fixes Things to Be Wary of With Computer Arithmetic Example 1 Too Small Too Big Once again recall our Mini Machine from class that used 6 bits to represent a number 1 bit to represent the sign 3 5 bits to represent the exponent c and 2 bits to represent the fraction In this case our oating point number was of the form 19 20 3 1 Thus the smallest positiue number representable on this machine is 20731 X g 3752 assuming the case that all c 0 and f 0 is reserved to represent 0 and the largest positiue number representable on this machine is 27731i 161 16XE 28 So the range ofpositiue numbers representable with this form is Let m and y 32 which are both outside of the range of the computers representation But m gt7 y gt7 32 2 is in the range of the computer What would happen if you tried to multiply m and g on this computer 908 flflx y fl X OVERFLOW and underflow WARNINGll STOP Example 2 Catastrophic Cancelation Subtraction of nearly equal numbers x z y can result in large round o errors in computer arithmetic Let x 041872940271 and y 041873016429 What is the relative error in computing m 7 y using 5 digit floating point representation using choppingf2 x 7 y 7 z e yl l0418729402717 041873016429 7 041872 x 100 7 041873 x 100 lz 7 yl l0418729402717 0418730164291 17000000076158 7 7010000 x 1074 000000076158 923842 x 105 076158 x 106 121305969169 Example 3 Failure of the Associative Law Suppose a computer is using 4 digit floating point representation with rounding Let 2 1229572 y 674198 2 252382 then 1012 01230 x 103 fly 06742 x 101 1012 02524 x 102 Thus myz fl 01230 x 103 fly 06742 x 101 fl fly 0129742 x 103 flflz fly 01297 x103 1012 02524 x102 lama fly m2 2 015494 x103 andzEByEBz fly 06742 x 101 1012 02524 x 102 fly 1012 031982 x 102 flfly flz 03198 x 102 fl 01230 x 103 1 f 3 7 015X10 So x EB y EB z 01549 X 103 but m EB y 692 01550 X103 Rearranging or Rewriting to Minimize the Effects of Roundoff 1 Whenever you re dealing with subtraction of nearly equal numbers involving square roots as may be the case with the quadratic equationlll try rationalizmg to avoid catastrophic cancellation Example 4 Dealing with Subtraction and Square Roots Compute V m2 1 7 m for large ualues of m Rationalize Vz21m 1 2 1 2 1 z z m r21 r21 And addition and division are more stable operations than subtraction to Whenever you re dealing with a polynomial hence calculating many multiplications to compute the various powers of m each operation incurring its own round off error rewrite the polynomial with nested multiplications Horner7s Method to reduce the number of operations Example 5 Horner7s Method Calculating 3m42z3717z28z75 3mzmz2zmzi17mz8z75 10 multiplications 2 additions 2 subtractions 75z8z717z23z 4 multiplications 4 additions with Homer s Method 3 Whenever you re dealing with summations always start with the smaller numbers and increase in magnitude and add the positive numbers and the negative numbers separately then perform the subtraction An Set of Excel Exercises to Try You are to use Excel to generate a sequence of decreasing numbers starting with 10 and decreasing by 02 each step down to 0 using the following methods 1 In column A enter the numbers 0 through 20 2 In column B start by typing 10 in the rst cell and 98 in the cell directly below it Highlight both cells then copy the pattern of the two down by dragging the cross hair at the lower right hand corner of the highlighted pair You ll need to copy down to row 51 3 In column C start by typing 10 in the rst cell Click on that cell and go to the Edit menu and select Fill and Series Indicate the series is in Columns with a step of size 02 and stop value of O 4 In column D start by typing 10 in the rst cell Go one cell down and type the formula 10 A2O 2 Hit enter Highlight this most recent cell and copy the formula down to row 51 5 In column E start by typing 10 in the rst cell Go one cell down and type the formula E1 02 Hit enter Highlight this most recent cell and copy the formula down to row 51 Comment on your results Are all columns identical What could be going on here Hm CaloIE 0 W0 flL39dV 3 WV 5v du Pad UL 7 MIN 5 SumPler I O5 lmote DJ ae z Gmdmh FL TedEgg ma a my Nmom Lyustandps g I Linear appfb 0 Cum 0t b gimmg Cloud Mud ats f Us qyodngpro o Curve at a I 3 mamquot pm Nahum Linearapprwbauvw I i dwlwvalw emp ts T39A Lb Made Quad rahrg ldm gt Cwr V orval Eagle n0 mulh39 e SuklvHena s y do Mod lrom vwfms wuL am Back gt 3 Naval or padres Wen01 Slmpsons md39 od gt Mares W W i f 8JkaNalS JPL L Wadmh c 6V 199mm M EMF 8N 170 6 Composd e TW acid T CWquot n0 nevmly S ad Submkr T V5 I 39 v VI Owl x x quotquot9 hb 9 n I M NH Ph g7 S a Jcr 20rd max 39 ion 3 0W M NZ Way 1b 11 bf 1 of M mf m cxa x 409 4bi 4CXM3 40 h J3 k 3 4 Ems ant M76pr 2 wig Whmex 5F XL s to Hand wow 7 use W1ltL Jailed d m39grw hams have n 8 8 qu campth w hJ2I D 4W of Xzexdx I I l I I l I 7 0 k j I w C4 mf L ofzxg39otx 5 oaik 0a qj 2 in 20 23 39 dlzi t 4 C299 3mg Dinah impsons 1 2 h X0 h5 m 25 f e smpsans gemdx 7 n Q0 4 4 Lng avian 093 Single i J n 51 WW 4 X 6 M 0 b a 2 4 a 0amp0 0 2 h 4 n n 1 2 Lt n i 4 Z 4 7 4 Z L L 3 1t V w t q 0 X914 2 Jflq t t m klfrUz Hf 330 0 3 l ClI a a31 Compoedt mayo 1 even a aquot MumNd 1 bef mad x 0 2h 52519qu 25er X0 I Warm d39 I Xn asl39 Mgw 3 WM 4 de 2 Dow W L39 in l b a b3 mm c Sump 0va und are WW9 Z I6 so I 8ab g53129 W L baul h 0 X I60 3a Sta squot53 h 0quot 50 3 55 753 N 5 395 4 hvah hvazh 1 94 In Read pp 2626 1463de IRE gouwan t acwrm e 1 22 N hwl H 2 lm WW 42 3 74 aubdivfdmg an Mcrval Dab Mun mono 5a gt3b1lt395 Pidure 21039 130 M 4 3 Raf quot 3 8 139 z39 7 0 b 11 lac 804 16423 4m h nu capta pmudure m 1 S sw 439 W right vb quot L amuse 5L S Lgmyz ior W arm would b 3 NM 4 to Q Of Sm Ax WH h XH 3 ii1mm 60 hi1 w z a W Sm l A AZ olzevmz at 8032 80324 30Ll iLlZlolaz S 739 L o I 03 J 1mm 98 80 14274357 lsuw SL012 61243 34 8 w 3149quot 3W 2quot Ol lt 16 9 89 qum 23gt Now 0M2 Paw half 24 sum N274 ZW f e SL233 Sb 3 Z SL233 113 41de 1 M2 18 at D bgeg SB L 3 4 85 4 1m foyqu 0 lZiff j Slim 8amp5 3354 2 q I Fund A76 2 m890 8947 mmcooC X 7 JIuaOBCM Uh ngc anJ 3 l2 W I Hol D44 mor ODS IOS WSS 4 ol MATH 441541 Numerical Analysis Second Meeting Computer Arithmetic Continued amp Root Finding Algorithms Thursday August 30th 2007 1 Preliminary Material Continued 0 Internal Number Representation 1 Bases Binary Decimal Hexidecimal Converting 2 Computer Floating Point Representation of Numbers IEEE Standard 7 BINARY y 71f 2cishift where s sign bit c 7 shift shifted exponent characteristic fractional part mantissa with double precision oating point numbers using 64 bit representation 1 bit for sign 3 11 bits for exponent c 52 bits for fraction 1 a The number of numbers we can represent exactly 0 c Plotting computer numbers to see the meshing pattern d Determining the pattern The range of the numbers we can represent i Increasingdecreasing number of bits for c gt 7 ii Increasingdecreasing number of bits for f gt 7 e De nitions i Under ow ii Over ow iii Machine Epsilon 6 iv Unit Roundoff u 3 Normalized k Digit DEClMAL Floating Point Representation of Numbers i0d1d2d3dk X10 d1 750 di 6 019 a Rounding vs Chopping b Absolute and Relative Error c Signi cant Digits 0 Computer Arithmetic 1 De nition of flz oating point representation of z flz z 1 6 where 6 lt u unit roundoff 2 Operations 3 Stable Operations proving or disproving 4 Handout on Computations to Be Wary Of 0 Rates of Convergence and Terminology 1 an a 04 with a rate of convergence Own 2 Root Finding ie Solving Nonlinear Equations in One Variable 0 Introductory Thoughts 1 2 How are root nding and solving nonlinear equations the same thing What are the challenges to doing this analytically 0 Section 21 The Bisection Method aka the Binary Search Method 1 HgtOJID m0 1 The Problem 7 Given Suppose you have a continuous function 1 de ned on 11 with fa and fb having opposite signs 7 Some Conclusions The Intermediate Value Theorem guarantees that f has at least one root on 11 call it p 7 The Big Question How do you go about nding the root p given this information and the formula for f Bracketng the Root The Process and A Picture The Bisection Method Algorithm OBJECTIVE Given the continuous function f on the interval 11 where fa and fb have opposite signs nd a solution to x 0 INPUT endpoints a and b tolerance TOL maximum number of iterations N and f OUTPUT approximate solution p or message of failure Other Possible Stopping Criteria Convergence Issues 7 Will it converge 7 How fast will it converge 7 Example The equation zcosm 3 8x 7 3 has a solution on the interval 2 5 How many iterations will you need at most to nd the solution with an accuracy of 1041 Strengths and Weaknesses of the Bisection Method 0 Section 23 Newton7s Method Secant Method and Method of False Position 1 The Problem 7 Given Suppose you have a continuous and possibly continuously differentiable function f and some reasonable guesses as to a root of the function 7 The Big Question How do you go about nding the root p given this information and the formula for f 2 The Secant Method a Given the continuous function x and two reasonable guesses to the root7 p0 and p1 b A Visual Explanation c Deriving the Formula for the New Guess at the Root d The Secant Method Algorithm OBJECTIVE Given the continuous function f and initial approximations p0 and p1 nd a solution to x 0 INPUT initial approximations p0 and p1 tolerance TOL maximum number of iterations N and f OUTPUT approximate solution p or message of failure ALGORITHM e An Example Use the Secant Method with initial guesses p0 2 and p1 3 to nd an approximation to the solution to xcosx 3 8x 7 x3 correct to three decimal places f What Problems Could Occur g Strengths and Weaknesses of the Secant Method Newton s Method a Given continuously differentiable f and one reasonable guesses to the root7 po 0 c Deriving the Formula for the New Guess at the Root d Newton s Method Algorithm OBJECTIVE Given the continuously differentiable function f and an initial approximation pg7 nd a solution to x 0 INPUT initial approximation p0 tolerance TOL maximum number of iterations N and f and f OUTPUT approximate solution p or message of failure ALGORITHM e The Relation to the Secant Method An Example Use Newton s Method with initial guess p0 2 to nd an approximation to the solution to xcosx 3 8x 7 x3 correct to three decimal places g What Problems Could Occur h Strengths and Weaknesses of Newton s Method AAA OJ A Visual Explanation A l h
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'