Lecture 3: Fixed Point Iteration Method

To answer the questions 2 and 3 in lecture 2, we need to give the following corollary to know which functions to be rejected in examples.
Answer: Change the root-finding problem into a fixed point problem that satisfies the conditions of Fixed-Point Theorem and has a derivative that is as small as possible near the fixed point.

Fixed Point Theorem:
If g satisfies the existence and uniqueness theorems, then bounds for the error involved in using pn to approximate p are given by
| pn ? p| ? kn max{ p0 ? a, b ? p0}
and
| pn ? p| ?k^n/(1-k) | p1 ? p0|, for all n ? 1.
And the so convergence occurs for g(pn).

Example 2:
For g1(x) = x ? x3 ? 4x2 + 10, we have g1(1) = 6 and g1(2) = ?12, so g1 does not map [1, 2] into itself. Moreover, g’1(x) = 1 ? 3x2 ? 8x, so |g’1(x)| > 1 for all x in [1, 2]. So no convergence.
With g2(x) = [(10/x)? 4x]1/2, we can see that g2 does not map [1, 2] into [1, 2], and the sequence { pn} is not defined when p0 = 1.5(why!). So no convergence

For the function g3(x) = 1/2 (10 ? x3)1/2, we have
g3(1)=1.5 and g3(2)=0.7, so g3 doesn’t satisfy existence theorem.
Note: if we take the interval [1,1.5], we have
g3(1)=1.5 and g3(1.5)=1.28, and g3 is decreasing since
g 3(x) = ?3/4x2(10 ? x3)?1/2 <0
so, g3 satisfies existence theorem on [1,1.5].
|g’3(x)| ? |g’3(1.5)| ? 0.66 on [1,1.5].
So Fixed point Theorem confirms the convergence on [1,1.5].
For g4(x) = (10/(4 + x))1/2, we have
|g’4(x)| =|(-5)/(?10 (4 + x)^(3?2) )|<5/(?10 ?( 5)?^(3?2) ) < 0.15, for all x ? [1, 2].
Note: The bound of g4(x) is much smaller than the bound of g3(x), which explains the faster convergence using g4.