CONVERGENCE

Notice that the true percent relative error for each iteration of Example is roughly proportional,(by a factor of about 0.5 to 0.6) to the error from the previous iteration. This property, called linear convergence, is characteristic of fixed-point iteration. 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. Recall that in , we graphed a function to visualize its structure and behavior. Such an approach is employed for the function

f(x) =(e^(-x) – x).

 An alternative graphical approach is to separate the equation into two component parts, as in

 f1(x) =f2(x)

Then the two equations

 Y1 = f1(x)                and

y2= f2(x)

can be plotted separately .

The x values corresponding to the intersections of these functions represent the roots of f(x) = O.

The two-curve method can now be used to illustrate the convergence and divergence of tixed-point iteration. First, can be fe-expressed as a pair of equations y1 = x and Y2 = g(x). These two equations can then be plotted separately. As was the case with and the r00tS of f(x) = 0 cOrrespond to the abscissa value at the intersection of the two curves. The function Y1 = x and four different shapes for Y2 = g(x) are plotted in For the first case, the initial guess of Xo is used to determine the corresponding point on the Y2 curve [xo. g(xo)].

 The point (X1, X1) is located by moving left horizontally to the Y I curve. These movements are equivalent to the first iteration in the fixed-point method:

 X I = g(xo)

 Thus, in both the equation and in the plot, a starting value of xo is used to-obtain an estimate of X1., The next iteration consists of moving to [Xl, g(xl)] and then to (X2, X2), This iteration is equivalent to the equation X2 = g(x1) The solution is convergent because the estimates of x move closer root with each iteration, where the iterations diverge from the root. Notice that Convergence seems to occur only when the absolute value of the slope of Y2=g(x) is less than the slope of Y1 =x, that is, when g’(x) < 1 . Box provides a theoretical derivation of this result.

X2 =g(X1)

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-poil1t iteration (or, as it is also called, one-point iteration or successive substitution) by rearranging the function f(x) = 0 so that x is or side of the equation: x=g(x) This transformation can be accomplished either by algebraic manipulation or by simply adding x to both sides of the original equation.

For example, x^2-2x+3=0 Can be simply manipulated to yield .

 x=(x^2+3)/2

 Whereas sin x=0 could be put into the form of equation by adding x to both sides to yield X=sin x +x The utility of Equation is that it 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 Xi, can be used to compute a new estimate Xi+l as expressed by the iterative formula x_(i+1)=g(x_i) As with other iterative formulas in this book, the approximate error for this equation can be determined using the error estimator :

 ε=(x_(i+1)-x_i)/x_(i+1)

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.