MATH3230 Numerical Analysis Tutorial 4 1 Recall: Quasi-Newton method: We first consider Newton’s method: x k +1 = x k − f ( x k ) f ′ ( x k ) , k = 0 , 1 , 2 , . . . . (1) At each iteration, we need to compute f ′ ( x k ) . This might be very difficult to do in some cases. For instance: ( a ) the expression f ( x ) is unknown; ( b ) the derivative f ′ ( x ) is very expensive to compute; ( c ) the value of function f may be the result of a long numerical calculation, so the derivative has no formula available. 1. Constant slope method: Approximating f ′ ( x k ) by a constant g k = g , Newton’s method becomes x k +1 = x k − f ( x k ) g , k = 0 , 1 , 2 , . . . . (2) This is called the constant slope method. In particular, we might take g = f ′ ( x 0 ) . 2. Secant method: Approximating f ′ ( x k ) by g k = f ( x k ) − f ( x k − 1 ) x k − x k − 1 , Newton’s method becomes x k +1 = x k − f ( x k ) g k , k = 0 , 1 , 2 , . . . . (3) This is called the secant method. Two initial values x 0 and x 1 are needed to start. 3. Fixed-point iterative methods: Both Newton’s method and Quasi-Newton’s method can be seen as special cases of fixed-point iterative methods. For a given function φ ( x ) , x ∗ is called its fixed point if x ∗ satisfies φ ( x ∗ ) = x ∗ . The iterative method x k +1 = φ ( x k ) , k = 0 , 1 , 2 , . . . is called a fixed-point iterative method associated with the function φ ( x ) , and φ ( x ) is called the iterative function. Theorem 1 (Convergence of fixed-point iterative method) . If the iterative function φ ( x ) satisfies the condition | φ ′ ( x ∗ ) | < 1 , then there exists δ > 0 such that for any x 0 ∈ [ x ∗ − δ, x ∗ + δ ] , the fixed-point iterative method converges. If φ ′ ( x ∗ ) ̸ = 0 , the convergence is linear with convergence rate ρ = | φ ′ ( x ∗ ) | . If φ ′ ( x ∗ ) = φ ′′ ( x ∗ ) = · · · = φ ( p − 1) ( x ∗ ) = 0 , but φ ( p ) ̸ = 0 , then the fixed-point iterative method converges with order p . 4. Cases with multiple zeros: A point x ∗ is called a zero of the function f ( x ) with multiplicity m ≥ 1 if it holds f ( x ∗ ) = f ′ ( x ∗ ) = · · · = f ( m − 1) ( x ∗ ) = 0 , but f ( m ) ( x ∗ ) ̸ = 0 . 5. Convergence of Newton’s method in the case of multiplicity: We have the following local convergence of Newton’s method when it is applied for solving a nonlinear equation with a zero of multiplicity m : (a) It converges quadratically for m = 1 , namely when x ∗ is a single zero; (b) It converges only linearly to the multiple zero x ∗ with rate ρ = 1 − 1 m for m > 1 . If m = 2 , the convergence rate is 1 / 2 , the same as the convergence rate of the bisection algorithm. Newton’s method converges more slowly when m is larger. 1

