Rate of Convergence of Borwein Algorithm for computing Pi

Question

In a book "Pi and the AGM" in 1987, authors, Jonathan Borwein and Peter Borwein, introduced a magical algorithm to compute $\pi$. However there is a problem that I couldn't understand and couldn't find any proof or explaination. It is related to rate of convergence of the algorithm.

Borwein brothers suggested two sequences $\{x_n\}_{ n\ge 0}$ and $\{y_n\}_{ n\ge 1}$ like:

\begin{equation} x_{0} := \sqrt{2} ~~~~,~~~~y_{1}:= 2^{1/4} \end{equation}

\begin{equation} x_{n+1}=\frac{\sqrt{x_n} ~+~ 1/\sqrt{x_n} }{2} ~~~,~~~ y_{n+1}=\frac{y_{n} \sqrt{x_n}~+~ 1/\sqrt{x_n}}{y_{n} +1} \end{equation}

Then my question is about a proof for the next inequality:

\begin{equation} \label{eq} \forall n \in \mathbb{N}~,~~~\frac{x_n -1}{y_n -1} < 2- \sqrt{3} \end{equation}

How can I prove this inequality?

Answer 1

Even for different starting values around $1$, both $x_n$ and $y_n$ rapidly approach $1$.

Define $\alpha_n = x_n-1$ and $\beta_n = y_n-1$. These will be very small quantities. $\beta_5 \lt 10^{-40}$ and $\alpha_5$ is smaller. We want to estimate $\alpha_n/\beta_n$.

$$\sqrt{x_n} = \sqrt{1+\alpha_n} = 1+\frac{1}{2}\alpha_n - \frac{1}{8}\alpha_n^2 + O(\alpha_n^3).$$

$$1/\sqrt{x_n} = 1/\sqrt{1+\alpha_n} = 1-\frac{1}{2}\alpha_n +\frac{3}{8} \alpha_n^2 + O(\alpha_n^3)$$

$$x_{n+1} = \frac{1}{2}(\sqrt{x_n} + 1/\sqrt{x_n}) = 1+\frac{1}{8}\alpha_n^2 +O(\alpha_n^3) $$

So, $\alpha_{n+1} = \frac{1}{8} \alpha_n^2 + O(\alpha_n^3)$.

$$\begin{eqnarray}y_{n+1} &=& \frac{y_n\sqrt{x_n} + \sqrt{x_n} - \sqrt{x_n} + 1/\sqrt{x_n}}{y_n+1} \newline &=& \sqrt{x_n} + \frac{-\sqrt{x_n} +1/\sqrt{x_n}}{y_n+1} \newline &=&1+\frac{1}{2}\alpha_n-\frac{1}{8}\alpha_n^2 + O(\alpha_n^3) + (-\alpha_n+\frac{1}{2}\alpha_n^2+O(\alpha_n^3))(\frac{1}{2} - \frac{1}{4}\beta_n + O(\beta_n^2)) \newline &=& 1 + \frac{1}{8}\alpha_n^2 + \frac{1}{4}\alpha_n\beta_n + O(\beta_n^3)\end{eqnarray}$$

So, $\beta_{n+1} = \frac{1}{8}\alpha_n^2 + \frac{1}{4}\alpha_n\beta_n + O(\beta_n^3)$.

Instead of $\alpha_n/\beta_n$, consider the reciprocal.

$\beta_{n+1}/\alpha_{n+1} = 1 + 2 \beta_n/\alpha_n + O(\alpha_n).$ This ratio grows exponentially, and we only need to establish that it is greater than $1/(2-\sqrt{3}) = 2+\sqrt{3} \lt 4$.

For example, $\beta_4/\alpha_4 = 99.53, \beta_5/\alpha_5 = 200.06$.

To turn this into a rigorous argument, you can use effective instead of asymptotic estimates for $\sqrt{1+\alpha_n}$, $1/\sqrt{1+\alpha_n}$, and $1/(2+\beta_n)$ when $\alpha_n$ and $\beta_n$ are small.