What is wrong with the Mann iteration?

I have written the Mann iteration's code for the mapping $\frac{z}{1+z^2}$, in Mathematica, but it is very slow. In fact it needs more than 200 seconds for obtaining 17th iteration, while Matlab does 100 iterations of the the Mann iteration in a second. Would you please tell me what is wrong with my code?

Clear[x, z, n, lambda, f]
For[n = 1; x[1] := 1;
lambda := 1/2; f[z_] := z/(1 + z^2), n < 21, n++,
x[n_] := (1 - lambda) x[n - 1] + lambda f[x[n - 1]]; Print[Timing[N[x[n]]]]]

• Do you really want to use exact arithmetic all the way? – Daniel Lichtblau Apr 24 '18 at 23:35

The following approach might be more "standard Mathematica":

Clear[f]
f[z_] := z/(1 + z^2)

lambda = 0.5;

Clear[x]
x[1] = 1;
x[n_] := x[n] = (1 - lambda) x[n - 1] + lambda f[x[n - 1]]

list = Table[x[n], {n, 1, 150}];
ListPlot[list, PlotRange -> All]


Memoization (i.e. saving intermediate values of x[n], see also Q2639) appears to help considerably. Execution is then practically instantaneous even for large $n$.

It also helps greatly to get away from symbolic calculations: instead of lambda = 1/2, use the machine-precision value lambda = 0.5.

More in general, you might also want to take a look at:

• Thank you for your detailed and complete answer – morapi Apr 24 '18 at 19:41
• @morapi You are welcome. – MarcoB Apr 24 '18 at 19:43
• Do you mean f[z_] := f[z] = z/(1 + z^2) (z instead of x)? – Henrik Schumacher Apr 24 '18 at 22:09
• @HenrikSchumacher Actually that part does not benefit from memoization. I took out the f[x] altogether, which must have been a leftover from a previous draft. Thank you for pointing it out! – MarcoB Apr 24 '18 at 22:56

note it is a little faster to march it out directly without recursion:

 list = NestList[ (1 - lambda) # + lambda f[#] & , 1 , 149]

• It is. Thank you – morapi Apr 24 '18 at 20:11