The method of simple iteration

The method of simple iteration involves writing the equation f(x) = 0 in a form suitable for the construction of a sequence of approximations to some root, in a repetitive fashion.

Procedure

The iteration procedure is as follows. In some way we obtain a rough approximation x0 of the desired root, which may then be substituted into the right-hand side to give a new approximation, . The new approximation is again substituted into the right-hand side to give a further approximation , and so on until (hopefully) a sufficiently accurate approximation to the root is obtained. This repetitive process, based on , is called simple iteration; provided that decreases as n increases, the process tends to . where denotes the root.

EXAMPLE

The method of simple itcration will be used to find the root of the equation 3xex=1 to an accuracy of 4D.

One first writes

Assuming x0 = 1 and with numbers displayed to 5D, successive iterations

We see Ihat after eight iterations the root is 0.2576 to 4<I>D</I>. A graphical interpretation of the first three iterations is shown in Figure

FIGURE 8. Iterative method.

1.      Convergence

Whether or not an iteration procedure converges quickly, or indeed at all, depends on the choice of the function , as well as the starting value x0. For example, thc equation x2 = 3 has two real roots: . It can be rewritten in the form

which suggests the iteration

However, if the starting value x0 = 1 is used, successive iterations yield

so that there is no convergence!

We can examine the convergence of the iteration process

to with the help of the Taylor series (cf. STEP 5]

where is a value between the root and the approximation xk. We have

Multiplying the n + 1 rows together and cancelling the common factors leaves

,

Consequently,

so that the absolute error can be made as small as we please by a sufficient number of iterations, if of the root. (Note that the derivative of is such that

CHECKPOINT

1. What should a programmer guard against in a computer prgram using the method of simple iteration?
2. What is necessary to ensure that the method of simple iteration does converge to a root?

EXERCISES

1. Assuming that the initial guess is x0 = 1, show by the method of simple iteration that one root of the equation 2x - 1 - 2sinx = 0 is 1.4973.
2. Use the method of simple itteration to find to 4 D the root of the equation x + cosx.
3. Use the method of simple iteration to find to 3 D the root of the equation in Exercise 2,2 of STEP6.

http://mpec.sc.mahidol.ac.th/numer/STEP9x.HTM. 07/06/2012