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

*To*: mathgroup at smc.vnet.net*Subject*: [mg71764] Functional decomposition (solving f[f[x]] = g[x] for given g)*From*: "Kelly Jones" <kelly.terry.jones at gmail.com>*Date*: Tue, 28 Nov 2006 06:04:18 -0500 (EST)

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.