[Date Index] [Thread Index] [Author Index]

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,
> 
> 
>>Please,
>>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/