Fixed Point Method
Any function in the form of f ( x ) 0 can be manipulated as x g ( x ).
The root of the equation x g ( x ) is the point of intersection of the curves
x g(x) and 𝑦 = 𝑔(𝑥), Known as fixed point of y x
Conversion to fixed point:
Add x to both side Algebraic Manipulation
x2 x 2 0 x x 2 2 x 2. x2 x 2 0 x 2 x2 .
tan x 0 x tan x x .
xn 1 g ( xn ) n 1, 2,...
Geometrical Representation
1
Example Locate root of the equation x 2 x 2 0 using fixed point method.
The given equation can be expressed as x 2 x 2 .
Initial guess x0 0
x1 2 0 2
x2 2 4 2 -2 is one of the roots
x3 2 4 2
Initial guess x0 1
x1 2 1 1
1 is another of the roots
x2 2 1 1
2
Convergence of Fixed Point Iteration Method:
Let, xn1 g ( xn ) True value, xt g ( xt )
Therefore, xt xn1 g ( xt ) g ( xn )
g ( xt ) g ( xn )
According to Mean-value theorem, g ' ( R) , R ( xn , xt )
xt xn
This gives, g ( xt ) g ( xn ) g ' ( R)( xt xn )
en 1 xt xn1 g ' ( R )( xt xn ) en1 g ' ( R ) en
Note:
Error decreases if g ( R ) 1
'
Linear Convergence
Error grows if g ( R ) 1
'
If g ' ( R) is positive, the convergence is monotonic.
If g ' ( R) is negative, the convergence will be oscillatory. 3
Solution Existence:
Lemma: Let g(x) be a continuous function on the interval [a; b], and suppose it satisfies the property
a ≤ x ≤ b ⟹ a ≤ g(x) ≤ b
Then the equation x = g(x) has at least one solution α in the interval [a; b].
Proof: The proof of this is fairly intuitive. Look at the function
f (x) = x - g(x); a≤x≤b
Evaluating at the endpoints,
f (a) ≤ 0; f (b) ≥ 0
The function 𝑓(𝑥) is continuous on [a; b], and therefore it contains a zero in the interval.
4
Example 1: Consider the equation 𝑥 = 1 + 0.5 sin 𝑥.
Here, 𝑔 𝑥 = 1 + 0.5 sin 𝑥 .
Note that 0.5 ≤ g(x) ≤ 1.5 for any 𝑥 ∈ ℝ, and g(x) is a continuous function.
Applying the existence lemma, we conclude that the equation 𝑥 = 1 + 0.5 sin 𝑥
has a solution in [a; b] with a ≤ 0.5 and b ≥ 1.5.
Exercise 1: Show that the equation 𝑥 = 3 + 2 sin 𝑥 has a solution in [a; b] with a ≤ 1 and b ≥ 5.
Theorem: Assume 𝑔(𝑥) and 𝑔 (𝑥) exist and are continuous on the interval [a; b]; and further, assume
𝑎≤𝑥≤𝑏 ⟹ 𝑎 ≤ 𝑔(𝑥) ≤ 𝑏
𝜆 ≡ max 𝑔 (𝑥) < 1
Then,
S1. The equation 𝑥 = 𝑔(𝑥) has a unique solution 𝛼 in [a; b].
5
S2. For any initial guess 𝑥 in [a; b], the iteration
𝑥 =𝑔 𝑥 , 𝑛 = 0, 1, 2, …
will converge to the true value 𝛼.
S3. 𝛼−𝑥 ≤ 𝑥 −𝑥 , 𝑛≥0
S4. lim = 𝑔 (𝛼)
⟶
Thus for 𝑥 close to 𝛼, 𝛼−𝑥 ≈𝑔 𝛼 𝛼−𝑥 .
Proof: Home Task.
6
Example 2: Consider 𝐸1: 𝑥 = 1 + 0.5 sin 𝑥
Here, 𝑔 𝑥 = 1 + 0.5 sin 𝑥
We can take [a; b] with any a ≤ 0:5 and b ≥ 1:5.
Note that 𝑔 𝑥 = 0.5 cos 𝑥 , 𝑔 (𝑥) ≤
Therefore, we can apply the theorem and conclude that the fixed point iteration
𝑥 = 1 + 0.5 sin 𝑥 will converge for E1.
Home Task: Check for the solutions of
Example 3: Consider 𝐸2: 𝑥 = 3 + 2 sin 𝑥 Example 2 and Example 3 using Fixed-point
Iteration method.
Here, 𝑔 𝑥 = 3 + 2 sin 𝑥
Note that 𝑔 𝑥 = 2 cos 𝑥 , 𝑎𝑛𝑑 𝑔 𝛼 = 2 cos (3.094) = −1.998
Therefore, the fixed point iteration 𝑥 = 3 + 2 sin 𝑥 will diverge for E2.
7
