Dr. Mohammad H.

Alaroud MATH 322

Section 2.2: Fixed-Point Iteration

Definition. We say that 𝑝 a fixed-point for 𝑔 if 𝑔(𝑝) = 𝑝.

Example. Determine the fixed points of 𝑔(𝑥) = 𝑥 2 − 2.

Solution. We have
𝑔(𝑥) = 𝑥 ⟺ 𝑥 2 − 2 = 𝑥 ⟺ 𝑥 2 − 𝑥 − 2 = 0 ⟺ 𝑥 = −1 , 2.

So, the fixed points are 𝑝 = −1 and 𝑝 = 2.

Definition. 𝑔 is called self-mapping on [𝑎, 𝑏] if

𝑎 ≤ 𝑔(𝑥) ≤ 𝑏 ∀𝑥 ∈ [𝑎, 𝑏].

Definition. 𝑔 is called contraction on [𝑎, 𝑏] if there is a constant 𝑘 < 1 such that

|𝑔′ (𝑥)| ≤ 𝑘 ∀𝑥 ∈ (𝑎, 𝑏).

Theorem 1. [Existence and Uniqueness]

(𝐢) If 𝑔 is continuous and self-mapping on [𝑎, 𝑏], then 𝑔 has at least one fixed-point in
[𝑎, 𝑏].

(𝐢𝐢) In addition, if 𝑔 is also a contraction on [𝑎, 𝑏], then 𝑔 has a unique fixed-point in
[𝑎, 𝑏].
1
Dr. Mohammad H. Alaroud MATH 322

Proof. The proof is an immediate consequence of the Intermediate and Mean Value
theorems. See the textbook.

Example 1. Show that the given function has a unique fixed-point on the given interval.
1
(𝐚) 𝑔1 (𝑥) = (𝑥 2 − 1) , − 1 ≤ 𝑥 ≤ 1.
3
Solution. Clear 𝑔1 is continuous on [−1, 1]. Now
2
𝑔1′ (𝑥) = 𝑥
3
and so, 𝑥 = 0 is the only critical point. Since
1
𝑔1 (−1) = 0, 𝑔1 (0) = − , 𝑔1 (1) = 0
3
we have
1
− ≤ 𝑔1 (𝑥) ≤ 0 ∀𝑥 ∈ [−1, 1] ⟹ −1 ≤ 𝑔1 (𝑥) ≤ 1 ∀𝑥 ∈ [−1, 1],
3
Hence 𝑔1 is self-mapping on [−1, 1]. Moreover
2 2 2
|𝑔1′ (𝑥)| = | 𝑥| = |𝑥| ≤ < 1 ∀𝑥 ∈ (−1, 1)
3 3 3
and so, 𝑔1 is contraction on [−1, 1] with 𝑘 = 2/3. By Theorem 1, 𝑔1 has exactly one
fixed point in [−1, 1].
1
(𝐛) 𝑔2 (𝑥) = (𝑥 2 − 1), 3 ≤ 𝑥 ≤ 4.
3
Solution. Notice Theorem 1 is not applicable here for two reasons:

(1) 𝑔2 is not self-mapping on [3, 4]: for instance, 𝑔2 (3.9) = 4.74 ∉ [3, 4].
2
(2) 𝑔2 is not contraction on [3, 4]: for instance, |𝑔2′ (3.9)| = ( ) (3.9) = 2.6 > 1.
3

However, 𝑔2 has a unique fixed in [3, 4]:

1 1
𝑔2 (𝑥) = 𝑥 ⟺ (𝑥 2 − 1) = 𝑥 ⟺ 𝑥 2 − 3𝑥 − 1 = 0 ⟺ 𝑥 = (3 + √13) = 3.3 ∈ [3, 4].
3 2

2
Dr. Mohammad H. Alaroud MATH 322
−𝑥
(𝐜) 𝑔3 (𝑥) = 3 , 0 ≤ 𝑥 ≤ 1.

Solution. Since 𝑔3 is decreasing, we have

1
𝑔3 (1) ≤ 𝑔3 (𝑥) ≤ 𝑔3 (0) ⟹ ≤ 𝑔3 (𝑥) ≤ 1 ∀𝑥 ∈ [0, 1].
3
So 𝑔3 is self-mapping on [0, 1].

Since 𝑔3′ (𝑥) = −3−𝑥 ln 3, we see that

|𝑔3′ (0.01)| = 1.09 > 1,

and so 𝑔3 is not contraction. This means Theorem 1 does not apply.

