   Next: Convergence of Fixed-Point Iteration, Up: Solutions of Equations Previous: Summary of Newton-Raphson

# Other Iterative Schemes

The Newton-Raphson method is an iterative scheme of the general form where It is possible to construct other iterative schemes that have a similar form to this by rearranging the equation F(x) = 0 into the form Then a possible iterative scheme is (1.14)

Will (1.14) converge to the root of the function ? If we can show that then so does Thus, is a solution to and so Thus, is a root of . is called a fixed point of the function . The advantage of this approach is that it is easy to obtain an iterative scheme of the form (1.14) but the problem is that not all schemes converge.

Example 1. .6Consider Since we are looking for the value of that makes we can set If we can find the value of that makes the left hand side equal the right hand side, then we have found the root of the original function . So we try as our iterative scheme Here we have chosen . The iterations, assuming an initial guess of , are shown in Table 1.5.

 n   0 1 0.4329 1 0.3679 0.1993 0.4603 2 0.6922 0.1251 0.6276 3 0.5005 0.0667 0.5331 4 0.6062 0.0391 0.5865 5 0.5454 0.0217 0.5562

Looking at the first two columns we see that the method is converging but only very slowly. If fact we would need 24 iterations to get an answer as accurate as the one obtained by 4 iterations with the Newton-Raphson method. The root obtained by Newton-Raphson is approximately given by Using this value, the absolute value of the absolute error is calculated in column 3 and it is clear that the error is reducing as more and more iterations are used. The final column takes the ratio of two successive absolute errors. There is an indication that the ratio is tending towards a constant value. Thus, where the constant of proportionality is about 0.56.

This fixed-point iteration scheme is illustrated in Figure 1.4. Taking the initial guess , we obtain the value of . This means we move from the -axis at up to the curve . From this curve, we move horizontally until we meet the line and this value of is the next estimate . This procedure is repeated, move up to the curve and then move along to the line to get the next estimate.

Note that we could rearrange the function in the following manner. Hence, another fixed-point iterative scheme is but this does not converge. To understand why we need to perform an error analysis for fixed-point iteration.

Subsections   Next: Convergence of Fixed-Point Iteration, Up: Solutions of Equations Previous: Summary of Newton-Raphson
Prof. Alan Hood
2000-02-01