MEC001P1M 2/18

Numerical Methods in Engineering Review

(Solution of Non-Linear Equations-2)
 We had seen the following methods
Kannan Iyer  Bisection Method
[Link]@[Link]
 Method of False Position
 Secant Method
 Newton’s Method
 Fixed Point Iteration
Department of Mechanical Engineering
Indian Institute of Technology, Jammu

MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

3/18 4/18
Agenda for Today Order of Convergence
A method is said to converge with order p, if the error
decays as given by the expression
 Today We shall discuss the rate of
convergence of the methods. 𝑒 =𝑎 𝑒
 First we will digest the meaning of the
order of a method.
 Then we shall derive the order of the three eN
popular methods we have discussed in
the last class.

Ln(N)
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

1
 5/18 6/18
Fixed Point Iteration-I Fixed Point Iteration-II
 Our recursive relation was  Eq. (3) can be written as
xn 1  g ( xn ) (1) en 1  g (   en )  g (  )
 If α is our root then en
2
 g (  )  en g (  )  g (  )  ...  g (  )
  g(  ) (2) 2
 Eqs. (1) and (2) imply that  en g (  ) Using Mean Value Theorem

(3) Where ξ is such that it lies between xn and α

xn 1    g( xn )  g(  )
 Defining the error at any level i as en  1
  g (  )
ei  x i   (4) en
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

7/18 8/18
Fixed Point Iteration-III Newton’s Method-I
 For the method to converge,  In this case our recursive relation was
en  1  xn1  xn  f ( xn ) / f ( xn ) (1)
  1 or g (  )  1
en
 In fact this must be true in its entire path of f ( xn )  f (  )
initial guess all the way to the route, as en  1    e n   
otherwise, it can be thrown out anywhere f ( x n )
 Since en+1 = c en the method is said to have Note that f(α) = 0 by definition
linear convergence near the root.
f ( x n )  f ( x n  en )
 It implies that the error will decrease linearly en  1    en   
in the error-number of iteration plot f ( x n )
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

2
 9/18 10/18
Bracketing of Roots-II Secant Method-I
 en  1  en



f ( x n )  f ( x n )  en f ( x n ) _ ( e n / 2 ) f ( x n )
2
  The error analysis for this method is
tedious but very illustrative of the
f ( x n )
power law technique

 en  1 
en
2
 f ( x n )   In this case our recursive relation was
2 f ( x n ) f ( xn )
 For the method to converge,  xn1  xn 
f ( xn )  f ( xn1 )
en  1 e  f ( x n )  xn  xn1
 1 n 1
en 2 f ( x n )
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

11/18 12/18
Secant Method-II Secant Method-III
 en1  en
 en1    en  
xn  xn1  f (   en )
f (   en )  f (   en1 ) 
en  en1 ( en f ( ) ( en2 / 2 ) f ( ))
2 2
e e
 en1  en =0 ( en  en1 ) f (  )  n n1 f (  )
2

en  en1 ( f ( )  en f ( ) ( en2 / 2 ) f ( )) en+en+1
e f (  )
2
f (  )  en f (  )  ( en / 2 ) f (  )
2
en  n
2 f (  )

 f (  )  en1 f (  )  ( en1 / 2 ) f (  )
2
  en1  en 
e  e f (  )
1  n n1
2 f (  )
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

3
 13/18 14/18
Secant Method-IV Secant Method-V
enen1 f (  )
 As x approaches the root,  en1  (1)
en  en1 f (  ) 2 f (  )
1  If we assume that the method is of order p, we
2 f (  ) can write
1

 e f (  )  en  en1 f (  )  en  aen1  en1   en 

2 p
en1  aen and
p p
 en1  en   en  n 1 
 
2 f 
 (  )  2 f (  )  a
   Eq.(1) can now be written as
1
 e  e f (  ) en f (  ) 3 
2
e  e  p f (  )
 en  en  en n n1  O( en )
p
  aen  n  n 
 2 f (  ) 2 f (  )  2  a  f (  )
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

15/18 16/18
Secant Method-VI Secant Method-VII
 By reorganising terms, we get  If p < 1, the method will diverge. Thus when the
1 method converges, p > 1, which leads to
p 1 1 1 f (  )
1
 a en  en p
p

2 f (  ) 1 5
p  1.62
 Since the power of n has to be homogeneous, 2
we can write
1  Thus the method is inferior to Newton’s method,
p  1  p  p 1  0
2 but needs only one function evaluation at a step
p and hence is competitive
1 5
p
2
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II

4
 17/18 18/18
Continuation Method Closure
 Many times, the equation may be difficult to solve
as the root is not known and the function is
difficult.  We understood the meaning of the order of
 A method called continuation method is very useful convergence.
 For an arbitrary x0, we can say that x0 is the root of  Fixed point iteration has linear convergence.
the function f(x)-f(x0)  Newton’s method has quadratic convergence.
 If we now define our function as  Secant method has an order of convergence =1.6.
 F(x) = f(x) – β f(x0), and use x0 as the guess for β =  We also understood the concept of the
0.9, we can find the root because the guess is continuation method.
good
 We can proceed in this manner successively by
reducing β to 0, root of f(x) can be found
MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II MEC001P1M, Numerical Methods in Engineering, Lecture 3 Non-linear Equations-II