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.

1. Procedure

   The iteration procedure is as follows. In some way we obtain a rough approximation x₀ 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 3xe^x=1 to an accuracy of 4D.

   One first writes

   

   Assuming x₀ = 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.

2. 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 x₀. For example, thc equation x² = 3 has two real roots: . It can be rewritten in the form

   

   which suggests the iteration

   

   However, if the starting value x₀ = 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 x_k. 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 x₀ = 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.