STEP 9

NONLINEAR EQUATIONS

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, http://mpec.sc.mahidol.ac.th/numer/STEP91a.gif. The new approximation is again substituted into the right-hand side to give a further approximation http://mpec.sc.mahidol.ac.th/numer/STEP93a.gif, and so on until (hopefully) a sufficiently accurate approximation to the root is obtained. This repetitive process, based on http://mpec.sc.mahidol.ac.th/numer/STEP96.gif, is called simple iteration; provided that http://mpec.sc.mahidol.ac.th/numer/STEP95a.gifdecreases as n increases, the process tends to http://mpec.sc.mahidol.ac.th/numer/STEP96.GIF. where http://mpec.sc.mahidol.ac.th/numer/STEP96a.GIFdenotes 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

http://mpec.sc.mahidol.ac.th/numer/STEP99.GIF

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

http://mpec.sc.mahidol.ac.th/numer/STEP910.GIF

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

http://mpec.sc.mahidol.ac.th/numer/STEP911.GIF

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 http://mpec.sc.mahidol.ac.th/numer/STEP912.GIF, as well as the starting value x0. For example, thc equation x2 = 3 has two real roots: http://mpec.sc.mahidol.ac.th/numer/STEP913.GIF. It can be rewritten in the form

http://mpec.sc.mahidol.ac.th/numer/STEP914.GIF

which suggests the iteration

http://mpec.sc.mahidol.ac.th/numer/STEP915.GIF

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

http://mpec.sc.mahidol.ac.th/numer/STEP916.GIF

so that there is no convergence!

We can examine the convergence of the iteration process

http://mpec.sc.mahidol.ac.th/numer/STEP917.GIF

to http://mpec.sc.mahidol.ac.th/numer/STEP96a.GIFwith the help of the Taylor series (cf. STEP 5]

http://mpec.sc.mahidol.ac.th/numer/STEP918.GIF

where http://mpec.sc.mahidol.ac.th/numer/STEP919.GIFis a value between the root http://mpec.sc.mahidol.ac.th/numer/STEP96a.GIFand the approximation xk. We have

http://mpec.sc.mahidol.ac.th/numer/STEP921.GIF

Multiplying the n + 1 rows together and cancelling the common factors http://mpec.sc.mahidol.ac.th/numer/STEP923.GIFleaves

, http://mpec.sc.mahidol.ac.th/numer/STEP924.GIF

Consequently,

http://mpec.sc.mahidol.ac.th/numer/STEP925.GIF

so that the absolute error http://mpec.sc.mahidol.ac.th/numer/STEP926.GIFcan be made as small as we please by a sufficient number of iterations, if http://mpec.sc.mahidol.ac.th/numer/STEP927.GIFof the root. (Note that the derivative of http://mpec.sc.mahidol.ac.th/numer/STEP928.GIFis such that http://mpec.sc.mahidol.ac.th/numer/STEP929.GIF

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