Re: Differences between recursions and limit

• To: mathgroup at smc.vnet.net
• Subject: [mg60595] Re: Differences between recursions and limit
• From: Peter Pein <petsie at dordos.net>
• Date: Wed, 21 Sep 2005 03:20:36 -0400 (EDT)
• References: <dgm01k\$njm\$1@smc.vnet.net> <dgokvv\$hmn\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```albert schrieb:
> Hi,
>
>
>>I want to know
>>why these two recursions,doing the same thing,
>>are the first one much more slow than the second
>
>
>
> because you are recalculating all intermediate results over and over again
> in the first case. Try instead:
>
> x[0] = 0;
> x[k_] := x[k] = .25*(1 + x[k - 1] + (x[k - 1])^2 + (x[k - 1])^3);
>
> For[k = 1, k < 12, Print[k, " ", SetPrecision[x[k], 30]]; k++] // Timing
>
> how this combination of SetDelayed (:=) and Set (=) works is explained in
> the online documentation (section 2.5.9 Functions That Remember Values They
> Have Found)...
>
> for your other question -- I don't remember the correct conditions for the
> following to work, but in your case the result (0.4142...) you are after
> can be received with (I get a negative result and 1 as other solutions of
> the NSolve, but these can be excluded with your starting value):
>
> NSolve[x == .25*(1 + x + (x)^2 + (x)^3), x]
>
>
> Albert
>
Hi Albert,

if I remember correctly (it has been more than 20 years ago...), there's
a theorem (I know it by its german name: "Banachscher Fixpunktsatz").
f'[x]<1 for all x in an neighbourhood of x0 is sufficient for the
existence of the limit of x[n+1]=f[x[n]] as n->infinity.

In[4]:= iter = (1 + #1 + #1^2 + #1^3)/4 & ;
Reduce[iter'[x] < 1, x]
Out[5]= (1/3)*(-1 - Sqrt[10]) < x < (1/3)*(-1 + Sqrt[10])
In[6]:= N[%]
Out[6]= -1.3874258867227933 < x < 0.7207592200561265

We see, it's OK to use a0==0 (if I am right).

--
Peter Pein, Berlin
GnuPG Key ID: 0xA34C5A82
http://people.freenet.de/Peter_Berlin/

```

• Prev by Date: More strange behavior by ComplexExpand
• Next by Date: Re: "layering" 2d plots
• Previous by thread: Re: Differences between recursions and limit
• Next by thread: Re: Differences between recursions and limit