Quadratic convergence

The iteration converges quadratically starting from any real initial guess a₀ except zero. When a₀ is negative, Newton's iteration converges to the negative square root. Quadratic convergence means that the square of the error $a_t-\sqrt{s}$ at one iteration is proportional to the error at the next iteration

$$\begin{eqnarray} a_{t+1} - \sqrt{s} \quad\sim\quad ( a_t-\sqrt{s})^2 = a_t^2 - 2 a_t \sqrt{s} + s \quad \gt \quad 0\end{eqnarray}$$ (6)

so, for example if the error is one significant digit at one iteration, at the next iteration it is two digits, then four, etc. We cannot use equation (6) in place of the Newton iteration itself, because it uses the answer $\sqrt{s}$ to get the answer a_t+1, and also we need the factor of proportionality. Notice, however, if we take this factor to be 1/(2a_t), then $\sqrt{s}$ cancels and equation (6) becomes itself the Newton iteration (3).

Even though we cannot estimate the rate of convergence by $a_t-\sqrt{s}$ because we don't know the answer s, we can get an estimate of it by looking at the difference between the intermediate solutions at two consecutive steps. From (3), we can write

$$a_{t+1}-a_t = {1\over 2} \left( a_t + {s\over a_t} \right) = \frac{a_t^2+s}{2a_t}-a_t$$ (7)

therefore  

$$a_{t+1}-a_t = \frac{s-a_t^2}{2a_t}.$$ (8)

Another interesting feature of the Newton iteration is that all iterations (except possibly the initial guess) overestimate the ultimate square root. This is obvious from equation (6).