# Fixed point iteration¶

Let’s convert the roots of a quadratic polynomial $$f(x)$$ to a fixed point problem.

using FundamentalsNumericalComputation

p = Polynomial([3.5,-4,1])
r = roots(p)
@show rmin,rmax = sort(r);

(rmin, rmax) = sort(r) = [1.2928932188134525, 2.7071067811865475]


We define $$g(x)=x-p(x)$$. Intersections of its graph with the line $$y=x$$ are fixed points of $$g$$ and thus roots of $$p$$. (Only one is shown in the chosen plot range.)

g = x -> x - p(x)
plt = plot([g x->x],2,3,l=2,label=["\$y=g(x)\$" "\$y=x\$"],aspect_ratio=1,
title="Finding a fixed point",legend=:bottomright)


If we evalaute $$g(2.1)$$, we get a value of almost 2.6.

x = 2.1;  y = g(x)

2.59


So $$g(x)$$ is considerably closer to a fixed point than $$x$$ was. The value $$y=g(x)$$ ought to become our new $$x$$ value! Changing the $$x$$ coordinate in this way is the same as following a horizontal line over to the graph of $$y=x$$.

plot!([x,y],[y,y],label="",arrow=true)


Now we can compute a new value for $$y$$. We leave $$x$$ alone here, so we travel along a vertical line to the graph of $$g$$.

x = y;  y = g(x)
plot!([x,x],[x,y],label="",arrow=true)


You see that we are in a position to repeat these steps as often as we like. Let’s apply them a few times and see the result.

for k = 1:5
plot!([x,y],[y,y],label="");  x = y;    # y --> new x
y = g(x);  plot!([x,x],[x,y],label="")  # g(x) --> new y
end
display(plt)


The process spirals in beautifully toward the fixed point we seek. Our last estimate has almost 4 accurate digits.

abs(y-rmax)/rmax

0.0001653094344995643


Now let’s try to find the other fixed point $$\approx 1.29$$ in the same way. We’ll use 1.3 as a starting approximation.

plt = plot([g x->x],1,2,l=2,label=["\$y=g(x)\$" "\$y=x\$"],aspect_ratio=1,
title="No convergence",legend=:bottomright)

x = 1.3; y = g(x);
for k = 1:5
plot!([x,y],[y,y],label="",arrow=true);  x = y;    # y --> new x
y = g(x);  plot!([x,x],[x,y],label="",arrow=true)  # g(x) --> new y
end

display(plt)


This time, the iteration is pushing us away from the correct answer.