[<< wikibooks] Fractals/Iterations in the complex plane/Fatou coordinate for f(z)=z+z^2)
= Will Jagy =
http://math.stackexchange.com/questions/208996/half-iterate-of-x2c?
"
This may be helpful.
Let

  
    
      
        f
        (
        x
        )
        =
        
          
            
              −
              1
              +
              
                
                  1
                  +
                  4
                  x
                
              
            
            2
          
        
        ,
        
        
        x
        >
        0
      
    
    {\displaystyle f(x)={\frac {-1+{\sqrt {1+4x}}}{2}},\;\;x>0}
  

We use a technique of Ecalle to solve for the Fatou coordinate 
  
    
      
        α
      
    
    {\displaystyle \alpha }
   that solves

  
    
      
        α
        (
        f
        (
        x
        )
        )
        =
        α
        (
        x
        )
        +
        1
      
    
    {\displaystyle \alpha (f(x))=\alpha (x)+1}
  

For any

  
    
      
        x
        >
        0
      
    
    {\displaystyle x>0}
  

let 

  
    
      
        
          x
          
            0
          
        
        =
        x
        ,
        
        
          x
          
            1
          
        
        =
        f
        (
        x
        )
        ,
        
        
          x
          
            2
          
        
        =
        f
        (
        f
        (
        x
        )
        )
        ,
        
        
          x
          
            n
            +
            1
          
        
        =
        f
        (
        
          x
          
            n
          
        
        )
      
    
    {\displaystyle x_{0}=x,\;x_{1}=f(x),\;x_{2}=f(f(x)),\;x_{n+1}=f(x_{n})}
  

Then we get the exact

  
    
      
        α
        (
        x
        )
        =
        
          lim
          
            n
            →
            ∞
          
        
        
          
            1
            
              x
              
                n
              
            
          
        
        −
        log
        ⁡
        
          x
          
            n
          
        
        +
        
          
            
              x
              
                n
              
            
            2
          
        
        −
        
          
            
              x
              
                n
              
              
                2
              
            
            3
          
        
        +
        
          
            
              13
              
                x
                
                  n
                
                
                  3
                
              
            
            36
          
        
        −
        
          
            
              113
              
                x
                
                  n
                
                
                  4
                
              
            
            240
          
        
        +
        
          
            
              1187
              
                x
                
                  n
                
                
                  5
                
              
            
            1800
          
        
        −
        
          
            
              877
              
                x
                
                  n
                
                
                  6
                
              
            
            945
          
        
        −
        n
      
    
    {\displaystyle \alpha (x)=\lim _{n\rightarrow \infty }{\frac {1}{x_{n}}}-\log x_{n}+{\frac {x_{n}}{2}}-{\frac {x_{n}^{2}}{3}}+{\frac {13x_{n}^{3}}{36}}-{\frac {113x_{n}^{4}}{240}}+{\frac {1187x_{n}^{5}}{1800}}-{\frac {877x_{n}^{6}}{945}}-n}
  

The point is that this expression converges far more rapidly than one would expect, and we may stop at a fairly small 
  
    
      
        n
      
    
    {\displaystyle n}
  .
It is fast enough that we may reasonably expect to solve numerically for 
  
    
      
        
          α
          
            −
            1
          
        
        (
        x
        )
      
    
    {\displaystyle \alpha ^{-1}(x)}
  .
We have 
  
    
      
        
          f
          
            −
            1
          
        
        (
        x
        )
        =
        x
        +
        
          x
          
            2
          
        
      
    
    {\displaystyle f^{-1}(x)=x+x^{2}}
  
Note

  
    
      
        α
        (
        x
        )
        =
        α
        (
        
          f
          
            −
            1
          
        
        (
        x
        )
        )
        +
        1
      
    
    {\displaystyle \alpha (x)=\alpha (f^{-1}(x))+1}
  

  
    
      
        α
        (
        x
        )
        −
        1
        =
        α
        (
        
          f
          
            −
            1
          
        
        (
        x
        )
        )
      
    
    {\displaystyle \alpha (x)-1=\alpha (f^{-1}(x))}
  

  
    
      
        
          α
          
            −
            1
          
        
        
          (
          
            α
            (
            x
            )
            −
            1
          
          )
        
        =
        
          f
          
            −
            1
          
        
        (
        x
        )
      
    
    {\displaystyle \alpha ^{-1}\left(\alpha (x)-1\right)=f^{-1}(x)}
  

