Newton's method for square root Solving $x^2-a=0$ with Newton's method, you can derive the sequence $x_{n+1}=(x_n + a/x_n)/2$ by taking the first order approximation of the polynomial equation, and then use that as the update. I can successfully prove that the error of this method converges quadratically. However, I can't seem to prove this for the residual, and this is likely a simple problem in arithmetic:
\begin{align*}
|x_{n+1}^2 - {a}| &= \left|\frac{1}{4}\Big(x_n+\frac{a}{x_n}\Big)^2 - {a}\right| \\
&= \left|\frac{1}{4}\Big(x_n^2+2a +\frac{a^2}{x_n^2}\Big) - {a}\right| \\
&= \left|\big(\frac{1}{2}x_n\big)^2-\frac{1}{2}a +\big(\frac{a}{2x_n}\big)^2\right| \\
&= \frac{1}{4}\left|x_n^2-2a +\big(\frac{a}{x_n}\big)^2\right| \\
&= \frac{1}{4}\left|\big(x_n+\frac{a}{x_n}\big)^2-2a +\big(\frac{a}{x_n}\big)^2\right|
\end{align*}
I get stuck here, as well as trying other expansions/factorizations. Is there a way to have this simplify?
 A: $\newcommand{\+}{^{\dagger}}%
 \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{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{x_{n + 1} = \half\pars{x_{n} + {a \over x_{n}}}\,,\quad\lim_{n \to \infty} = \root{a}}$.

Let's define $\epsilon_{n} \equiv x_{n} - \root{a}$ and we assume $x_{n}$'s are 'close' $\pars{~\verts{\epsilon_{n}} \ll \root{a}~}$ to $\root{a}$. Then,
\begin{align}
\epsilon_{n + 1} + \root{a}
&=
\half\pars{\epsilon_{n} + \root{a} + {a \over \epsilon_{n} + \root{a}}}
=
\half\pars{\epsilon_{n} + \root{a} + {\root{a} \over 1 + \epsilon_{n}/\root{a}}}
\\[3mm]&\approx
\half\bracks{\epsilon_{n} + \root{a}
+
\root{a}\pars{1 - {\epsilon_{n} \over \root{a}} + {\epsilon_{n}^{2} \over a}}}
=
\root{a} + {\epsilon_{n}^{2} \over 2\root{a}}
\end{align}

$$
\color{#0000ff}{\large\epsilon_{n + 1}}
\approx
\color{#0000ff}{\large{\epsilon_{n}^{2} \over 2\root{a}}}
$$
That is what is usually means by "$\tt\mbox{the error decreases quadratically}$". Notice that the worst scenario is $a \gtrsim 0$.

Also,
$$
\verts{x_{n + 1}^{2} - a} = \verts{x_{n + 1} - \root{a}}\
\verts{x_{n + 1} + \root{a}}
\approx
\verts{\epsilon_{n + 1}}\pars{2\root{a}}
$$

$$
\color{#0000ff}{\large\verts{x_{n + 1}^{2} - a}}
\approx \color{#0000ff}{\large\epsilon_{n}^{2}}
$$
A: After the second line, you can go to $ |\frac 14(x_n-\frac a{x_n})^2|$
A: 1) It is symmetry when $x>0$ and $x<0$, so we can only prove $x>0$. And the other half part of the proof is very similar
2) $\forall x_0>0$, it is easy to see that $x_1=(x_0+a/x_0)/2>\sqrt{a}$
3) If $x_n^2>a$, then follow your derivation until the second last line
$$
x_{n+1}^2-a = \frac{1}{4}\left(x_n-\frac{a}{x_n}\right)^2 = \frac{x_n^2-a}{4x_n^2} ( x_n^2-a) 
$$
$$
\text{So, }0<x_{n+1}^2-a<\frac{1}{4}(x_n^2-a)
$$
So the residual converges since the second step.
