# Tetration Forum

Full Version: computing the iterated exp(x)-1
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2
$f^n(z)=z+\frac{1}{2} n z^2 + \frac{1}{12} (3n^2-n) z^3 + \frac{1}{48} (6n^3-5n^2+n) z^4 + \cdots$ is the general solution where

$f^0(z) = z$

$f^1(z) = e^z-1$ and

$f^m(f^n(z)) = f^{m+n}(z)$.
Daniel Wrote:$f^n(z)=z+\frac{1}{2} n z^2 + \frac{1}{12} (3n^2-n) z^3 + \frac{1}{48} (6n^3-5n^2+n) z^4 + \cdots$ is the general solution

Which formula for the coefficients is this exactly?
bo198214 Wrote:
Daniel Wrote:$f^n(z)=z+\frac{1}{2} n z^2 + \frac{1}{12} (3n^2-n) z^3 + \frac{1}{48} (6n^3-5n^2+n) z^4 + \cdots$ is the general solution

Which formula for the coefficients is this exactly?

I get a similar formula.

$
\begin{eqnarray}
f(z) & = & e^z-1 \\
\vspace{10} \\
f^{\circ n}(z) & = &
\left(\frac{1}{2^0}\right)\left(n^0\right)z^1\ +\\ & &
\left(\frac{1}{2^1}\right)\left(n^1\right)z^2\ +\\ & &
\left(\frac{1}{2^2}\right)\left(n^2-\frac{n}{3}\right){z^3}\ +\\ & &
\left(\frac{1}{2^3}\right)\left(n^3-\frac{5n^2}{6}+\frac{n}{6}\right)z^4\ +\\ & &
\left(\frac{1}{2^4}\right)\left(n^4-\frac{13n^3}{9}+\frac{2n^2}{3}-\frac{4n}{45}\right)z^5\ +\\ & &
\left(\frac{1}{2^5}\right)\left(n^5-\frac{77n^4}{36}+\frac{89n^3}{54}-\frac{91n^2}{180}+\frac{11n}{270}\right)z^6\ +\\ & &
\left(\frac{1}{2^6}\right)\left(n^6-\frac{29n^5}{10}+\frac{175n^4}{54}-\frac{149n^3}{90}+\frac{91n^2}{270}-\frac{n}{105}\right)z^7\ + \\ & &
\left(\frac{1}{2^7}\right)\left(n^7-\frac{223n^6}{60}+\frac{1501n^5}{270}-\frac{37n^4}{9}+\frac{391n^3}{270}-\frac{43n^2}{252}-\frac{11n}{1890}\right)z^8\ + \\ & &
\left(\frac{1}{2^8}\right)\left(n^8-\frac{481n^7}{105}+\frac{2821n^6}{324}-\frac{13943n^5}{1620}+\frac{725n^4}{162}-\frac{2357n^3}{2268}+\frac{17n^2}{420}+\frac{29n}{5670}\right)z^9\ +\ \cdots
\end{eqnarray}
$

It's hard to pick out any particular pattern, but I gave it an initial try...

Edit: Removed an extra factorial that I had added to make finding the fractions easier. I forgot to pull the factorial back out.

Edit #2: I removed the second set of factorials because they cancel out. They were useful for seeing the growth rate, but they made the formula look more complicated than it really is.
It seems clear to me that these polynomials should be stored in a matrix. You have two sets of variables: n^0, n^1, n^2, ..., and z^0, z^1, z^2, ..., and a you have one coefficient for each combination, so long as the degree of n is less than the degree of z.

Depending on whether you make the z's a row vector or a column vector, you'll either have an upper triangular matrix or a lower triangular matrix. Once in that format, it should be much easier to pick out the patterns, and it should provide an effective viewpoint to assess convergence.

At any rate, I'm not terribly concerned if the radius of convergence is goes to 0 as the number of terms goes to infinity. There should still be a limit that is well-behaved, even if it means taking the limit as z goes to 0, with an integer iteration count that goes to infinity to get us back up the vicinity of z=1.

This is essentially what I did with my cheta function, but with linear interpolation. With a higher degree interpolation function based on the power series derived here (e.g., the first 20 terms should converge very nicely for z <0.01), convergence should be even more well-behaved, and by extension, the limit that much more defensible. Assuming the limit is defensible, then less accuracy could be acceptable by using a non-limited approximation.

