Roots of Equations
ROOTS OF EQUATIONS
Years ago you learned to use the quadratic formula:
−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝑥=
2𝑎
to solve
𝑓(𝑥) = 𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 = 0
The values calculated are called roots of the equation. They represent the values of x that make 𝑓(𝑥) = 0.
For this reason, roots are sometimes called the zeros of the equation. Although the quadratic formula is
handy for solving quadratic equation, there are many other functions for which roots cannot be determined
so easily. For these cases, the numerical methods described in this chapter provide efficient means to obtain
the answer.
Graphical Method:
Graphical techniques are useful for visualizing the properties of the function and the behavior of the various
numerical methods. A simple method for obtaining an estimate of the root of the equation 𝑓(𝑥) = 0 is to
make a plot of the equation and observe where it crosses the x axis. This which represents the x value for
which f(x) =0, provides a rough approximation of the root.
EX: use the graphical method to determine the roots for the equation
𝑓(𝑥) = 𝑒 𝑥 − 𝑥 − 2
in the interval [0,4]
Solution:
First
we X 0 1 2 3 4
will Y -1 -0.28 3.4 15 49
find the values of f(x) for several values of x:
From the graph the root is approximately 1.2. Graphical techniques are of limited practical value because
they are not precise. However, graphical methods can be utilized to obtain rough estimations of roots. These
estimates can employ as starting guess for numerical methods.
Page 1 of 10 2025-03-17
Roots of Equations
Numerical method for finding a root of an equation can be classified to two classes of methods which are
Bracketing and Opening methods.
BRACKETING METHOD
Bisection Method:
When applying graphical technique, you have observed that 𝑓(𝑥) changed sign on opposite sides of the
root. In general, if f(x) is real and continuous in the interval from 𝑓(𝑥𝑙 ) and 𝑓(𝑥𝑢 ) have opposite signs that is
𝑓(𝑥𝑙 )𝑓(𝑥𝑢 ) < 0 then there is at least one real root between 𝑥𝑙 and 𝑥𝑢 .
The bisection method is one type of incremental search method in which the interval is always divided in
half. If the location of the root is then determine as lying at the midpoint of the subinterval within which the
sign change occurs. The process repeated to obtain refined estimates. A simple algorithm for the bisection
calculation is listed below:
Step1: choose lower 𝑥𝑙 and upper 𝑥𝑢 guesses for the root such that function changes sign over the interval.
This can be checked by ensuring that 𝑓(𝑥𝑙 )𝑓(𝑥𝑢 ) < 0.
xl xu
Step 2: an estimate of the root xf is determined by x f
2
Step 3: make following evaluation to determine in which subinterval the root leis:
a- if 𝑓(𝑥𝑙 )𝑓(𝑥𝑓 ) < 0, the root leis in the lower subinterval. Therefore, set 𝑥𝑢 = 𝑥𝑓 , and return to step 2
b- if 𝑓(𝑥𝑙 )𝑓(𝑥𝑓 ) > 0, the root leis in the `upper subinterval. Therefore, set 𝑥𝑙 = 𝑥𝑓 , and return to step 2
c- if (𝑥𝑙 )𝑓(𝑥𝑓 ) = 0 , the root equal 𝑥𝑓 ; terminate the computation.
The following is the flowchart for the previous steps.
EX: use the bisection method to find the root of the equation
𝑓(𝑥) = cos(𝑥) – 𝑥 = 0
in the interval [0.5, 1.5].
Solution: first we have to make sure that that f(0.5) and f(1.5) are different in sign. That is true f(0.5)=0.38
and f(1.5)= -1.43. Because there is a sign change in this interval, there will be root in this interval.
First step in bisection methods calculates the midpoint of the interval:
Now we need to know the sign of 𝑓(𝑥𝑓 ) = 𝑓(1) = −0.46. The sign is negative which means that the root
is interval [0.5,1]. The sign of f(x) changes from positive at x=0.5 to negative at x=1.
Page 2 of 10 2025-03-17
Roots of Equations
0.5 + 1.5
𝑥𝑓 = =1
2
The second estimated root 𝑥𝑓 is the midpoint in the new interval:
0.5 + 1
𝑥𝑓 = = 0.75
2
and because of f(0.75)= -0.018 is negative the root is in interval [0.5,0.75].
The third estimated:
0.5 + 0.75
𝑥𝑓 = = 0.625
2
and 𝑓(0.625) = 0.186 which is positive that mean the root is in the interval [0.625,0.75]. We continue to
perform same process until we get the root.
Termination Criteria and Error Estimates:
An initial suggestion might be to end the calculation when the true error falls below some prespecified level.
We might decide that we should terminate when the error drops below say 0.1 percent. An estimated percent
relative error can be calculated:
𝑥𝑓𝑛𝑒𝑤 − 𝑥𝑓𝑜𝑙𝑑
𝜀𝑎 = | |
𝑥𝑓𝑛𝑒𝑤
Where 𝑥𝑓𝑛𝑒𝑤 is the root for the present iteration and 𝑥𝑓𝑜𝑙𝑑 is the root of previous iteration. The absolute value
is used because we are usually concerned with the magnitude of a rather than with its sign.
Page 3 of 10 2025-03-17
Roots of Equations
EX: continue the previous example until the approximate error falls below a a =0.5%.
Solution: the results of the iterations for previous example are listed below:
Iteration Xl Xu Xf a (%)
1 0.5 1.5 1
2 0.5 1 0.75 33.3
3 0.5 0.75 0.625 20
4 0.625 0.75 0.6875 9
5 0.6875 0.75 0.71875 4.3
6 0.71875 0.75 0.734375 2.1
7 0.734375 0.75 0.7421875 1
8 0.734375 0.7421875 0.73828125 0.53
9 0.73828125 0.7421875 0.740234375 0.26
The False-Position Method:
Although the bisection is a perfectly valid technique for determining roots, it is relatively inefficient. False
position is an alternative based on a graphical insight. A shortcoming of the bisection method is that in
dividing the interval from 𝑥𝑙 to 𝑥𝑢 into equal halves, no account is taken of the magnitudes of 𝑓(𝑥𝑙 ) and
𝑓(𝑥𝑢 ). For example, if 𝑓(𝑥𝑙 ) is much closer to zero than 𝑓(𝑥𝑢 ), it is likely that the root is closer to 𝑥𝑙 than to
𝑥𝑢 as shown in the figure.
An alternative method that exploits this graphical insight is to join
f(x)
𝑓(𝑥𝑙 ) and 𝑓(𝑥𝑢 ) by a straight line. The intersection of this line with
f(xu)
the 𝑥 axis represents an improved estimate of the root. The fact that
replacement the curve by a straight line gives a false position of the root xf
xl
is the origin of the name. It is also called the linear interpolation
xu x
method. The intersection of the line with the x axis f(xl)
𝑓(𝑥𝑙 ) 𝑓(𝑥𝑢 ) 𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
= ⇒ 𝑥𝑓 = 𝑥𝑢 −
𝑥𝑓 − 𝑥𝑙 𝑥𝑓 − 𝑥𝑢 𝑓(𝑥𝑙 ) − 𝑓(𝑥𝑢 )
This is the false position formula. The algorithm is identical to the one for bisection with the exception that
𝑥𝑓 is calculated according to false position formula.
EX: continue the previous example until the approximate error falls below a a =0.5%.
Page 4 of 10 2025-03-17
Roots of Equations
Solution: the results of the iterations for previous example are listed below:
i 𝒙𝒍 𝒇(𝒙𝒍 ) 𝒙𝒖 𝒇(𝒙𝒖 ) 𝒙𝒇 𝜺𝒂 (%)
1 0.5 0.38 1.5 -1.43 0.701
2 0.701 0.0574 1.5 -1.43 0.732 4.2
3 0.732 0.01184 1.5 -1.43 0.7383 0.85
4 0.7383 0.00131 1.5 -1.43 0.739 0.094
5 0.739 0.00014
OPEN METHODS
For the bracketing methods in the previous section, the root is located within an interval prescribed by a
lower and an upper bound. Repeated application of these methods always results in closer estimates of the
true value of the root. Such methods are said to be convergent because they move closer to the truth as
computation progress.
In contrast, the open methods described in this section are based on formulas that require only a single
starting value of x or two starting values that do not necessary bracket the root. As such they sometimes
diverge or move away from the true root as the computation progresses. However, when open methods
converge, they usually do so much more quickly than the bracketing methods.
Simple Fixed-Point Iteration:
As mentioned above, open methods employ a formula to predict the root. Such a formula can be developed
for simple fixed-point iteration by rearranging the function:
𝑓(𝑥) = 0
so that 𝑥 is on the left hand side of the equation:
𝑥 = 𝑔(𝑥)
This transformation can be accomplished either by algebraic manipulation or by simply adding 𝑥 to both
sides of the original equation.
x2 3
2
For example, x -2x +3=0 can be simply manipulated to yield x .
2
Page 5 of 10 2025-03-17
Roots of Equations
x2 3
So g ( x) . Whereas sin x=0 could be put into the form by adding x to both sides to yield
2
𝑥 = 𝑠𝑖𝑛 𝑥 + 𝑥 . so g(x) = sin x + x. Given an initial guess at the root 𝑥𝑖 , a new estimate xi+1 can be computed
from iterative formula: 𝑥𝑖+1 = 𝑔(𝑥𝑖 )
EX: use simple fixed-point iteration to locate the root of 𝑓(𝑥) = 𝑒 −𝑥 − 𝑥.
Solution: the function can be separated directly and expressed in the form: 𝑥 = 𝑒 −𝑥 . So the iterative formula
𝑥𝑖+1 = 𝑒 −𝑥𝑖 Starting with an initial guess of 𝑥0 = 0 this iterative equation can be applied to compute the
table.
error
i xi a% t % *100 xi+1
true
0 0 100 1 f(x)
f(x)=e-x-x
1 1 100 76.3 0.367879 Root
2 0.367879 171.8 35.1 0.692201 x
3 0.692201 46.9 22.1 0.500473
f(x)
4 0.500473 38.3 11.8 0.606244 g(x)=x
5 0.606244 17.4 6.89 0.545396 g(x)=e-x
Root
6 0.545396 11.2 3.83 0.579612
x
7 0.579612 5.9 2.2 0.560115
8 0.560115 3.48 1.24 0.571143
9 0.571143 1.93 0.705 0.564879
10 0.564879 1.11 0.399
Thus, each iteration bring the estimate closer to the true value of the root: 0.56714329
Convergence:
Notice that the true percent relative error for each iteration of previous example is roughly proportional (by
factor of 0.5 to 0.6) to the error from previous iteration. This property called linear convergence. It is
characteristic of fixed-point iteration. The concepts of convergence or divergence can be depicted
graphically. The solution is Convergent when the estimates of x move closer to the root with each iteration
Page 6 of 10 2025-03-17
Roots of Equations
and the solution is divergent when the estimates of x move away from the root with each iteration. Notice
the convergence seems to occur only when the absolute value of the slope f(x)=g(x) is less than 1 that means
g ' ( x) 1 .
The Newton-Raphson Method:
Perhaps the most widely used of all root-locating formula is the
Newton-Raphson equation. If the initial guess at the root is 𝑥𝑖 , a f(x) Slope = f’(xi)
tangent can be extended from the point [𝑥𝑖 , 𝑓(𝑥𝑖 )]. The point f(xi)
where this tangent crosses the x axis usually represented an f(xi )-0
improved estimate of the root. The Newton-Raphson method can xi+1 xi x
be derived on the basis of this geometrical interpretation. As in xi -xi+1
the figure, the first derivative at x is equivalent to the slope
f x i 0
f ' x i
x i x i 1
which can be rearranged to
f x i
x i 1 x i
f ' x i
which is called Newton-Raphson formula
EX: use Newton-Raphson method to estimate the root of 𝑓(𝑥) = 𝑒 −𝑥 − 𝑥 employing an initial guess of
𝑥0 = 0.
Solution: the first derivative of the function can be evaluated as f'(x) = - e-x-1
e xi x i
Which can be substituted with the original function give x i 1 x i
e xi 1
Starting with an initial guess of 𝑥0 = 0, this iterative equation can
i xi εt(%)
be applied to compute the table. Thus, the approach rapidly
0 0 100
converges on the true root. Notice that the true percent relative
1 0.5 11.8
error at each iteration decrease much faster than it does in simple
2 0.566311003 0.147
fixed-point iteration
3 0.567143165 0.000022
4 0.567143290 <10-8
Page 7 of 10 2025-03-17
Roots of Equations
Pitfalls of the Newton-Raphson Method:
Although, the Newton_Raphson method is often very efficient, there are situations where it is perform
poorly. A special case –multiple roots- will be addressed later. However,
iteration x
even dealing with simple roots, difficulties can also arise, as in the
0 0.5
following example:
1 51.65
EX: determine the positive root of f(x) = x10 -1 using the Newton-Raphson
2 46.485
method and an initial guess of x = 0.5.
3 41.8365
Solution: The Newton-Raphson formula in this case:
4 37.65285
x i10` 1
x i 1 x i
10 x i9 5 33.887565
This can be used to compute the table. Thus, after the first predication, the .
technique is converging on the true root of 1, but at a very slow rate. ∞ 1.00000000
Aside of slow convergence due to the nature of the function, other difficulties can arise, as illustrated in
following figure. For example:
a) Depicts the case where an inflection point [that is, f''(x) = 0 ] occurs in the vicinity of a root. Notice that
iterations beginning at 𝑥0 progressively diverge from the root.
b) Illustrates the tendency of the Newton-Raphson technique to oscillate around a local maximum of
minimum. Such oscillations may persist f(x) f(x)
or a near-zero slope is reached,
x1 x1
x2
whereupon the solution is sent far from x0 x2
x x0 x
the area of interest.
(a) (c)
c) Shows how an initial guess that is close
f(x)
f(x)
to one root can jump to a location
several roots away. This tendency to
x2 x 1 x0 x1 x
move away from area of interest. That x0
x
is because near-zero slopes are (b) (d)
encountered.
Page 8 of 10 2025-03-17
Roots of Equations
d) Obviously a zero slope truly a disaster because in causes division by zero in the Newton-Raphson
formula. Graphically, it means that the solution shoots off horizontally and never hits the x axis.
The Secant Method:
A potential problem in implementing the Newton-Raphson method
f(x)
is the evolution of the derivative. Although this is not inconvenient f(xi)
for polynomials and may other functions, there are certain functions
whose derivatives may be extremely difficult or inconvenient to
evaluate. For these cases, the derivative can be approximated by f(xi-1)
backward finite divided difference as shown in the figure. xi-1 xi x
f x i 1 f x i
f ' x i .
x i 1 x i
f ( xi )
This approximation can be substituted into x i 1 x i
f ' x i
f ( x i )x i 1 x i
to yield the following iterative equation x i 1 x i .
f x i 1 f x i
This equation is the formula of the secant method. Notice that the approach requires two initial estimates of
x.
EX: use secant method to estimates the root of f(x) = e-x – x. start with initial estimates of xi-1 = 0 and x0 =
1.
Solution: the true root is 0.56714329…..
First iteration
xi-1 = 0 f(xi-1) = 1
x0 = 1 f(x0) = -0.63212
0.632120 1
x1 1 0.6127 t 8.0%
1 0.63212
Second iteration
x0 = 1 f(x0) = -0.63212
x1 = 0.61270 f(x1) = -0.07081
Page 9 of 10 2025-03-17
Roots of Equations
Note that both estimates are now on the same side of the root.
0.07081 1 0.61270
x2 1 0.56384 t 0.58%
0.63212 0.07081
Third iteration:
x1 = 0.61270 f(x1) = -0.07081
x2 = 0.56384 f(x2) = 0.00518
0.00518 0.61270 0.56384
x 3 0.56384 0.56717 t 0.0048%
0.07081 0.00518
Page 10 of 10 2025-03-17
