Newton Raphson Method for simple root
Consider an approximation 𝑥𝑛 in the neighbourhood of a root of 𝑓 𝑥 = 0.
Let B 𝑥𝑛 , 𝑓(𝑥𝑛 ) be the point on the curve 𝑦 = 𝑓(𝑥).
y
B(x n ,f (x n ))
x
C(x n 1,0)
Prepared by Dr. V. Prabhakar, School of Advanced Sciences, VIT Chennai
Equation of the tangent at the point B is
𝑦 − 𝑓 𝑥𝑛 = 𝑓′(𝑥𝑛 )(𝑥 − 𝑥𝑛 )
In Newton-Raphson method, the new approximation is the
intersection point of the tangent line with the x-axis.
Let this tangent line at B cut the x-axis at the intersection point
C 𝑥𝑛+1 , 0 . If 𝑓(𝑥𝑛+1 ) ≠ 0 , then the new approximation is 𝑥𝑛+1 .
As C 𝑥𝑛+1 , 0 is a point on the tangent line, we have
0−𝑓 𝑥𝑛 = 𝑓′(𝑥𝑛 )(𝑥𝑛+1 − 𝑥𝑛 )
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
On re-arranging, we get the Newton-Raphson iteration scheme for
𝑓 𝑥 = 0 as
𝑓(𝑥𝑛 )
𝑥𝑛+1 = 𝑥𝑛 − , 𝑛 = 0,1,2, …
𝑓 ′ (𝑥𝑛 )
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Worked Problem
Find a smallest positive real root of the equation
𝑥 3 + 𝑥 2 − 1 = 0 , correct to 4 decimal places using Newton-
Raphson method.
Solution: Let 𝑓(𝑥) = 𝑥 3 + 𝑥 2 − 1. 𝑓 0 = −1 and 𝑓(1) = 1
Hence a smallest positive real root lies in the interval (0,1).
𝑓 ′ 𝑥 = 3𝑥 2 + 2𝑥
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Let the initial approximation be 𝑥0 = 0.5.
The iteration scheme for Newton-Raphson method is
𝑓(𝑥𝑛 )
𝑥𝑛+1 = 𝑥𝑛 − ′
𝑓 (𝑥𝑛 )
, 𝑛 = 0,1,2, …
Iteration1 (n=0) :
𝑓 𝑥0 = 𝑓 0.5 = −0.6250
𝑓 ′ 𝑥0 = 𝑓′ 0.5 = 1.7500
f x0 −0.6250
x1 = x0 − ′ = 0.5 − =0.8571
f x0 1.7500
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
The sequence of iterates are given below.
𝑛 𝑥𝑛 𝑓(𝑥𝑛 ) 𝑓′(𝑥𝑛 ) 𝑥𝑛+1 𝑓(𝑥𝑛+1 )
0 0.5000 -0.6250 1.7500 0.8571 0.3644
1 0.8571 0.3644 3.9181 0.7641 0.0301
2 0.7641 0.0301 3.2800 0.7550 0.0003
3 0.7550 0.0003 3.2198 0.7549 0.0000
4 0.7549 0.0000 3.2193 0.7549 0.0000
The required root is 0.7549 correct to 4 decimal places.
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Rate of convergence of Newton-Raphson method
Let 𝜉 be a simple root of 𝑓 𝑥 = 0. The iteration scheme for
Newton-Raphson method is
𝑓(𝑥𝑘 )
𝑥𝑘+1 = 𝑥𝑘 − 𝑓 ′ (𝑥𝑘 )
, 𝑘 = 0,1,2, …
Let the error in the 𝑘 𝑡ℎ iteration be ∈𝑘 = 𝑥𝑘 − 𝜉.
Substituting 𝑥𝑘 = 𝜉+∈𝑘 , in the iteration scheme, we get
𝑓(𝜉+∈𝑘 )
∈𝑘+1 =∈𝑘 − ---------- (A)
𝑓 ′ (𝜉+∈𝑘 )
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Now, Taylor expansion of 𝑓 ∈𝑘 +𝜉 about the point 𝜉 is
2
∈ 𝑘
𝑓 ∈𝑘 +𝜉 = 𝑓 𝜉 + ∈𝑘 𝑓 ′ 𝜉 + 𝑓 ′′ 𝜉 + ⋯
2
Also, Taylor expansion of 𝑓′ ∈𝑘 +𝜉 about the point 𝜉 is
2
∈ 𝑘
𝑓′ ∈𝑘 +𝜉 = 𝑓′ 𝜉 + ∈𝑘 𝑓 ′′ 𝜉 + 𝑓 ′′′ 𝜉 + ⋯
2
Using the above Taylor’s series expansions about the point 𝜉,
and noting that 𝑓 𝜉 = 0 (as 𝜉 is a simple root) ,
the iteration scheme (A) becomes
∈2𝑘 ′′ ′
∈𝑘 𝑓 𝜉 + 𝑓 𝜉 + ⋯
∈𝑘+1 =∈𝑘 − 2
2
∈
𝑓′ 𝜉 + ∈𝑘 𝑓 ′′ 𝜉 + 𝑘 𝑓 ′′′ 𝜉 + ⋯
2
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
1 𝑓′′ 𝜉
∈𝑘+1 =∈𝑘 − ∈𝑘 + ′ ∈2𝑘 + ⋯ 1+𝑧 −1 ,
2𝑓 𝜉
𝑓 ′′ 𝜉 1 𝑓 ′′ 𝜉 2
where 𝑧 = ∈𝑘 + ∈𝑘 + ⋯
𝑓 𝜉′ 2𝑓 𝜉 ′
1 𝑓 ′′ 𝜉 2
⇒ ∈𝑘+1=∈𝑘 − ∈𝑘 +
2𝑓 𝜉 ′ ∈𝑘 + ⋯ 1 − 𝑧 + 𝑧2 − ⋯
𝑓 ′′ 𝜉 2 1 𝑓 ′′ 𝜉 2 3
⇒ ∈𝑘+1 = ′ ∈𝑘 − ′
∈ 𝑘 +𝒪(∈ 𝑘)
𝑓 𝜉 2𝑓 𝜉
1 𝑓 ′′ 𝜉 2 3 1 𝑓 ′′ 𝜉
⇒ ∈𝑘+1 = ∈ +𝒪(∈ 2
′ 𝑘 𝑘) ⇒ ∈𝑘+1 ≤ ∈𝑘
2𝑓 𝜉 2 𝑓′ 𝜉
Thus, the rate of convergence of the Newton-Raphson
method is 2 or the convergence of the method is quadratic.
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Newton’s method for multiple root
Case(i) : For a multiple root with multiplicity known
Let 𝜉 be a multiple root of the equation 𝑓 𝑥 = 0 with multiplicity 𝑚.
Although Newton-Raphson method can be used for a multiple root, it
has linear rate of convergence when 𝑚 >1. The Newton-Raphson
method is modified by introducing parameter dependent on the
multiplicity of the root to increase their order of convergence, and is
called modifed Newton-Raphson method.
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Case (ii) : For a multiple root with unknown multiplicity
In this case, we can use the following procedure.
If 𝑓 𝑥 = 0 has a multiple root 𝜉 of multiplicity 𝑚 defined by
𝑚
𝑓 𝑥 = 𝑥−𝜉 𝑔(𝑥), 𝑔 𝜉 ≠ 0, then it is known that
𝑓 ′ 𝑥 = 0 will have the same root 𝜉 of multiplicity 𝑚 − 1
defined by 𝑓 ′ (𝑥) = 𝑥 − 𝜉 𝑚−1
ℎ(𝑥), h 𝜉 ≠ 0
𝑓 𝑥
If we now define 𝑔 𝑥 = 𝑓′ 𝑥
, then 𝑔(𝑥) has a simple root 𝜉.
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
We can find the approximate value of the root 𝜉 of 𝑔 𝑥 = 0
using the Newton-Raphson method iterative scheme
𝑔 𝑥𝑘
𝑥𝑘+1 = 𝑥𝑘 − ′
𝑔 𝑥𝑘
𝑓 𝑥
Using 𝑔 𝑥 = and simplifying, we get the following
𝑓′ 𝑥
iteration scheme for 𝑓 𝑥 = 0.
𝑓𝑘 𝑓𝑘′
𝑥𝑘+1 = 𝑥𝑘 −
𝑓𝑘′2 −𝑓𝑘 𝑓𝑘′′
This iteration scheme can be used to find the multiple root 𝜉 of
𝑓 𝑥 = 0.
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Modified Newton-Raphson method
(for multiple root with multiplicity known)
If 𝑓 𝑥 = 0 has a root of multiplicity m, then
The iteration scheme is given by
𝑓 𝑥𝑛
𝑥𝑛+1 = 𝑥𝑛 − 𝑚 ′ , 𝑛 = 0,1,2,3 …
𝑓 𝑥𝑛
Proof : Define F x = 𝑓(𝑥)1/𝑚 .
If 𝑓 𝑥 = 0 has a root of multiplicity m,
then FDr.𝑥V. Prabhakar,
Prepared by will
= 0School of Advanced the same root as a simple root.
haveSciences,
VIT Chennai
By Newton-Raphson iteration formula to F 𝑥 = 0,
the sequence of iterates are
𝐹 𝑥𝑛
𝑥𝑛+1 = 𝑥𝑛 − ′ , 𝑛 = 0,1,2,3 …
𝐹 𝑥𝑛
In terms of the given function 𝑓(𝑥), we finally get
the following sequence of iterates
𝑓 𝑥𝑛
𝑥𝑛+1 = 𝑥𝑛 − 𝑚 ′ , 𝑛 = 0,1,2,3 …
𝑓 𝑥𝑛
(Modified Newton-Raphson method)
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai
Worked Example (multiple root).
Determine the double root of 𝑥 3 − 5𝑥 2 + 8𝑥 − 4 = 0,
correct to 3 decimal places, given that the root is close to 1.6.
Solution. 𝑓 𝑥 = 𝑥 3 − 5𝑥 2 + 8𝑥 − 4
𝑓′ 𝑥 = 3𝑥 2 − 10𝑥 + 8
The iteration scheme for modified Newton-Raphson method
with 𝑚 = 2 becomes
𝑓 𝑥𝑛
𝑥𝑛+1 = 𝑥𝑛 − 2 ′ , 𝑛 = 0,1,2,3 …
𝑓 of𝑥Advanced
Prepared by Dr. V. Prabhakar, School 𝑛 Sciences,
VIT Chennai
Starting with the initial approximation 𝑥0 = 1.6, the
sequence of iterates are given below.
𝑛 𝑥𝑛 𝑓(𝑥𝑛 ) 𝑓′(𝑥𝑛 ) 𝑥𝑛+1 𝑓(𝑥𝑛+1 )
0 1.6000 0.0960 -0.3200 2.2000 0.0480
1 2.2000 0.0480 0.5200 2.0154 0.0002
2 2.0154 0.0002 0.0315 2.0001 0.0000
3 2.0001 0.0000 0.0002 2.0000 0.0000
Thus, the double root correct to 3 decimal places is 2.000.
Exercise : Find a double root of 𝑥 3 − 7𝑥 2 + 16𝑥 = 12
near 1, correct to 3 decimal places. Ans : 2.000
Prepared by Dr. V. Prabhakar, School of Advanced Sciences,
VIT Chennai