2 Exercises: Please do the star problem (*) in tutorial class and finish the rest after class. 1. * Consider the following nonlinear equation f ( x ) := x 3 − 2 x 2 + x = 0 , and the sequence generated from an iterative function ϕ : R → R such that x n +1 = ϕ ( x n ) with initial guess x 0 . (a) For the iterative function ϕ ( x ) := x − 2 f ( x ) f ′ ( x ) . Does the fixed-point iterative method have local convergence near x = 1 ? If so, find the order of convergence. (b) For the iterative function ϕ ( x ) := x + 10 f ( x ) f ′ ( x ) . Does the fixed-point iterative method have local convergence near x = 1 ? If so, find the order of convergence. (c) Which iterative function ϕ ( x ) (the one in (a) and (b)) is better for the fixed-point iterative method? Please explain. Solution. Note that f = x ( x − 1) 2 , f ′ = ( x − 1)(3 x − 1) , f ′′ = 6 x − 4 , f ′′′ = 6 . (a) Consider ϕ ′ ( x ) = 1 − 2 [ f ′ ( x )] 2 − f ′′ ( x ) f ( x ) [ f ′ ( x )] 2 = − 1 + 2 f ′′ ( x ) f ( x ) ( f ′ ( x )) 2 = − 1 + 2 x ( x − 1) 2 (6 x − 4) ( x − 1) 2 (3 x − 1) 2 = − 1 + 4 x (3 x − 2) (3 x − 1) 2 . Hence, we have ϕ ′ (1) = 0 . Also, notice that ϕ ′′ ( x ) = 4 (3 x − 1) 4 ( 2(3 x − 1) 3 − 6(3 x − 1)(3 x − 2) x ) = 8 (3 x − 1) 3 . Hence, ϕ ′′ (1) ̸ = 0 . We conclude that the fixed-point iterative method has convergence of order 2 . (b) Note that ϕ ′ ( x ) = 1 + 10 [ f ′ ( x )] 2 − f ′′ ( x ) f ( x ) [ f ′ ( x )] 2 = 11 − 10 f ′′ ( x ) f ( x ) ( f ′ ( x )) 2 = 11 − 10 2 x (3 x − 2) (3 x − 1) 2 . Because ϕ ′ (1) = 11 − 5 = 6 > 1 . this iteration can not ensure local convergence near x = 1 . (c) The one in ( a ) is better, as the corresponding fixed-point iterative method converges with order 2. 2

(a) * Let f ( x ) = x 2 − 3 x + 1 and x 0 = 1 , x 1 = 3 , compute x 3 generated from the secant method. (b) Show that if f ′ ( q ) ̸ = 0 and x n → q as n → ∞ , then f ( q ) = 0 . Solution. (a) By secant method, we have f ( x 1 ) = 1 , f ( x 0 ) = − 1 , x 2 = f ( x 1 ) x 0 − x 1 f ( x 0 ) f ( x 1 ) − f ( x 0 ) = 3 + 1 2 = 2 , f ( x 2 ) = − 1 , f ( x 1 ) = 1 , x 3 = f ( x 2 ) x 1 − x 2 f ( x 1 ) f ( x 2 ) − f ( x 1 ) = − 3 − 2 − 2 = 2 . 5 . (b) By secant method, we have x n +1 = x n − f ( x n ) x n − x n − 1 f ( x n ) − f ( x n − 1 ) . We notice that if x n → q , we have f ( x n ) = f ( q ) + f ′ ( q )( x n − q ) + f ′′ ( ζ n )( x n − q ) 2 . Hence lim n →∞ x n − x n − 1 f ( x n ) − f ( x n − 1 ) = 1 f ′ ( q ) . Therefore, q = q − f ( q ) /f ′ ( q ) which implies f ( q ) = 0 . 5. Let x ∗ be a root of f ( x ) with multiplicity 2 and f ( x ) is continuous and differentiable up to the second order near x ∗ . (a) * Let φ ( x ) = x − a f ( x ) f ′ ( x ) , 0 < a ≤ 2 . Show that lim x → x ∗ φ ′ ( x ) = 1 − a 2 . (b) * Let x n +1 = x n − a f ( x n ) f ′ ( x n ) , 0 < a ≤ 2 , Show { x n } converges in a neighborhood of x ∗ . (c) For the sequence generated from (b), let ϵ n = x n − x ∗ . Assuming there exist δ > 0 , such that φ ′′ ( x ) is bounded when | x − x ∗ | < δ . Prove that, when a = 2 , | ϵ n +1 | < Cϵ 2 n , for some positive constant C . (d) Apply the iteration in (b) with a = 2 to find the root of f ( x ) = x 5 − 3 x 4 − 18 x 3 + 86 x 2 − 111 x + 45 with initial value x 0 = 2.5, please write down the approximate solution at the 4 th iteration . Solution. (a) We note that by definition of φ , we have lim x → x ∗ φ ′ ( x ) = 1 − a + a lim x → x ∗ f ( x ) f ′′ ( x ) f ′ ( x ) 2 . Since x ∗ is a root of f ( x ) with multiplicity 2 , then f ( x ) can be written as f ( x ) = ( x − x ∗ ) 2 g ( x ) , where g ( x ) is two times continuously differentiable and g ( x ∗ ) ̸ = 0 . Therefore, we have f ′ ( x ) = 2( x − x ∗ ) g ( x ) + ( x − x ∗ ) 2 g ′ ( x ) , f ′′ ( x ) = 2 g ( x ) + 4( x − x ∗ ) g ′ ( x ) + ( x − x ∗ ) 2 g ′′ ( x ) ; 4

