OPEN METHODS

For the bracketing methods in the previous chapter, the root is located within an interval prescribed by a lower and an upper bound. Repeated application of these methods always results in doser estimates of the true value of the root.

Such methods are said to be convergent because they move closer to the truth as the computation progresses. For the contrast, the open methods described in this chapter are based on formulas that require only a single starting value of x 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 lhan the bracketing methods. We will begin ours discussion of open techniques with a simple version that is useful for illustrating their general form and also for demonstrating the concept of convergence.

Pitfalls of the False-Position Method

Although the false-position method would seem to always be the bracketing method of Preference, there are cases where it performs poorly. In fact, as in the following example, there are certain cases where bisection yields superior results.

THE FALSE-POSITION METHOD

Although bisection is a perfectly valid technique for determining roots, its “brute-force” approach 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 Xl to Xu into equal halves, no account is taken of the magnitudes of f(Xl) and f(xu). For example, if f(Xl) is much closer to zero than f(xu), it is likely that the root is closer to xl than to Xu. An alternative method that exploits this graphical insight is to join f(Xl) and f(Xu) by a straight line. 

The intersection of this line with the x axis represents an improved estimate of the root. The fact that the replacement of the curve by a straight line gives a “false position” of the root is the origin of the name, method of false position, or in Latin. Regula falsi. It is also called the linear interpolation method.

THE BISECTION METHOD

In general, if f(x) is real and continuous in the interval from Xl to XU and f(xl) and f(xU) have opposite signs, that is, . f(xl)*f(xU ) < 0 then there is at least one real root between Xl and Xu. Incremental search methods capitalize on this observation by locating un interval where the function changes sign.

 Then the location of the sign change (and consequently, the root) is identified more precisely by dividing the interval into a number of subintervals Each of these subinterval s is searched to locate the sign change. The process is repeated and the root estimate refined by dividing the subintervals into finer increments. 

The bisection method, which is alternatively called binary chopping, interval halving, or Bolzano’s method, is one type of incremental search method in which the interval is always divided in half. If a function changes sign over an interval, the function value at the midpoint is evaluated.

 The location of the root is then determined as lying at the midpoint of the subinterval within which the sign change occurs. The process is repeated to obtain refined estimates.

GRAPHICAL METHODS

A simple method for obtaining an estimate of the root of the equation f(x) = 0 is to make a plot of the function and observe where it crosses the x axis. This point, which represents the x value for which f(x) = 0, provides a rough approximation of the root.

BRACKETING METHODS

This chapter on roots of equations deals with methods that exploit the. fact that a fuction typically changes sign in the vicinity of a root. These techniques are called bracketing methods because two initial guesses for the root are required. As the name implies, these guesses must "bracket," or be on either side of. the foal.

 The particular methods described herein employ different strategies to systematically reduce the width of the bracket and hence, home in on the correct answer. As a prelude to these techniques, we will briefly discuss graphical methods for depicting functions and their roots.

 Beyond their utility for providing rough guesses, graphical techniques are also useful for visualizing the properties of the functions and the behavior of the various numerical methods.

ROOTS OF EQUATIONS

The purpose of calculating the roots of an equation is to determine the values of x for which holds:

f (x) = 0 (28)

The determination of the roots of an equation is one of the oldest problems in mathematics and there have been many efforts in this regard. Its importance is that if we can determine the roots of an equation we can also determine the maximum and minimum, eigenvalues of matrices, solving systems of linear differential equations, etc ...

The determination of the solutions of equation (28) can be a very difficult problem. If f (x) is a polynomial function of grade 1 or 2, know simple expressions that allow us to determine its roots. For polynomials of degree 3 or 4 is necessary to use complex and laborious methods. However, if f (x) is of degree greater than four is either not polynomial, there is no formula known to help identify the zeros of the equation (except in very special cases).

There are a number of rules that can help determine the roots of an equation:

• Bolzano's theorem, which states that if a continuous function, f (x) takes on the ends of the interval [a, b] values of opposite sign, then the function accepts at least one root in that interval.

• In the case where f (x) is an algebraic function (polynomial) of degree n and real coefficients, we can say that will have n real roots or complex.

• The most important property to verify the rational roots of an algebraic equation states that if p / q is a rational root of the equation with integer coefficients:

then the denominator q divides the coefficient a and the numerator p divides the constant term a0.

Example: We intend to calculate the rational roots of the equation:

3x3 3x2 - x - 1 = 0

First, you make a change of variable x = y / 3:

and then multiply by 32:

3y2 y3-3y = -90

with candidates as a result of the polynomial are:

Substituting into the equation, we obtain that the only real root is y = -3, that is to say, (which is also the only rational root of the equation). Logically, this method is not as effective, so we can serve only as guidelines.

Most of the methods used to calculate the roots of an equation are iterative and are based on models of successive approximations. These methods work as follows: from a first approximation to the value of the root, we determine a better approximation by applying a particular rule of calculation and so on until it is determined the value of the root with the desired degree of approximation.