It follows that if we define

  
    
      
        g
        (
        x
        )
        =
        
          α
          
            −
            1
          
        
        
          (
          
            α
            (
            x
            )
            −
            
              
                1
                2
              
            
          
          )
        
      
    
    {\displaystyle g(x)=\alpha ^{-1}\left(\alpha (x)-{\frac {1}{2}}\right)}
  

we get the miraculous

  
    
      
        g
        (
        g
        (
        x
        )
        )
        =
        
          α
          
            −
            1
          
        
        
          (
          
            α
            (
            x
            )
            −
            1
          
          )
        
        =
        
          f
          
            −
            1
          
        
        (
        x
        )
        =
        x
        +
        
          x
          
            2
          
        
      
    
    {\displaystyle g(g(x))=\alpha ^{-1}\left(\alpha (x)-1\right)=f^{-1}(x)=x+x^{2}}
  

...
Note that 
  
    
      
        α
      
    
    {\displaystyle \alpha }
   is actually holomorphic in an open sector that does not include the origin, such as real part positive. That is the punchline here, 
  
    
      
        α
      
    
    {\displaystyle \alpha }
   cannot be extended around the origin as single-valued holomorphic.
So, since we are finding a power series around 
  
    
      
        0
      
    
    {\displaystyle 0}
  , not only are there a 
  
    
      
        1
        
          /
        
        z
      
    
    {\displaystyle 1/z}
   term, which would not be so bad, but there is also a 
  
    
      
        log
        ⁡
        z
      
    
    {\displaystyle \log z}
   term. 
So the 
  
    
      
        …
        −
        n
      
    
    {\displaystyle \ldots -n}
   business is crucial.
I give a complete worked example at my question http://mathoverflow.net/questions/45608/formal-power-series-convergence 
as my answer http://mathoverflow.net/questions/45608/formal-power-series-convergence/46765#46765
The Ecalle technique is described in English in a book, see  

[K_C_G PDF] http://zakuski.utsa.edu/~jagy/K_C_G_book_excerpts.pdf
[BAKER] http://zakuski.utsa.edu/~jagy/other.htmlThe Julia equation is Theorem 8.5.1 on page 346 of KCG.
It would be no problem to produce, say, 50 terms of 
  
    
      
        α
        (
        x
        )
      
    
    {\displaystyle \alpha (x)}
   with some other computer algebra system that allows longer power series and enough programming that the finding of the correct coefficients, which i did one at a time, can be automated.
No matter what, you always get the

  
    
      
        α
        =
        
          
            stuff
          
        
        −
        n
      
    
    {\displaystyle \alpha ={\mbox{stuff}}-n}
  

when

  
    
      
        f
        ≤
        x
      
    
    {\displaystyle f\leq x}
  

As I said in comment, the way to improve this is to take a few dozen terms in the expansion of 
  
    
      
        α
        (
        x
        )
      
    
    {\displaystyle \alpha (x)}
   so as to get the desired decimal precision with a more reasonable number of evaluations of 
  
    
      
        f
        (
        x
        )
        .
        <
        m
        a
        t
        h
        >
        S
        o
        h
        e
        r
        e
        i
        s
        a
        b
        r
        i
        e
        f
        v
        e
        r
        s
        i
        o
        n
        o
        f
        t
        h
        e
        G
        P
        −
        P
        A
        R
        I
        s
        e
        s
        s
        i
        o
        n
        t
        h
        a
        t
        p
        r
        o
        d
        u
        c
        e
        d
        <
        m
        a
        t
        h
        >
        α
        (
        x
        )
      
    
    {\displaystyle f(x).SohereisabriefversionoftheGP-PARIsessionthatproduced\alpha (x)}
  :

