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:

> 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