Lecture note 2 Numerical Analysis ·Newton's method: Pn+1=g(Pn), g)=x- f(c) f'(E) g(a)= f(x)f"(z) (f'()2 It is order 2 because g'(p)=0 ·Suppose that p is a zero of f of multiplicity m≥2，i.e,f(p)=f'(p)=0. We don't have g'(p)=0.Because g'(p)=. Therefore,Newton's method may not converge of order 2. f()=(x-p)"h(z),h(p)#0. f'()=m(x-p)m-1h()+(-p)"h'(x) (x-p)mh(x) (x-p)m-1h(x) g四=T-mc-pm-h田+e-pm石=r-mh回+e-pm石 h(z) g)=x-(x-p)·mhr)+(c-phN回 g(x)=1- h(x) d h(z) nh田+e-p石+c-pm云{nha+-p阿}） 9=1- =1品 mh(p) So, -g(p)=0,ifm=1. -g(p)≠0fm=2,3… Recall that only when g'(p)=0 the method converges quadratically,otherwise linearly.So if p os a zero pf multiplicity >2,then Newton's method converges with order 1. How to modify such that Newton's method converges quadratically when m≥2？ (= f(z) (x-p)mh(x) h(x) 问=me-p)m-h回+e-pmn石=-pmh四+x-pg西 h(x) 1 mh四+-pg阿=元≠0. lim u(x)has a simple root p. Apply Newton's method to u: 9)-x-4 f(x)/f'(x) -0=x-P-F"/四亦 16Lecture note 2 Numerical Analysis • Newton’s method: pn+1 = g(pn), g(x) = x − f(x) f ′(x) g ′ (x) = f(x)f ′′(x) (f ′(x))2 It is order 2 because g ′ (p) = 0 • Suppose that p is a zero of f of multiplicity m ≥ 2, i.e., f(p) = f ′ (p) = 0. We don’t have g ′ (p) = 0. Because g ′ (p) = 0 0 . Therefore, Newton’s method may not converge of order 2. f(x) = (x − p) mh(x), h(p) 6= 0. f ′ (x) = m(x − p) m−1h(x) + (x − p) mh ′ (x) g(x) = x − (x − p) mh(x) m(x − p)m−1h(x) + (x − p)mh ′(x) = x − (x − p) m−1h(x) mh(x) + (x − p)h ′(x) g(x) = x − (x − p) · h(x) mh(x) + (x − p)h ′(x) g ′ (x) = 1 −  h(x) mh(x) + (x − p)h ′(x) + (x − p) d dx  h(x) mh(x) + (x − p)h ′(x)  g ′ (p) = 1 − h(p) mh(p) = 1 − 1 m So, – g ′ (p) = 0, if m = 1. – g ′ (p) 6= 0 if m = 2, 3, . . . Recall that only when g ′ (p) = 0 the method converges quadratically, otherwise linearly. So if p os a zero pf multiplicity ≥ 2, then Newton’s method converges with order 1. • How to modify such that Newton’s method converges quadratically when m ≥ 2? µ(x) = f(x) f ′(x) = (x − p) mh(x) m(x − p)m−1h(x) + (x − p)mh ′(x) = (x−p) h(x) mh(x) + (x − p)q ′(x) limx→p h(x) mh(x) + (x − p)q ′(x) = 1 m 6= 0. µ(x) has a simple root p. Apply Newton’s method to µ: g(x) = x − µ(x) µ′(x) = x − f(x)/f′ (x) [(f ′(x) 2) − f(x)f ′′(x)]/(f ′(x))2 . 16