Solution of Nonlinear
Equation
Lecture no: 3
By: Dr. Yaseen Adnan
Ahmed
Topics covered:
Introduction
Methods of solution
Bisection Method
Newton-Rapson Method
Secant Method
Fixed point iteration or
successive substitution method
Solutions for systems of nonlinear
equations
Computer Programming using Matlab
as Practical Session
By the end of this lecture,
you will be able to:
Solve Nonlinear equation numerically
Introduction
Mathematical models for a variety of
problems can be formulated into equations
of the form:
..(1)
where x and f(x) may be real, complex or
vector quantities.
The solution involves finding the values of
x that satisfy the above equation. These
values are called the roots of the
equation.
Equation (1) may belong to
a) Algebraic equations
Or
b) Polynomial equations
c) Transcendental equations
Include trigonometric, exponential and
logarithmic terms
Linear and Non-linear
Equation
Linear: If the dependent variable
changes directly proportion to the
change in independent variable.
Non-linear: Any function with one
variable which does not graph as a
straight line in 2D or any function of
two variables which does not graph
as a plane in
Roots of Equations
Why?
ax 2 bx c 0
b b 2 4ac
x
2a
But
ax 5 bx 4 cx 3 dx 2 ex f 0 x ?
sin x x 0 x ?
Solution Methods
Several ways to solve nonlinear equations are
possible.
Analytical Solutions
possible for special equations only
Graphical Illustration
Useful for providing initial guesses for other methods
Numerical Solutions
Open methods / extrapolation methods
Bracketing methods / interpolation methods
Graphical Illustration
Graphical illustration are useful to provide an
initial guess to be used by other methods
Solve
x e x
The root [0,1]
root 0.6
x
2
Root
Bracketing/Open Methods
In bracketing methods, the method starts
with an interval that contains the root and a
procedure is used to obtain a smaller interval
containing the root.
Examples of bracketing methods : Bisection
method
In the open methods, the method starts with
one or more initial guess points. In each
iteration a new guess of the root is obtained.
Solution Methods
Many methods are available to solve nonlinear
equations
Bisection Method
Newtons Method
These will be
covered.
Secant Method
Fixed point iterations
Mullers Method
Bairstows Method
False Position Method
.
Stopping an Iteration
2.
3.
4.
Bracketing Methods
(Or, two point methods for finding roots)
Two initial guesses for the
root are required. These
guesses must bracket or
be on either side of the root.
== > See figure
If one root of a real and
continuous function, f(x)=0,
is bounded by values x=xl, x
=xu then
f(xl) . f(xu) <0. (The function
changes sign on opposite sides of the
root)
15
No answer (No
root)
Nice case (one
root)
Oops!! (two
roots!!)
Three
roots( Might
work for a
while!!)
Two roots( Might
work for a
while!!)
Discontinuous
function. Need
special method
Bisection Method
The Bisection method is one of the simplest
methods to find a zero of a nonlinear function.
To use the Bisection method, one needs an initial
interval that is known to contain a zero of the
function.
The method systematically reduces the interval.
It does this by dividing the interval into two
equal parts, performs a simple test and based on
the result of the test half of the interval is thrown
away.
The procedure is repeated until the desired
interval size is obtained.
Fin500J Topic 3
18
Intermediate Value Theorem
Let f(x) be defined on the
interval [a,b],
Intermediate value
theorem:
if a function is continuous
and f(a) and f(b) have
different signs then the
function has at least one
zero in the interval [a,b]
Fin500J Topic 3
f(a)
b
f(b)
19
Bisection Algorithm
Assumptions:
f(x) is continuous on [a,b]
f(a) f(b) < 0
f(a)
Algorithm:
Loop
1. Compute the mid point c=(a+b)/2
2. Evaluate f(c )
3. If f(a) f(c) < 0 then new interval [a, c]
If f(a) f( c) > 0 then new interval [c, b]
c b
a
f(b)
End loop
Fin500J Topic 3
20
Bisection Method
Assumptions:
Given an interval [a,b]
f(x) is continuous on [a,b]
f(a) and f(b) have opposite signs.
These assumptions ensures the existence of at
least one zero in the interval [a,b] and the
bisection method can be used to obtain a
smaller interval that contains the zero.
Fin500J Topic 3
21
Bisection Method
b0
a0
Fin500J Topic 3
a1
a2
Fall 2010 Olin Business School
22
Example:
Can you use Bisection method to find a zero of
f ( x) x 3 3 x 1 in the interval [0,1]?
Answer:
f ( x) is continuous on [0,1]
f(0) * f(1) (1)(-1) 1 0
Assumption s are satisfied
Bisection method can be used
Fin500J Topic 3
Fall 2010 Olin Business School
24
Stopping Criteria
Two common stopping criteria
1. Stop after a fixed number of
iterations b a
n 1
2
2. Stop when
Fin500J Topic 3
Fall 2010 Olin Business School
25
Example
Use Bisection method to find a root of the
equation x = cos (x) with (b-a)/2n+1<0.02
(assume the initial interval [0.5,0.9])
Question 1: What is f (x) ?
Question 2: Are the assumptions satisfied ?
Fin500J Topic 3
Fall 2010 Olin Business School
26
Fin500J Topic 3
Fall 2010 Olin Business School
27
Bisection Method
Initial Interval
f(a)=-0.3776
a =0.5
Fin500J Topic 3
f(b) =0.2784
c= 0.7
b= 0.9
Fall 2010 Olin Business School
28
-0.3776
0.5
-0.0648
0.7
Fin500J Topic 3
-0.0648
0.7
0.1033
0.8
0.2784
(0.9-0.7)/2 = 0.1
0.9
0.2784
(0.8-0.7)/2 = 0.05
0.9
Fall 2010 Olin Business School
29
-0.0648
0.7
0.8
-0.0648
0.70
Fin500J Topic 3
0.0183
0.1033 (0.75-0.7)/2=
0.025
0.75
-0.0235
0.725
0.0183 (0.750.75
Fall 2010 Olin Business School
0.725)/2= .0125
30
Summary
Initial interval containing the root
[0.5,0.9]
After 4 iterations
Interval containing the root [0.725 ,
0.75]
Best estimate of the root is 0.7375
| Error | < 0.0125
Fin500J Topic 3
Fall 2010 Olin Business School
31
Example
Given with interval , find the root of equation, .
Solution:
1. Take and
2. Use convergence criterion
3. Take
4. Do calculation based on below conditions:
5. If both and will have the same sign, hence set and .
6. If and will have opposite signs, hence set and .
2.0
1.5
-1
2.88
1.5
1.25
-1
2.88
0.70
1.25
1.125
-1
0.70
-0.20
1.125
1.25
1.19
-0.2
0.70
0.26
1.125
1.19
1.16
-0.2
0.26
0.04
1.125
1.16
1.14
-0.2
0.04
-0.09
1.14
1.16
1.15
-0.09
0.04
-0.029
1.15
1.16
1.155
-0.029
0.04
0.005
1.15
1.155
1.1525
-0.029
0.005
-0.01
10
If the absolute magnitude of the error
is
and Lo=2, how many iterations will
you have to do to get the required
accuracy in the solution?
10
2
k
2
by Lale Yurttas, Texas
A&M University
2 k 2 10 4
Chapter 5
k 14.3 15
35
Evaluation of Method
Pros
Easy
Always find root
Number of iterations
required to attain an
absolute error can be
computed a priori.
by Lale Yurttas, Texas
A&M University
Chapter 5
Cons
Slow
Know a and b that
bound root
Multiple roots
No account is taken of
f(xa) and f(xb), if f(xa) is
closer to zero, it is
likely that root is closer
to xa .
36
Newton-Raphson Method
(also known as Newtons Method)
Given an initial guess of the root x 0 ,
Newton-Raphson method uses
information about the function and its
derivative at that point to find a better
guess of the root.
Assumptions:
f (x) is continuous and first derivative is
known
An initial guess x0 such that f (x0) 0 is
given
Newtons Method
Suppose we have current
approximation x i , we
want to find a better
approximation x i 1
f ( xi ) 0
f ( xi )
xi xi 1
'
Xi+1
Fin500J Topic 3
Xi
f ( xi )
xi 1 xi
f ' ( xi )
Fall 2010 Olin Business School
38
Limitations
1. Division by zero may occur if is
zero or very close to zero.
2. If the initial guess is too far away
from the required root, the process
may converge to some other root.
3. A particular value in the iteration
sequence may repeat, resulting in
an infinite loop.
Example 2.4
Approximate
a real root for on using
Newton-Raphson method at the
starting point , and the convergence
criterion .
Solution:
Derive the given function to be
Use
formula:
-1.000
-1.000
4.000
-0.750
-0.750
-0.172
2.690
-0.686
-0.686
-0.009error,
2.412
-0.682
with
=0.005
Exercise
1. (a) Use the Newton-Raphson method to estimate the root of the
following equation to 6 d.p. using the starting value given:
x3 2x2 2 0 ;
(b) What happens if you use x 0 0 ?
x0 1
(c) Use your calculator or a graph plotter to sketch the graph of
.
3
2
y x 2x 2
(d) What is special about the graph at x 0 0 and why does it
explain the answer to (b) ?
2. Use the Newton-Raphson method to estimate one root of
3 cos x 1 x
to 4 d.p. using
x0 2
(a)
x3 2x2 2 0 ;
Solution: Let
x n 1 x n
x0 1 ,
x0 1
f ( x) x 3 2 x 2 2
f / ( x) 3 x 2 4 x
f ( xn )
f / ( xn )
3
2
( x n 2 x n 2)
x n 1 x n
2
(3 x n 4 x n )
(ANS3 2ANS 2 2)
ANS
( 3ANS 2 4ANS)
x1 0 857143 , x 2 0 839545 , . . .
x 0 839287 ( 6 d.p. )
x n 1 x n
(b) What happens if you use
( x n 2 x n 2)
2
(3 x n 4 x n )
?
x0 0
The iteration fails immediately.
(c)
y x 2x 2
x = 0, there is a
stationary point.
At
At a stationary point
/
f ( x) 0
so in the formula
we are dividing by
We also notice that the tangent never meets the
0.
x-axis.
2. Use the Newton-Raphson method to estimate one root of
Solution:
Let
3 cos x 1 x
to 4 d.p. using x 0 2
f ( x ) 3 cos x 1 x
f / ( x ) 3 sin x 1
( 3 cos x n 1 x n )
x n 1 x n /
x n 1 x n
( 3 sin x n 1)
f ( xn )
( 3 cos ANS 1 ANS )
x n1 ANS
( 3 sin ANS 1)
Radians!
x 0 2,
f ( xn )
x1 1 8562, x 2 1 8624
x 1 8624 ( 4 d.p. )
Secants Method
nt
ca
Se e
lin
Finally,
Now,
adding and subtracting to the numerator
and rearranging the terms we get:
Secant formula, general
Example 2.5
Consider
finding the root of
By using Secant method. Start with and .
1
1
2
2
3
3
0.0000
0.0000
0.5000
0.5000
0.4902
0.4902
0.5000
0.5000
0.4902
0.4902
0.4906
0.4906
-1.0210
-1.0210
-0.2810
-0.2810
-0.2861
-0.2861
0.0204
0.0204
0.0101
0.0101
0.0105
0.0105
0.4902
0.4902
0.4906
0.4906
0.4906
0.4906
0.4906 with error, =0.0007
1.0000
1.0000
0.0199
0.0199
0.0007
0.0007
Example
50
40
find the roots of
f ( x) x x 3
initial points
x0 1 and x1 1.1
5
30
20
10
0
-10
with three iterations
-20
-30
-40
-2
Fin500J Topic 3
-1.5
-1
-0.5
Fall 2010 Olin Business School
0.5
48
1.5
Evaluation of Secant Method
Pros
To need to evaluate the
derivatives. This can be a
big deal in other languages
since many derivatives can
only be estimated.
by Lale Yurttas, Texas
A&M University
Chapter 5
Cons
Previous two iterates are
required to get the new
one.
The number of
iterations required
can not be
determined before
the algorithm begins.
Convergence rate is slow.
51
Fixed Point Method
Any function
..(1)
can be manipulated such that x is on the lefthand side of the equation as shown below:
.. (2)
Therefore, a root of (2) is also a root of (1).
The root of (2) is given the point of
intersection of the curve . This intersection
point is known as the fixed point of .
Fin500J Topic 3
Fall 2010 Olin Business School
52
If is the initial guess of a root, then the next
approximation is given by
In general is given by:
Difficulties: Arranging function in a proper way
Example
Find
the root of the equation
Using the fixed point iteration with and .
Solution:
Equation can be rearranged as
Where
Thus,
the iterative process can be
expressed as .
At the starting point, , the value of can
be found as .
Since , set and find
Again, , and hence proceed to the next
iteration with .
The results of the iterative process are as
follows:
Is
1
0.100000
0.606535
NO
0.606525
0.472035
NO
0.472035
0.481914
NO
0.481914
0.480744
NO
0.480744
0.480878
NO
0.480878
0.480863
NO
0.480863
0.480864
YES
The specified convergence criterion is
satisfied at the end of iteration, as such, the
root of the equation is taken as .
Summary
Bisection
Reliable, Slow
One function evaluation per iteration
Needs an interval [a,b] containing the root, f(a) f(b)<0
No knowledge of derivative is needed
Newton
Fast (if near the root) but may diverge
Two function evaluation per iteration
Needs derivative and an initial guess x0, f (x0) is
nonzero
Secant
Fast (slower than Newton) but may diverge
one function evaluation per iteration
Needs two initial guess points x0, x1 such that
f (x0)- f (x1) is nonzero.
No knowledge of derivative is needed