And this is assuming the radius of convergence indeed goes to 0. I don't have access to Baker's proof, so I don't have a lot to go on at the moment.
jaydfox Wrote:It seems clear to me that these polynomials should be stored in a matrix. You have two sets of variables: n^0, n^1, n^2, ..., and z^0, z^1, z^2, ..., and a you have one coefficient for each combination, so long as the degree of n is less than the degree of z.
Jay, I'd like to check around with this matrix. I was starting to manually extract the coefficients... but this is tedious and I'm not sure about some signs, where the regularity breaks.
Could you provide this matrix, possibly some more rows, in a comma-separated format? Also, I reorder this coefficients for increasing powers of n, including zeros for nonoccurence of the specific coefficient,
so for instance I can write
M * V(n)
where M is the matrix of coefficients and V(n) is the vector of powers of n
V(n) = colvec(1,n,n^2,n^3,n^4,...). I can then try with M, similarity scalings, inverse, powers, logs, etc.

What I have now is
Code:
1, 0,   1, 0, -1/3,         1, 0,  1/6,       -5/6,       1, 0, -4/45,       2/3,     -13/9,     1, 0, 11/270,    -91/180,    89/54,  -77/36,   1, 0, -1/105,     91/270,  -149/90,  175/54,  -29/10,  1, 0, -11/1890,  -43/252,   391/270, -37/9,   1501/270, 223/60,  1

Gottfried
I'm working on an Excel program to generate the first 50 polynomials or more, as many as I can get with the precision I'm limited to. It'll probably be tomorrow before I can get it done, because I have some other work to do in the meantime.
Here I show some matrices, which allow to compute real iterates
for x -> exp(x)-1

The matrix, which performs the iterate is

$\hspace{24} C = F^{-1} * St2 * F$

Code:
C=  (only 8 rows/columns shown)   1        .        .        .      .      .   .   .   0        1        .        .      .      .   .   .   0      1/2        1        .      .      .   .   .   0      1/6        1        1      .      .   .   .   0     1/24     7/12      3/2      1      .   .   .   0    1/120      1/4      5/4      2      1   .   .   0    1/720   31/360      3/4   13/6    5/2   1   .   0   1/5040     1/40   43/120    5/3   10/3   3   1

This matrix allows to compute

$\hspace{24} V(x)\sim * C = V(e^x - 1)\sim$

Example 1: normal iterates

$\hspace{24} V(1)\sim * C = V(e - 1)\sim$
$\hspace{24} V(1)\sim * C^2 = V(e^{e - 1}-1)\sim$

Code:
results V(e - 1)= [1, e-1, (e-1)^2, (e-1)^3, ...] = [    1.0000000    1.7182818    2.9524924    5.0732098    8.7170908    14.976648 ...] V(e^(e - 1)-1 )= [1, e^(e-1)-1, (e^(e-1)-1)^2,  ...] = [    1.0000000    4.5749415   20.930084    95.751617   437.84444    1994.7177   ...]

-----------------------------------------------------------------------

To obtain real or complex iterates real or complex powers of
C are needed. The eigensystem of C is degenerate, so this cannot
be used. But there is the possibility of computing the matrix-
logarithm of C.

$\hspace{24} LC = \log{\left(C\right)}$
Code:
LC =   0         .         .       .      .       .   .   .   0         0         .       .      .       .   .   .   0       1/2         0       .      .       .   .   .   0     -1/12         1       0      .       .   .   .   0      1/48      -1/6     3/2      0       .   .   .   0    -1/180      1/24    -1/4      2       0   .   .   0   11/8640     -1/90    1/16   -1/3     5/2   0   .   0   -1/6720   11/4320   -1/60   1/12   -5/12   3   0

Of this we can compute arbitrary complex multiples, say for
a start, to realize the half-iterate means the square-root of
C, and this means 1/2*LC (not documented here, trivial)

Example 2: Square-root - 1/2-iterates

From this, the top left of C^0.5 is then
$\hspace{24} C^{0.5} = \exp(0.5*LC)$

Code:
C^0.5=   1          .          .         .       .       .     .   .   0          1          .         .       .       .     .   .   0        1/4          1         .       .       .     .   .   0       1/48        1/2         1       .       .     .   .   0          0       5/48       3/4       1       .     .   .   0     1/3840       1/96       1/4       1       1     .   .   0   -7/92160   11/11520      3/64   11/24     5/4     1   .   0   1/645120   -1/46080   23/3840     1/8   35/48   3/2   1

(note, that the second column is just the sequence, Henryk provided us with in the first post of this thread)

