4
$\begingroup$

I'm working with this iteration used for approximating square roots and trying to see what I can draw out from it, and in doing so I found something very strange that I can't logically explain. I'm looking for any insight into why this is the case or perhaps a proof of it. The iteration is as follows:

$$\rho_{n+1}=\frac{(\rho_n)^2+x}{2\rho_n},\rho_0=1$$ which approximates $\sqrt x$

I'll list the first four general results here:

$$\rho_1=\frac{x+1}{2}$$ $$\rho_2=\frac{x^2+6x+1}{4x+4}$$ $$\rho_3=\frac{x^4+28x^3+70x^2+28x+1}{8x^3+56x^2+56x+8}$$ $$\rho_4=\frac{x^8+120x^7+1820x^6+8008x^5+12870x^4+8008x^3+1820x^2+120x+1}{16x^7+560x^6+4368x^5+11440x^4+11440x^3+4368x^2+560x+16}$$

The property I spotted was that in all cases, the co-efficients of $(x+1)^{2^n}$ appear in $\rho_n$, with the co-efficients of even powers on the numerator and of odd powers on the denominator of $\rho_n$, in such a way that they snake through the polynomial fractions. For example $$(x+1)^8=x^8+8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1$$ and a comparison with $\rho_3$ shows my point nicely.

I can show the general results as sums of multiples of powers of $(x+1)$ and $x$, e.g. $$\rho_2=\frac{(x+1)^2+4x}{4(x+1)}$$ $$\rho_3=\frac{(x+1)^4+24x(x+1)^2+16x}{8(x+1)^3+32x(x+1)}$$

however I don't know how much use this is in explaining the property I found.

Any ideas will be appreciated.

$\endgroup$
3
$\begingroup$

Possible fixed points of the iteration are $\sqrt x$ and $-\sqrt x$, this suggests to look at $$ \frac{\rho_{n+1} - \sqrt x}{\rho_{n+1} + \sqrt x} = \frac{\rho_n^2 - 2 \sqrt x \rho_n + x}{\rho_n^2 + 2 \sqrt x \rho_n + x} = \left( \frac{\rho_n - \sqrt x}{\rho_n + \sqrt x} \right)^2 \, . $$ It follows that $$ \frac{\rho_n - \sqrt x}{\rho_n + \sqrt x} = \left( \frac{1 - \sqrt x}{1 + \sqrt x} \right)^{2^n} \, . $$ This implies (quadratic) convergence of $\rho_n$ to $\sqrt x$ because the fraction on the right-hand side is of absolute value less than one if $x > 0$. It also gives the explicit formula $$ \rho_n=\frac{(\sqrt x+1)^{2^n}+(\sqrt x-1)^{2^n}} {(\sqrt x+1)^{2^n}-(\sqrt x-1)^{2^n}}\sqrt x $$ which Lord Shark the Unknown found.

If we expand all expressions using the binomial formula then all odd powers of $\sqrt x$ cancel in the numerator, and all even powers of $\sqrt x$ cancel in the denominator. This gives the expression (first found by achille hui in a now deleted answer): $$ \rho_n = \frac{\sum_{k=0}^{2^{n-1}} \binom{2^n}{2k} x^k}{\sum_{k=0}^{2^{n-1}}\binom{2^n}{2k+1} x^k} $$ where the coefficients of the binomial expansion of $(x+1)^{2^n}$ appear alternatingly in the numerator and denominator.

Note also that this is exactly Newton's method to find a zero of $f(\rho) = \rho^2 - x$: $$ \rho_{n+1} = \rho_n - \frac{f(\rho_n)}{f'(\rho_n)} = \rho_n - \frac{\rho_n^2 - x}{2 \rho_n} = \frac{\rho_n^2 + x}{2 \rho_n} \, . $$

$\endgroup$
  • $\begingroup$ Hi Martin, many thanks for the answer, but I'm not sure if it does, or exactly how it answers my question. I understand and appreciate that this iteration converges to $\sqrt x$ (a quicker way to show this is to show that when $\rho_k=\sqrt x, \rho_{k+1}=\rho_k$ and we have a cut-off point). My question is asking why the co-efficients of the general result of $\rho_n$ match those of $(x+1)^{2^n}$, and I'm not sure if/how your answer provides a solution to that. $\endgroup$ – Rhys Hughes Jul 14 '18 at 17:49
  • $\begingroup$ @RhysHughes: See update. The new expression appeared first in an answer from achille hui and I did not want to copy it. Now that answer is deleted, so I have added it here. $\endgroup$ – Martin R Jul 14 '18 at 18:07
4
$\begingroup$

From these formulae, it appears that $$\rho_n=\frac{(\sqrt x+1)^{2^n}+(\sqrt x-1)^{2^n}} {(\sqrt x+1)^{2^n}-(\sqrt x-1)^{2^n}}\sqrt x$$ and once one has that formula, one may verify it by induction.

$\endgroup$

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.