UNIT-2
ROOT FINDING METHODS
Root finding methods
Bisection Method
Newton-Raphson Method
Secant Method
Roots of polynomial Equations
[Link] 1
Bisection Method
2
Basis of Bisection Method
Theorem An equation f(x)=0, where f(x) is a real continuous function,
has at least one root between xl and xu if f(xl) f(xu) < 0.
f(x)
x
x
xu
Figure 1 At least one root exists between the two points if the function is
real, continuous, and changes sign.
3 [Link]
Basis of Bisection Method
Figure 2 If function f x does not change sign between two
points, roots of the equation f x 0 may still exist between the two
points.
4 [Link]
Basis of Bisection Method
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 0the two
between
points.
5 [Link]
Basis of Bisection Method
Figure 4 If the function f x changes sign between two points,
more than one root for the equation f x 0 may exist between the two
points.
6 [Link]
Algorithm for Bisection Method
7 [Link]
Algorithm for Bisection Method
8 [Link]
Example 1
Thermistors are temperature-measuring devices based on the
principle that the thermistor material exhibits a change in electrical
resistance with a change in temperature. By measuring the resistance
of the thermistor material, one can then determine the temperature. For a
10K3A Betatherm thermistor, the relationship between the resistance R
of the thermistor and the temperature is given by
Figure. A typical
thermistor
where T is in Kelvin and R is in ohms.
A thermistor error of no more than ± 0.01°C is acceptable. To find the range of
the resistance that is within this acceptable limit at 19 °C , we need to solve
9 [Link]
Example 1 Cont.
Use the bisection method of finding roots of equations to find the
resistance R at 18.99C . Conduct three iterations to estimate the root of
the above equation. Find the absolute relative approximate error at the
end of each iteration and the number of significant digits at least correct
at the end of each iteration.
10 [Link]
Solution
11 [Link]
12
13 [Link]
14
Seven more iterations were conducted and these iterations are shown
in the Table 1
15
Hence the number of significant digits at least
correct is given by the largest value of m for which
So ,the number of significant digits at least correct in the
estimated root 13077 is 3.
16
Advantages
Always convergent
The root bracket gets halved with each
iteration - guaranteed.
17 [Link]
Drawbacks
Slow convergence
If one of the initial guesses is close to
the root, the convergence is slower
18 [Link]
Drawbacks (continued)
f(x)
f x x2
x
19 [Link]
Drawbacks (continued)
f(x)
1
f x
x
x
20 [Link]
Newton-Raphson Method
•Bisection method of finding roots of a nonlinear equation f (x) = 0
require bracketing of the root by two guesses.
•These methods are always convergent since they are based on reducing the
interval between the two guesses.
•In the Newton-Raphson method, the root is not bracketed. In fact, only one initial
guess of the root is needed to get the iterative process started to find the root of an
equation.
•Convergence in open methods is not guaranteed but if the method does converge,
it does so much faster than the bisection methods.
•The Newton-Raphson method is based on the principle that if the initial guess of
the root of
f (x) = 0 is at xi , then if one draws the tangent to the curve at f (xi ) , the point xi+1
Where the tangent crosses the x -axis is an improved estimate of the root (Figure 1).
Newton-Raphson Method
f(xi )
xi 1 = xi -
f (xi )
Figure 1 Geometrical illustration of the Newton-Raphson method.
22 [Link]
Derivation
f(x)
AB
f(xi) B tan(
AC
f ( xi )
f ' ( xi )
xi xi 1
C A X f ( xi )
xi+1 xi xi 1 xi
f ( xi )
Figure 2 Derivation of the Newton-Raphson method.
23 [Link]
Algorithm for Newton-Raphson Method
24 [Link]
25 [Link]
26 [Link]
27 [Link]
28 [Link]
.65519
29 [Link]
30 [Link]
Advantages
Converges fast (quadratic convergence), if
it converges.
Requires only one guess
31 [Link]
Drawbacks
1. Divergence at inflection points
Selection of the initial guess or an iteration value of the root that is
close to the inflection point of the function may start
diverging away from the root in their Newton-Raphson method.
f x x 1 0.512 . 0
3
For example, to find the root of the equation
The Newton-Raphson method reduces to xi 1 xi
x
3
i 3
1 0..512
3 xi 1
2
Table 1 shows the iterated values of the root of the equation.
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.
32 [Link]
Drawbacks – Inflection Points
Table 1 Divergence near inflection point.
Iteration xi
Number
0 5.0000
1 3.6560
2 2.7465
3 2.1084
4 1.6000
5 0.92589
6 −30.119
7 −19.746 Figure 8 Divergence at inflection point for
f x x 1 0.512 0
3
18 0.2000
33 [Link]
Drawbacks – Division by Zero
2. Division by zero
For the equation
f x x 3 0.03x 2 2.4 10 6 0
the Newton-Raphson method
reduces to
xi3 0.03 xi2 2.4 10 6
xi 1 xi
3xi2 0.06 xi
For x0 0 or x0 0.02 , the Figure 9 Pitfall of division by zero
denominator will equal zero. or near a zero number
34 [Link]
35 [Link]
Secant Method
Derivation
Newton’s Method
f(xi )
xi 1 = xi - (1)
f (xi )
Approximate the derivative
f ( xi ) f ( xi 1 )
f ( xi ) (2)
xi xi 1
Substituting Equation (2)
into Equation (1) gives the
Secant method
f ( xi )( xi xi 1 )
Figure 1 Geometrical illustration of
xi 1 xi
f ( xi ) f ( xi 1 )
the Newton-Raphson method.
36
Secant Method – Derivation
The secant method can also be derived from geometry:
The Geometric Similar Triangles
AB DC
AE DE
can be written as
f ( xi ) f ( xi 1 )
xi xi 1 xi 1 xi 1
On rearranging, the secant
method is given as
f ( xi )( xi xi 1 )
Figure 2 Geometrical representation of xi 1 xi
the Secant method. f ( xi ) f ( xi 1 )
37 [Link]
Step 1
Calculate the next estimate of the root from two initial guesses
f ( xi )( xi xi 1 )
xi 1 xi
f ( xi ) f ( xi 1 )
Find the absolute relative approximate error
xi 1- xi
a = 100
xi 1
38 [Link]
Step 2
Find if the absolute relative approximate error is greater
than the pre-specified relative error tolerance.
If so, go back to step 1, else stop the algorithm.
Also check if the number of iterations has exceeded the
maximum number of iterations.
39 [Link]
40
41 [Link]
42
43 [Link]
44 [Link]
FIXED POINT ITERATION METHOD
A formula can be developed for fixed point iteration by
rearranging the function f (x) = 0
So that x is on the left-hand side of the equation:
----1
For example,
Can be simply manipulated to yield
Whereas sinx=0 could be put in to the form of equation(1) by
adding x to both sides to yield
45 [Link]
The utility of eqn(1) is that it provides a formula to predict a new
value of x as a function of an old value of x .
Thus, given an initial guess at the root xi, eqn(1) can be used to
compute a new estimate xi+1 as expressed by the iterative formula
The sequence has the pattern
The approximate error can be determined using the error estimator
46 [Link]
47 [Link]
So, from the discussions,
There are two methods of finding roots of a nonlinear equation
f(x)=0, these are The bracketing methods and the open methods.
Bracketing methods
Bisection Method
Open methods
Fixed point Iteration
Newton-Raphson Method
Secant Method
48 [Link]
Roots of polynomial Equations
A polynomial of degree n has the form
Where the coefficients ai are real.
The polynomial equation has exactly n roots, which
may be real or complex.
For real coefficients, the number of real roots can be estimated
from the rule of Descartes:
49
Deflation of Polynomials
After a root r of has been computed, it is desirable to
factor the polynomial as follows:
This procedure, known as deflation or synthetic division, involves nothing
more than computing the coefficients of .
Since the remaining zeros of are also the zeros of , the root
finding procedure can now be applied to rather than .
50
51 [Link]
Laguerre’s Method
If the polynomial has a zero at x = r and (n− 1) zeros at x = q. If the
zeros were known, this polynomial can be written as
52 [Link]
53 [Link]
54 [Link]
55 [Link]
56 [Link]
57 [Link]
