MathGroup Archive 2005

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

Search the Archive

Re: Differences between recursions and limit

  • To: mathgroup at smc.vnet.net
  • Subject: [mg60535] Re: [mg60509] Differences between recursions and limit
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Tue, 20 Sep 2005 05:18:50 -0400 (EDT)
  • References: <200509190845.EAA23449@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On 19 Sep 2005, at 17:45, anbra1 wrote:

> Please,
> I want to know
> why these two recursions,doing the same thing,
> are the first one much more slow than the second
>
> -------------------------
>
> x[0]=0;
> 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++]
>
> -------------------------
>
> a=0;
>
> For[k=1,k<12,k++,
>
> b= .25 (1 + a + a^2 + a^3);a:=b;Print[k," ",SetPrecision[b,30]]]


Your first code evaluates x[k] recursively every time a step in the  
For loop is executed; hence the slowness. You can speed up the first  
code by using dynamic programming:

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++]



>
> -------------------------
> Another question
> How can I calculate
> the limit of this recursion for k->Infinite ?
> Thank you all
>


Using Mathematica you can get the approximate fixed point of the  
recursion by using FixedPoint:


FixedPoint[0.25*(1+#+#^2+#^3)&,0]


0.414214

But it is better to solve it exactly:



x /. Solve[x == (1/4)*(1 + x + x^2 + x^3), x]


{1, -1 - Sqrt[2], -1 + Sqrt[2]}


N[%]


{1., -2.414213562373095, 0.41421356237309515}


The limit, if it exists (it is easy to show it does) must be one of  
these roots, and clearly it is the third one.

Andrzej Kozlowski


  • Prev by Date: Re: Differences between recursions and limit
  • Next by Date: Re: 'Changing' parameters in an expression
  • Previous by thread: Re: Differences between recursions and limit
  • Next by thread: Re: Differences between recursions and limit