Numerical

Technique
(MA-201)
Numerical Technique (MA-201)
Prof. S.
Mukhopadhyay Lecture Note-9
Fixed-Point
Iteration
Method
by
Method for
finding solution Prof. Santwana Mukhopadhyay
g(x ) = x

Convergence
Result for
Department of Mathematical Sciences
Fixed-Point IIT(BHU), Varanasi
Iteration
Method
 Fixed-Point Iteration Method

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay
Contents
Fixed-Point
Iteration
Method

Method for
finding solution
1 Fixed-Point Iteration Method
g(x ) = x

Convergence
Result for
Fixed-Point 2 Method for finding solution g(x ) = x
Iteration
Method

3 Convergence Result for Fixed-Point Iteration Method

 Fixed-Point Iteration Method

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay

Fixed-Point Introduction
Iteration
Method In fixed point iteration method, search for a solution of
Method for
finding solution
nonlinear equation f (x ) = 0 is replaced by search for a fixed
g(x ) = x point of a function g(x ), and with the property that if αR is
Convergence
Result for
a fixed point of g (i.e., g(α) = α), then f (α) = 0.
Fixed-Point
Iteration In general, there may be more than one choice of g with
Method
this property.

.
 Examples

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay

Fixed-Point Example. 1
Iteration
Method

Method for
finding solution Note that αR is a solution of the equation x 2 − x − 2 = 0 if
g(x ) = x
and only if α is a solution of each of the following equations.
Convergence
Result for 1 x = x 2 − 2, by choosing g(x ) = x 2 − 2
Fixed-Point
Iteration
√ √
Method 2 x = x + 2, implying g(x ) = x + 2
3 x = 1 + x2 , implying g(x ) = 1 + 2
x
 Method for finding solution of g(x ) = x

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay
The fixed-point iteration method
Fixed-Point
Iteration The fixed-point iteration method for finding a solution of
Method

Method for
g(x ) = x consists of a sequence of iterations {xn }, starting
finding solution from an initial guess x0 , defined by
g(x ) = x

Convergence
Result for
Fixed-Point
xn = g(xn−1 ) (2.1)
Iteration
Method

The crucial point in this method is to choose a good

iteration function g(x ).
 Properties of a good iteration function :

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay
Properties of g(x)
Fixed-Point
Iteration
Method 1 For the given starting point x0 , the successive
Method for
finding solution
approximations xn as (2.1) can be calculated.
g(x ) = x
2 The sequence x1 , x2 , ... converges to some point ξ.
Convergence
Result for
Fixed-Point
3 The limit ξ is a fixed point of g(x ),, i.e., ξ = g(ξ).
Iteration
Method
Remark
Not every iteration function has all these properties.
 Assumptions on the iterative function

Numerical
Technique
(MA-201)
Assumptions on the iterative function
Prof. S.
Mukhopadhyay
In order to have g(x) satisfying above properties, the following
Fixed-Point assumpsions are needed:
Iteration
Method 1 a ≤ g(x ) ≤ b for all a ≤ x ≤ b.
Method for
finding solution 2 The iterative function g(x ) is continuous.
g(x ) = x

Convergence
3 The iteration function g(x ) is differentiable on I = [a, b].
Result for Further, there exists a constant 0 < K < 1 such that
Fixed-Point
Iteration
Method
g 0 (x ) ≤ K , x I. (2.2)

4 Such a function is called the contraction map.

 Convergence Result for Fixed-Point Iteration
Method
Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay
Hypothesis:
Fixed-Point
Iteration Let the iterative function g(x) be chosen so that
Method

Method for 1 g is defined on the interval [a, b] and a ≤ g(x ) ≤ b. That

finding solution
g(x ) = x is, g is a self map on [a, b].
Convergence
Result for
2 g is continuously differentiable on [a, b].
Fixed-Point
Iteration 3 g is a contraction map. That is,
Method

λ = max g 0 (x ) < 1 (3.1)

a≤x ≤b
 Numerical Conclusion Theorem
Technique
(MA-201) Then
Prof. S.
Mukhopadhyay
1 x = g(x ) has a unique solution r in [a, b].
2 For any choice of x0 [a, b], with xn+1 = g(xn ),
Fixed-Point
Iteration n = 0, 1, 2..
Method
Lim xn = r .
Method for n
∞
finding solution
g(x ) = x 3 We further have
Convergence
Result for
λn
Fixed-Point
Iteration xn − r ≤ λn x0 − r ≤ x1 − x0 (3.2)
Method 1−λ
r − xn+1
Lim = g 0 (r ) (3.3)
n
∞ r − xn
 Proof

