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.
Figure of computing the square root of 3
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.
$x = $  
$x_{0} = $  


Computation result
$x_{1} = $
$x_{2} = $
$x_{3} = $
$x_{4} = $
$x_{5} = $
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} $.