=======

        ? taylor( (-1 + sqrt(1 + 4 * x))/2  , x  )
        %1 = x - x^2 + 2*x^3 - 5*x^4 + 14*x^5 - 42*x^6 + 132*x^7 - 429*x^8 + 1430*x^9 - 4862*x^10 + 16796*x^11 - 58786*x^12 + 208012*x^13 - 742900*x^14 + 2674440*x^15 + O(x^16) 
        
        f = x - x^2 + 2*x^3 - 5*x^4 + 14*x^5 - 42*x^6 + 132*x^7 - 429*x^8 + 1430*x^9 - 4862*x^10 + 16796*x^11 - 58786*x^12 + 208012*x^13 - 742900*x^14 + 2674440*x^15  
        
        ? fp = deriv(f) 
        %3 = 40116600*x^14 - 10400600*x^13 + 2704156*x^12 - 705432*x^11 + 184756*x^10 - 48620*x^9 + 12870*x^8 - 3432*x^7 + 924*x^6 - 252*x^5 + 70*x^4 - 20*x^3 + 6*x^2 - 2*x + 1 
        
        L = - f^2 + a * f^3 
        
        R = - x^2 + a * x^3
        
        compare = L - fp * R 
        
        19129277941464384000*a*x^45 - 15941064951220320000*a*x^44 +
     8891571783902889600*a*x^43 - 4151151429711140800*a*x^42 + 
    1752764158206050880*a*x^41 - 694541260905326880*a*x^40 + 
    263750697873178528*a*x^39 - 97281246609064752*a*x^38 + 35183136631942128*a*x^37 
    - 12571609170862072*a*x^36 + 4469001402841488*a*x^35 - 1592851713897816*a*x^34 + 
    575848308018344*a*x^33 - 216669955210116*a*x^32 + 96991182256584*a*x^31 + 
    (-37103739145436*a - 7152629313600)*x^30 + (13153650384828*a + 
    3973682952000)*x^29 + (-4464728141142*a - 1664531636560)*x^28 + (1475471500748*a 
    + 623503489280)*x^27 + (-479514623058*a - 220453019424)*x^26 + (154294360974*a + 
    75418138224)*x^25 + (-49409606805*a - 25316190900)*x^24 + (15816469500*a + 
    8416811520)*x^23 + (-5083280370*a - 2792115360)*x^22 + (1648523850*a + 
    930705120)*x^21 + (-543121425*a - 314317080)*x^20 + (183751830*a + 
    108854400)*x^19 + (-65202585*a - 39539760)*x^18 + (-14453775*a + 15967980)*x^17 
    + (3380195*a + 30421755)*x^16 + (-772616*a - 7726160)*x^15 + (170544*a + 
    1961256)*x^14 + (-35530*a - 497420)*x^13 + (6630*a + 125970)*x^12 + (-936*a - 
    31824)*x^11 + 8008*x^10 + (77*a - 2002)*x^9 + (-45*a + 495)*x^8 + (20*a - 
    120)*x^7 + (-8*a + 28)*x^6 + (3*a - 6)*x^5 + (-a + 1)*x^4 
       
        Therefore a = 1  !!! 
        
        ? 
        L = - f^2 +  f^3 + a * f^4
        
        R = - x^2 +  x^3 + a * x^4 
        
        compare = L - fp * R 
         ....+ (1078*a + 8008)*x^10 + (-320*a - 1925)*x^9 + (95*a + 450)*x^8 + (-28*a - 100)*x^7 + (8*a + 20)*x^6 + (-2*a - 3)*x^5 
        
        This time a = -3/2  !
        
        
        L = - f^2 +  f^3  - 3 * f^4 / 2  + c * f^5 
        
        R = - x^2 +  x^3 - 3 * x^4 / 2  + c * x^5  
        
         compare = L - fp * R
        ...+ (2716*c - 27300)*x^11 + (-749*c + 6391)*x^10 + (205*c - 1445)*x^9 + (-55*c + 615/2)*x^8 + (14*c - 58)*x^7 + (-3*c + 8)*x^6 
        
        
        So c = 8/3 . 
        
        The printouts began to get too long, so I said no using semicolons, and requested coefficients one at a time..
        
        L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 + a * f^6; 
        
        R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  + a * x^6; 
        
           compare = L - fp * R;
         
        ? polcoeff(compare,5)
        %22 = 0
        ? 
        ?  polcoeff(compare,6)
        %23 = 0
        ? 
        ?  polcoeff(compare,7)
        %24 = -4*a - 62/3
        
        So this a = -31/6 
        
        
        I ran out of energy about here:
          L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 - 31 * f^6 / 6 + 157 * f^7 / 15 - 649 * f^8 / 30 + 9427 * f^9 / 210 + b * f^10 ; 
        
          R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  - 31 * x^6 / 6 + 157 * x^7 / 15 - 649 * x^8 / 30 + 9427 * x^9 / 210  + b * x^10;
        
           compare = L - fp * R; 
        ? 
        ?  polcoeff(compare, 10 )
        %56 = 0
        ? 
        ? 
        ?  polcoeff(compare, 11 ) 
        %57 = -8*b - 77692/105
        ? 
        ? 
          L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 - 31 * f^6 / 6 + 157 * f^7 / 15 - 649 * f^8 / 30 + 9427 * f^9 / 210 - 19423 * f^10 / 210 ; 
        
          R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  - 31 * x^6 / 6 + 157 * x^7 / 15 - 649 * x^8 / 30 + 9427 * x^9 / 210 - 19423 * x^10 / 210;
        
           compare = L - fp * R; 
        ?  polcoeff(compare, 10 )
        %61 = 0
        ? 
        ?  polcoeff(compare, 11 ) 
        %62 = 0
        ? 
        ?  polcoeff(compare, 12) 
        %63 = 59184/35
        ? 
        
        So R = 1 / alpha' solves the Julia equation   R(f(x)) = f'(x) R(x).
        
        Reciprocal is alpha'
        
        ? S =   taylor( 1 / R, x)
        %65 = -x^-2 - x^-1 + 1/2 - 2/3*x + 13/12*x^2 - 113/60*x^3 + 1187/360*x^4 - 1754/315*x^5 + 14569/1680*x^6 + 532963/3024*x^7 + 1819157/151200*x^8 - 70379/4725*x^9 + 10093847/129600*x^10 - 222131137/907200*x^11 + 8110731527/12700800*x^12 - 8882574457/5953500*x^13 + 24791394983/7776000*x^14 - 113022877691/18144000*x^15 + O(x^16) 
        
        The bad news is that Pari refuses to integrate 1/x, 
    even when I took out that term it put it all on a common denominator,
     so i integrated one term at a time to get
    
    alpha = integral(S)
    
    and i had to type in the terms myself, especially the log(x)
        
        ? alpha = 1 / x - log(x) + x / 2 - x^2 / 3 + 13 * x^3 / 36 - 113 * x^4 / 240 + 1187 * x^5 / 1800 - 877 * x^6 / 945 + 14569 * x^7 / 11760 + 532963 * x^8 / 24192