and we get the first four half-iterates (the interesting result is in 2'nd column)

Code:
1/2-iterates    1.0000000    1.2710274    1.6155107    2.0533584    2.6098746     3.3172201    1.0000000    1.7182818    2.9524924    5.0732098    8.7170908    14.976648    1.0000000    2.5645129    6.5767163   16.865290    43.227699    110.47725    1.0000000    4.5749415   20.930084    95.751617   437.84444    1994.7177

Example 3: Cube-root - 1/3-iterates

The top-left of the cube-root of C, C^(1/3) is

Code:
C^(1/3)=   1           .         .        .      .      .   .   .   0           1         .        .      .      .   .   .   0         1/6         1        .      .      .   .   .   0           0       1/3        1      .      .   .   .   0           0      1/36      1/2      1      .   .   .   0      1/4860         0     1/12    2/3      1   .   .   0    -7/58320    1/2430    1/216    1/6    5/6   1   .   0   23/612360   -1/5832   1/1620   1/54   5/18   1   1

We get the first six 1/3-iterates
Code:
1/3-iterates    1.0000000    1.1667861    1.3613899    1.5884509    1.8533825    2.1625009    1.0000000    1.3939228    1.9430208    2.7084211    3.7753299    5.2625167    1.0000000    1.7182818    2.9524924    5.0732137    8.7171961   14.978293    1.0000000    2.2116542    4.8914136   10.818048    23.923566    52.871434    1.0000000    3.0306304    9.1846792   27.831709    84.229412   253.25930    1.0000000    4.5749415   20.930084    95.751617   437.84444   1994.7177

------------------------------------------------------------------------

The convergence of the series for fractional iterates was worse than that
of integral iterates.
It looks also suspicious, that with dim=32, in the matrix-logarithm the
entries first decrease to higher indexed rows, (which suggests good
approximability) but increase again from, say,
row 24, so I don't know about the general behaviour (see table below)

This may have the same consequences for the fractional powers of C. (see table below)

I arrived at the above values using 32 coefficients "by default" by Euler-
summation. May be this procedure is required in general, in case the
entries of the fractional powers of C diverge but alternate in sign.
(That is then the field of analytic continuation, I assume?)

Gottfried
-------------------------------------------------------------------------

Top left from the matrix-logarithm of C
Code:
1.0*LC=   0                  .                  .                  .   0                  0                  .                  .   0         0.50000000                  0                  .   0       -0.083333333          1.0000000                  0   0        0.020833333        -0.16666667          1.5000000   0      -0.0055555556        0.041666667        -0.25000000   0       0.0012731481       -0.011111111        0.062500000   0     -0.00014880952       0.0025462963       -0.016666667   0    -0.000045469577     -0.00029761905       0.0038194444   0     0.000019979056    -0.000090939153     -0.00044642857   0     0.000011321465     0.000039958113     -0.00013640873   0    -0.000011319378     0.000022642931     0.000059937169   0   -0.0000017266470    -0.000022638755     0.000033964396   0    0.0000070561217   -0.0000034532940    -0.000033958133   0   -0.0000010130178     0.000014112243   -0.0000051799409   0   -0.0000055954100   -0.0000020260355     0.000021168365   0    0.0000027850090    -0.000011190820   -0.0000030390533   0    0.0000055636225    0.0000055700180    -0.000016786230   0   -0.0000054890313     0.000011127245    0.0000083550269   0   -0.0000066929168    -0.000010978063     0.000016690867   0     0.000011612181    -0.000013385834    -0.000016467094   0    0.0000092209451     0.000023224363    -0.000020078750   0    -0.000028132640     0.000018441890     0.000034836544   0    -0.000013074482    -0.000056265279     0.000027662835   0     0.000079067854    -0.000026148964    -0.000084397919   0     0.000012559808      0.00015813571    -0.000039223446   0     -0.00025744463     0.000025119617      0.00023720356   0     0.000039946326     -0.00051488925     0.000037679425   0      0.00096515491     0.000079892652     -0.00077233388   0     -0.00047939822       0.0019303098      0.00011983898   0      -0.0041340004     -0.00095879644       0.0028954647   0       0.0036464303      -0.0082680007      -0.0014381947

Top left from C^(1/2) = Exp(1/2*log©)
Code:
1.0*C^(1/2)=   1.0000000                    .                   .                   .           0            1.0000000                   .                   .           0           0.25000000           1.0000000                   .           0          0.020833333          0.50000000           1.0000000           0                    0          0.10416667          0.75000000           0        0.00026041667         0.010416667          0.25000000           0      -0.000075954861       0.00095486111         0.046875000           0      0.0000015500992     -0.000021701389        0.0059895833           0       0.000015404111     -0.000024026538       0.00048828125           0     -0.0000090745391      0.000028418485     -0.000018859540           0   -0.000000082819971     -0.000010314618      0.000032939608           0      0.0000036074073    -0.0000041006314    -0.0000054640997           0     -0.0000016951497     0.0000068018753    -0.0000091647597           0     -0.0000013308992    -0.0000015822591     0.0000083398934           0      0.0000017752144    -0.0000033661285   0.000000062080956           0     0.00000037035398     0.0000028157312    -0.0000054374338           0     -0.0000019147568     0.0000015749616     0.0000029115066           0     0.00000034467343    -0.0000035720802     0.0000033166038           0      0.0000024191341   -0.00000025294483    -0.0000046812506           0     -0.0000014770587     0.0000049320576    -0.0000016708263           0     -0.0000036046260    -0.0000017303876     0.0000071932744           0      0.0000042603060    -0.0000078480430   -0.00000075380949           0      0.0000061940178     0.0000066573185     -0.000012268458           0      -0.000012625293      0.000014369165     0.0000069893294           0      -0.000011736089     -0.000021977272      0.000023806922           0       0.000041395229     -0.000029528323     -0.000027370787           0       0.000022203030      0.000076399188     -0.000052087716           0       -0.00015310857      0.000064617129       0.00010284248           0      -0.000027832787      -0.00029339839       0.00012465733           0        0.00064101866      -0.00013129869      -0.00041348905           0       -0.00011130752        0.0012617648      -0.00030496184           0        -0.0030302667      0.000096739308        0.0018342749
jaydfox Wrote:
bo198214 Wrote:
Daniel Wrote:$f^n(z)=z+\frac{1}{2} n z^2 + \frac{1}{12} (3n^2-n) z^3 + \frac{1}{48} (6n^3-5n^2+n) z^4 + \cdots$ is the general solution

Which formula for the coefficients is this exactly?

The coefficients occur also by explicitely computing
the matrix-exponential via the exponential-series.

Let CL = log( C ) ,
where C is the iterable operator for exp(z)-1 as defined in my other post, then

Code:
.      exp(n*CL)= (n Cl)^0 + (n CL)^1 + (n CL)^2/2! + (n CL)^3/3! ...

with as many terms as a given finite dimension requires
(CL is nilpotent to the order of its dimension)

Then we have (selecting dimension 5 for an example)

Code:
exponential-series      tmpm = CL*n      tmpe= matid(5)+ tmpm + tmpm^2/2! + tmpm^3/3! + tmpm^4/4!

and tmpe is
Code:
tmpe   1                        .              .      .  .   0                        1              .      .  .   0                    1/2*n              1      .  .   0           1/4*n^2-1/12*n              n      1  .   0  1/8*n^3-5/48*n^2+1/48*n  3/4*n^2-1/6*n  3/2*n  1

The value for the half-iterate h(z) occurs then from the matrix-product
Code:
V(z)~ * tmpe [,1]

where as usual the second column of tmpe is the interesting one.

Code:
second column of tmpe:     tmpe[,1]= [0, 1, 1/2*n, 1/4*n^2 - 1/12*n, 1/8*n^3 - 5/48*n^2 + 1/48*n]~

and with h(z) for the value of the half-iterate resp to parameter z in
Code:
.     h(z) = V(z)~ * tmpe [,1]

we have

Code:
formula for half-iterate, using matrix dimension 5 h(z) = z^0 * 0        +z^1 * 1        +z^2 * 1/2 *(1*n)        +z^3 * 1/12*(3*n^2 - 1*n)        +z^4 * 1/48*(6*n^3 - 5*n^2 + 1*n]

which agrees with your formula.

Gottfried
I come to the same formula, however computing indexes above 15 is nearly impossible. So it seems that your methods somehow are faster than the direct double binomial expansion executed in Maple.

Whats your biggest index (say it takes below 5min) that you can compute and by which method on which system?
bo198214 Wrote:I come to the same formula, however computing indexes above 15 is nearly impossible. So it seems that your methods somehow are faster than the direct double binomial expansion executed in Maple.

Whats your biggest index (say it takes below 5min) that you can compute and by which method on which system?

Hmm, with dimension = 64 , let it come to 1 minute for the computations of that matrix-exponential with the variable n.
[update:]
Just tried with dim=32, it was, let's say 2 seconds. (So the above guess was a bit rough... ;-) )
[/update]

Usually I calculate with dim=32 and can be in a reasonable dialog with the system, so less a second to some seconds.
If I compute eigensystems I had longer computation times, assumably because of required higher precision (my default is 80 or 200 digits float, with eigensystem analysis I needed sometimes 800 digits with dim=32) and for such analyses I wait possibly some minutes. My application is Pari/GP, btw.

In the german math-newsgroup some readers provided me with results for crosscheck and mentioned, they were able to do such eigenanalyses with mathematica or maple up to dimension =128 in some seconds or few minutes - don't know how this difference is possible (I even didn't try the eigenanalysis with dim=64 in my Pari/GP-setting).

Gottfried

Ah, well, the system: 1 GHz CPU, 1 GByte Ram, Win Xp
Pari/Gp interfaced by my Pari-TTY-Gui

[edit 2]
Actually, with nilpontent matrices I use the simpler formula, given M
F=matid(dim);S=F;
for(k=1,dim,
F = F*M/k ; S = S + F )
[/edit 2]
Pages: 1 2