Solution of None Linear
Equations
Digitally signed by Dr Abdul Khaliq
DN: cn=Dr Abdul Khaliq, o, ou,
email=abdulkhaliquaf@gmail.com, c=US
Date: 2014.11.03 01:12:27 +05'00'
Engineering Numerical Analysis
Roots of Equations
Why?
ax 2 bx c 0
b b 2 4ac
x
2a
But
ax 5 bx
b 4 cx 3 dx
d 2 ex f 0 x ?
sin x x 0 x ?
Engineering Numerical Analysis
Nonlinear Equation
Solvers
Bracketing
Graphical
Open Methods
Newton Raphson
Bisection
False Position
Secant
All Iterative
Engineering Numerical Analysis
Bisection Method
Engineering Numerical Analysis
Basis of Bisection Method
Theorem
An equation f(x)=0, where f(x) is a real continuous function, has at
l t one roott b
least
between
t
xl and
d xu if f(
f(xl) f(x
f( u) < 0.
0
f(x)
xl
xu
Figure 1 At least one root exists between the two points if the function is
real, continuous, and changes sign.
Engineering Numerical Analysis
Basis of Bisection Method
f(x )
Figure2
x
u
Iffunction f(x)doesnotchangesignbetweentwopoints,rootsofthe
equationf(x)=0 maystillexistbetweenthetwopoints.
Engineering Numerical Analysis
Basis of Bisection Method
f(x)
f(x)
xu
x xu
Figure 3 If the function f(x) does not change sign between
two points, there may not be any roots for the
equation f(x)
f(x)=00 between the two points.
Engineering Numerical Analysis
Basis of Bisection Method
f( x )
xu
Fig re 4 If the function
Figure
f nction f(x)
f( ) changes sign bet
between
een ttwo
o points
points, mo
more
e than one
root for the equation f(x)=0 may exist between the two points.
Engineering Numerical Analysis
Algorithm for Bisection Method
Engineering Numerical Analysis
Step 1
Ch
l andx
d u astwoguessesfortherootsuchthatf(x
t
f th
t
hth tf( l)
Choosex
f(xu)<0,orinotherwords,f(x) changessignbetweenxl and
xu.ThiswasdemonstratedinFigure1.
f(x)
x
xu
Figure1
Engineering Numerical Analysis
10
Step
p2
Estimatetheroot,xm oftheequationf(x)=0 asthemid
pointbetweenxl andxu as
f(x)
xl xu
xm
2
x
xm
xu
Figure5Estimateofxm
Engineering Numerical Analysis
11
Step 3
Nowcheckthefollowing
Iff(xl)f(xm)<0,thentherootliesbetweenxl andxm;
thenxl =xl ;xu =xm.
Iff(xl)f(xm)>0thentherootliesbetweenxm andxu;then
xl =xm;xu =xu.
If f(xl)f(xm)=0;thentherootisxm. Stopthealgorithmif
thisistrue.
thisistrue
Engineering Numerical Analysis
12
Step 4
Find the new estimate of the root
xl xu
xm
2
Find the absolute relative approximate error
old
x new
x
m
m
new
m
100
where
xmold previous estimate of root
xmnew current estimate of root
Engineering Numerical Analysis
13
Step 5
Compare the absolute relative approximate error |a| with
the pre-specified error tolerance s .
Yes
Go to Step 2 using new
upper and lower
guesses.
No
Stop the algorithm
Is a s ?
Note one should also check whether the number of iterations is
more than the maximum number of iterations allowed. If so, one
needs to terminate the algorithm and notify the user about it.
Engineering Numerical Analysis
14
Example1
YouareworkingforDOWNTHETOILETCOMPANYthat
makesfloatsforABCcommodes.Thefloatingballhasa
spec c g a ty o 0.6 a d as a ad us o 5.5 c . ou a e
specificgravityof0.6andhasaradiusof5.5cm.Youare
askedtofindthedepthtowhichtheballissubmerged
whenfloatinginwater.
Figure 6 Diagram of the floating ball
Engineering Numerical Analysis
15
Example1Cont.
Theequationthatgivesthedepthx towhichtheballis
submergedunderwaterisgivenby
x 3 0.165 x 2 3.993 10 4 0
a)Usethebisectionmethodoffindingrootsofequationsto
findthedepthx towhichtheballissubmergedunder
water.Conductthreeiterationstoestimatetherootofthe
aboveequation.
b)Findtheabsoluterelativeapproximateerrorattheendof
eachiteration,andthenumberofsignificantdigitsatleast
correctattheendofeachiteration.
Engineering Numerical Analysis
16
Example1Cont.
Fromthephysicsoftheproblem,theballwouldbe
submergedbetweenx =0andx =2R,
whereR
h R =radiusoftheball,
di f h b ll
thatis
0 x 2R
0 x 20.055
0 x 0.11
Figure 6 Diagram of the floating ball
Engineering Numerical Analysis
17
Example 1 Cont
Example1Cont.
Solution
To aid in the understanding
of how this method works to
find the root of an equation,
the graph of f(x) is shown to
the right,
where
f x x 3 0.165 x 2 3.993 10- 4
Figure 7 Graph of the function f(x)
Engineering Numerical Analysis
18
Example1Cont.
a p e Co t
Let us assume
x 0.00
xu 0.11
Check if the function changes sign between x and xu .
f xl f 0 0 0.1650 3.993 10 4 3.993 10 4
3
f xu f 0.11 0.11 0.1650.11 3.993 10 4 2.662 10 4
3
Hence
f xl f xu f 0 f 0.11 3.993 10 4 2.662 10 4 0
So there is at least on root between x and xu, that is between 0 and 0.11
Engineering Numerical Analysis
19
Example1Cont.
Figure 8 Graph demonstrating sign change between initial limits
Engineering Numerical Analysis
20
Example1Cont.
Iteration 1
The estimate of the root is
x xu 0 0.11
0.055
xm
2
2
f xm f 0.055 0.055 0.1650.055 3.993 10 4 6.655 10 5
3
f xl f xm f 0 f 0.055 3.993 10 4 6.655 10 5 0
Hence the root is bracketed between xm and xu, that is, between 0.055
and 0.11. So, the lower and upper limits of the new bracket are
xl 0.055, xu 0.11
At this point, the absolute relative approximate error a cannot be
calculated as we do not have a previous approximation.
approximation
Engineering Numerical Analysis
21
Example1Cont.
Figure 9 Estimate of the root for Iteration 1
Engineering Numerical Analysis
22
Example1Cont.
Iteration 2
The estimate of the root is
x xu 0.055 0.11
0.0825
xm
2
2
f xm f 0.0825 0.0825 0.1650.0825 3.993 10 4 1.622 10 4
3
f xl f xm f 0.055 f (0.0825) 1.622 10 4 6.655 10 5 0
Hence the root is bracketed between xand xm, that is, between 0.055
and 0.0825. So, the lower and upper limits of the new bracket are
xl 0.055, xu 0.0825
Engineering Numerical Analysis
23
Example1Cont.
Figure 10 Estimate of the root for Iteration 2
Engineering Numerical Analysis
24
Example1Cont.
The absolute relative approximate error a at the end of Iteration 2 is
xmnew xmold
a
100
new
xm
0.0825 0.055
100
0.0825
33.333%
None of the significant digits are at least correct in the estimate root of
xm = 0.0825 because the absolute relative approximate error is greater
than 5%.
Engineering Numerical Analysis
25
Example1Cont.
Iteration 3
The estimate of the root is
x xu 0.055 0.0825
0.06875
xm
2
2
f xm f 0.06875 0.06875 0.1650.06875 3.993 10 4 5.563 10 5
3
f xl f xm f 0.055 f 0.06875 6.655 10 5 5.563 10 5 0
Hence the root is bracketed between xand xm, that is, between 0.055
and 0.06875. So, the lower and upper limits of the new bracket are
xl 0.055, xu 0.06875
Engineering Numerical Analysis
26
Example1Cont.
Figure 11 Estimate of the root for Iteration 3
Engineering Numerical Analysis
27
Example1Cont.
The absolute relative approximate error a at the end of Iteration 3 is
xmnew xmold
a
100
new
xm
0.06875 0.0825
100
0.06875
20%
Still none of the significant digits are at least correct in the estimated
root of the equation as the absolute relative approximate error is
greater than 5%.
Seven more iterations were conducted and these iterations are shown in
Table 1.
Engineering Numerical Analysis
28
T bl 1 C t
Table1Cont.
Table
T
bl 1 Root
R t off f(
f(x)=0
) 0 as ffunction
ti off number
b off it
iterations
ti
ffor
bisection method.
Iteration
xu
xm
a %
f(xm)
0.00000
0.11
0.055
----------
6.655105
2
3
0.055
0.055
0.11
0.0825
0.0825
0.06875
33.33
20.00
1.622104
5.563105
4
5
0.055
0.06188
0.06875
0.06875
0.06188
0.06531
11.11
5.263
4.484106
2.593105
0.06188
0.06531
0.06359
2.702
1.0804105
7
8
0.06188
0.06188
0.06359
0.06273
0.06273
0.0623
1.370
0.6897
3.176106
6.497107
9
10
0.0623
0 0623
0.0623
0.06273
0 06252
0.06252
0.06252
0 06241
0.06241
0.3436
0 1721
0.1721
1.265106
3.076810
3 0768 1077
Engineering Numerical Analysis
29
T bl 1 C t
Table1Cont.
Hence the number of significant digits at least correct is given by the
largest value or m for which
a 0.5 10 2m
0.1721 0.5 10 2 m
0.3442 10 2 m
log0.3442 2 m
m 2 log0.3442 2.463
So
m2
The number of significant digits at least correct in the estimated root
of 0.06241 at the end of the 10th iteration is 2.
Engineering Numerical Analysis
30
Advantages
Alwaysconvergent
Therootbracketgetshalvedwitheachiteration
Therootbracketgetshalvedwitheachiteration
guaranteed.
Engineering Numerical Analysis
31
Drawbacks
Slow convergence
If one off th
the iinitial
iti l guesses is
i close
l
to
t
the root, the convergence is slower
Engineering Numerical Analysis
32
Drawbacks(continued)
Ifafunctionf(x)issuchthatitjusttouchesthexaxis
itwillbeunabletofindthelowerandupperguesses.
f(x)
f x x
Engineering Numerical Analysis
33
Drawbacks(continued)
Function changes sign but root does not
exist
f(x)
1
f x
x
x
Engineering Numerical Analysis
34
NewtonRaphson
p
Method
Engineering Numerical Analysis
35
NewtonRaphsonMethod
f(x)
x f x
f(xi)
i,
f(xi )
xi 1 = xi f ((xi )
f(x
( ii-11)
xi+2
xi+1
xi
Figure 1 Geometrical illustration of the Newton-Raphson method.
36
Engineering Numerical Analysis
36
http://numericalmethods.eng.usf.edu
Derivation
f(x)
f(xi)
tan(
AB
AC
f ((xxi )
f ' ( xi )
xi xi 1
C
xi+1
xi
f ( xi )
xi 1 xi
f ( xi )
Figure 2 Derivation of the Newton-Raphson method.
Engineering Numerical Analysis
37
http://numericalmethods.eng.usf.edu
AlgorithmforNewtonRaphson
Method
Engineering Numerical Analysis
38
http://numericalmethods.eng.usf.edu
Step 1
Step1
E l t
Evaluate
39
f (x
( )
symbolically.
b li ll
http://numericalmethods.eng.usf.edu
Step2
Use an initial guess of the root, xi , to estimate the new
value of the root, xi 1 , as
f xi
xi 1 = xi f xi
40
Engineering Numerical Analysis
40
http://numericalmethods.eng.usf.edu
Step3
Find the absolute relative approximate error a as
xi 1- xi
a =
100
xi1
41
Engineering Numerical Analysis
41
http://numericalmethods.eng.usf.edu
Step4
Comparetheabsoluterelativeapproximateerrorwith
theprespecifiedrelativeerrortolerance.
s
Yes
Go to Step 2 using new
estimate of the root.
No
Stop the algorithm
Is a s ?
Also,checkifthenumberofiterationshasexceeded
Also
checkifthenumberofiterationshasexceeded
themaximumnumberofiterationsallowed.Ifso,one
needstoterminatethealgorithmandnotifytheuser.
42
Engineering Numerical Analysis
42
http://numericalmethods.eng.usf.edu
Example1
YouareworkingforDOWNTHETOILETCOMPANYthat
makesfloatsforABCcommodes.Thefloatingballhasa
spec c g a ty o 0.6 a d as a ad us o 5.5 c . ou a e
specificgravityof0.6andhasaradiusof5.5cm.Youare
askedtofindthedepthtowhichtheballissubmerged
whenfloatinginwater.
Figure 3 Floating ball problem.
43
Engineering Numerical Analysis
43
http://numericalmethods.eng.usf.edu
Example1Cont.
Theequationthatgivesthedepthx inmetersto
whichtheballissubmergedunderwaterisgiven
by
f x x 3-0.165 x 2+3.993 10- 4
Figure 3 Floating ball problem.
Use the Newtons method of finding
g roots of equations
q
to find
a) the depth x to which the ball is submerged under water. Conduct three
iterations to estimate the root of the above equation.
b) The absolute relative approximate error at the end of each iteration, and
c)) The
Th number
b off significant
i ifi
t digits
di it att least
l t correctt att the
th end
d off each
h
iteration.
44
Engineering Numerical Analysis
44
http://numericalmethods.eng.usf.edu
Example1Cont.
Solution
To aid in the understanding
of how this method works to
find the root of an equation,
the graph of f(x) is shown to
the right,
where
f x x 3-0.165 x 2+3.993 10 - 4
Figure 4 Graph of the function f(x)
Engineering Numerical Analysis
45
Example1Cont.
Solve for f ' x
f x x 3-0.165 x 2+3.993 10- 4
f ' x 3 x 2 -0.33 x
Let us assume the initial guess of the root of f x 0
is x0 0.05m . This is a reasonable guess (discuss why
x 0 aandd x 0.11m are
a not
o good choices)
o
) as
a the
extreme values of the depth x would be 0 and the
diameter (0.11 m) of the ball.
Engineering Numerical Analysis
46
Example1Cont.
Iteration 1
The estimate of the root is
x1 x 0
f x 0
f ' x 0
0 . 05
0 . 05 3 0 . 165 0 . 05 2 3 .993
2
3 0 . 05 0 . 33 0 . 05
10 4
1 . 118 10 4
0.05
9 10 3
0.05 0 . 01242
0 . 06242
Engineering Numerical Analysis
47
Example1Cont.
Figure 5 Estimate of the root for the first iteration.
Engineering Numerical Analysis
48
Example1Cont.
The absolute relative approximate error a at the end of Iteration 1
is
x1 x 0
100
x1
0 . 06242 0 . 05
100
0 . 06242
19 . 90 %
The number of significant digits at least correct is 0, as you need an
absolute relative approximate error of 5% or less for at least one
significant digits to be correct in your result.
Engineering Numerical Analysis
49
Example1Cont.
Iteration 2
The estimate of the root is
f x1
x 2 x1
f ' x1
0 . 06242
0 . 06242 3 0 . 165 0 . 06242 2 3 .993
993
2
3 0 . 06242 0 . 33 0 . 06242
10 4
3 . 97781 10 7
0 . 06242
8 . 90973 10 3
0 . 06242 4 . 4646 10 5
0 . 06238
Engineering Numerical Analysis
50
Example1Cont.
Figure 6 Estimate of the root for the Iteration 2.
Engineering Numerical Analysis
51
Example1Cont.
The absolute relative approximate error a at the end of Iteration 2
is
x 2 x1
100
x2
0 . 06238 0 . 06242
100
0 . 06238
0 . 0716 %
2m
The maximum value of m for which a 0 . 5 10
is 2.844.
Hence, the number of significant digits at least correct in the
answer is 2.
Engineering Numerical Analysis
52
Example1Cont.
Iteration 3
The estimate of the root is
x3 x2
f x 2
f ' x 2
0 . 06238
0 . 06238 3 0 . 165 0 . 06238 2 3 .993
993
2
3 0 . 06238 0 . 33 0 . 06238
10 4
4 . 44 10 11
0 . 06238
8 . 91171 10 3
0 . 06238 4 . 9822 10 9
0 . 06238
Engineering Numerical Analysis
53
Example1Cont.
Figure 7 Estimate of the root for the Iteration 3.
Engineering Numerical Analysis
54
Example1Cont.
The absolute relative approximate error a at the end of Iteration 3
is
x 2 x1
100
x2
0 . 06238 0 . 06238
100
0 . 06238
0%
The number of significant digits at least correct is 4, as only 4
significant digits are carried through all the calculations.
Engineering Numerical Analysis
55
Advantages
Convergesfast(quadraticconvergence),ifitconverges.
Requiresonlyoneguess
Engineering Numerical Analysis
57
Drawbacks
1.
Divergence at inflection points
Selection of the initial guess or an iteration value of the root that
is close to the inflection p
point of the function f x mayy start
diverging away from the root in ther Newton-Raphson method.
For example, to find the root of the equation f x x 1 0.512 0 .
3
The Newton-Raphson method reduces to xi 1 xi
3
i
1 0.512
.
2
3 xi 1
T bl 1 shows
Table
h
the
th iterated
it t d values
l
off the
th roott off the
th equation.
ti
The root starts to diverge at Iteration 6 because the previous estimate
of 0.92589 is close to the inflection point of x 1 .
Eventually after 12 more iterations the root converges to the exact
value of x 0.2.
Engineering Numerical Analysis
58
Drawbacks InflectionPoints
Table 1 Divergence near inflection point.
Iteration
Number
xi
5.0000
3.6560
2.7465
2.1084
1.6000
0.92589
30.119
19.746
18
0.2000
Fi
Figure
8 Divergence
Di
att iinflection
fl ti point
i t for
f
Engineering Numerical Analysis
f x x 1 0.512 0
3
59
Drawbacks DivisionbyZero
2. Division by zero
For the equation
f x x 3 0.03 x 2 2.4 10 6 0
the Newton-Raphson method
reduces to
xi3 0.03 xi2 2.4 10 6
xi 1 xi
3 xi2 0.06 xi
For x0 0 or x0 0.02 , the
denominator will equal zero.
Engineering Numerical Analysis
Figure 9 Pitfall of division by zero
or near a zero number
60
Drawbacks Oscillationsnearlocal
Oscillations near local
Drawbacks
maximumandminimum
3. Oscillations near local maximum and minimum
Results obtained from the Newton-Raphson method may
oscillate about the local maximum or minimum without
converging
g g on a root but converging
g g on the local maximum or
minimum.
Eventually, it may lead to division by a number close to zero
and may diverge.
diverge
2
For example for f x x 2 0 the equation has no real
roots.
Engineering Numerical Analysis
61
Drawbacks Oscillationsnearlocal
Oscillations near local
Drawbacks
maximumandminimum
Table 3 Oscillations near local maxima
and mimima in Newton-Raphson method.
Iteration
Number
0
1
2
3
4
5
6
7
8
9
xi
1.0000
0.5
1.75
0.30357
3 1423
3.1423
1.2529
0.17166
5.7395
2.6955
0.97678
f xi a %
3.00
2.25
5.063
2.092
11 874
11.874
3.570
2.029
34.942
9.266
2.954
f(x)
3
3
300.00
128.571
476.47
109 66
109.66
150.80
829.88
102.99
112.93
175.96
11
4
0
-2
-1.75
-1
-0.3040
0.5
3.142
-1
Figure 10 Oscillations around local
2
minima for f x x 2 .
Engineering Numerical Analysis
62
Drawbacks RootJumping
4. Root Jumping
In some cases where the function f x is oscillating and has a number
of roots, one may choose an initial guess close to a root. However, the
guesses may jump and converge to some other root.
f(x)
For example
1.5
f x sin
i x0
0.5
Choose
x0 2.4 7.539822
It will converge to
x0
-2
-0.06307
0.5499
4.461
7.539822
10
-0.5
-1
x 2 6.2831853 Figure 11 Root jumping from intended
-1.5
instead of
Engineering Numerical Analysis
location of root for
f x sin
. x0
63
THEEND
Engineering Numerical Analysis
64
