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)