4

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.

AccidentalFourierTransform
  • 2,592
Rhys Hughes
  • 12,842

2 Answers2

4

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.

Angina Seng
  • 158,341
3

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} \, . $$

Martin R
  • 113,040
  • 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. – Rhys Hughes Jul 14 '18 at 17:49
  • @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. – Martin R Jul 14 '18 at 18:07