Numerical

techniques
(MA-201)
Numerical techniques (MA-201)
Prof. S.
Mukhopadhyay Lecture Notes-6-8
Iterative
methods

Newton- by
Raphson
method Prof. Santwana Mukhopadhyay
Convergence
and Order of
iterative
Department of Mathematical Sciences
methods IIT(BHU), Varanasi
 Roots of transcendental equations

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay
Contents
Iterative
methods

Newton-
Raphson
method
1 Examples of Iterative methods
Convergence
and Order of
iterative
methods 2 Newton-Raphson method

3 Convergence and Order of iterative methods

 Task

Numerical
techniques
(MA-201)

Prof. S. Task(previous class): Find a positive real root of each of the

Mukhopadhyay
following equations, corrcet upto 4 decimal places, by secant
Iterative method:
methods

Newton-
Raphson (i)x 4 − x − 10 = 0
method

Convergence
and Order of
iterative (ii) sin x + x 2 − 1 = 0.
methods

Also apply bisection method and Regula-Falsi method to find

the root with same accuracy, and compare thre three methods
with the no of iterations performed.
********
 Task

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay

Iterative
methods

Newton-
Raphson
method

Convergence
Ans???
and Order of
iterative
methods
 Solution of Example-3

Numerical
techniques
Sol. Let f (x ) = x 4 − x − 10. We find that
(MA-201)

Prof. S. f (0) = –10, f (1) = –10, f (2) = 4.

Mukhopadhyay

Iterative
Hence, the smallest positive root lies in the interval (1, 2).
methods The Secant method gives the iteration scheme
Newton-
Raphson xk − xk−1
method xk+1 = xk − fk , k = 1, 2, ...
Convergence fk − fk−1
and Order of
iterative
methods With x0 = 1, x1 = 2, we obtain the sequence of iterates

x2 = 1.7143, x3 = 1.8385, x4 = 1.8578,

x5 = 1.8556, x6 = 1.8556.

The root correct to three decimal places is 1.856. No of

iterations = 6.
By Bisection no of iterations for same accuracy is 10.
 Example

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay

Iterative
methods

Newton- Example
Raphson
method
Given that the equation x 2.2 = 69 has a root between 5 and
Convergence
and Order of 8. Use the method of regula-falsi to determine it.
iterative
methods
 Solution

Numerical
techniques Sol. Let f (x ) = x 2.2 − 69. We find
(MA-201)

Prof. S.
Mukhopadhyay
f (5) = −34.50675846 and f (8) = 28.00586026.

Iterative
methods
Hence
Newton-
5(28.00586026) − 8(−34.50675846)
Raphson
method
x1 = = 6.655990062.
28.00586026 + 34.50675846
Convergence
and Order of
iterative Now, f (x1 ) = −4.275625415 and therefore, the root lies
methods
between 6.655990062 and 8. We obtain

x2 = 6.83400179, x3 = 6.850669653.

And so on. The correct root is 6.852, correct to three decimal

places.
Find No of steps. Also apply Secant method and compare.
 Newton-Raphson method

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay In this method, we approximate the graph of the function
y = f (x ) in the neighborhood of the root by the tangent to
Iterative
methods the curve at the point (xk , fk ) and take its point of
Newton- intersection with the x -axis as the next iterate. We have the
Raphson
method formula of Newton-Raphson method as
Convergence
and Order of
fk
iterative
xk+1 = xk − , k = 0, 1, ... (2.1)
methods
fk0

This method requires one function evaluation and one first

derivative evaluation per iteration.
 Example

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay

Iterative
methods

Newton- Example
Raphson
method
Use the Newton-Raphson method to find a root of the
Convergence
and Order of equation x 3 − 2x − 5 = 0.
iterative
methods
 Solution

Numerical
techniques
Sol. Here f (x ) = x 3 − 2x − 5 and f 0 (x ) = 3x 2 − 2. Hence,
(MA-201)

Prof. S. xn3 − 2xn − 5

Mukhopadhyay xn+1 = xn − (2.2)
3xn2 − 2
Iterative
methods Choosing x0 = 2, we obtain f (x0 ) = −1 and f 0 (x0 ) = 10.
Newton-
Raphson
Putting n = 0 in Eq. (2.2), we obtain
method
1
 
Convergence
and Order of x1 = 2 − − = 2.1
iterative 10
methods

Now,

f (x1 ) = (2.1)3 − 2(2.1) − 5 = 0.061 and f 0 (x1 ) = 11.23.

Hence
0.061
x2 = 2.1 − = 2.094568.
11.23
 Convergence of Iterative Methods

Numerical In practical applications, it is not always possible to find ξ exactly.

techniques
(MA-201) We therefore apply an iterative scheme and attempt to obtain an
approximate root xk+1 such that |f (xk+1 )| < ε and / or |xk+1 –xk | < ε .
Prof. S.
Mukhopadhyay where xk and xk+1 are two consecutive iterates and ε is the prescribed
error tolerance.
Iterative Definition :
methods
A sequence of iterates xk is said to converge to the root ξ if |xk –ξ| = 0 as
Newton-
Raphson
k→∞. If xk , xk–1 , ..., xk–m+1 are m approximates to a root, then we write
method an iteration method in the form
Convergence
and Order of xk+1 = ϕ(xk , xk–1 , ..., xk–m+1 )
iterative
methods where we have written the equation in the equivalent form x = ϕ(x ). The
function φ is called the iteration function. For m = 1, we get the
one-point iteration method xk+1 = ϕ(xk ), k = 0, 1, ...
Theorem: If φ(x) is continuous in the interval [a, b] that contains the
root and | φ´(x) | ≤ c < 1 in this interval, then for any choice of
x0 ∈ [a, b], the sequence of iteratesxk obtained as above converges to the
root of x = φ(x) or f (x) = 0.
Thus, for any iterative method of the above form, we need the iteration
function φ(x) and one or more initial approximations to the root.
 Order of Iterative Methods

