Speed of the binomial series for calculating $\sqrt{3}$

Question

Calculating $\sqrt{3}$ by the binomial series for $(4-1)^{\frac{1}{2}}$ seems to converge very much more slowly than the Newton Raphson method for improving an initial approximation of $\sqrt{3}\approx 2$. Is that right?

This is not a sophisticated question. I ask because I'm trying to understand an algebra textbook from 1826 (Bridge The Elements of Algebra). So I have done some hand calculations with the binomial series and they seem much slower than the obvious Newton Raphson calculations although Bridge says the binomial series is very fast. So I want to check with people who know this method. Should I expect the binomial theorem to be slower than Newton Raphson for this problem?

Answer 1

The binomial series, or more general, Taylor's formula in general converges at an exponential rate, here like $(1/4)^n$ (related to singulaties in the complex plane). Newton's method is in general quadratic or super-exponential fast (faster than any exponential) when you are close enough to the 'true' value.

Answer 2

Binomial Series $$ \begin{align} \sqrt3 &=2\sqrt{1-\frac14}\\ &=2\left(1+\frac{\frac12}{1!}\left(-\frac14\right)+\frac{\frac12\left(-\frac12\right)}{2!}\left(-\frac14\right)^2+\frac{\frac12\left(-\frac12\right)\left(-\frac32\right)}{3!}\left(-\frac14\right)^3+\dots\right)\\ &=-2\sum_{k=0}^\infty\frac{(2k-3)!!}{8^kk!} \end{align} $$ where $n!!$ is the Double Factorial. Note that $(-3)!!=-1$ and $(-1)!!=1$.

Each term in the series is about $\frac14$ the size of the previous term.

---

Newton Raphson

Newton's Method for $\sqrt3$ gives $$ x_{n+1}=\frac{x_n^2+3}{2x_n} $$ For $x_n\gt0$, we have $x_{n+1}\ge\sqrt3$.

Thus, $$ \begin{align} x_{n+1}-\sqrt3 &=\frac{\left(x_n-\sqrt3\right)^2}{2x_n}\\ &\le\frac{\left(x_n-\sqrt3\right)^2}{2\sqrt3} \end{align} $$ Each term in the sequence is proportional to the square of the previous term.

Answer 3

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \root{3} & = \root{147 \over 7^{2}} = {1 \over 7}\root{144 + 3} = {12 \over 7}\pars{1 + {1 \over 48}}^{1/2} = {12 \over 7}\sum_{k = 0}^{\infty}{1/2 \choose k}{1 \over 48^{k}} \end{align}

---

$$ \begin{array}{ccc}\hline \ds{n\quad} & \ds{\quad R_{n} \equiv{12 \over 7}\sum_{k = 0}^{n}{1/2 \choose k}{1 \over 48^{k}}\quad} & \ds{\quad R_{n}^{2}} \\ \hline && \\[3mm] \ds{0} & \ds{{12 \over 7} \approx 1.7\color{#f00}{1428571428571}} & \ds{2.93877551020408} \\[2mm] \ds{1} & \ds{{97 \over 56} \approx 1.732\color{#f00}{14285714286}} & \ds{3.00000004307126} \\[2mm] \ds{2} & \ds{{18623 \over 10752} \approx 1.732\color{#f00}{04985119048}} & \ds{2.99999668700895} \\[2mm] \ds{3} & \ds{{18623 \over 10752} \approx 1.7320508\color{#f00}{2000248}} & \ds{3.00000004307126} \\[2mm] \ds{4} & \ds{{98074093 \over 56623104} \approx 1.732050807\color{#f00}{38774}} & \ds{2.99999999937252} \end{array} $$

With Newton-Rapson, it's better to start with $\ds{\root{3} = 2\root{3 \over 4} = 2\root{0.75}}$. Since $\ds{0.75< \root{0.75} < 1}$, we start with $\ds{x_{0} = {0.75 + 1 \over 2} = 0.875}$ and $$ x_{n} = \half\pars{x_{n - 1} + {0.75 \over x_{n - 1}}}\,,\qquad n \geq 1 $$ With $\ds{\large 3}$ iterations we'll get $\ds{\large 17}$ right decimals $$ 2x_{3} \approx 1.73205080756887729 $$