# Fixed Point Iteration: Solving “almost” any Equation !

0

## 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 then evaluate then and so on then eventually we can converge to where .
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 using many (sometimes infinitely many) choices of functions. Furthermore, in the next section, I will show four different choices of .

## Choice of g(x)

Indeed for the function

We can manipulate it in multiple ways, namely bringing to the other side yields

as one possible fixed-point iteration method. Another possibility is taking on the Right hand side

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 , solve

So, let’s work out by hand . Give me (initial guess) and let’s find ,

Let’s obtain at a iteration the value of , similarly as above

and so on until convergence, if any !!!} The reason we say if any is the following: The root of are and . We see that at each iteration, fixed point using is diverging away from either roots. In the next section, we emphasise on conditions that guarantee convergence

## 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 are and . Let us focus on as the question is saying}. So, no matter what interval you choose containing , (), you can not ensure that , simply because . Therefore you can not converge using fixed point to . One might ask, “what if i pick “. Here, the fixed point theorem applies and you will converge to a fixed point solution in , but this is not interesting because does not contain the root of .
Now, let’s do . Derive, we get

Is ? If yes, you will converge to the . At this point, it should be clear how to tackle and .

## 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 😊☕️

[paypal_donation_block email=’myprivateotherstuff@gmail.com’ amount=’15.00′ currency=’USD’ size=’large’ purpose=’Buy me coffee ^^’ mode=’live’]

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.