9
$\begingroup$

Let $f(x) := x^2+(1-x^2)x$. Is there a nice nontrivial closed form approximation $g_n(x)$ over $[0,1]$ for the $n$-fold composition $f^{\circ n}(x)$? Obviously near $0$ we have that $f^{\circ n}(x) = x+nx^2+...$ but this is not much use to me. Rather than try to pin down what "nice" ought to mean, I'll channel Potter Stewart and just say I (and I'm sure also a respondent) would know it upon sight.

One might be tempted to mumble "solve Schroder's equation" but I don't see how that helps. Nor do I see how computing the Carleman matrix of $f$ helps (but for what it's worth, I believe the matrix elements are $M_{jk} := \sum_{r=0}^j \binom{j}{r} (-1)^{j-r} \binom{r}{k-3j-2r}$). Such tactics are suggested in How would I go about finding a closed form solution for $g(x,n) = f(f(f(...(x))))$, $n$ times?

$\endgroup$
  • $\begingroup$ Note $f(0) = 0$ and $f(1) = 1$ are stationary points. $f(x) = x^2+(1-x^2)x = x(1 + x - x^2)$ , $g(x,n) = x(1 + x - x^2) \phi (x,n)$ , $\phi(1,n)=1$ $\endgroup$ – arthur Jul 26 '16 at 2:28
  • $\begingroup$ Also $\phi(0,n)=1$ $\endgroup$ – arthur Jul 26 '16 at 3:40
  • $\begingroup$ @Arthur: Yes, I'm aware. Large iteration numbers give a function that starts at 0 as $\approx x+nx^2$, then quickly climbs before leveling off near 1. Trying Pade approximants and fitting various sigmoids has got me nowhere. $\endgroup$ – S Huntsman Jul 26 '16 at 13:31
  • $\begingroup$ Maybe this can give some idea $x^2+(1-x^2)x = 1 + (x^2-1) + (1-x^2)x = 1 + (1-x^2)(x-1) = 1-(1+x)(1-x)^2$ $\endgroup$ – mathreadler Jul 26 '16 at 16:23
6
+100
$\begingroup$

We have that $f(x) - x = x^2 - x^3$, so if we pretend that $n$ is a continuous variable, and treat the iterates $x(n)$ as functions of this continuous variable, then we are led to the differential equation:

$$\frac{dx}{dn} = x^2 - x^3$$

Which has the solution:

$$\log\left[\frac{x(n)}{1-x(n)}\right]-\frac{1}{x(n)} = \log\left[\frac{x(0)}{1-x(0)}\right]-\frac{1}{x(0)} + n$$

You can then approximately solve for $x(n)$, what is then clear is that for $x(n)$ near zero the $\frac{1}{x(n)}$ term dominates while for $x(n)$ near $1 $ the logarithmic term dominates.

$\endgroup$
  • $\begingroup$ This is so pretty :) $\endgroup$ – Shakespeare Jul 27 '16 at 8:53
  • $\begingroup$ @Count Iblis: very cute. See my illustration of your answer in a CW answer of my own. $\endgroup$ – S Huntsman Jul 27 '16 at 13:22
  • $\begingroup$ @Count Iblis : Brilliant. I wonder how well it would generalize an approximation to any iteration $x := f(x)$, $\frac{dx}{dn} = f(x) - x$? $\endgroup$ – arthur Jul 27 '16 at 23:58
  • 1
    $\begingroup$ I still don't understand how it answers the question to set $x^\prime(n)=f^{\circ n}(x(n))-x(n)$. $\endgroup$ – user90369 Jul 28 '16 at 8:37
  • $\begingroup$ FYI, I have asked a followup about this construction from the PoV of approximate equivariance at mathoverflow.net/questions/245278 $\endgroup$ – S Huntsman Jul 28 '16 at 14:25
3
$\begingroup$

