Lecture note 2 Numerical Analysis 1.3 Newton's method Newton's(or Newton-Raphson)method is one of the most powerful and well- known root-finding method. It converges much faster than what we have studied. .Goal:Find a root of f(x). ·Assumption:f∈C2[a,b. We use Taylor's expansion to derive the Newton's method. ·Recall:Taylor's expansion.ff∈C2[a,bl,and zo∈[a,b.For every x∈[a,bl, there exists a number between z and zo such that f回=fo+e-ofol+E-,oe. 2 Suppose that we have a po which is close to the root p.How to get a pi that is closer to p than po？ 1.According to Taylor's expansion,there exists a between p and po, 0=f(p)=f(p)+(p-m)()+"(). 2 2.p-po is assumed small,so lp-po2p-pol.Neglect the term involving (p-Po)2. 0f(po)+(p-po)f'(po), thus f(Po) p≈P0- f'(po) So we define f(po) P1=P0- f'(po) The strategy behind the Newton(Raphson)method is to approximate the curve of f (x)by its tangential line at some estimate xk y-f(p)=f'(p)(x- pk)and set the zero (crossing the x-axis)of the tangent line to the next estimate k+1.0-f(k)=f'(pk)(PR+1-PR)PK+1 Pkfp f(Pk】 ·Newton's Method: Given po,generate a sequence pn by f(Pn) Pn+1 Pn- f'(pn) Use a graph to illustrate the Newton's method. 12Lecture note 2 Numerical Analysis 1.3 Newton’s method • Newton’s (or Newton-Raphson) method is one of the most powerful and well￾known root-finding method. • It converges much faster than what we have studied. • Goal: Find a root of f(x). • Assumption: f ∈ C 2 [a, b]. • We use Taylor’s expansion to derive the Newton’s method. • Recall: Taylor’s expansion. If f ∈ C 2 [a, b], and x0 ∈ [a, b]. For every x ∈ [a, b], there exists a number ξ between x and x0 such that f(x) = f(x0) + (x − x0)f ′ (x0) + (x − x0) 2 2 f ′′(ξ). • Suppose that we have a p0 which is close to the root p. How to get a p1 that is closer to p than p0? 1. According to Taylor’s expansion, there exists a ξ between p and p0, 0 = f(p) = f(p0) + (p − p0)f ′ (p0) + (p − p0) 2 2 f ′′(ξ). 2. p−p0 is assumed small, so |p−p0| 2 ≪ |p−p0|. Neglect the term involving (p − p0) 2 . 0 ≈ f(p0) + (p − p0)f ′ (p0), thus p ≈ p0 − f(p0) f ′(p0) So we define p1 = p0 − f(p0) f ′(p0) . • The strategy behind the Newton(Raphson) method is to approximate the curve of f (x) by its tangential line at some estimate xk y−f(pk) = f ′ (pk)(x− pk) and set the zero (crossing the x-axis) of the tangent line to the next estimate xk+1. 0 − f(xk) = f ′ (pk)(pk+1 − pk) pk+1 = pk − f(pk) f′(pk) • Newton’s Method: Given p0, generate a sequence pn by pn+1 = pn − f(pn) f ′(pn) . • Use a graph to illustrate the Newton’s method. 12