Numerical Methods Page 1 of 12

Open Methods

INTENDED LEARNING OUTCOMES: At the end of this lesson, the students will be able to:
1. Define Open Methods;
2. Illustrate the difference between the Secant and False-Position Method; and
3. Identify the Secant Method and how it relates to convergence.

LESSON PROPER:

Open Methods
Bracketing methods use two initial guesses and the bounds converge to the solution. In open
methods, we need only one starting point or two (that not necessarily bracket the root).

Open methods differ from bracketing methods, in that open methods require only a single starting
value or two starting values that do not necessarily bracket a root. Open methods may diverge as the p
y g computation progresses, but when they do converge, they usually do so much faster g y y
than bracketing methods.

Bracketing methods use two initial guesses and the bounds converge to the solution. In open methods,
we need only one starting point or two (that not necessarily bracket the root).
These methods may diverge, contrary to the bracketing methods, but when they converge, they usually
do it much more quickly than bracketing methods.

Simple fixed-point method

A fixed point is a periodic point with period equal to one. In projective geometry, a fixed point of a
projectivity has been called a double point. In Galois theory, the set of the fixed points of a set of field
automorphisms is a field called the fixed field of the set of automorphisms.

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. More
specifically, given a function defined on the real numbers with real values and given a point in the
domain of , the fixed point iteration is.
In open methods, we have to use a formula to predict the root, as an example for the fixed-point iteration
method we can rearrange f(x) so that x is on the left-hand side of the equation:
x = g (x )
 Numerical Methods Page 2 of 12
Open Methods

This can be achieved by algebraic manipulation of by simply adding x to both sides of the original
equation, example:
1 − x2
x 2 + 3x − 1 = 0  x =
3
sin ( x ) = 0  x = sin( x) + x

This is important since it will allow us to develop a formula to predict the new value for x as a function of
an old value of x:
xi+1 = g ( xi )

Newton-Raphson method

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 3.12).
Using the definition of the slope of a function, at x = xi

f(xi ) − 0
 i)==
