# Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?

For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $\small z^2$ by recursion according to $$\small x_0 = 1 \qquad x_{k+1} = \left( {z^2 \over x_k}+x_k \right)/2$$ where only $\small z^2$ is known and z is sought by $\small z = \lim_{k \to \infty} x_k$.

After expanding some iterations in symbolic variables I got the pattern for a closed form $$\small x_k = z{ (z+x_0)^{2^k} + (z-x_0)^{2^k} \over (z+x_0)^{2^k} - (z-x_0)^{2^k} }$$ which might further be compacted to $$\small x_k = z \cdot \left(1 - { 2\over 1- \left({ z+x_0 \over z-x_0 }\right)^{2^k} } \right)$$ If z is known then this is a nice form for fractionally iterating the original recursion; given some $\small x_0$ and $\small \sqrt{z^2}$ I can plot the function and see the quality of approximation by a smooth curve (its logarithm shows a parabola), ... but the requirement is obviously from the statement of the problem (" find the squareroot of z ") that z should occur in even powers only.

Well, if I expand the first version of the two closed forms then only the binomial coefficients at even order in the numerator and at odd order in the denominator remain (where the z at the beginning of the formula cancels against one occurence in the denominator) and thus I've to deal with the given $\small z^2$ only. However, then I have variable number of terms for varying k and for fractional k their number is even infinite, so this is not the final solution where I'm after.

I might overlook something trivial, but how could I reformulate this such that I get even powers of z only and still have an expression, where k can be taken fractional?

Just a short addendum Sep 18. The Kalantari-paper has the formula a bit different; significant is a sign-change(I'll have to check my other derivation again) such that I should assume the more correct form: $$\small x_k = z{ (x_0+z)^{2^k} + (x_0-z)^{2^k} \over (x_0+z)^{2^k} - (x_0-z)^{2^k} }$$ This can be reformulated into the surprising form, where k is the index of iterations if the Newton-formula is employed: $$\small {x_k-z \over x_k+z}= \left( {x_0-z \over x_0+z}\right)^{2^k}$$

This form has the interesting property, that -once $\small \left| x_0-z \right| <1$ - then it is immediately visible, that each iteration approximates zero with quadratic error reduction, simply because of the repeated squaring of the small numerator.

[update] While for integer-indexed iterations the sign-question is irrelevant (and the significant terms in the binomial expansions cancel, so the effect is invisible) this is not so for the 0'th iteration: then the numerators and denominators of the lhs and rhs should be equal, so the Kalantari-sign-scheme was the meaningful one.

-
I'll just note that your closed form is the same as what Kalantari derived in his paper (and also generalizes, e.g. the Halley iterates are obtained by replacing the $2^k$ with $3^k$ in the expression you gave). It doesn't look to me that there's a neat way to express the iterates such that you are dealing with $z^2$ instead of $z$... – J. M. Aug 31 '11 at 16:33
@J.M.:very nice! Unfortunately no access to the article further than the first page. (But the polynomial art at Professor Kalantari's site is marvelous!) – Gottfried Helms Aug 31 '11 at 18:48
Yeah, Polynomiography looks quite fun, and I'd probably be doing it if I had more time on my hands. On the article: I can hook you up with a copy; I've tried looking for your e-mail address in your home page yet I can't seem to find it... – J. M. Aug 31 '11 at 18:54
It's not really that different; remember that you're raising to an even exponent, and since $(-1)^{2n}=1$... ;) – J. M. Sep 18 '11 at 22:47
@J.M.:true; but remember, I'm considering fractional iteration (or: a continuous function in k), so 2^k is not always even. But setting k=0 gives a decisive answer. – Gottfried Helms Sep 18 '11 at 22:57
show 2 more comments