Numerical Solutions of NonLinear equations
Raju Sharma
Assistant Professor
Department of Civil Engineering
Chandigarh University
Introduction of polynomial
If f(x) is a quadratic or cubic equation then we can
find the root of the equation f(x) =0
(1) 2x2-8x+6=0
(2) 2x3+x2-13x+5=0
f(x) =a0xn+ a1xn-1+ . + an-1x +an
When f(x) is a polynomial of higher degree or an
expression involving transcendental functions (equation
contains trigonometric, logarithmic, exponential) e.g.
1+cos-5x, xtanx-cosx, e-x sin x etc, algebraic methods
are not available.
To find the roots of such types of equations, numerical
methods are used.
Following are the Numerical Methods
1. Bisection Method
2. Regula - falsi Method or method of false
position
3. Secant Method
4. Newton-Raphson Method
5. Iteration Method
Bisection Method
This method is based on the theorem:
If a function f(x) is continuous b/w a
f(
x)
& b, and f(a) , f(b) are of opposite
Y=
signs then there exist at least one
root b/w a & b.
Suppose that a root of f(x)=0 lies in
a
the interval (a, b) i.e. f(a) f(b)<0. we
bisect this interval and obtain
x1 = (a+b)/2
If f(x1)=0, then x1 is a root of f(x)=0
Otherwise root lies b/w a and x1 or x1
& b
x2
x3
x1
interval as
e
h
t
t
c
e
is
b
Then, we
e process
h
t
e
u
in
t
n
o
before and c
desired
o
t
d
n
u
o
f
is
t
until the roo
accuracy.
Then the second approximation to the root is x2 = (a+x1)/2
We have f(x2)<0
and f(x2) f(x1) <0
Root lies in (x2, x1)
If f(x2) is ve, The root lies between x1 & x2 . Then the third
approximation to the root is
x3 = (x1+ x2 )/2
and so on..
Q-1 Find a root of the equation x3-4x-9=0,using the
bisection method correct the three decimal places
f(x) =x3-4x-9
(1)
f(2)=23-4 x 2 -9=-9
f(3)= 33-4 x 3 -9=6
Hence root lies b/w 2 and 3
First approximation to the root
is x1=(2+3)/2 = 2.5
Then put x1 in eq. 1
f(2.5)= 2.53-4 x 2.5-9=-3.375<
0
f(x1) f(3) < 0
root lies b/w x1 and 3
x2 = (2.5+3)/2 =2.75
Then put x2 in eq. (1)
f(2.75)= 2.753-4 x 2.759=0.796 > 0
f(x1) f(x2) < 0
Root lies between x1 & x2
Thus, the third approximation
to the root is
x 3 = (x1 + x2 )/2 = 2.625
f(2.625)= 2.6253-4 x 2.625-9=1.4121 <0
And f(x2) f(x3) < 0
Root lies b/w x2 & x3
Thus, the fourth
approximation to the root is
x4 = (x2 + x3 )/2 = 2.6875
By repeating the process, the
successive approximation are
x5 = 2.71875
x6 = 2.70313
x7 = 2.71094
x8 = 2.70703
x9 = 2.70508
x10 = 2.70605
x11 = 2.70654
x12 = 2.70642
Hence the required root is 2.706
Regula - falsi Method or method of false
position
Choose two points x0 & x1, such
that f(x0) & f(x1) are of opposite
signs i.e., f(x0) f(x1) < 0
The graph of y= f(x) crosses the xaxis b/w these points.
A[x0, f(x0)]
This method consist in replacing
the curve AB by the chord AB and
taking the point of intersection of
the chord with the x-axis as an
approximation to the root
x3
O x
0
P(x)
x2 x1
B[x1, f(x1)]
Equation of the chord joining the points
A[x0, f(x0)] and B[x1, f(x1)] is
y-f(xo) =((f(x1)- f(xo)/(x1-xo))/ (x-xo)
The abscissa of the point where the
chord cuts the x-axis (y=0) is given by
x =x2=(xo (x1-xo)/(f(x1)- f(xo)) f(xo)
---- (1)
A[x0, f(x0)]
Which is the approximation to the root.
Or x2 = (xo f(x1)-x1 f(xo))/( f(x1)- f(xo))
If now f(xo) and f(x2) are of opposite
x
3
signs, then the root lies b/w xo and x2
So replacing x1 by x2 and find the new
root x3
x
0
P(x)
B[x1, f(x1)]
The procedure is repeated till the root is found to
desired accuracy. The iteration process based on
equation 1 is known as Regula Falsi Method.
Note :- if the root lies initially in (xo, x1), then one of the
end points is fixed for all iterations.
For example, if xo is fixed, then the method is of the
form
xk+1= xo f(xk)- xk f(xo)/ f(xk) - f(xo)
K=1,2,3,
Find a real root of the equation x3-2x-5=0,
by regula falsi method correct to three
decimal places
Solution:-
A real root of the equation
f(x) = x3-5x+1=0
lies in the interval (0, 1). Perform four
iterations of regular-falsi method to
obtain this root
Solution:-
Secant method
This method is an improvement over the method of false
position (or Regula-falsi method ) as it does not require
the condition
f(xo) x f(x1) < 0
In this method two most recent approximations to the
root are used to find the next approximation
Let xk-1, xk be two
approximations to the root of
f(x)=0. Then p (xk-1 , f(xk-1)) Q
p((xk-1, f(xk-1))
(xk, f (xk)) are points on the
curve y=f(x)
a(xk , f(xk))
the equation of straight line PQ
is given by
y- f(xk) = (f(xk-1)- f(xk)/(xk-1-xk)) (x-xk)
we get
Substitute y=o, and solving for x,
xk+1
x=xk-((xk-xk-1)/f(xk)-f(xk-1)) x f(xk)
The next approximation, xk+1 , to the root is
written as
xk+1=(xk-1 f(xk) xk f(xk-1))/ f(xk) - f(xk-1)
k = 1,2,3
Find a root of the equation x3-2x-5=0 using
secant method correct to three decimal
places
Solution:-
Drawback of secant method
If at any intersection f(xn)= f(xn-1), this method
fails and shows that it does not converge
necessarily. This is a drawback of secant
method over the method of false position which
always converge. But if the secant method once
converges, its rate of convergence is 1.6 which is
faster that that of the method of false position.
Newton-Raphson Method
Let x0 be an approximate root of the equation
f(x)=0. if x1 = x0+h be the exact root then f(x1)=0
Expanding f(x0+h) by Talors series
f(x0) +h f (x0) +(h2 /2!) f (x0) +_ _ _ _=0
Since h is very small, neglecting h2 & higher power
of h, we get
f(x0) +h f (x0) =0
h = -(f(x0)/ f (x0))
We have x1 = x0+h
x1 = x0 -(f(x0)/ f (x0))
Successive approximation are given by x2, x3, _
_ _ _, xn+1
Where
xn+1 = x0 -(f(xn)/ f (xn))
Which is known as Newton-Raphson formula
Find the positive root of x4-x=10 correct to three
decimal places, using newton - raphson method
Solution:-
Some deduction from Newton-Rapson
formula
Iterative formula to find 1/N is xn+1 = xn (2-Nxn)
Iterative formula to find N is xn+1 = (xn +N/xn)
Iterative formula to find 1/ N is xn+1 = (xn +1/Nxn )
k
Iterative formula to find 1/ N is xn+1 =1/ k [(k-1) xn+
N/xnk-1)
Let x = 1/N or (1/x)-N =0
Take f(x) = (1/x)-N where f(x) = -(1/x2)
Newtons formula gives
xn+1
= xn f(xn)/f (xn)
= xn ((1/ xn) N)/ -(1/xn2 )
= xn + ((1/ xn) N) xn2
= xn + xn N xn2
= 2xn N xn2
xn(2-N xn)
Hence Proved
Evaluate 1/31 correct to four decimal places by newton/s
iteration method
Solution:-
Iteration Method
To find the root of the equation f(x) =0
..(i)
By successive approximation, we rewrite (i) in the form
x= (x).
x
=
Y
Y = (x)
o
x0
x2
x3
x1
Let x = xo be an initial approximation of the desired root
then the first approximation x1 is given by
x1= (x0)
Now treating x1 as the initial value, the second
approximation is x2= (x1)
Processing in this way, the nth approximation is xn=
(xn-1)
Sufficient condition for the convergence of
iterations
If
I. is a root of f(x)=0 which is equivalent to x= (x)
II. I, be any interval containing the point x=
III. | (x)|< 1 for all x lies b/w I
Then the sequence of approximations x 0, x1, x2,_ _ _
_,xn all converge to the root provided the initial
approximation x0 in chosen I
Find the real root of the equation Cosx=3x-1.correct
to three decimal places using iteration method.
Solution
Rate of convergence
Let x0,x1,x2, _ _ _ _ be the value of root () of an
equation at the o , 1st ,2nd iterations while its actual
value is 3.5567
The value of this root calculated by three different
methods are as given below:Root
1st Method
2nd Method
3rd method
x0
x1
5.6
3.8527
3.8327
x2
6.4
3.5693
3.56834
x3
8.3
3.55798
3.55743
x4
9.7
3.55687
3.55672
x5
10.6
3.55676
x6
11.9
3.55671
Rate of convergence
Bisection Method
1/2
Regula-falsi Method
1.62
Secent method
1.6
Newton Rapson
The fastness of convergence in any method is represented by its rate
of convergence
