Roots equations.
Introduction
Once upon a time…
Once upon a time…
1. Approximation through
graphical solution
2. Trial and Error
Example
Example
An overview
Roots equations.
(Graphical approach)
Graphical method
• Plot a function
• Observe where it crosses the x axis → Zoom in..
Example
Concern 1: Not precise (The approximate of approximate)
Example (2)
Concern 2: Only 2 out of 6
→
Zoom
in
However..
• Graphical method gives overview
of properties of the functions →
anticipating the pitfalls of the
numerical methods Exception
• (a) and (c) → No roots or even
number of roots
• (b) and (d) → odd number of roots
• For exceptional cases
a) Multiple root when functions are
tangential to the x-axis
Special strategies are
b) Discontinuous function required for
determining the
roots for these cases.
Roots equations.
(Bracketing methods: Bisection and False-Position, FP)
Bracketing method (General)
• Exploit the fact that a function typically changes sign in the vicinity of
a root
• If f(x) is real and continuous in a given interval of (xu and xl), if f(xu).f(xl)<0, then
there is at least 1 root between them. .
• Bracketing → because two initial guesses for the root are required.
• Guesses must “bracket,” or be on either side of, the root.
• Iterative process of finding root within brackets.
• The particular bracketing methods to be covered are:
1. Bisection method
2. False-position method
Bisection
method
+
+ xu
xr
xl -
-
*Alternatively
called binary
chopping, interval
halving or Bolzano’s
method.
In dividing xu and xl into halves, this
method doesn’t take into
consideration f(xu) and f(xl)
magnitudes.
False-position method
• Improved estimate of root with
intersection of line
• False position → Because we replace curve with
the straight line
• It is also called “Linear interpolation
method”
False position method
+
+ xu
+
xr
xl -
?
Always converge!
But it is slow!
Determining initial guesses
• Besides checking an individual answer, you must determine whether
all possible roots have been located.
• Solution: Incorporation of an incremental search at the beginning of
the computer program.
• Start at one end of the region of interest and then making function
evaluations at small increments across the region.
• When the function changes sign, it is assumed that a root falls within the
increment.
• The x values at the beginning and the end of the increment can then serve as
the initial guesses for one of the bracketing techniques
Incremental search
Size of increment
length matters!
Root equtions
(Open methods: Fixed-point, Newton-Raphson and Secant methods)
Open methods
• Based on formulas that require only a single starting value of x
or two starting values that do not necessarily bracket the root
→Potential divergence
• But in convergence cases, this method is faster.
• The particular open methods to be covered are:
1. Newton-Raphson method
2. Secant method
3. Modified Newton-Raphson
The
Newton-Raphson
method
f(x0)
f(x3)~f(xr)
x3 x1
x0 x2
f(x1)
The
Newton-Raphson
method
Example
Example
Slow
convergence
case
(pg. 154)
Also, non-
convergence cases
(pg. 155)
Notes
• No general convergence criterion for Newton-Raphson.
• Its convergence depends on the nature of the function and on the
accuracy of the initial guess.
• The only remedy is to have an initial guess that is “sufficiently” close to
the root.
• However, for some functions, no guess will work!
• Good guesses are usually predicated on knowledge of the physical
problem setting or on devices such as graphs that provide insight into
the behavior of the solution
‘Manual’ Improvement to the program
1. A plotting routine should be included in the program.
2. At the end of the computation, the final root estimate should always be
substituted into the original function to compute whether the result is close to
zero. This check partially guards against those cases where slow or oscillating
convergence may lead to a small value of 𝜀𝑎 while the solution is still far from a
root.
3. The program should always include an upper limit on the number of iterations to
guard against oscillating, slowly convergent, or divergent solutions that could
persist interminably.
4. The program should alert the user and take account of the possibility that f ‘(x)
might equal zero at any time during the computation.
Secant
method
f(x3)~f(xr)
xr x2
x0 x1 x3
Summary
False position method Secant method
Similar but different. What is the difference?
How to choose your
method?
Comparison of the true percent
relative errors Ɛ𝑡 for the methods
to determine the roots of f(x)= 𝑒 −𝑥 − 𝑥.
Open methods
(Multiple root problems: Modified Newton-Raphson Method)
Example:
Multiple roots problem
• Difficulties for numerical method:
1. If function does not change sign → We cannot use
bracketing methods.
Thus, of the methods covered, we are limited to the open methods that
may diverge.
2. That not only f(x) but also f’(x) goes to zero at the root. →
Problems for Newton-Raphson and Secant methods, which
both contain the derivative (or its estimate) in the
denominator in their formulas.
3. Slow convergence
Page 167
Modified Newton-Raphson Method
[Link]
Summary
Understanding this class in 1 minute