FYI, here is a picture illustrating Count's answer at https://math.stackexchange.com/a/1872168/241. Blue curves are the zeroth through tenth iterates of $f$; red curves are obtained by numerically inverting $F(f^{\circ N}(x)) \approx N + F(x)$ for $F(x) := \log \frac{x}{1-x} + \frac{1}{x}$. I will mention that this is an improvement on the exact fourth-order approximation $f^{\circ N}(x) \approx x+Nx^2+(N^2-2N)x^3+([N-1]^3-2[N-1]^2-3[N-1])x^4$ near $0$, and I imagine an improvement on all exact fixed-order approximations.

See https://math.stackexchange.com/a/1872168/241

On a separate note, I will also mention the Carleman approach I originally mentioned can be pursued along the lines of http://www.sciencedirect.com/science/article/pii/S0022247X98959868.

$\endgroup$
  • $\begingroup$ @S Huntsman: Interesting paper, but it doesn't give you a "closed form" for your problem. E.g. the approximation for $n=2$ with $x+2x^2-4x^4$ (see $N:=2$ above) is (more or less) only very good for $0≤x≤0.5$ and very bad for $0.5≤x≤1$. $\endgroup$ – user90369 Jul 27 '16 at 14:11
  • $\begingroup$ @user90369 - as I mentioned in my own question, the Carleman approach indeed does not lend itself to closed form. $\endgroup$ – S Huntsman Jul 27 '16 at 14:34
2
$\begingroup$

In blue: $g(x,25)$. In orange: $0.5\tanh(x(1+x)^{25})+0.5$. Your function does stay at $y=1$ thereafter.

The behaviour near zero is entirely influenced by $u(x)=x(1+x)$, neglecting the $-x^3$ term. The obvious approximate composition that I mentioned above, $u^n(x)\approx x(1+x)^n$ simply doesn't increase fast enough. Perhaps your Carlemann matrix aproach could be used on this simpler function to yield a more meaningful approximation near zero?

The $\tanh$ motivation should also be obvious. I hope this helps.

enter image description here

$\endgroup$
  • $\begingroup$ To whomever downvoted: I know this isn't a complete answer, merely meant to help visualise and see the focus of the problem. If you could please explain, maybe I could improve the answer. $\endgroup$ – Shakespeare Jul 26 '16 at 16:04
  • $\begingroup$ wasn't me who downvoted. As I said, fitting sigmoids (e.g., tanh and the logistic function) got me nowhere. Indeed, one can even show that the most obvious sigmoid fits along the lines $S(aS^{-1}(x)+b)$ for a fixed sigmoid $S$ won't work because of boundary constraints on the function values and derivative. For this reason your choice of argument to tanh is rather interesting and suggests a general approach that I will probably fiddle around with. Thanks! $\endgroup$ – S Huntsman Jul 26 '16 at 18:24
  • $\begingroup$ @SHuntsman NB my tanh was wrong, I scaled it so that it gives what's in the picture $\endgroup$ – Shakespeare Jul 26 '16 at 20:53
1
$\begingroup$

You have worked out that $f^{\circ n}(x)\approx a(x)=x+nx^2$ near $x=0$. You can do something similar near $x=1$ and then "glue" the two ends together.

$$\begin{align} f(x)&=x^2+(1-x^2)x=x+x^2-x^3=1-2(1-x)^2+(1-x)^3\\ p(x)&:=1-f(1-x)=2x^2-x^3 \end{align}$$

Approximating $f^{\circ n}(x)$ near $x=1$ is essentially the same as approximating $p^{\circ n}(x)$ near $x=0$. $p^{\circ n}(x)\approx 2^{2^n-1}x^{2^n}$, and near $x=1$, you have $$f^{\circ n}(x)\approx b(x)=1-2^{2^n-1}(1-x)^{2^n}\qquad{x\text{ near }1}$$

If you could find some way to glue these, you'd have an approximation. Shooting from the hip, if you could follow each curve ($a$ forward from $0$, $b$ backward from $1$) until they no longer worked well as approximations, then connect the curves with a cubic spline, that's one idea. [It would require figuring out where to make the transitions though].

But there may be better ways to glue them.

$\endgroup$
  • 1
    $\begingroup$ This was precisely my original idea, but unless you can take it further than I did I just never felt it was "nice" enough. $\endgroup$ – Shakespeare Jul 27 '16 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.