Numerical Methods
PART II: ROOTS OF EQUATIONS
Chapter 6: Open Methods
Dr. Amer M. Magableh
OPEN METHODS
2
Open methods do not rely on having the root between two values
Open methods depends on an initial guess and then apply an iterative
process to get better estimates for the root.
Open methods are usually faster in convergence, if they converge,
than bracketing methods, but they don’t always converge.
When the method converges, the error is roughly proportional to or
less than the error of the previous step, therefore it is called “linearly
convergent.”
Fixed-Point Iteration Method
Newton Raphson Method
Secant Method.
Brent’s Method
Dr. Amer M. Magableh
Dr. Amer M. Magableh
Fixed-Point Iteration Method
Example: f ( x) x 2 x 2 x 0
g ( x) x 2 2
or
g ( x) x 2
or
2
g ( x) 1
x
Dr. Amer M. Magableh
Fixed Point iteration
5
Algorithm
The fixed-point iteration method relies on replacing the
expression 𝑓(𝑥) = 0 with the expression 𝑥 = 𝑔(𝑥).
Assume an initial guess for the root 𝑥𝑜 to be used in 𝑔(𝑥).
Then, the value of the first iteration is 𝑥1 = 𝑔(𝑥𝑜 ).
𝑥𝑖+1 −𝑥𝑖
Calculate the relative error 𝜖𝑟 =
𝑥𝑖+1
The iteration stops if 𝜀𝑟 ≤ 𝜀𝑠 or number of iterations reaches the maximum
number of allowed iterations N
Dr. Amer M. Magableh
Example
6
Consider the function 𝑓(𝑥) = cos(𝑥) − 𝑥. We wish to find the root
of the equation 𝑓(𝑥) = 0. let 𝜀𝑠 = 0.0001
Solution
We assume
g 𝑥 = 𝑥 = cos(𝑥)
We assume initial guess 𝑥𝑜 = 0.1
𝑖 = 1,
0.995004 − 0.1
𝑥1 = cos 0.1 = 0.995004, 𝜀1 = = 0.899498
0.995004
𝑖 = 2,
0.544499 − 0.995004
𝑥2 = cos 0.995004 = 0.544499, 𝜀2 = = −0.827374
0.544499
𝑖 = 3,
0.855387 − 0.544499
𝑥3 = cos 0.544499 = 0.855387, 𝜀3 = = 0.363447
0.855387
𝑖 = 4,
0.655927 − 0.855387
𝑥4 = cos 0.855387 = 0.655927, 𝜀4 = = −0.304089
0.655927
Dr. Amer M. Magableh
7
Convergence
The fixed-point iteration method converges easily if in the
region of interest we have |𝑔′(𝑥)| < 1
Dr. Amer M. Magableh
Example
8
Consider the function 𝑓 𝑥 = sin 5𝑥 + cos(2𝑥), we need to find the root of the
equation 𝑓(𝑥) = 0
Solution
If we define x = g x = sin 5𝑥 + cos 2𝑥 + 𝑥
Notice for this function, 𝑔′ 𝑥 > 1, so, we expect No convergence
Does Not Converge Dr. Amer M. Magableh
9
𝑓 𝑥 = sin 5𝑥 + cos(2𝑥)
g x = sin 5𝑥 + cos 2𝑥 + 𝑥
Dr. Amer M. Magableh
Same Example
10
If we select another function for g(x) for the same root finding for f(x)
𝑠𝑖𝑛 5𝑥 + cos 2𝑥
𝑓 𝑥 = sin 5𝑥 + cos 2x = 0, then = 0 for all x ∈ 𝑅 − 0
𝑥
𝑠𝑖𝑛 5𝑥 + cos 2𝑥
⇒𝑥=𝑔 𝑥 = +𝑥
𝑥
Convergence depends
on the initial value
Dr. Amer M. Magableh
Newton Raphson Method
11
Newton-Raphson method is one of the most used methods of all root-
finding methods since it converges very fast in most cases, and can be easily
extended to multiple variable
If the initial guess is 𝑥𝑖 , then a tangent can be extended from the point
𝑥𝑖 , 𝑓 𝑥𝑖 . This tangent will cross the x-axis and will give an improved
estimate for the root.
Dr. Amer M. Magableh
12
Dr. Amer M. Magableh
13
We can use also Taylor series expansion to find same result before
for the root estimate
Dr. Amer M. Magableh
14
Algorithm
Set an initial guess 𝑥𝑜 , error tolerance 𝜀𝑠 , and maximum number of
iterations N
Calculate the next estimate
Calculate
Stop iterations if
Dr. Amer M. Magableh
Example
15
Consider the function 𝑓 𝑥 = sin 5𝑥 + cos(2𝑥), we need to find the root of the
equation 𝑓(𝑥) = 0 using Newton Raphson Method
Dr. Amer M. Magableh
16
Dr. Amer M. Magableh
17
Dr. Amer M. Magableh
Convergence of Newton Raphson Method
18
Let the estimated root is 𝑥𝑖+1
The true root is 𝑥𝑡 , and its Taylor series expansion is
Subtract the two equations 𝑓 𝑥𝑡 − 𝑓(𝑥𝑖+1 )
Let
If the method converges, then
Dr. Amer M. Magableh
Some cases where Newton Raphson Method performs poorly
19
Dr. Amer M. Magableh
Secant Method
20
The Secant Method is an alternative for Newton Rapson method
that is by replacing the derivative function by its equivalent difference
approximation
Dr. Amer M. Magableh
Secant Method
21
Dr. Amer M. Magableh
Assignment
22
Consider the function 𝑓 𝑥 = sin 5𝑥 + cos(2𝑥), we need to find the root of the
equation 𝑓(𝑥) = 0 using Secant Method with initial conditions 𝑥0 = 0.4, 𝑥1 = 0.6
Dr. Amer M. Magableh
Brent Method
23 Brent’s method combining bracketing method with open method.
It is a hybrid method which combines the reliability of bracketing method and the
speed of open methods
Here we require three points 𝑃𝑜 𝑥𝑜 , 𝑦𝑜 , 𝑃1 𝑥1 , 𝑦1 , 𝑎𝑛𝑑 𝑃2 𝑥2 , 𝑦2
Comparison of (a) the secant method and (b) inverse quadratic interpolation. Note
that the dark parabola passing through the three points in (b) is called “inverse”
because it is written in y rather than in x.
Dr. Amer M. Magableh
24
Two parabolas fit to three points. The parabola written as a function of 𝑥, 𝑦
= 𝑓(𝑥), has complex roots and hence does not intersect the 𝑥 axis. In contrast, if
the variables are reversed, and the parabola developed as 𝑥 = 𝑓(𝑦), the function
does intersect the 𝑥 axis.
This why it called sometimes Inverse Quadratic Interpolation
Dr. Amer M. Magableh
Brent Method
25
Brent’s method combining bracketing method with open method.
It is a hybrid method which combines the reliability of bracketing method
and the speed of open methods
Here we require three points 𝑃𝑜 𝑥𝑜 , 𝑦𝑜 , 𝑃1 𝑥1 , 𝑦1 , 𝑎𝑛𝑑 𝑃2 𝑥2 , 𝑦2
Then, we can have a quadratic polynomial that passes through the three
points as follows
𝑦 − 𝑦1 𝑦 − 𝑦2 𝑦 − 𝑦0 𝑦 − 𝑦2 𝑦 − 𝑦0 𝑦 − 𝑦1
𝑔 𝑦 = 𝑥0 + 𝑥1 + 𝑥2
(𝑦0 − 𝑦1 )(𝑦0 − 𝑦2 ) (𝑦1 − 𝑦0 )(𝑦1 − 𝑦2 ) (𝑦2 − 𝑦0 )(𝑦2 − 𝑦1 )
And
𝑦 − 𝑦1 𝑦 − 𝑦2 𝑦 − 𝑦0 𝑦 − 𝑦2 𝑦 − 𝑦0 𝑦 − 𝑦1
𝑥= + +
(𝑦0 − 𝑦1 )(𝑦0 − 𝑦2 ) (𝑦1 − 𝑦0 )(𝑦1 − 𝑦2 ) (𝑦2 − 𝑦0 )(𝑦2 − 𝑦1 )
Dr. Amer M. Magableh
26
To estimate the root of the function
Now for 𝑦 = 0 the expression above, then we can write the expression
for the root as:
𝑥𝑖+1
𝑦𝑖−1 𝑦𝑖 𝑦𝑖−2 𝑦𝑖 𝑦𝑖−1 𝑦𝑖−2
= 𝑥𝑖−2 + 𝑥𝑖−1 + 𝑥
(𝑦𝑖−2 − 𝑦𝑖−1 )(𝑦𝑖−2 − 𝑦𝑖 ) (𝑦𝑖−1 − 𝑦𝑖−2 )(𝑦𝑖−1 − 𝑦𝑖 ) (𝑦𝑖 − 𝑦𝑖−1 )(𝑦𝑖 − 𝑦𝑖−2 ) 𝑖
Dr. Amer M. Magableh
27
Dr. Amer M. Magableh
28
Dr. Amer M. Magableh
29
Suggested Problems of Chapter 6
1, 2, 3, 4, 5, 6, 7, 8, 10, 14, 19, 21 (for Multiple roots)
Dr. Amer M. Magableh