   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