1/18/2015
AML702 Applied Computational Methods
I
I
T
Dc
Lecture 04
E Finding Roots of equations
L Bracketing Methods
H
I
Bracketing Methods
• Root finding methods can be classified into
I (a) Bracketing methods and (b) Open methods
I • Estimating the errors in computation roots of
T equations
Dc • The methods we are going to study are:
E • Graphical method
L • Bisection Method
H • False position method
I • Compare these methods and their error
estimation schemes
2
1
1/18/2015
Non-linear Equation solving
I Nonlinear Equation
I Solvers
T
D Bracketing Graphical Open Methods
E
L Bisection Newton Raphson
H False Position
(Regula-Falsi) Secant
I
All Iterative
3
Graphical Method
The real number x=x0 is a root of the polynomial
I f(x) if and only if f(x)=0
I
T
D
E
L
H
At least one root exists between two bounds xu
I
(upper) and xl (lower) if the function is real,
continuous, and changes sign.
2
1/18/2015
Graphical Method - Roots
•Graphical methods not very
precise.
I •Serve as rough estimates of
I roots.
T •Helpful to understanding the
behavior of the functions
D
•Upper and lower bounds f(u)
E and f(l)
L
•(a) no sign change – no roots
H
•(b) sign change – 1 root
I
•(c) no sign change – 2 roots
•(d) sign change – 3 roots
5
Graphical Method - Exceptions
•There are some
exceptions to the general
I observations made
I previously.
T
•(a) The curve is tangential
D to x-axis
E
L •(b) Discontinuous
H functions violate the
I general principles
applicable otherwise
6
3
1/18/2015
Incremental Search
This method is based on the observation that when a real
continuous function f(x) changes sign there exists a root between
I them, i.e f ( x l ) f ( x u )<0
I
T Problem: The choice of the increment length. If the length is too
small, the search can be very time consuming. On the other
hand, if the length is too great, there is a possibility that closely
D spaced roots might be missed
E
L
H
I
Bisection Method
I
I
T
D
E
L
H
I
4
1/18/2015
Bisection Method
The Algorithm:
1. For the arbitrary equation of one variable, f(x)=0
I
2. Pick xl and xu such that they bound the root of interest, check
I if f(xl).f(xu) <0.
T
D 3. Estimate the root by evaluating f[(xl+xu)/2].
E
L 4. Find the pair If f(xl). f[(xl+xu)/2]<0, root lies in the lower
interval, then xu=(xl+xu)/2 and go to step 2.
H
I
Bisection Method (contd.)
5. If f(xl). f[(xl+xu)/2]>0, root lies
in the upper interval, then xl=
I [(xl+xu)/2, go to step 2.
I x l +x u
T xl−
6. If f(xl). f[(xl+xu)/2]=0, then root 2
100
x l + xu
D is (xl+xu)/2 and terminate.
2
E or
L Compare εs with εa xl+ xu
x u−
H 2
100
If εa< εs, stop. Otherwise repeat x l + xu
I
the process. 2
5
1/18/2015
Graphical Veiew of Bisection
I
I
T
D
E
L
H
I
Error Estimation
• To estimate the relative error, we can base it on
I the true value of root. If our guess is in doubt
I the error estimate may not be appropriate.
T • Therefore, we require an error estimate that is
not contingent on prior knowledge of the root.
D One way to do this is by estimating an
E approximate percent relative error as in
L
H
I
6
1/18/2015
Example Error Estimation
• A typical error computation is shown in the
table below. Here xr are the roots, εr and εt
I are approximate relative error and true
I relative error based on true value.
T
D
E
L
H
I
Approximate Error vs True Error
I
I
T
D
E
L
H
I
7
1/18/2015
Estimation of Iteration
Length of the first Interval Lo=b-a
I After 1 iteration L1=Lo/2
I After 2 iterations L2=Lo/4
T After k iterations Lk=Lo/2k
D • When εa becomes less than a prespecified stopping
E criterion εs , the computation is terminated.
Lk
L εa ≤ ×100% εa ≤ εs
H x
I If the absolute magnitude of the error is E and Lo=2, how many
iterations will you have to do to get the required accuracy in the
solution?
2
E= 10 − 4 = ⇒ 2 k = 2 × 10 4 ⇒ k ≅ 14.3 = 15
2k
False Position Method
(Regula-Falsi)
• If a real root is
bounded by xl and
I xu of f(x)=0, then
I approximate
T solution is a linear
interpolation
D between the points
[xl, f(xl)] and [xu,
E f(xu)] to find the xr
L value such that
H l(xr)=0, l(x) is the
I linear
approximation of
f(x).
• The method is also
known as Regula- 16
Falsi
8
1/18/2015
False Position Method
• To determine xr
I • Consider the slope of the chord
of f(x)=0
I f ( xu ) − f ( xl ) f ( xu ) − f ( xr ) f ( xl ) − 0
= =
T xu − xl xu − xr xu − xr
D f ( xu )( xu − xl )
E xu − xr =
f ( xu ) − f ( xl )
L
H
I
f ( xu )( xl − xu ) xl f ( xu ) − xu f ( xl )
xr = xu − =
f ( xl ) − f ( xu ) f ( xl ) − f ( xu )
17
The Regula-falsi Algorithm
1. Find a pair of values of x, xl and xu such that fl=f(xl) <0 and
fu=f(xu) >0.
I
2. Estimate the value of the root from the following formula
I and evaluate f(xr).
T
xl f u − xu f l
xr =
D 3. ⇒ fu − fl
E
L Use the new point to replace one of the original points,
H keeping the two points on opposite sides of the x axis.
I If f(xr)<0 then xl=xr == > fl=f(xr)
If f(xr)>0 then xu=xr == > fu=f(xr)
If f(xr)=0 then you have found the root and need go no
further!
9
1/18/2015
Regula-falsi Algorithm (contd.)
4. See if the new xl and xu are close enough for
I convergence to be declared. If they are not go back
I to step 2.
T
Why this method?
D
Faster (than bisection)
E
Always converges for a single root.
L
H
I Note: Always check by substituting estimated root in the
original equation to determine whether f(xr) ≈ 0.
Bisection and False Position
Consider the solution of between 0 and 1.3
first by bisection and then by false position
I
I
T
D
E
L
H
I
10
1/18/2015
Modified False Position – Illinois Method
• The improved false position
method is obtained by
I modifying the root finding
I expression as given below
T • This is known as Illinois
method. Here we multiply by
D ½ the first term in the
E numerator and in the
denominator.
L 1
xl f ( xu ) − xu f ( xl )
H xr = 2
2 f ( xu ) − f ( xl )
1
I
xl f ( xu ) − 12 xu f ( xl )
• Or xr =
f ( xu ) − 12 f ( xl ) 21
11
