0

http://www.mathpath.org/Algor/squareroot/algor.bhaskara.brouncker.htm

What is the convergence rate of this algorithm? I have tried various google searches to no avail.

(For example, the convergence of Newton's Method is Quadratic, the convergence of the Bisection method is linear, and the convergence of the Secant Method is between linear and quadratic)

user1380792
  • 203

2 Answers2

1

Note: This is more convergence analysis in response to comments by OP to my original answer.

The iterative method, using $x_n = a_n/b_n$, can be written as $$ x_{n+1} = \frac{x_n + Q}{x_n + 1} \tag 1$$ To keep algebra simple, let $s = \sqrt{Q}$. Then $$ x_{n+1} - s = \frac{x_n+s^2}{x_n + 1} - s = (x_n -s) \frac{1-s}{x_n+1} \tag 2$$

Now suppose that $Q > 1$ and $x_0 > 0$. Then from (1), $x_n >0 \, \forall n$

From (2), we see that $x_n - s$ changes sign at each step. If $x_n > s$ then $$ \frac{x_{n+2}-s}{x_n-s} = \frac{(s-1)^2}{2 x_n + s^2 +1} < \left(\frac{s-1}{s+1}\right)^2 < 1$$ This shows that the sub sequence of the entries $> s$ converge to $s$. From (2), if $x_n>s$, $$ \left |x_{n+1} - s \right|=\left|x_n -s\right| \left|\frac{s-1}{x_n+1}\right| < \left|x_n -s\right| $$ So the entire sequence converges to $s$.

Now for the rate of convergence:

$$ \lim_{n\rightarrow \infty} \frac { \left |x_{n+1} - s \right|}{\left|x_n -s\right|} = \lim_{n\rightarrow \infty} \frac{s-1}{x_n+1} = \frac{s-1}{s+1} < 1 $$

So the convergence is linear with rate $$ \frac{\sqrt{Q}-1}{\sqrt{Q}+1} $$

user44197
  • 9,730
0

Very slow!

The convergence is geometric with ratio $\approx (\sqrt{Q}-1)/(\sqrt{Q}+1) $

The iterative formula is $$x_{n+1} = \frac{x_n + Q}{x_n + 1}$$

start with $Q=10^4$ and $x=50$ and see how slowly it gets to 100!

The main use of the formula is not to find square roots but to do with quadratic residues and factorization. I can't think of a slower way to calculate square roots!

user44197
  • 9,730
  • Well, isn't that less than one? then how come it is faster than the Midpoint/Bisection Method, which is linear? – user1380792 Dec 30 '13 at 21:18
  • It is super slow. Just try finding the square root of $1024$. Starting at $1$, 10 steps gets you to only 10.5. Bisection by definition will get you to $32 \pm 1$. This algorithm is used to solve number theoretic problems and not finding square roots. If you need to find square roots as ratios, try $x_{n+1} = x_n^2 + Q y_n^2$, $y_{n+1} = 2 x_n y_n$ – user44197 Dec 30 '13 at 21:33
  • I know but I am mainly considered for Q = sqrt2. I am doing this for a science fair project, so I need to explain convergences really shortly. Therefore I use terms like linear, quadratic, and between linear and quadratic for the bisection, newton, and secant methods, but I don't know what to use for this method. Should I just say geometric? Should I say a convergence rate between the secant and bisection methods? – user1380792 Dec 31 '13 at 16:46
  • I am sorry, I should have mentioned that geometric is same as linear. I will provide a detailed analysis in another answer as it is too difficult to use the comment box. – user44197 Dec 31 '13 at 18:25