Newton Iteration For Square Roots

Why This Recurrence Finds a Square Root

For $a>0$, we want to find the positive number whose square is $a$. Newton’s method turns this equation into an iteration: each new estimate is formed from the previous one and the correction suggested by the equation. For square roots, the resulting recurrence is especially simple:

x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right).

The formula averages $x_n$ with $a/x_n$. If $x_n$ is too large, then $a/x_n$ is small, and the average moves downward. If $x_n$ is too small, then $a/x_n$ is large, and the average moves upward. To prove convergence, we will make these observations precise and show that the sequence settles at $\sqrt a$.

Definition: Fix $a>0$ and $x_0>0$. The Newton iteration for $\sqrt a$ is the recursively defined sequence $$ x_{n+1}=\frac{x_n+a/x_n}{2},\qquad n\ge 0. $$

The recurrence is defined at every step: if $x_n>0$, then $a/x_n>0$, so $x_{n+1}>0$. Since $x_0>0$, induction gives $x_n>0$ for every $n\in\mathbb N\cup\{0\}$.

Where the Formula Comes From

Apply Newton’s method to $f(x)=x^2-a$. At a positive estimate $x$, the tangent-line update is $x-f(x)/f'(x)$. Since $f'(x)=2x$, the update is

x-\frac{x^2-a}{2x} =\frac{2x^2-(x^2-a)}{2x} =\frac{x^2+a}{2x} =\frac{1}{2}\left(x+\frac{a}{x}\right).

The condition $x>0$ matters: it ensures that the derivative $2x$ is nonzero, and that the recurrence’s division by $x$ is defined. This derivation explains how the iteration is obtained. It does not by itself establish that the iterates converge; that requires a separate argument.

The Key Inequalities

Write $r=\sqrt a$, so $r>0$ and $a=r^2$. Two identities give the bounds and monotonicity we need. For any $x>0$,

\frac{x+a/x}{2}-r =\frac{x^2-2xr+a}{2x} =\frac{(x-r)^2}{2x} \ge 0,

so one application of the recurrence always produces a value at least $r$. Also,

\frac{x+a/x}{2}-x =\frac{a-x^2}{2x}.

When $x>r$, we have $x^2>a=r^2$, making this last difference negative. Thus an iterate above the root is followed by a strictly smaller iterate. Together, the identities explain an important feature of the sequence: the first step reaches or passes the root, and later steps move downward without going below it.

Takeaway: For every positive input $x$, the next iterate is at least $\sqrt a$. For every input $x>\sqrt a$, the next iterate is strictly smaller than $x$.

Worked Examples

Worked Example: Starting Below the Root

Use $a=4$ and $x_0=1$. Here $\sqrt a=2$, and the starting value is below the root. Compute the first three iterates:

x_1=\frac{1+4/1}{2}=\frac{5}{2},

Then

x_2=\frac{5/2+4/(5/2)}{2} =\frac{5/2+8/5}{2} =\frac{25/10+16/10}{2} =\frac{41}{20}.

Next,

x_3=\frac{41/20+4/(41/20)}{2} =\frac{41/20+80/41}{2} =\frac{1681/820+1600/820}{2} =\frac{3281}{1640}.

The first step moves upward: $x_1=5/2>x_0$. After that, the terms move downward: $x_2=41/20<5/2$, and $x_3=3281/1640<41/20$. They remain above $2$: $41/20>2$, and $3281/1640>2$ because $3281>3280$. As an arithmetic check, substituting $x_2=41/20$ into the recurrence gives $x_3=(41/20+80/41)/2=3281/1640$, as calculated.

Worked Example: Starting Above the Root

Let $a=9$ and $x_0=5$, so the root is $3$. The first iterate is

x_1=\frac{5+9/5}{2} =\frac{25/5+9/5}{2} =\frac{17}{5}.

Continue:

x_2=\frac{17/5+9/(17/5)}{2} =\frac{17/5+45/17}{2} =\frac{289/85+225/85}{2} =\frac{257}{85}.

Each computed value is above $3$: $5>3$, $17/5>3$, and $257/85>3$ because $257>255$. The values decrease: $17/5<5$, and $257/85<17/5$ because $257\cdot5=1285<1445=17\cdot85$. Checking the last recurrence calculation, $9/(17/5)=45/17$, so $(17/5+45/17)/2=(289/85+225/85)/2=257/85$, as required.

Worked Example: An Irrational Square Root

Take $a=2$ and $x_0=2$. The root is irrational, but the terms of the recurrence can still be calculated exactly:

x_1=\frac{2+2/2}{2}=\frac{3}{2}.

Then

x_2=\frac{3/2+2/(3/2)}{2} =\frac{3/2+4/3}{2} =\frac{17}{12}.

One more step gives

x_3=\frac{17/12+2/(17/12)}{2} =\frac{17/12+24/17}{2} =\frac{289/204+288/204}{2} =\frac{577}{408}.

