APM3715: Numerical Methods for Civil Engineers
Numerical Methods for Solving Non-linear Equations
J Sibanda
Reference: Numerical Methods for Engineers, Chapra and Canale, chapter 5, 6
1
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
Bracketing methods
2
Solution Methods:
Analytical Solutions
Analytical solutions are available for special equations only.
Analytical solution of a x + b x + c = 0
2
− b b 2 − 4ac
roots =
2a
−x
No analytical solution is available for x −e =0
3
Graphical Illustration
Graphical illustration are useful to provide an initial
guess to be used by other methods
−x
Solve e
2 Root
−x
x=e x
The root [0,1] 1
root 0.6
1 2
4
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.
5
Solution Methods
Many methods are available to solve nonlinear equations
❑ Bisection Method
❑ Newton’s Method
❑ Secant Method These will be
False position Method covered.
Muller’s Method
Bairstow’s Method
Fixed point iterations
……….
6
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.
7
Intermediate Value Theorem
Let f(x) be defined on the interval
[a,b],
f(a)
Intermediate value theorem:
if a function is continuous and f(a)
and f(b) have different signs then a b
the function has at least one zero
in the interval [a,b] f(b)
8
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
c b
2. Evaluate f(c ) a
3. If f(a) f(c) < 0 then new interval [a, c]
If f(a) f( c) > 0 then new interval [c, b] f(b)
End loop
9
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.
10
Bisection Method
b0
a0 a1 a2
11
Flow chart of Bisection Method
Start: Given a,b and ε
u = f(a) ; v = f(b)
c = (a+b) /2 ; w = f(c) no
yes
is no is
Stop
yes (b-a)/2 <ε
u w <0
b=c; v= w a=c; u= w
12
Example:
Can you use Bisection method to find a zero of
f ( x) = x 3 − 3x + 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
13
Stopping Criteria
Two common stopping criteria
1. Stop after a fixed number of iterations
2. Stop when
b−a
r - cn n +1
2
cn is the midpoint of the interval at the n th iteration
( cn is usually used as the estimate of the root).
r is the zero of the function
14
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 ?
15
16
Bisection Method
Initial Interval
f(a)=-0.3776 f(b) =0.2784
a =0.5 c= 0.7 b= 0.9
17
-0.3776 -0.0648 0.2784
(0.9-0.7)/2 = 0.1
0.5 0.7 0.9
-0.0648 0.1033 0.2784
(0.8-0.7)/2 = 0.05
0.7 0.8 0.9
18
-0.0648 0.0183 0.1033
(0.75-0.7)/2=
0.7 0.75 0.8 0.025
-0.0648 -0.0235 0.0183
(0.75-0.725)/2=
0.70 0.725 0.75 .0125
19
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
20
Bisection Method Programming in
Matlab
c=
a=.5; b=.9; 0.7000
u=a-cos(a); fc =
v= b-cos(b); -0.0648
for i=1:5 c=
c=(a+b)/2 0.8000
fc=c-cos(c) fc =
if u*fc<0 0.1033
b=c ; v=fc; c=
else 0.7500
a=c; u=fc; fc =
end 0.0183
end c=
0.7250
fc =
-0.0235
21
Newton-Raphson Method
(also known as Newton’s Method)
Given an initial guess of the root x0 , 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
22
Newton’s Method
Suppose we have current
approximat ion x i , we
want to find a better
approximat ion x i +1
f ( xi ) − 0
f ( xi ) =
'
xi − xi +1
f ( xi )
xi +1 = xi −
Xi+1 Xi f ' ( xi )
23
Example
Use Newton' s Method to find a root of
f ( x ) = e − x − x, f ' ( x) = −e − x − 1. Use the initial points x0 = 1
Stop after three iterations
FN.m function [ FN ] = FN ( X )
FN = exp(− X ) − X
Given f ( x), f ' ( x), x0
FNP.m function [ FNP ] = FNP ( X )
Assumpution f ' ( x0 ) 0 FNP = − exp(− X ) − 1
__________ __________ __
% MATLAB PROGRAM
for i = 0 : n
X =1
f ( xi ) for i = 1 : 3
xi +1 = xi −
f ' ( xi ) X = X − FN ( X ) / FNP ( X )
end FN ( X )
end
24
Results
X = 0.5379
FNX =0.0461
X =0.5670
FNX =2.4495e-004
X = 0.5671
FNX =6.9278e-009
25
Secant Method
if xi and xi −1 are two initial points
f ( xi ) − f ( xi −1 )
f ' ( xi ) =
( xi − xi −1 )
f ( xi ) ( xi − xi −1 )
xi +1 = xi − = xi − f ( xi )
f ( xi ) − f ( xi −1 ) f ( xi ) − f ( xi −1 )
( xi − xi −1 )
26
Secant Method
Assumption s :
Two initial points xi and xi −1
such that f ( xi ) f ( xi −1 )
New estimate (Secant Method) :
( xi − xi −1 )
xi +1 = xi − f ( xi )
f ( xi ) − f ( xi −1 )
27
Example
50
40
find the roots of
30
f ( x) = x + x + 3
5 3
20
initial points
10
x0 = −1 and x1 = −1.1 0
-10
with three iterations -20
-30
-40
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
28
Example
f ( x) = x 5 + x 3 + 3 function [ FSe ] = FSe ( X )
x0 = −1, x1 = −1.1 FSe = X ^5 + X ^3 + 3
( xi − xi −1 )
xi +1 = xi − f ( xi )
f ( xi ) − f ( xi −1 )
% MATLAB PROGRAM
X = zeros(5,1);
X(1) = -1; X(2) = -1.1;
for i = 3 : 5;
X(i) = X(i - 1) - FSe(X(i - 1)) * (X(i - 1) - X(i - 2))/(FSe(X(i - 1)) - FSe(X(i - 2)));
end
for i = 1 : 5
Xi = X(i)
FXi = FSe(X(i))
end
29
Results
Xi = -1
FXi =1
Xi =-1.1000
FXi =0.0585
Xi =-1.1062
FXi =-0.0102
Xi =-1.1053
FXi =8.1695e-005
Xi = -1.1053
FXi =1.1276e-007
30
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
31
Solving Non-linear Equation using Matlab
• Example (i): find a root of f(x)=x-cos x, in [0,1]
>> f=@(x) x-cos(x);
>> fzero(f,[0,1])
ans =
0.7391
• Example (ii): find a root of f(x)=e-x-x using the initial
point x=1
>> f=@(x) exp(-x)-x;
>> fzero(f,1)
ans =
0.5671
32
Solving Non-linear Equation using R, Matlab
etc.
• Example (iii): find a root of f(x)=x5+x3+3 around -1
>> f=@(x) x^5+x^3+3;
>> fzero(f,-1)
ans =
-1.1053
• Because this function is a polynomial, we can find other roots
>> roots([1 0 1 0 0 3])
ans =
0.8719 + 0.8063i
0.8719 - 0.8063i
-0.3192 + 1.3501i
-0.3192 - 1.3501i
-1.1053
33
Use fzero Solver in Matlab
• >>optimtool
• For example:
want to find a
root around -1
for x5+x3+3=0
• The algorithm
of fzero uses a
combination
of bisection,
secant, etc.
34
Package you can use in R
Package: `rootSolve` to install use this command:
install.packages("rootSolve") and
library(rootSolve)
Bisection Method
The rootSolve package provides a function called uniroot which can be used
for the Bisection Method.
Newton's Method
In the same package, you also find a function called Newton which can be
used for Newton's Method.
Secant Method
Lastly, the rootSolve package provides a function called secant which can be
used for the Secant Method.
NOTE: For more help regarding the functions, install the package, write the
name of the function and click anywhere you’ve typed and press the F1 key
on your keyboard OR type the name of the function followed by a question
mark and press enter. This is very helpful!
35