======

"


= Jonathan Lubin =
From http://math.stackexchange.com/questions/911818/how-to-obtain-fx-if-it-is-known-that-ffx-x2x?
"Here’s a technique for finding the first few terms of a formal power series representing the fractional iterate of a given function like

  
    
      
        f
        (
        x
        )
        =
        x
        +
        
          x
          
            2
          
        
      
    
    {\displaystyle f(x)=x+x^{2}}
  .
I repeat that this is a formal solution to the problem, and leaves unaddressed all considerations of convergence of the series answer.
I’m going to find the first six terms of

  
    
      
        
          f
          
            ∘
            1
            
              /
            
            2
          
        
        (
        x
        )
      
    
    {\displaystyle f^{\circ 1/2}(x)}
  
the “half-th” iterate of 
  
    
      
        f
      
    
    {\displaystyle f}
  , out to the 
  
    
      
        
          x
          
            5
          
        
      
    
    {\displaystyle x^{5}}
  -term.
Let’s write down the iterates of 
  
    
      
        f
      
    
    {\displaystyle f}
  , starting with the zero-th.

  
    
      
        
          
            
              
                
                  f
                  
                    ∘
                    0
                  
                
                (
                x
                )
              
              
                
                =
                x
              
            
            
              
                
                  f
                  
                    ∘
                    1
                  
                
                =
                f
              
              
                
                =
                x
              
              
                +
                
                  x
                  
                    2
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    2
                  
                
              
              
                
                =
                x
              
              
                +
                2
                
                  x
                  
                    2
                  
                
              
              
                
                +
                2
                
                  x
                  
                    3
                  
                
              
              
                +
                
                  x
                  
                    4
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    3
                  
                
              
              
                
                ≡
                x
              
              
                +
                3
                
                  x
                  
                    3
                  
                
              
              
                
                +
                6
                
                  x
                  
                    3
                  
                
              
              
                +
                9
                
                  x
                  
                    4
                  
                
              
              
                
                +
                10
                
                  x
                  
                    5
                  
                
              
              
                +
                8
                
                  x
                  
                    6
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    4
                  
                
              
              
                
                ≡
                x
              
              
                +
                4
                
                  x
                  
                    2
                  
                
              
              
                
                +
                12
                
                  x
                  
                    3
                  
                
              
              
                +
                30
                
                  x
                  
                    4
                  
                
              
              
                
                +
                64
                
                  x
                  
                    5
                  
                
              
              
                +
                118
                
                  x
                  
                    6
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    5
                  
                
              
              
                
                ≡
                x
              
              
                +
                5
                
                  x
                  
                    2
                  
                
              
              
                
                +
                20
                
                  x
                  
                    3
                  
                
              
              
                +
                70
                
                  x
                  
                    4
                  
                
              
              
                
                +
                220
                
                  x
                  
                    5
                  
                
              
              
                +
                630
                
                  x
                  
                    6
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    6
                  
                
              
              
                
                ≡
                x
              
              
                +
                6
                
                  x
                  
                    2
                  
                
              
              
                
                +
                30
                
                  x
                  
                    3
                  
                
              
              
                +
                135
                
                  x
                  
                    4
                  
                
              
              
                
                +
                560
                
                  x
                  
                    5
                  
                
              
              
                +
                2170
                
                  x
                  
                    6
                  
                
              
            
            
              
                
                  f
                  
                    ∘
                    7
                  
                
              
              
                
                ≡
                x
              
              
                +
                7
                
                  x
                  
                    2
                  
                
              
              
                
                +
                42
                
                  x
                  
                    3
                  
                
              
              
                +
                231
                
                  x
                  
                    4
                  
                
              
              
                
                +
                1190
                
                  x
                  
                    5
                  
                
              
              
                +
                5810
                
                  x
                  
                    6
                  
                
                
                ,
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}f^{\circ 0}(x)&=x\\f^{\circ 1}=f&=x&+x^{2}\\f^{\circ 2}&=x&+2x^{2}&+2x^{3}&+x^{4}\\f^{\circ 3}&\equiv x&+3x^{3}&+6x^{3}&+9x^{4}&+10x^{5}&+8x^{6}\\f^{\circ 4}&\equiv x&+4x^{2}&+12x^{3}&+30x^{4}&+64x^{5}&+118x^{6}\\f^{\circ 5}&\equiv x&+5x^{2}&+20x^{3}&+70x^{4}&+220x^{5}&+630x^{6}\\f^{\circ 6}&\equiv x&+6x^{2}&+30x^{3}&+135x^{4}&+560x^{5}&+2170x^{6}\\f^{\circ 7}&\equiv x&+7x^{2}&+42x^{3}&+231x^{4}&+1190x^{5}&+5810x^{6}\,,\end{aligned}}}
  
