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
- References:
- Differences between recursions and limit
- From: "anbra1" <xyxanbra1@tiscalixxxyxxx.it>
- Differences between recursions and limit