Lecture note 2 Numerical Analysis 1.3.1 Convergence Theorem 6 Suppose that 1.f∈C2[a, 2.fp)=0andf'(p)≠0. Then there exists 6>0 such that nliee Pn=p where pn is generated by the Newton's method with po Ep-6,p+. Newton's method converges if the initial guess is sufficiently close to the root. We use fixed-point Theorem to prove it. Proof.Let f(x) g)=工-而 Letk∈(0，l).Ve only need to find a6 such that g(x)∈p-6,p+,x∈p-6,p+】 and lg(x川≤k,z∈(p-6,p+6). There are 3 steps in the proof. 1.There exists an interval [p-61,p+61]on which g is differentiable. 2.There exist an interval [p-6,p+6]C [p-61,p+61]on which lg'()<k and k<1. 3.g(x)∈[p-6,p+d】for allx∈p-6,p+d. Let us prove it step by step. Since f'is continuous and f'(p)0,there exists an interval [p-61,p+61]on which f'(z)0.Then,g is well defined and differentiable on [p-61,p+61]. g=1-f'of四-ff"四=fef”包 (f'(x)2 (f"()2 So,g'is continuous and g'(p)=0.For any 0<k<1,there exists a 6 such that lg(x川≤k,z∈p-6,p+dcp-di,p+dl 13Lecture note 2 Numerical Analysis 1.3.1 Convergence Theorem 6 Suppose that 1. f ∈ C 2 [a, b]. 2. f(p) = 0 and f ′ (p) 6= 0. Then there exists δ > 0 such that lim n→+∞ pn = p where pn is generated by the Newton’s method with p0 ∈ [p − δ, p + δ]. • Newton’s method converges if the initial guess is sufficiently close to the root. • We use fixed-point Theorem to prove it. Proof. Let g(x) = x − f(x) f ′(x) . Let k ∈ (0, 1). We only need to find a δ such that g(x) ∈ [p − δ, p + δ], ∀x ∈ [p − δ, p + δ] and |g ′ (x)| ≤ k, ∀x ∈ (p − δ, p + δ). There are 3 steps in the proof. 1. There exists an interval [p − δ1, p + δ1] on which g is differentiable. 2. There exist an interval [p − δ, p + δ] ⊂ [p − δ1, p + δ1] on which |g ′ (x)| ≤ k and k < 1. 3. g(x) ∈ [p − δ, p + δ] for all x ∈ [p − δ, p + δ]. Let us prove it step by step. • Since f ′ is continuous and f ′ (p) 6= 0, there exists an interval [p−δ1, p+δ1] on which f ′ (x) 6= 0. Then, g is well defined and differentiable on [p − δ1, p + δ1]. • g ′ (x) = 1 − f ′ (x)f ′ (x) − f(x)f ′′(x) (f ′(x))2 = f(x)f ′′(x) (f ′(x))2 . So, g ′ is continuous and g ′ (p) = 0. For any 0 < k < 1, there exists a δ such that |g ′ (x)| ≤ k, ∀x ∈ [p − δ, p + δ] ⊂ [p − δ1, p + δ1]. 13