Lecture note 2 Numerical Analysis Step 5 Divide [1.5,1.75]into two equal section (by the middle point of it): [1.5,1.625]and[1.625,1.75l. f(1.625)≈-0.203 f(1.5)f(1.625)<0 So the root is in [1.5,1.625]. Step 6 Take the middle of the interval as the guess of p. p=15+62=1.5625 2 The real solution is p =1.5121.We get an approximate root with 2 correct digits！ The Algorithm Problem:find a number pE [a,b]such that f(p)=0. ·Assumptions. 1.f(x)is continuous on [a,b. 2.f(x)have opposite signs at a and b,i.e.,f(a)f(b)<0. Some remarks on the assumptions. -Here is“<”not“≤”we exclude f(a)f(b)=0 because in this case either a or b is a root. -Emphasize the assumptions.These are the same assumptions as in the intermediate value theorem.Recall the intermediate value theorem. ·Algorithm. -eta,]=a,,p1=岁. Set n 1. ()If pn is close enough to p,then we stop;otherwise,we cut [an,bn]into two parts [an,Pn]and [pn,bn]. If f(an)f(pn)<0,then p is in [an,pn].Set [an+1,on+1][an:Pnl If f(an)f(pn)>0,then f(pn)f(n)<0.Therefore p is in [pn:bn]. Set [an+1,6n+1]=[Pn,on]. -Set pn+1=ata±，and go to step(). 2 The algorithm will produce a sequence of intervals [an,bn]satisfying 1.p∈[an,bnl. 2.The interval length (on+1-an+1)=(on an) 3.pPn=an地m 2 One issue remains:How to judge if pn is close enough to p?Stopping criteria! 3Lecture note 2 Numerical Analysis Step 5 Divide [1.5, 1.75] into two equal section (by the middle point of it): [1.5, 1.625] and [1.625, 1.75]. f(1.625) ≈ −0.203 f(1.5)f(1.625) < 0 So the root is in [1.5, 1.625]. Step 6 Take the middle of the interval as the guess of p. p = 1.5+1.625 2 = 1.5625 The real solution is p = 1.5121. We get an approximate root with 2 correct digits! The Algorithm • Problem: find a number p ∈ [a, b] such that f(p) = 0. • Assumptions. 1. f(x) is continuous on [a, b]. 2. f(x) have opposite signs at a and b, i.e., f(a)f(b) < 0. Some remarks on the assumptions. – Here is “<” not “≤” we exclude f(a)f(b) = 0 because in this case either a or b is a root. – Emphasize the assumptions. These are the same assumptions as in the intermediate value theorem. Recall the intermediate value theorem. • Algorithm. – Set [a1, b1] = [a, b], p1 = a+b 2 . – Set n = 1. (⋆) If pn is close enough to p, then we stop; otherwise, we cut [an, bn] into two parts [an, pn] and [pn, bn]. ∗ If f(an)f(pn) < 0, then p is in [an, pn]. Set [an+1, bn+1] = [an, pn]. ∗ If f(an)f(pn) > 0, then f(pn)f(bn) < 0. Therefore p is in [pn, bn]. Set [an+1, bn+1] = [pn, bn]. – Set pn+1 = an+1+bn+1 2 , and go to step (⋆). • The algorithm will produce a sequence of intervals [an, bn] satisfying 1. p ∈ [an, bn]. 2. The interval length (bn+1 − an+1) = 1 2 (bn − an). 3. pn = an+bn 2 . • One issue remains: How to judge if pn is close enough to p? Stopping criteria! 3