Skip to content

DA7. Newton’s Method to find square root

Statement

How might Newton’s Method be used to find the square roots of numbers that are otherwise hard to find. (eg, “the square root of 2”)? Provide examples.

Solution

Newton’s method is used to find the roots of a function, that is, the values of \(x\) that make \(f(x)=0\). The formula is:

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \]

For Square roots, we can use the function \(f(x)=x^2 - a\) where \(a\) is the number we want to find the square root of. For example, if we want to find the square root of 2, we can use \(f(x)=x^2 - 2\).

The meaning of \(f(x) = x^2 - a\) is that we want to find the value of \(x\) that makes \(x^2 - a = 0\), where \(x\) is the square root of \(a\).

Let’s try to apply the Newton’s method on \(f(x)=x^2 - a\):

\[ \begin{aligned} x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \\ &= x_n - \frac{x_n^2 - a}{2x_n} \\ &= \frac{2x_n^2 - x_n^2 + a}{2x_n} \\ &= \frac{x_n^2 + a}{2x_n} \\ &= \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) \end{aligned} \]

The formula that we got exactly matches the formula mentioned by (Johnson, 2015). So we can use this formula to find the square root of any number \(a\).

When to stop iterating

There is one more critical point, is to know when to stop iterating, as we know, we can apply the Newton’s rule infinitely, but we need to stop at some point, accepting some kind of accuracy as this may never ends for irrational numbers.

According to (ASMI, 2015), Iterations of Newton’s should be stopped in any of the following cases, assuming that \(x_n\) is the current iteration and \(x_{n+1}\) is the next iteration, with some accuracy \(\epsilon\):

  1. If \(f'(x_n) = 0\), then we cannot proceed further as we will divide by zero.
  2. If \(|f(x_{n+1})| < \epsilon\), then we are close enough to the zero and no point of iterating further.
  3. If \(|f(x_{n+1}) - f(x_n)| < \epsilon\), then we are close enough to the root and no point of iterating further.
  4. If \(|x_{n+1} - x_n| < \epsilon\).
  5. If \(x_{n+1} = x_n\) (covered by point 4).
  6. If \(f(x_{n+1}) = f(x_n)\) (covered by point 3).
  7. If we exceed the maximum number of iterations that is allowed.

Examples

I will use two examples, one is hard to find the square root of like 13, and the other is easy like 100.

Let’s find the square root of 13, we can start with \(x_0 = 3\) and \(\epsilon = 0.06\):

\[ \begin{aligned} x_1 &= \frac{1}{2} \left( x_0 + \frac{a}{x_0} \right) \\ &= \frac{1}{2} \left( 3 + \frac{13}{3} \right) \\ &= \frac{1}{2} \left( 3 + 4.3333 \right) \\ &= \frac{1}{2} \left( 7.3333 \right) \\ &= 3.6667 \\ \end{aligned} \]

The accuracy is \(|3.6667 - 3| = 0.6667 > 0.06\), so we need to continue.

Now we can use \(x_1\) to find \(x_2\):

\[ \begin{aligned} x_2 &= \frac{1}{2} \left( x_1 + \frac{a}{x_1} \right) \\ &= \frac{1}{2} \left( 3.6667 + \frac{13}{3.6667} \right) \\ &= \frac{1}{2} \left( 3.6667 + 3.5500 \right) \\ &= \frac{1}{2} \left( 7.2167 \right) \\ &= 3.6083 \\ \end{aligned} \]

We can see that \(|3.6667 - 3.6083| = 0.0584 < 0.06\), so we can stop here and say that the square root of 13 is 3.6083 (approximately).

Let’s find the square root of 100, we can start with \(x_0 = 10\) and \(\epsilon = 0.06\):

\[ \begin{aligned} x_1 &= \frac{1}{2} \left( x_0 + \frac{a}{x_0} \right) \\ &= \frac{1}{2} \left( 10 + \frac{100}{10} \right) \\ &= \frac{1}{2} \left( 10 + 10 \right) \\ &= \frac{1}{2} \left( 20 \right) \\ &= 10 \\ \end{aligned} \]

The accuracy is \(|10 - 10| = 0 < 0.06\), so we can stop here and since \(x_1 = x_0\), we can say that the square root of 100 is 10 (exactly).

References