+- Tetration Forum (https://tetrationforum.org)
+-- Forum: Tetration and Related Topics (https://tetrationforum.org/forumdisplay.php?fid=1)
+--- Forum: Mathematical and General Discussion (https://tetrationforum.org/forumdisplay.php?fid=3)
+--- Thread: computing the iterated exp(x)-1 (/showthread.php?tid=18)
Pages:
1
2
computing the iterated exp(x)-1 - Daniel - 08/13/2007
\( 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) \).
RE: Iterability of exp(x)-1 - bo198214 - 08/13/2007
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?
RE: Iterability of exp(x)-1 - jaydfox - 08/14/2007
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 \\
\\[10pt]
\\
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.
RE: Iterability of exp(x)-1 - jaydfox - 08/14/2007
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.
RE: Iterability of exp(x)-1 - Gottfried - 08/14/2007
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, 1Gottfried
RE: Iterability of exp(x)-1 - jaydfox - 08/14/2007
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.
RE: Iterability of exp(x)-1 - Gottfried - 08/14/2007
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 1This 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 0Of 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.7177Example 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 1We 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.0014381947Top 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.0018342749RE: Iterability of exp(x)-1 - Gottfried - 08/14/2007
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 1The 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
RE: Iterability of exp(x)-1 - bo198214 - 08/14/2007
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?
RE: Iterability of exp(x)-1 - Gottfried - 08/14/2007
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]