Numerical
Technique
(MA-201)
Proof
Prof. S.
Mukhopadhyay From mean-value theorem and Eq.(2.2), we have
Fixed-Point
Iteration r − xn+1 = g(r ) − g(xn ) ≤ λ r − xn (3.4)
Method

Method for By induction, we have

finding solution
g(x ) = x
r − xn+1 = λn x0 − r , n = 0, 1, , ..
Convergence
Result for
Fixed-Point
Iteration
Since, as n → ∞, λn → 0, we have xn → r . Further, we have
Method

x0 − r = x0 − x1 + x1 − r
≤ x0 − x1 + x1 − r
≤ λ x0 − r + x0 − x1
 Proof cont...

Numerical
Technique
(MA-201)
Proof
Prof. S.
Mukhopadhyay Then solving for x0 − r , we get (3.2).
Fixed-Point Now we will prove the rate of convergence (3.3). From
Iteration
Method Mean-value theorem
Method for
finding solution
g(x ) = x

Convergence
r − xn+1 = g(r ) − g(xn ) = g 0 (ξn )(r − xn ), n = 0, 1, ..
Result for
Fixed-Point
Iteration with ξn an unknown point between r and xn . Since xn → r , we
Method
must have ξn → r and therefore,
r − xn+1
lim = lim g 0 (ξn ) = g 0 (r ).
n→∞ r − xn n→∞
 Example

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay

Fixed-Point
Iteration
Method
Example
Method for
finding solution
Consider the equation
g(x ) = x

Convergence Sinx + x 2 − 1 = 0
Result for
Fixed-Point
Iteration
Method
 Example

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay

Fixed-Point
Iteration Ex.
Method

Method for
Take the initial interval as [0, 1]. There are three possible
finding solution
g(x ) = x
choices for the iteration function, namely,
Convergence 1 g1 (x ) = sin−1 (1 − x 2 ),
Result for √
Fixed-Point 2 g2 (x ) = − 1 − Sinx ,
Iteration
Method
√
3 g3 (x ) = 1 − Sinx .
 Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay

Fixed-Point
Taking x0 = 0.8 and denoting the absolute error as , we have
Iteration n g1 (xk ) 
Method

Method for
0 0.368268 0.268465
finding solution
g(x ) = x
1 1.043914 0.407181 with Exact root as 0.636733
Convergence
2 −0.089877 0.726610
Result for
Fixed-Point
3 1.443606 0.806873
Iteration The sequence of iterations is diverging as expected as we can
Method
see that g1 (x ) does not satisfy criteria of the hypothesis of
fixed point iteration scheme.
 ex..cont..

Numerical
Technique
(MA-201)
If we take g2 (x ), clearly the assumption 1 is violated and
Prof. S.
Mukhopadhyay therefore is not suitable for the iteration process.
Let us take g3 (x ). Here, we have
Fixed-Point
Iteration
Method −Cosx
Method for
g30 (x ) = √
finding solution 1 − Sinx
g(x ) = x

Convergence Therefore
Result for
Fixed-Point √
Iteration 1 − Sin2 x
Method g30 (x ) = √
2 1 − Sinx
√
1 + Sinx
=
2
1
≤ √ < 1.
2
 Numerical
exam cont...
Technique
(MA-201) Taking x0 = 0.8 and denoting the absolute error as , we have
Prof. S. n g1 (x ) 
Mukhopadhyay
0 0.531643 0.105090
Fixed-Point 1 0.702175 0.065442
Iteration
Method 2 0.595080 0.041653
Method for 3 0.662891 0.026158
finding solution
g(x ) = x

Convergence The sequence is converging.

Result for
Fixed-Point
Iteration
Method
 Task

Numerical
Technique
(MA-201)

Prof. S.
Mukhopadhyay
1. For each of the following equations, determine a function a g(x ) and an interval [a,b] on which
Fixed-Point fixed-point iteration will converge to a positive solution of the equation :
Iteration (a)f (x ) = 3x 2 − e x
Method (b) x − cosx = 0.7
2. Find the zero of f (x ) = x 2 + 10cosx by using the fixed-point iteration method for an appropriate
Method for iteration function g(x).
finding solution
g(x ) = x 3.Find the iterative methods based on the Newton-Raphson method for finding N, 1/N, N 1/3 , where N is a
positive real number. Apply the methods to N = 18 to obtain the results correct to two decimal places.
Convergence 4. The equation x = f (x ) is solved by the iteration method xk+1 = f (xk ), and a solution is wanted with a
Result for maximum error not greater than 0.5 × 10–4 . The first and second iterates were computed as :
Fixed-Point x1 = 0.50000 and x2 = 0.52661. How many iterations must be performed further, if it is known that
Iteration |f 0(x )| ≤ 0.53 for all values of x .
Method *****************