Solving Polynomials using
Numerical Methods
(Open Methods)
Numerical Methods
MATH160
Open Methods
The open methods described in this
chapter require only a single starting
value or two starting values that do
not necessarily bracket the root. As
such, they sometimes diverge or
move away from the true root as the
computation progresses. However,
when the open methods converge
they usually do so much more
quickly than the bracketing
methods.
Method of Successive
Substitution (MOSS)
This is also called fixed-point iteration or one-point iteration. In this
method, the function 𝑓 𝑥 = 0 is rearranged so that x is on the left-
hand side of the equation:
𝑥 = 𝑔(𝑥).
This transformation can be accomplished either by algebraic
manipulation or by simply adding x to both sides of the original
equation.
Method of Successive
Substitution (MOSS)
The equation 𝑥 = 𝑔(𝑥) 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 𝑥𝑖 , the equation presented can be used to compute a new
estimate 𝑥𝑖+1 as expressed by the iterative formula,
𝑥𝑖+1 = 𝑔(𝑥𝑖 )
Method of Successive
Substitution (MOSS)
For this method, the true percent relative error for each iteration is
roughly proportional to the error from the previous iteration.
%𝜀𝑟(𝑖+1)
%𝜀𝑟(𝑖)
This property, called linear convergence, is characteristic of fixed-
point iteration.
Method of Successive
Substitution (MOSS)
STEPS
1. Use an initial guess of the root, 𝑥𝑖 , to estimate the new value of
the root, 𝑥𝑖+1 , as
𝑥𝑖+1 = 𝑔(𝑥𝑖 )
2. Find the approximate percent relative error as
𝑥𝑖+1 −𝑥𝑖
%𝜀𝑎𝑟 = × 100%
𝑥𝑖+1
Method of Successive
Substitution (MOSS)
3. Compare the approximate percent relative error %𝜀𝑎𝑟 , with the
pre-specified relative error tolerance %𝜀𝑠 . If % 𝜀𝑎𝑟 > %𝜀𝑠 , then
repeat step 1, else stop the algorithm.
Example
1. Use simple fixed-point iteration to locate the root of 𝑓 𝑥 = 𝑒 −𝑥 −
𝑥 using initial value of 𝑥0 = 0 with 1.5% error tolerance.
Solution
Step 1: Manipulate the given function so that it is expressed in the
form,
𝑥𝑖+1 = 𝑔(𝑥𝑖 )
To solve for the root, we equate the given equation to zero,
𝑓 𝑥 = 𝑒 −𝑥 − 𝑥
0 = 𝑒 −𝑥 − 𝑥
Form 1: 𝑥 = 𝑒 −𝑥
Form 2: 𝑥 = − ln 𝑥
Choosing form 1, 𝑥𝑖+1 = 𝑒 −𝑥
Solution
Step 2: Make a table with the following columns:
iteration 𝑥(𝑖+1) %error remarks
0
1
2
3
4
5
6
Step 3: At Iteration 0, substitute the initial value of x, 𝑥0 = 0, to the
𝑥𝑖+1 equation.
𝑥𝑖+1 = 𝑒 −0 = 1
Solution
iteration 𝑥(𝑖+1) %error remarks
0 1
1
2
3
4
5
6
Step 4: At Iteration 1, substitute the previous value of 𝑥𝑖+1 (at
iteration 0), to the 𝑥𝑖+1 equation.
𝑥𝑖+1 = 𝑒 −1 = 0.36787944
Solution
Step 5: Calculate the approximate percent relative error as
𝑥𝑖+1 −𝑥𝑖 0.36787944−1
%𝜀𝑎𝑟 = × 100% = × 100% = 171.83%
𝑥𝑖+1 0.36787944
iteration 𝑥(𝑖+1) %error remarks
0 1
1 0.36787944 171.83% Continue
2
3
4
5
6
Step 6: Compare the approximate percent relative error, with the
given error tolerance %𝜀𝑠 = 1.5%. As seen, % 𝜀𝑎𝑟 > %𝜀𝑠 , then repeat
steps 4 and 5.
Solution
Step 7: At Iteration 2, substitute the previous value of 𝑥𝑖+1 (at
iteration 1), to the 𝑥𝑖+1 equation.
𝑥𝑖+1 = 𝑒 −0.36787944 = 0.69220063
Step 8: Calculate the approximate percent relative error and
compare it to the tolerance error. If % 𝜀𝑎𝑟 > %𝜀𝑠 , then repeat step 4
and 5, else stop the algorithm.
𝑥𝑖+1 − 𝑥𝑖 0.69220063 − 0.36787944
%𝜀𝑎𝑟 = × 100% = × 100%
𝑥𝑖+1 0.69220063
%𝜀𝑎𝑟 = 46.85%
Solution
iteration 𝑥(𝑖+1) %error remarks
0 1
1 0.367879441 171.83% Continue
2 0.692200628 46.85% Continue
3 0.500473501 38.31% Continue
4 0.606243535 17.45% Continue
5 0.545395786 11.16% Continue
6 0.579612336 5.90% Continue
7 0.560115461 3.48% Continue
8 0.571143115 1.93% Continue
9 0.564879347 1.11% Stop
Estimated root = 0.564879347
Method of Successive
Substitution (MOSS)
Aside from the “rate” of
convergence, we must comment
at this point about the
“possibility” of convergence. The
concepts of convergence and
divergence can be depicted
graphically. From the previous
example, we can let
𝑓1 (𝑥) = 𝑓2 (𝑥)
𝑥 = 𝑒 −𝑥
Method of Successive
Substitution (MOSS)
For the first case (figure a), the
initial guess of 𝑥0 is used to
determine the corresponding
point on the 𝑦2 curve [𝑥0 , 𝑔(𝑥0 )]
. The point 𝑥1 is located by
moving left horizontally to the
𝑦1 curve. These movements are
equivalent to the first iteration
of the fixed-point method.
Method of Successive
Substitution (MOSS)
A theoretical derivation can be used to gain insight into the process.
It can be shown that the error for any iteration is linearly
proportional to the error from the previous iteration multiplied by
the absolute value of the slope of 𝑔(𝑥) :
𝐸𝑖+1
𝐸𝑖+1 = 𝑔′(𝑥)𝐸𝑖 = 𝑔′(𝑥)
𝐸𝑖
If 𝑥 = 𝑥𝑖+1 ,
𝑔′(𝑥𝑖+1 ) < 1, the error decreases with iteration (converges)
𝑔′(𝑥𝑖+1 ) > 1, the error increases with iteration (diverges)
Example
For the function,
2
𝑥3 + 2𝑥 + 2 = 10𝑒 −2𝑥
Which of the following 𝑥 = 𝑔(𝑥) forms will converge? Using the
converging form, solve for the root using MOSS with initial value of
𝑥0 = −0.5 and %𝜀𝑠 = 0.05%.
1 2
a. 𝑥 = [10𝑒 −2𝑥 − (𝑥 3 + 2)]
2
1 𝑥 3 +2𝑥+2
b. 𝑥 = − ln
2 10
Newton-Raphson Method
Perhaps the most widely used of all
root-locating formulas is the
Newton-Raphson method or simply
the Newton’s Method.
If the initial guess at the root is 𝑥𝑖 , a
tangent can be extended from the
point [𝑥𝑖 , 𝑓(𝑥𝑖 )]. The point where
this tangent crosses the x axis
usually represents an improved
estimate of the root.
Newton-Raphson Method
The Newton-Raphson method can be derived on the basis of this
geometrical interpretation.
𝑓(𝑥𝑖 ) − 0
𝑓′ 𝑥 =
𝑥𝑖 − 𝑥𝑖+1
which can be rearranged to yield
𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 − ′
𝑓 𝑥𝑖
which is called the Newton-Raphson formula.
Newton-Raphson Method
STEPS
1. Evaluate 𝑓 ′ 𝑥 .
2. Use an initial guess of the root, 𝑥𝑖 , to estimate the new value of
the root, 𝑥𝑖+1 , as
𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 − ′
𝑓 𝑥𝑖
Newton-Raphson Method
3. Find the approximate percent relative error as
𝑥𝑖+1 −𝑥𝑖
%𝜀𝑎𝑟 = × 100%
𝑥𝑖+1
4. Compare the approximate percent relative error %𝜀𝑎𝑟 , with the
pre-specified relative error tolerance %𝜀𝑠 . If % 𝜀𝑎𝑟 > %𝜀𝑠 , then
repeat step 2, else stop the algorithm.
Examples
1. You are working for ‘DOWN THE TOILET COMPANY’ that makes
floats for ABC company. You are asked to find the depth to which
the ball is submerged when floating in water. The equation that
gives the depth x to which the ball is submerged under water is
given by
𝑦 = 𝑥 3 − 0.165𝑥 2 + 3.993 × 10−4
Solve this equation using Newton’s Method given that the error
tolerance is 0.3% and 𝑥0 = 0.5.
Example
For the function,
2
𝑓 𝑥 = 𝑥3 + 2𝑥 + 2 − 10𝑒 −2𝑥
Solve for the root using Newton-Rhapson Method with initial value
of 𝑥0 = −0.5 and %𝜀𝑠 = 0.05%.
2
𝑓′ 𝑥 = 3𝑥 2 +2+ 40𝑥𝑒 −2𝑥
Advantages
• Converges fast (quadratic convergence), if it converges.
• Requires only one guess.
Disadvantages
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 the Newton-Raphson method.
For example, the equation 𝑓 𝑥 = 𝑥 − 1 3 + 0.512
could diverge if the initial value 𝑥0 is close to the
inflection point.
Disadvantages
2. The initial root approximation could make the 𝑓 ′ 𝑥 = 0. Thus
𝑓 𝑥𝑖
making the equation 𝑥𝑖+1 = 𝑥𝑖 − diverge.
𝑓′ 𝑥
3. Results obtained from the Newton-Raphson method may oscillate
about the local maximum or minimum without converging on a
root but converging on the local maximum or minimum. Eventually,
it may lead to division by a number close to zero and may diverge.
For example for 𝑓 𝑥 = 𝑥 2 + 2 the equation has no real roots.
Disadvantages
Iteration 𝑥𝑖+1 𝑓 𝑥𝑖 %𝜀𝑎𝑟
Number 6
f(x)
0 –1.0000 3.00 5
1 0.5 2.25 300.00 4
2 –1.75 5.063 128.571
3 –0.30357 2.092 476.47 3
3
4 3.1423 11.874 109.66 2
2
5 1.2529 3.570 150.80
6 –0.17166 2.029 829.88 11
4
7 5.7395 34.942 102.99 x
0
8 2.6955 9.266 112.93 -2
-1.75
-1
-0.3040
0
0.5
1 2 3
3.142
9 0.97678 2.954 175.96 -1
Oscillations near local maxima and mimima in Newton-Raphson method.
Disadvantages
4. In some cases where the function 𝑓 𝑥 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.
For example f(x)
1.5
𝑓 𝑥 = sin 𝑥.
0.5
Choose 𝑥0 = 2.4𝜋 = 7.539822 0
x
-2 0 2 4 6 8 10
-0.06307 0.5499 4.461 7.539822
It will converge to 𝑥 = 0 -0.5
instead of 𝑥 = 2𝜋.
-1
-1.5
END