# Computing square root : an example of Newton's method

Using Newton's method,
When calculating the approximate value of $\sqrt{3}$,

is obtained through five iterations,

This value coincides with the correct value up to 10 digits.
A specific calculation method will be described below.
.

### Explanation

**
Preparation:
**

The Newton's method is a method of obtaining a solution of the equation
$ f(x) = 0 $
by iterative calculations,
and the calculation of each step is defined by the following recurrence formula.

, where $n=0,1,2,\cdots$.

Using this method,
it is known that correct numerical solutions can be obtained for some problems,
and the problem of finding the square root is a typical example.
In the following,
we compute an approximated value of $ \sqrt {3} $ by Newton's method, and compare it with the correct value.

**
Computation:
**

Since $\sqrt{3}$ is one of the solutions of

,
we define the function f (x) as

and solve the equation

by Newton's method.

We start with the initial value

.
Since the derivative of $f(x)$ is

,
From $ (1) (2) (3) $,
the value after the first iteration is

.
From $ (1) (3) (4) $,
the value after the second iteration is

.
From $ (1) (3) (5) $,
the value after the third iteration is

.
From $ (1) (3) (6) $,
the value after the fourth iteration is

.
From $ (1) (3) (7) $,
the value after the fifth iteration is

.

Since the correct value is

,
the value after the fifth iteration coincides with the correct value up to 10 digits.

If we repeat the calculation like this,
we can continue computing as much as we want.
However, we need to halt the computation at some step.
One strategy to stop at a certain iteration is to stop the computation
when the absolute value of the change amount between each step becomes smaller than a predetermined value (threshold).

For example,
the absolute value of the difference between $ x_ {5} $ and $ x_ {4} $ is less than $ 10 ^ {- 4} $ as follows

.
Therefore, if the threshold is set to $ 10^{- 4} $,
the computation is stopped in the fifth step.

**
Caluculator of square root:
**

Enter the original value $ x $ and initial value $ x_ {0} $ in the following input form
and press the "Execute" button.
The result of the Newton's method for computing the square root of $ x $
is displayed up to the value of the fifth step.

Computation result

**
On convergence of calculation
**

In general,
the correct solution can not always be obtained by the Newton's method.
In addition,
the computation result may not converge.
However,
it is known that, under some conditions,
it converges to the correct solution.
One of the conditions is as follows.

The first and second derivative of the function both exist ($f(x) \in C^{2}$),
and $f(x)$ satisfies

at $x_{0}$,
and there exists at $a$ less than $x_{0}$
satisfying

, and
$f (x)$ is a monotonically increasing and convex function in $[a, x_{0}]$ , i.e.,

.
Under these condition,
the Newton's method gives a solution that converges to $x$ where $ f(x) = 0$.

Here,
let us make sure that Newton's method for obtaining the value of $ \sqrt {3} $ satisfies these conditions.
If $x_{0}=5$,
from $(1)$, we have

.
Thus the condition $(6)$ satisfies.
If $a=1$,
from $(1)$, we have

Thus the condition $(10)$ satisfies.
And

in $[a, x_{0}]$.
Thus the conditions $(11)(12)$ satisfies.
Therefore all the conditions satisfies.

This guarantees that the computation result given by the above method always converge
and the convergence value is $ \sqrt {3} $.