1
$\begingroup$

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]]]]]
$\endgroup$
  • $\begingroup$ Do you really want to use exact arithmetic all the way? $\endgroup$ – Daniel Lichtblau Apr 24 '18 at 23:35
6
$\begingroup$

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.

Mathematica graphics

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your detailed and complete answer $\endgroup$ – morapi Apr 24 '18 at 19:41
  • $\begingroup$ @morapi You are welcome. $\endgroup$ – MarcoB Apr 24 '18 at 19:43
  • $\begingroup$ Do you mean f[z_] := f[z] = z/(1 + z^2) (z instead of x)? $\endgroup$ – Henrik Schumacher Apr 24 '18 at 22:09
  • $\begingroup$ @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! $\endgroup$ – MarcoB Apr 24 '18 at 22:56
2
$\begingroup$

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

 list = NestList[ (1 - lambda) # + lambda f[#] & , 1 , 149]
| improve this answer | |
$\endgroup$
  • $\begingroup$ It is. Thank you $\endgroup$ – morapi Apr 24 '18 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.