f (x
xi − xi +1
which gives
f(xi )
xi +1 = xi -
f'(xi )
This equation is called the Newton-Raphson formula for solving nonlinear equations of the form f ( x ) = 0
. So starting with an initial guess, xi, one can find the next guess, xi+1, by using the above equation. One
can repeat this process until one finds the root within a desirable tolerance.
Numerical Methods Page 3 of 12
Open Methods

f(x)

f(xi)
x f (x )
i, i

f(xi+1)


xi+2 xi+1 xi X

Figure.3.12. Geometrical illustration of the Newton-Raphson method

 Numerical Methods Page 4 of 12
Open Methods

Drawbacks of Newton-Raphson Method

Divergence at inflection points: If the selection of a guess or an iterated value turns out to be close to
the inflection point of f(x), that is, near where f”(x)=0, the roots start to diverge away from the true root.

10

0
-2 -1 0 1 2

-5

-10

-15

-20

Figure.3.13. Divergence at inflection point.

Division by zero or near zero: The formula of Newton-Raphson method is

f(xi )
xi +1 = xi −
f (xi )
Consequently if an iteration value, x i is such that f ( xi )  0 , then one can face division by zero or a

near-zero number. This will give a large magnitude for the next value, xi+1. An example is finding the root
of the equation
f (x ) = x 3 − 0.03 x 2 + 2.4  10 −6
in which case
f ( x ) = 3 x 2 − 0.06 x
For x 0 = 0 or x0 = 0.02 , division by zero occurs (Figure 3.14). For an initial guess close to 0.02, of

x0 = 0.01999 , even after 9 iterations, the Newton-Raphson method is not converging.

 Numerical Methods Page 5 of 12
Open Methods

Iteration xi a f(xi)
Number
0 0.019990 -1.6000 x 10-6
1 -2.6480 100.75 -18.778
2 -1.7620 50.282 -5.5638
3 -1.1714 50.422 -1.6485
4 -0.77765 50.632 -0.48842
5 -0.51518 50.946 -0.14470
6 -0.34025 51.413 -0.042862
7 -0.22369 52.107 -0.012692
8 -0.14608 53.127 -0.0037553
9 -0.094490 54.602 -0.0011091

1.00E-05

7.50E-06
f(x)
5.00E-06

2.50E-06

3.00E-21 x
-0.03 -0.02 -0.01 0 0.01 0.02 0.03 0.04
-2.50E-06
0.02
-5.00E-06

-7.50E-06

-1.00E-05

Figure 3.14. Division by zero or a near zero number.

Root jumping: In some case where the function f(x) 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 for solving the equation
sin x = 0
if you choose x0 = 2.4 = (7.539822 ) as an initial guess, it converges to the root of x=0 as shown in Table

3. However, one may have chosen this an initial guess to converge to x = 2 = 6.2831853 .

Iteration xi f(xi) a
Number
0 7.539822 0.951
1 4.461 -0.969 68.973
2 0.5499 0.5226 711.44
3 -0.06303 -0.06303 971.91
4 6.376x10-4 8.375x10-4 7.54x104
5 -1.95861x10-13 -1.95861x10-13 4.27x1010
 Numerical Methods Page 6 of 12
Open Methods
1.5
f(x)
1

0.5

0 x
-2 0 2 4 6 8 10
-0.06307 0.5499 4.461
-0.5

-1

-1.5

Figure 3.15. Root jumping from intended location of root for f (x ) = sin x = 0

Oscillations near local maximum and minimum: Results obtained from 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
f (x ) = x 2 + 2 = 0
the equation has no real roots

Iteration xi f(xi) a
Number
0 -1.0000 3.00 _____
1 0.5 2.25 300.00
2 -1.75 5.062 128.571
3 - 2.092 476.47
4 0.30357 11.874 109.66
5 3.1423 3.57 150.80
6 1.2529 2.029 829.88
7 - 34.942 102.99
8 0.17166 9.268 112.927
9 5.7395 2.954 175.96
2.6955
0.9770
6
f(x)
5

3
3
2 2

11
4
0 x
-2 -1 0 1 2 3
-1.75 - 0.5 3.14
-1

Figure.3.16. Oscillations around local minima for f ( x ) = x 2 + 2

 Numerical Methods Page 7 of 12
Open Methods

The Secant Method

The Newton-Raphson method of solving the nonlinear equation f(x)=0 is given by the recursive formula
f(xi )
xi +1 = xi - (1)
f'(xi )

From the above equation, one of the drawbacks of the Newton-Raphson method is that you have to
evaluate the derivative of the function. With availability of symbolic manipulators such as Maple, Mathcad,
Mathematica and Matlab, this process has become more convenient. However, it is still can be a
laborious process. To overcome this drawback, the derivative, f’(x) of the function, f(x) is approximated
as
f ( xi ) − f ( xi −1 )
f ( xi ) = (2)
xi − xi −1
Substituting Equation (2) in (1), gives
f ( xi )( xi − xi −1 )
xi +1 = xi − (3)
f ( xi ) − f ( xi −1 )
The above equation is called the Secant method. This method now requires two initial guesses, but
unlike the bisection method, the two initial guesses do not need to bracket the root of the equation. The
Secant method may or may not converge, but when it converges, it converges faster than the bisection
method. However, since the derivative is approximated, it converges slower then Newton-Raphson
method.

The Secant method can be also derived from geometry shown in Figure (3.17). Taking two initial guesses,
xi and xi-1, one draws a straight line between f(xi) and f(xi-1) passing through the x-axis at xi+1. ABE and
DCE are similar triangles. Hence
AB DC
=
AE DE
f ( xi ) f ( xi −1 )
=
xi − xi +1 xi −1 − xi +1
Rearranging, it gives the secant method as
f ( xi )( xi − xi −1 )
xi +1 = xi −
f ( xi ) − f ( xi −1 )
 Numerical Methods Page 8 of 12
Open Methods

f(x)

f(xi) B

f(xi-1) C

E D A X
xi+1 xi-1 xi

Figure.3.17. Geometrical representation of the Secant method.

Difference Between Secant and False-Position Method

In the false position method, the latest estimate of the root replaces whichever of the original values
yielded a function value with the same sign as f(xr). The root is always bracketed by the bonds and the
method will always converge.

For the secant method, xi+1 replaces xi and xi replaces xi-1. As a result, the two values can sometimes lie
in the same side of the root and lead to divergence. But when, the secant method converges, it usually
does it at a quicker rate.

Rate of Convergence

Figure (3.18) compares the convergence of all the methods.

Figure.3.18. Rate of convergence of all the methods.

 Numerical Methods Page 9 of 12
Open Methods

Additional problems

P I. Find the largest root of:

f ( x) = x 6 − x − 1 = 0

Using the bisection method (Plot the function first to determine your initial guesses)

Solution: x = 1.1328
 Numerical Methods Page 10 of 12
Open Methods

FORMATIVE ASSESSMENT

NAME DATE
YEAR AND SECTION SCORE

A. IDENTIFICATION: Identify the concept being described in each item. Write your answers on the
spaces provided before each item.
_______________ 1. A method determines successively smaller intervals (brackets) that contain a root.

_______________ 2. One of the simplest and reliable iterative methods for the solution of nonlinear
equation

_______________ 3. It is a value which, when plugged into the polynomial for the variable, results in 0

_______________ 4. The roots of a polynomial whose factors show up more than once in the complete
factorization of the polynomial.

_______________ 5. It is the number of occurrences of this root in the complete factorization of the
polynomial, by means of the fundamental theorem of algebra

_______________ 6. The functions that are not a continuous curve - there is a hole or jump in the
graph.

_______________ 7. It is defined as a point where the function becomes infinite

_______________ 8. It is always bracketed by the bonds, and the method will always converge.

_______________ 9. A Method in which if one limit is detected to be stuck, the function value of the
stagnant point is divided by 2.

_______________ 10. It is the fact that one limit may stay fixed during the computation.
 Numerical Methods Page 11 of 12
Open Methods

B. TRUE OR FALSE: For a statement to be TRUE, each part must be true. One detail can make an
entire statement FALSE. Write TRUE if the statement is true, and FALSE, if the statement is
incorrect.
__________ 1. Bracketing with a super-linear order of convergence as the secant method can be
attained with improvements to the false position method.

__________ 2. One of the first numerical methods developed to find the root of a nonlinear equation f(x)
= 0 was the bisection method (also called Binary-Search method).

__________ 3. Root of a Polynomial is a value which, when plugged into the polynomial for the
variable, results in 0.

__________ 4. If is a root of multiplicity of a polynomial, then it is a root of multiplicity of its constant.

__________ 5. Discontinuous functions are functions that are not a continuous curve - there is a hole
or jump in the graph

__________ 6. In a removable function, the point can be redefined to make the function continuous by
matching the value at that point with the rest of the function.

__________ 7. The bisection method is always convergent. Since the method brackets the root, the
method is guaranteed to converge.

__________ 8. As iterations are conducted, the interval gets halved. So one can guarantee the
decrease in the error in the solution of the equation.

__________ 9. The convergence of bisection method is slow as it is simply based on halving the interval.

__________ 10. If one of the initial guesses is closer to the root, it will take smaller number of iterations
to reach the root.
 Numerical Methods Page 12 of 12
Open Methods

C. MULTIPLE CHOICE Read and understand the statements given below. ENCIRCLE the letter of the
correct answer.
1. This is a method that determines successively smaller intervals (brackets) that contain a root.
A. Bisection Method C. Root of a Polynomial
B. Multiple Roots D. Bracketing methods
2. This is one of the simplest and reliable iterative methods for the solution of nonlinear equation
A. Bisection Method C. Root of a Polynomial
B. Multiple Roots D. Bracketing methods
3. It is a value which, when plugged into the polynomial for the variable, results in 0
A. Bisection Method C. Root of a Polynomial
B. Multiple Roots D. Bracketing methods
4. ________________ of a polynomial are roots whose factors show up more than once in the complete
factorization of the polynomial.
A. Bisection Method C. Root of a Polynomial
B. Multiple Roots D. Bracketing methods
5. The number of occurrences of this root in the complete factorization of the polynomial, by means of the
fundamental theorem of algebra
A. Singularity in a Function C. Multiplicity of a Root .
B. Discontinuous Functions D. Incremental Search
6. Functions that are not a continuous curve - there is a hole or jump in the graph.
A. Singularity in a Function C. Multiplicity of a Root .
B. Discontinuous Functions D. Incremental Search
7. It is defined as a point where the function becomes infinite
A. Singularity in a Function C. Multiplicity of a Root .
B. Discontinuous Functions D. Incremental Search
8. To determine the number of roots within an interval, it is possible to use an ________________.
A. Singularity in a Function C. Multiplicity of a Root .
B. Discontinuous Functions D. Incremental Search
9. A Method in which if one limit is detected to be stuck, the function value of the stagnant point is divided by 2.
A. Singularity in a Function C. Modified False-Position Method
B. Discontinuous Functions D. Incremental Search
10. It is the fact that one limit may stay fixed during the computation,
A. Singularity in a Function C. Multiplicity of a Root .
B. Original False-Position Method D. Incremental Search