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/