Next: Summary Up: Other Iterative Schemes Previous: Other Iterative Schemes

Convergence of Fixed-Point Iteration, Error Analysis

As in section 1.3.2, we use a Taylor series expansion to see how the error behaves from one step to another. Again we take

where is the exact value of the root, is the value of the iterate and is the error after iterations. Hence, fixed-point iteration can be written as

If is small we may expand the function in a Taylor series about . Hence,

However, remembering that the root is a fixed-point and so satisfies , the leading term in the Taylor series gives
 (1.15)

(1.15) shows us that fixed-point iteration is a first-order scheme provided . We can use (1.15) to see if the scheme converges or not.

Assume that the initial error is . Then (1.15) gives

Repeated use of (1.15) gives

From these first few terms it is clear that in general
 (1.16)

(1.16) shows us that
• the error reduces if , the scheme converges,

• the error increases if , the scheme diverges.
When the scheme converges we can see that
• the error decreases monotonically if ,

• the error decreases in an oscillatory manner if .

Example 1. .7Consider the previous example with . Using the scheme

we have

Thus,

and so the scheme converges.

However, if you use the scheme

we have

In this case we have

and the scheme does not converge.

Example 1. .8Consider . The roots are and . We will express in three different forms and test the convergence criterion for each form.

1. Express as . Hence, we have

Hence, and

Thus,
• , the scheme will NOT converge.

• , the scheme will converge to the root at .

2. Express as . Thus,

In this example and so

Thus,
• , the scheme converges to .

• , this scheme does not converge to .

3. Finally, express as , so that

Here we have and so

So the convergence condition gives
• so does not converge to .

• and again the iterative scheme does not converge.

Next: Summary Up: Other Iterative Schemes Previous: Other Iterative Schemes
Prof. Alan Hood
2000-02-01