where the congruences are modulo all terms of degree 
  
    
      
        7
      
    
    {\displaystyle 7}
   and more.
Now look at the coefficients 

of the 
  
    
      
        x
      
    
    {\displaystyle x}
  -term: always 
  
    
      
        1
      
    
    {\displaystyle 1}
  .
Of the 
  
    
      
        
          x
          
            2
          
        
      
    
    {\displaystyle x^{2}}
  -term? In 
  
    
      
        
          f
          
            ∘
            n
          
        
      
    
    {\displaystyle f^{\circ n}}
  , it’s 
  
    
      
        
          C
          
            2
          
        
        (
        n
        )
        =
        n
      
    
    {\displaystyle C_{2}(n)=n}
  .
The coefficient of 
  
    
      
        
          x
          
            3
          
        
      
    
    {\displaystyle x^{3}}
   in 
  
    
      
        
          f
          
            ∘
            n
          
        
      
    
    {\displaystyle f^{\circ n}}
   is 
  
    
      
        
          C
          
            3
          
        
        (
        n
        )
        =
        n
        (
        n
        −
        1
        )
        =
        
          n
          
            2
          
        
        −
        n
      
    
    {\displaystyle C_{3}(n)=n(n-1)=n^{2}-n}
  , as one can see by inspection.Now, a moment’s thought (well, maybe several moments’) tells you that 
  
    
      
        
          C
          
            j
          
        
        (
        n
        )
      
    
    {\displaystyle C_{j}(n)}
  , the coefficient of 
  
    
      
        
          x
          
            j
          
        
      
    
    {\displaystyle x^{j}}
   in 
  
    
      
        
          f
          
            ∘
            n
          
        
      
    
    {\displaystyle f^{\circ n}}
  , is a polynomial in 
  
    
      
        n
      
    
    {\displaystyle n}
   of degree 
  
    
      
        j
        −
        1
      
    
    {\displaystyle j-1}
  .
