Re: RE: RE: Functional decomposition (solving f[f[x]] = g[x] for given g)

*To*: mathgroup at smc.vnet.net*Subject*: [mg71885] Re: [mg71872] RE: [mg71839] RE: [mg71764] Functional decomposition (solving f[f[x]] = g[x] for given g)*From*: "Gregory Duncan" <gmduncan at gmail.com>*Date*: Sat, 2 Dec 2006 05:11:07 -0500 (EST)*References*: <200612011122.GAA25968@smc.vnet.net>*Reply-to*: gmduncan at econ.berkeley.edu

The problem falls generally into the the area of functional equations. See J. Aczel Functional Equations: History, Applications and Theory or any of his other books. One can also try to find a fixed point in a function space. On 12/1/06, Ingolf Dahl <ingolf.dahl at telia.com> wrote: > Some further comments on the equation f(f(x)) = g(x): > For the case g(x) = exp(x) some work have been done, see > http://www.math.niu.edu/~rusin/known-math/index/39-XX.html , > http://www.math.niu.edu/~rusin/known-math/99/sqrt_exp > and http://www.newton.dep.anl.gov/newton/askasci/1993/math/MATH023.HTM . > (found by a Google search for "f(f(x))") > > However, I have not penetrated deeply enough into all references to really > see if there are good methods to find (precise) numerical values for at > least one solution of the equation. Or a plot... > > But some thoughts further, somewhat fishing on deep water: If we have a > function g(x) that is such that g(0)=0 (or g(x0)=x0 for some x0) and where > g(x) also has a Maclaurin expansion with a positive first coefficient, it > should be easy to find a Maclaurin series which composed to itself is > identical to that of g(x). Examples of such functions g(x) are sin(x) and > sinh(x). Then there is the question if this series converges in some range, > I have not tested yet. (In the links above they refer to a theorem by Polya, > stating that convergence range must be limited.) For some other functions, > we could also think of expansions in x^(Sqrt(2)). > Suppose that we find such a function f(x) for g(x) = sinh(x), name it > fsinh(x), with convergence in some region near origo. Then it might be > possible to extend that to the whole axis if we for any x apply ginv (the > inverse of g) a number of times until we reach the convergence region. (we > might have to use extended precision.) There we apply f, and then apply g > the same number of times as we did with ginv. Then we should have obtained > f(x). > > If we now look at the case g(x) = exp(x), we can note that if x > 20, exp > and 2*sinh are essentially identical (to machine precision). Thus we could > assume that fsinh(x)*Sqrt[2] is a good approximation of the solution f(x) > for g(x)=exp(x) and x>20, and then we might use the same procedure as for > g(x)=x^2+1 to extend this to zero. With the power of Mathematica available, > just a few lines of code maybe are all that is needed. But maybe some devils > are hiding in the details? > > Is there anyone who knows more about this? > > Ingolf Dahl > > > > -----Original Message----- > > From: Ingolf Dahl [mailto:ingolf.dahl at telia.com] > > Sent: den 30 november 2006 12:06 > > To: mathgroup at smc.vnet.net > > Subject: [mg71839] RE: [mg71764] Functional decomposition > > (solving f[f[x]] = g[x] for given g) > > > > Hi Kelly, > > Here is a rapid amateur answer (but without scary rhymes, as > > in my last answer). If you are satisfied with the numerical > > values of the function, you can investigate > > > > g[x_]:=1+x^2; > > ginv[x_]:=Sqrt[x-1]; > > f[x_Real]:=Nest[ginv,Power[Nest[g,x,9],Sqrt[2]],9] > > > > f[x_Real] appears to be a good solution to f[f[x]] == g[x] to > > approximate machine precision. The solution is based on two > > observations: > > 1) Nest[g,x,9] is equivalent to Nest[f,x,18], and we reach > > very large values when this is calculated. There g[x] is > > approximately equal to x^2 (to machine precision), and f[x] > > can be approximated by x^Sqrt[2]. Thus we might reach a good > > approximation of Nest[f,x,19] by Power[Nest[g,x,9],Sqrt[2]]. > > 2) We can then apply the inverse function ginv of g 9 times > > to reach f[x]. > > The relative error is reduced by the application of the > > inverse function. > > > > We can note that f[0.] is 0.6420945043908285` which do not > > appear to be a known mathematical constant. But now it is. > > (If someone can check... I cannot reach the "The Inverse > > Symbolic Calculator" at CESM. Is it down?) > > > > Generalize and write f[x] as DecompositionPower[x,1/2] and > > the solution to f[f[f[x]]]\[Equal]g[x] as > > DecompositionPower[x,1/3] For the given function g then we can try > > > > DecompositionPower[x_,p_]:=Nest[ginv,Power[Nest[g,x,9],Power[2,p]],9] > > > > and we might for instance plot > > > > Plot[DecompositionPower[0.,p],{p,0,1}] > > > > The function DecompositionPower[x_,p_] should be quite easy > > to generalize to a large set of polynomial functions g. Maybe > > it then should have the name FractionalNest? > > > > Best regards > > > > Ingolf Dahl > > > > -----Original Message----- > > From: Kelly Jones [mailto:kelly.terry.jones at gmail.com] > > Sent: 28 November 2006 12:04 > > To: mathgroup at smc.vnet.net > > Subject: [mg71839] [mg71764] Functional decomposition > > (solving f[f[x]] = g[x] for given g) > > > > Given a function g[x], is there a standard methodology to > > find a function f[x] such that: > > > > f[f[x]] == g[x] > > > > A "simple" example (that doesn't appear to have a closed form > > solution): > > > > f[f[x]] == x^2+1 > > > > There are probably several (approximable? > > power-series-expressible?) answers, but the most natural > > answer would be everywhere positive and monotone increasing for x>0. > > > > For x^2, there are at least two continuous solutions: > > x^Sqrt[2] and x^-Sqrt[2], the former being more "natural". > > It's somewhat amazing that x^2+1 is so much harder. > > > > Of course, the next step would be to find f[x] such that: > > > > f[f[f[x]]] == g[x] > > > > for given g[x], and so on. > > > > Thought: is there any operator that converts functional > > composition to multiplication or something similar? That > > would reduce this problem to find nth roots and applying the > > inverse operator? > > > > Other thought: For some reason, taking the geometric average > > of the identity function and g, and then iterating, seems > > like a good idea. EG, Sqrt[x*g[x]], Sqrt[x*Sqrt[x*g[x]]], and so on. > > > > -- > > We're just a Bunch Of Regular Guys, a collective group that's > > trying to understand and assimilate technology. We feel that > > resistance to new ideas and technology is unwise and > > ultimately futile. > > > > > > > > >

**References**:**RE: RE: Functional decomposition (solving f[f[x]] = g[x] for given g)***From:*"Ingolf Dahl" <ingolf.dahl@telia.com>