However, the graph of 𝑦 = 𝑔3 (𝑥) intersects the line 𝑦 = 𝑥 only once. Therefore, 𝑔3 has
one and only one fixed point 𝑝 in [0, 1] located at the point of intersection.

Remark. The above examples show that Theorem 1 gives only sufficient but not
necessary conditions for existence and uniqueness.

Next question: how to approximate the fixed-point?

3
Dr. Mohammad H. Alaroud MATH 322

➢ Fixed-Point Iteration: Motivation

Let 𝑝0 be some initial approximation. Consider the recursive iteration

𝑝𝑛 = 𝑔(𝑝𝑛−1 ).

Assume that the sequence {𝑝𝑛 } = {𝑝0 , 𝑝1 , 𝑝2 , … } converges to a number 𝑝 that is 𝑝𝑛 → 𝑝.

If 𝑔 is continuous then

𝑝 = lim 𝑝𝑛 = lim 𝑔(𝑝𝑛−1 ) = 𝑔 ( lim 𝑝𝑛−1 ) = 𝑔(𝑝).

𝑛→∞ 𝑛→∞ 𝑛→∞

Thus, 𝑝 must be a fixed-point of 𝑔.

Fixed-Point Iteration: Start with initial guess 𝑝0 , then compute approximations via the
functional iteration
𝑝𝑛 = 𝑔(𝑝𝑛−1 ), 𝑛 = 1, 2, 3, …

Example. Consider the function 𝑔(𝑥) = 1 + 𝑥 −1 , 1.25 ≤ 𝑥 ≤ 2. If we take 𝑝0 = 1.5, then

5
Iteration 1: 𝑝1 = 𝑔(𝑝0 ) = = 1.666 …
3
8
Iteration 2: 𝑝2 = 𝑔(𝑝1 ) = = 1.6
5
13
Iteration 3: 𝑝3 = 𝑔(𝑝2 ) = = 1.625
8
21
Iteration 4: 𝑝4 = 𝑔(𝑝3 ) = = 1.61538
13

etc…
1
Exact fixed point: 𝑝 = (1 + √5) = 1.6180339 (Homework)
2

We have the following important result regarding the convergence and error bound.

Fixed-Point Theorem:

Suppose that 𝑔 is continuous, self-mapping, and contraction on [𝑎, 𝑏], and 𝑝0 ∈ [𝑎, 𝑏].

(𝐢) The sequence 𝑝𝑛 = 𝑔(𝑝𝑛−1 ) converges to the unique fixed point 𝑝 ∈ [𝑎, 𝑏].
4
Dr. Mohammad H. Alaroud MATH 322

(𝐢𝐢) The error bound holds:

𝑘𝑛
|𝑝𝑛 − 𝑝| ≤ |𝑝 − 𝑝0 |, 𝑛 ≥ 1.
1−𝑘 1
Let us examine some applications.

Example. Consider the function 𝑔(𝑥) = 1 + 𝑥 −1 , 1.25 ≤ 𝑥 ≤ 2.

(a) Show that 𝑔 has a unique fixed point 𝑝 ∈ [1.25, 2].

(b) Find an approximation to 𝑝 accurate to within 10−2 if 𝑝0 = 1.5.

Solution. (a) I will leave it as an exercise.

(b) We have
1 1 5
|𝑔′ (𝑥)| = ≤ = 0.64 ≡ 𝑘 and 𝑝1 = 𝑔(𝑝0 ) = .
𝑥 2 (1.25)2 3

From the error bound, we can determine the required number of iterations:
𝑘𝑛 −2
(0.64)𝑛 5 3
|𝑝𝑛 − 𝑝| ≤ |𝑝1 − 𝑝0 | ≤ 10 ⟹ | − | ≤ 10−2 ⟹ 𝑛 ≥ 8.6.
1−𝑘 1 − 0.64 3 2
Therefore, we need at least 9 iterations to ensure that the error is less than 10−2 .
5
Iteration 1: 𝑝1 = 𝑔(𝑝0 ) = = 1.666 …
3
8
Iteration 2: 𝑝2 = 𝑔(𝑝1 ) = = 1.6
5
13
Iteration 3: 𝑝3 = 𝑔(𝑝2 ) = = 1.625
8
21
Iteration 4: 𝑝4 = 𝑔(𝑝3 ) = = 1.61538
13

⋮
21
Iteration 9: 𝑝9 = 𝑔(𝑝8 ) = = 1.61806
13

Exact: 𝑝 = 1.6180339

Remark. Note the actual error is |𝑝9 − 𝑝| = 2 × 10−5 which is much less than 10−2 .
5