Numerically find the half-iterate of a quadratic

Question

Let's say we have a function $f(x)=n+mx+lx^2$, and want to find another function $h(x) = a+bx+cx^2 $ such that $h(h(x)) = f(x)$. Here's what you get when composing h on itself:

$$h(h(x)) = a+ab+b^{2}x+bcx^{2}+a^{2}c+2abcx+2ac^{2}x^{2}+b^{2}cx^{2}+2bc^{2}x^{3}+c^{3}x^{4}$$

If we ignore the $x^3$ and onwards terms and gather the constants, $x$ terms, and $x^2$ terms, we can get a system of three equations which ignores enough terms to not be overly specified, but including enough terms to be a half-decent approximation:

$$a+ab+a^{2}c = n,$$ $$b^{2} + 2abc = m,$$ $$bc+2ac^{2}+b^{2}c = l$$

My original plan was to get $c$ isolated in each of these like so: $$c = \frac{(n - a (b + 1))}{a^2},$$ $$c = \frac{(m - b^2)}{2 a b},$$ $$c = \frac{l}{(b^2 + b)}$$

This way I could treat each of these as 3D functions and find their intersection (much like how you can solve a system of 2 equations by treating the equations as 2D functions). Using the identity that $2x-y-z=0$ if $x=y=z$, I could reduce the intersection problem further down into one equation (which can also be treated as a 3D function) which I need to find the zero/root of: $$2\cdot{\frac{(n - a (b + 1))}{a^2}} -\frac{(m - b^2)}{2 a b} - \frac{l}{(b^2 + b)} = 0$$

The problem is, I don't know of any root/zero-finding algorithms supporting 2-argument functions, since for example, Netwon's method requires a derivative which we can't do here. So, is my approach wrong, is there a root-finding method I don't know of, or is there no solution? And if there is a solution, could this method be applied to higher-order polynomials?

Answer 1

In general, half iterates of quadratics may not even exist, or exist on the entirety of $\mathbb R$.

As for the main question, solving for the coefficients amounts to solving 5th 7th order polynomials (after you isolate each variable), and generalizing this to higher order polynomial approximations about $x=0$ will result in increasingly complex polynomials to be solved.

For alternative methods, you can see here.

For small values of $x$, one approach is to take the Taylor expansion about $x=h(x)=f(x)$.

For large values of $x$, an iterative approach can be used based on the asymptotic behavior of $h$. See this graph for an example.

Answer 2

By eliminating $a$ and $c$, I obtained a polynomial equation in $b$: $$a=\frac{2nb}{2b+b^2+m},$$ $$c=\frac{(m-b^2)(m+b^2+2b)}{4nb^2},$$ $$m^3+2bm^2+(m^2-4ln-2m)b^3+mb^4-2b^6-b^7=0.$$

You can solve it with a polynomial solver, or even with just Newton. There is at least one real root.