Scribd
Upload
279 views25 pages

Fixed Point Algorithm

The document discusses fixed point iteration, which is a method for finding the roots of an equation or the fixed points of a function. It defines fixed points as numbers where a function is equal to itself. An example is provided of finding the fixed points of the function g(x)=x^2-2. The document then explains that a fixed point problem can be constructed from a root finding problem by defining an iteration function g(x). It provides an example of using fixed point iteration to find the smallest positive root of cos(x)-x=0. The importance of choosing an appropriate iteration function g(x) is also discussed.

Uploaded by

SakshamJain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
279 views25 pages

Fixed Point Algorithm

The document discusses fixed point iteration, which is a method for finding the roots of an equation or the fixed points of a function. It defines fixed points as numbers where a function is equal to itself. An example is provided of finding the fixed points of the function g(x)=x^2-2. The document then explains that a fixed point problem can be constructed from a root finding problem by defining an iteration function g(x). It provides an example of using fixed point iteration to find the smallest positive root of cos(x)-x=0. The importance of choosing an appropriate iteration function g(x) is also discussed.

Uploaded by

SakshamJain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

FIXED POINT ITERATION

By Raj Nandkeolyar

BACKGROUND
Definition: A number p is said to be a fixed point
of a function g(x) defined on [a, b] if g(p) = p for
some
.
p [ a, b]
For example:
1. g(x) = x2 has two fixed points x = 0 and x = 1.
2. g(x) = 1/x has two fixed points x = 1 and x = -1.
3. g(x) = x2 2 has two fixed points x = -1 and 2.

Definition: The problem of finding the fixed


points of a function g(x) is called a fixed point
problem.

FINDING FIXED POINTS AND


GEOMETRICAL INTERPRETATION
Find the fixed points of the function g(x) = x2 2.
Solution: Let p be the fixed point of g(x), then by
the definition of fixed points:

g ( p) p
p2 2 p
p2 p 2 0
p 1, 2

7
6
5
4
3
2
1
0
-1
-2
-3
-3

-2

-1

FIXED POINT ITERATION


In the previous example we have seen that the fixed
points of g(x) are the roots of the equation x
g(x) = 0,
or, f(x) = 0.
Conversely, the problem of finding the roots of the
2
equation x x 2 0 is equivalent to the fixed
2
point problem x g ( x ) x 2.
Thus, for a given root finding problem f(x) = 0 we
can construct a corresponding fixed point
problem x = g(x), such that the solution of both
the problems are same.

7
6
5
4
3
2
1
0
-1
-2
-3
-3

10
-2

-1

Graph of y = x, and y = g(x)

8
6
4
2
0
-2
-4
-3

-2

-1

Graph of f(x)=x2 -x-2

AN EXAMPLE OF FIXED POINT


ITERATION

Example:

Solve the following equation for the smallest positive root


cos x x 0
Solution:
Write x = cosx
such that g(x) = cosx

x1

x0

xn 1 g ( xn ), n 0, 1, 2,...

FIXED POINT ITERATION SCHEME


For the root finding problem f(x) = 0,
We write the corresponding fixed point problem
x = g(x)
Then the fixed point iteration scheme is given by

xn 1 g ( xn ), n 0, 1, 2,...

CHOICE OF ITERATION FUNCTION


Finding a suitable iteration function g(x) is
critical:
Example: Find the smallest positive root of the
equation x2 - 2x +1 = 0
Solution:
Writing x 2 x 1 ( g ( x))
Such that xn 1 2 xn 1, n 0, 1, 2,...
Taking x0 = 0.8, we obtain

x1 = 0.7746,
x2 = 0.7411,
x3 = 0.6944The sequence of iterates is diverging

2.5

1.5

0.5

0.5

1.5

2.5

x2 1
Writing
x
2
We obtain the scheme:
2

xn 1
xn 1
, n 0, 1, 2,...
2
Taking x0 = 0.8, we obtain
x1 = 0.82,
x2 = 0.8362,
x3 = 0.8496,
x4 = 0.8609,
x5 = 0.8706,
The sequence of iterates is approaching towards the
exact root x = 1.

5
4
3
2
1
0
-1
-2
-3
-3

-2

-1

Assumption 1: g(x) is defined on [a, b]

Assumption 2 : g ( x) [ a, b] for all x [a, b]

Conclusion: g(x) has a fixed point in [a, b]

You might also like