These terms decrease: $2>3/2>17/12>577/408$, where the last comparison follows from $17\cdot408=6936>6924=577\cdot12$. The later terms are above $\sqrt2$: $17/12>\sqrt2$ because $17^2=289>288=2\cdot12^2$, and $577/408>\sqrt2$ because $577^2=332929>332928=2\cdot408^2$. As a final check, the recurrence with $x_2=17/12$ gives $x_3=(17/12+24/17)/2=577/408$.

Proof of Convergence

We now prove the claim for every $a>0$ and every $x_0>0$, including starting values on either side of the root. We use the Monotone Convergence Theorem: every monotone sequence of real numbers that is bounded converges.

Theorem: If $a>0$ and $x_0>0$, the sequence defined by $$ x_{n+1}=\frac{x_n+a/x_n}{2} $$ converges to $\sqrt a$.

Establish positivity and a lower bound.
We have $x_0>0$. If $x_n>0$, then $x_{n+1}=(x_n+a/x_n)/2>0$, so all terms are positive. Applying the first identity above with $x=x_n$ gives $x_{n+1}\ge r$ for every $n\ge0$. In particular, $x_n\ge r$ for every $n\ge1$.

Show decrease from the first iterate onward.
Since $x_1\ge r$, if $x_1=r$, then the recurrence gives $x_2=r$, and all subsequent terms equal $r$. Otherwise $x_1>r$. For any $n\ge1$ with $x_n>r$, the second identity gives $x_{n+1}-x_n=(a-x_n^2)/(2x_n)<0$, because $x_n>0$ and $x_n^2>a$. Also $x_{n+1}\ge r$. Thus either the sequence reaches $r$ and stays there, or it is decreasing from $x_1$ onward and bounded below by $r$.

Obtain a limit.
The tail $(x_n)_{n\ge1}$ is monotone and bounded below by $r$. By the Monotone Convergence Theorem, it converges to a real number $L$ with $L\ge r>0$. Adding or removing the single initial term $x_0$ does not change whether a sequence converges or its limit, so $(x_n)_{n\ge0}$ also converges to $L$.

Identify the limit.
The recurrence function $T(x)=(x+a/x)/2$ is continuous for $x>0$, and $L>0$. Taking limits in $x_{n+1}=T(x_n)$ therefore gives $L=T(L)$. Hence $2L=L+a/L$, so $L=a/L$, and multiplying by $L>0$ gives $L^2=a$. Since $L\ge r>0$, the positive solution is $L=r=\sqrt a$.

This proves convergence and identifies the limit. Notice that the argument does not assume the sequence decreases from $x_0$. If $x_0<\sqrt a$, the first step can increase, as the example with $a=4$ shows. What the proof establishes is that the tail beginning at $x_1$ is bounded below and monotone.

A Common Pitfall: Fixed Points Are Not Enough

A fixed point of the recurrence is a number $c$ satisfying $c=(c+a/c)/2$. For $c>0$, this equation implies $c^2=a$, so the only positive fixed point is $\sqrt a$. But finding a fixed point does not prove that an arbitrary sequence of iterates converges to it.

For example, the calculation $x_{n+1}=x_n$ at $x_n=\sqrt a$ shows only that a sequence started exactly at the root stays there. It says nothing by itself about a different starting value. The convergence proof needs the separate facts that the tail is monotone and bounded; only after obtaining a limit can we use the recurrence to identify that limit as a fixed point.

Common mistake: Claiming that the sequence decreases starting at $n=0$ for every positive $x_0$. With $a=4$ and $x_0=1$, the recurrence gives $x_1=5/2>1=x_0$, so that claim is false. The correction is to prove $x_1\ge\sqrt a$, then establish decrease from $x_1$ onward.

Why the Proof Matters

The recurrence is useful because it turns the problem of finding a square root into a sequence of arithmetic operations. But its usefulness is not a substitute for understanding its behavior. A numerical list of terms may suggest that an iteration approaches a value; the proof establishes that it must converge and shows exactly which value it reaches.

The structure of the argument is reusable: identify a lower bound, prove monotonicity on the relevant tail, apply the Monotone Convergence Theorem, and then use the recurrence to determine the limit. Here the algebraic identities make each part explicit. The lower bound is the desired root itself, and the fixed-point equation forces the limit to be that root rather than another positive number.

Check Your Understanding

Use the recurrence and the proof above to answer these questions.

For $a>0$ and $x>0$, verify that $(x+a/x)/2-\sqrt a=(x-\sqrt a)^2/(2x)$. What does this imply about $x_1$?
For which inputs $x$ is the next iterate smaller than $x$, and which inequality establishes this?
Why is it not always correct to say the sequence decreases starting with $x_0$? Give a specific starting value that demonstrates the issue.
After proving that the tail converges to $L$, why may the recurrence be used to conclude $L^2=a$?
Why must the limit be the positive square root rather than the negative square root?