Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.