Fixed Point Method: What you need to know
In this article, I will clarify how fixed point iteration works by example. This article could be considered as lecture notes of my YouTube lecture you see above The one and only thing to keep in mind is that the fixed point iteration solves almost any function (given some conditions which we state in the fixed point theorem below) of the form
Firstly, the magical trick here is no matter how ugly your function looks like, we can almost always write the equation as
. For example,
could be written as
.
Fixed Point Method in Action
OK so now what ? Well, the fixed point method states that, under some conditions (see the fixed point theorem below), we can converge to the root of just by iterating as follows
Yes if we start by a point





On the other hand, One of the most crucial factor that affects the speed of convergence (if any) is the choice of

Indeed, we can re-write the same function



Choice of g(x)
Indeed for the function
We can manipulate it in multiple ways, namely bringing

as one possible fixed-point iteration method. Another possibility is taking

then taking the square root as
and so on. Other possibilities are indeed
and
So, the main idea of Fixed point iterations is to solve the following:\
Given an initial guess

So, let’s work out by hand



Let’s obtain at a


and so on until convergence, if any !!!} The reason we say if any is the following: The root of




Fixed Point Theorem: When do we converge ?
The Fixed Point Theorem states the following:
Let be a fixed point function continuous on
and
. Suppose that the derivative
also exists on
. Let
. If
for all
, then for any initial guess
in
, the sequence in
, i.e.
converges to a unique fixed point
in
.
This is a super powerful theorem stating that where-ever you start in , you will converge. Now, let us derive
and see what we get.
Remember that the roots of




![Rendered by QuickLaTeX.com [a,b]](https://bazziahmad.com/wp-content/ql-cache/quicklatex.com-798b02822ccf3db95c5159537a7619be_l3.png)

![Rendered by QuickLaTeX.com 2 \in [a,b]](https://bazziahmad.com/wp-content/ql-cache/quicklatex.com-d897764e952ddc6b1f460da19013c792_l3.png)



![Rendered by QuickLaTeX.com [0, \frac{1}{2}]](https://bazziahmad.com/wp-content/ql-cache/quicklatex.com-1af648f18da9cf5047225be77ea3af0d_l3.png)
![Rendered by QuickLaTeX.com [0, \frac{1}{2}]](https://bazziahmad.com/wp-content/ql-cache/quicklatex.com-1af648f18da9cf5047225be77ea3af0d_l3.png)
![Rendered by QuickLaTeX.com [0, \frac{1}{2}]](https://bazziahmad.com/wp-content/ql-cache/quicklatex.com-1af648f18da9cf5047225be77ea3af0d_l3.png)

Now, let’s do

Is




MATLAB implementation of Fixed Point Iteration method
This is easily achieved on MATLAB. First let’s define the total number of fixed point iterations and a starting point to run our fixed point iteration method
Niter = 20; % total number of iterations
x = 0; % starting point
followed by the functions we would like to test, i.e.
,
,
, and
g1 = @(x) x^2 - 2;
g2 = @(x) sqrt(x+2);
g3 = @(x) 1 + (2/x);
g4 = @(x) (x^2 + 2)/(2*x - 1);
Now that we have the functions, let’s compute the absolute value of the derivatives to check if the fixed point theorem conditions are satisfied, so
dg1 = abs(2*x);
dg2 = 1/(2*sqrt(x+2));
dg3 = 2/x^2;
dg4 = abs( (2*x^2 - 2*x - 4)/((2*x-1)^2) );
At this point of the code, we have the derivatives, as well as the starting point, which is enough to say something about convergence of fixed point. In other words, if , we are guaranteed to converge, else we are not, hence:
if dg1 < 1
disp(['Fixed point is GUARANTEED to converge for x = ',num2str(x),' and g1(x)'])
else
disp(['Fixed point is NOT GUARANTEED to converge for x = ',num2str(x),' and g1(x)'])
end
We will replicate the above block for the other functions as
if dg2 < 1
disp(['Fixed point is GUARANTEED to converge for x = ',num2str(x),' and g2(x)'])
else
disp(['Fixed point is NOT GUARANTEED to converge for x = ',num2str(x),' and g2(x)'])
end
if dg3 < 1
disp(['Fixed point is GUARANTEED to converge for x = ',num2str(x),' and g3(x)'])
else
disp(['Fixed point is NOT GUARANTEED to converge for x = ',num2str(x),' and g3(x)'])
end
if dg4 < 1
disp(['Fixed point is GUARANTEED to converge for x = ',num2str(x),' and g4(x)'])
else
disp(['Fixed point is NOT GUARANTEED to converge for x = ',num2str(x),' and g4(x)'])
end
Good. At this point of the code, we get display messages stating convergence information about each of the four choices of the functions. Now, we are ready to run fixed point iteration for each
and experiment what we get. For example, if we were to do so on
we get
x = 0;
for n = 1:Niter
f1(n) = x; % you can omit this line, here I am just saving all values of x for plotting, that's all :) !
x = g1(x); % run fixed point iteration
end
We will do the same thing for the other functions we have as follows:
x = 0;
for n = 1:Niter
f2(n) = x;
x = g2(x);
end
x = 0;
for n = 1:Niter
f3(n) = x;
x = g3(x);
end
x = 0;
for n = 1:Niter
f4(n) = x;
x = g4(x);
end
We have all the fixed point iteration values per where
and so we are now ready to summarise everything we did in one plot using the following plotting code:
figure
plot(f1,'r','LineWidth',2)
hold on
plot(f2,'m','LineWidth',2)
plot(f3,'k','LineWidth',2)
plot(f4,'b','LineWidth',2)
plot(2*ones(Niter,1),'g--','LineWidth',2)
legend('
','
','
','
','True root','Interpreter','latex','FontSize',25)
xlabel('Iteration number
','Interpreter','latex','FontSize',25)
ylabel('
','Interpreter','latex','FontSize',25)
grid on
grid minor



Follow my other courses such as convex optimization.
Buy me a cup of coffee using the donate link below 😊☕️
PS: I’m on twitter. I retweet stuff around algorithms, python, MATLAB and mathematical optimization, mostly convex.
PSS: We are so close to 100K subscribers on YouTube. It would mean so much if you could share the channel and subscribe to help us sustain.
Recent Comments