And a familiar technique of finite differences shows you that

  
    
      
        
          
            
              
                
                  C
                  
                    4
                  
                
                (
                n
                )
              
              
                
                =
                
                  
                    
                      2
                      
                        n
                        
                          3
                        
                      
                      −
                      5
                      
                        n
                        
                          2
                        
                      
                      +
                      3
                      n
                    
                    2
                  
                
              
            
            
              
                
                  C
                  
                    5
                  
                
                (
                n
                )
              
              
                
                =
                
                  
                    
                      3
                      
                        n
                        
                          4
                        
                      
                      −
                      13
                      
                        n
                        
                          3
                        
                      
                      +
                      18
                      
                        n
                        
                          2
                        
                      
                      −
                      8
                      n
                    
                    3
                  
                
                
                ,
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}C_{4}(n)&={\frac {2n^{3}-5n^{2}+3n}{2}}\\C_{5}(n)&={\frac {3n^{4}-13n^{3}+18n^{2}-8n}{3}}\,,\end{aligned}}}
  
I won’t go into the details of that technique. The upshot is that, modulo terms of degree 
  
    
      
        6
      
    
    {\displaystyle 6}
   and higher, you have

  
    
      
        
          f
          
            ∘
            n
          
        
        (
        x
        )
        ≡
        x
        +
        n
        
          x
          
            2
          
        
        +
        (
        
          n
          
            2
          
        
        −
        n
        )
        
          x
          
            3
          
        
        +
        
          
            1
            2
          
        
        (
        2
        
          n
          
            3
          
        
        −
        5
        
          n
          
            2
          
        
        +
        3
        n
        )
        
          x
          
            4
          
        
        +
        
          
            1
            3
          
        
        (
        3
        
          n
          
            4
          
        
        −
        13
        
          n
          
            3
          
        
        +
        18
        
          n
          
            2
          
        
        −
        8
        n
        )
        
          x
          
            5
          
        
      
    
    {\displaystyle f^{\circ n}(x)\equiv x+nx^{2}+(n^{2}-n)x^{3}+{\frac {1}{2}}(2n^{3}-5n^{2}+3n)x^{4}+{\frac {1}{3}}(3n^{4}-13n^{3}+18n^{2}-8n)x^{5}}
  .
Now, you just plug in 
  
    
      
        n
        =
        
          
            1
            2
          
        
      
    
    {\displaystyle n={\frac {1}{2}}}
   in this formula to get your desired series.
And I’ll leave it to you to go one degree higher, using the iterates I’ve given you."