Numerical
techniques Definition : An iterative method is said to be of order p or
(MA-201)
has the rate of convergence p, if p is the largest positive real
Prof. S.
Mukhopadhyay number for which
Iterative
methods |εk+1 | ≤ c|εk |p
Newton-
Raphson
method
where εk = xk –ξ is the error in the kth iterate. The constant c
Convergence
and Order of is called the asymptotic error constant.
iterative
methods It depends on various order derivatives of f (x) evaluated at ξ
and is independent of k.
The relationεk+1 = cεpk + O(εp+1k ) is called the error equation.

By substituting xi = ξ + εi for all i in any iteration method

and simplifying we obtain the error equation for that method.
The value of p thus obtained is called the order of this method.
 Convergence of Secant Method

Numerical
techniques
Hypothesis:
(MA-201) (1) Let f : R → R be a C 2 (R) function.
Prof. S.
Mukhopadhyay
(2) Let ξ be a simple root of the nonlinear equation f (x ) = 0,
that is f 0 (ξ) 6= 0.
Iterative
methods

Newton- Conclusion: Then there exists a δ > 0 such that for every
Raphson
method x0 , x1 ∈ [r − δ, ξ + δ],
Convergence (1) the secant method iterative sequence {xk } is well-defined.
and Order of
iterative (2) the sequence {xk } belongs to the interval [ξ − δ, ξ + δ].
methods
(3) lim xk = ξ.
k→∞
(4) Further, we have
p/(p+1)
|xk+1 − ξ| f 00 (ξ)
lim =
k→∞ |xk − ξ|p 2f 0 (ξ)
√
where p = ( 5 + 1)/2 ≈ 1.62. See whiteboard.
 Convergence of Regula-falsi Method

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay
Hypothesis:
Iterative Let f : [a0 , b0 ] → R be a continuous function such that the
methods

Newton-
numbers f (a0 ) and f (b0 ) have opposite signs.
Raphson
method

Convergence
Conclusion:
and Order of
iterative
If {xk } is the iterative sequence defined by regula-falsi
methods method. Then the sequence {xk } converges to an ξ ∈ (a0 , b0 )
such that f (ξ) = 0. The Regula-Falsi Method has linear rate
of convergence.
 Convergence of Newton-Raphson method

Numerical
techniques
(MA-201)

Prof. S.
Newton-Raphson formula given in Eq. (4.1) converges,
Mukhopadhyay
provided that the initial approximation x0 is chosen sufficiently
Iterative close to ξ. To obtain the rate of convergence of the method,
methods
we note that f (ξ) = 0 so that Taylor’s expansion of
Newton-
Raphson f (xk ) = f (ξ + k ) and f 0 (xk ) = f 0 (ξ + k ) gives
method

Convergence 1
and Order of f (xk ) = f (ξ) + k f 0 (ξ) + (k )2 f 00 (ξ) + ...
iterative
methods
2
and
1
f 0 (xk ) = f 0 (ξ) + k f 00 (ξ) + (k )2 f 000 (ξ) + ...
2
 Continued

Numerical
techniques
(MA-201)
Therefore, from the formula
Prof. S.
Mukhopadhyay
f (xk )
xk+1 = xk − (3.1)
Iterative
methods
f 0 (xk )
Newton-
Raphson we obtain that
method

Convergence
and Order of
f (ξ) + k f 0 (ξ) + 21 (k )2 f 00 (ξ) + ...
iterative k+1 = k −
methods f 0 (ξ) + k f 00 (ξ) + 12 (k )2 f 000 (ξ) + ...

k f 0 (ξ)[1 + 21 (k )f 00 (ξ)/f 0 (ξ) + ...]

= k −
f 0 (ξ)[1 + k f 00 (ξ)/f 0 (ξ) + 12 (k )2 f 000 (ξ)//f 0 (ξ) + ...]
 Continue

Numerical
techniques
(MA-201)

Prof. S.
Mukhopadhyay
1 00 0 00 0 1 2 000 0 −1
k+1 = k − k [1 + (k )f (ξ)/f (ξ) + ...][1 + k f (ξ)/f (ξ) + (k ) f (ξ)//f (ξ) + ...]
Iterative 2 2
methods

Newton- Therefore, we finally have

Raphson
method
1
Convergence
and Order of
k+1 = − f 00 (ξ)/f 0 (ξ)2k (3.2)
iterative
2
methods
Hence the rate of convergence of Newton-Raphson method is
2 and the asymptotic error constant c is fiven by
− 21 f 00 (ξ)/f 0 (ξ) which is dependent on the given function.
 Iterative method for multiple roots

Numerical
techniques
If the root ξ of f (x ) = 0 is a repeated root, then we may write
(MA-201) it as
Prof. S.
Mukhopadhyay
f (x ) = (x − ξ)m g(x ) = 0
where g(x ) is bounded and g(ξ) 6= 0. The root ξ is called a
Iterative
methods multiple root of multiplicity m. We obtain from the above
Newton-
Raphson
equation
method

Convergence
f (ξ) = f 0 (ξ) = ... = f (m−1) (ξ) = 0, f (m) (ξ) 6= 0.
and Order of
iterative
methods
Modified Newton-Raphson method for finding a multiple
root with multiplicity m is
fk
xk+1 = xk − m , k = 0, 1, ...
fk0
Task: Show that the rate of convergence of Newton-Raphson
method is linear, but modified Newton-Raphson method is
quadratic for a root with multiplicity m.