which implies lim x → x ∗ f ( x ) f ′′ ( x ) f ′ ( x ) 2 = lim x → x ∗ ( x − x ∗ ) 2 g ( x )(2 g ( x ) + 4( x − x ∗ ) g ′ ( x ) + ( x − x ∗ ) 2 g ′′ ( x )) (2( x − x ∗ ) g ( x ) + ( x − x ∗ ) 2 g ′ ( x )) 2 = lim x → x ∗ 2 g 2 ( x ) + 4( x − x ∗ ) g ( x ) g ′ ( x ) + ( x − x ∗ ) 2 g ( x ) g ′′ ( x ) 4 g 2 ( x ) + 4( x − x ∗ ) g ( x ) g ′ ( x ) + ( x − x ∗ ) 2 g ′ ( x ) 2 = 1 2 . Hence, lim x → x ∗ ϕ ′ ( x ) = 1 − a/ 2 . (b) Since 0 ⩽ φ ′ ( x ∗ ) = 1 − a 2 < 1 , there exists a (closed) neighbourhood of x ∗ , say B ( x ∗ , δ ) such that 0 ⩽ φ ′ ( x ) ⩽ c < 1 , for ∀ x ∈ B ( x ∗ , δ ) . Note that φ ( x ∗ ) = x ∗ as f ( x ∗ ) = 0 . Define ϵ n +1 = x n +1 − x ∗ = φ ( x n ) − φ ( x ∗ ) , then by mean value theorem, ϵ n satisfies: ϵ n +1 = φ ′ ( ζ n )( x n − x ∗ ) = φ ′ ( ζ n ) e n where ζ n lies between x n and x ∗ . Therefore, we have ϵ n → 0 as c < 1 . (c) We note that the Taylor series of ϕ ( x ∗ + ϵ n ) is x n +1 = φ ( x n ) = φ ( x ∗ ) + φ ′ ( x ∗ )( x n − x ∗ ) + φ ′′ ( ξ ) 2 ( x n − x ∗ ) 2 , where ξ lies between x ∗ and x n . If a = 2 , we have φ ′ ( x ∗ ) = 1 − a 2 = 0 . Moreover, since φ ( x ∗ ) = x ∗ , we have | ϵ n +1 | = | x n +1 − x ∗ | = | φ ′′ ( ξ ) | 2 ϵ 2 n < Cϵ 2 n . Here we use the assumption that φ ′′ ( ξ ) 2 is bounded in the neighborhood of x ∗ . (d) We note f ′ ( x ) = 5 x 4 − 12 x 3 − 54 x 2 + 172 x − 111 , then the iteration is x k +1 = x k − 2 x 5 − 3 x 4 − 18 x 3 + 86 x 2 − 111 x + 45 5 x 4 − 12 x 3 − 54 x 2 + 172 x − 111 The results of the first four iterations are as follows: x 0 = 2 . 5 x 1 = 3 . 2895 x 2 = 3 . 036414485 x 3 = 3 . 000719162 . 5