Newton’s Method

Newton’s method is a method for finding approximations to the roots of a given function.

The method itself is very simple, you give an initial guess of the root, \(x_0\), and calculate further values using the following equation: \(x_{n+1}=x_n-\frac{f’(x_n)}{f(x_n)}\).
Generally, each term in the sequence is more accurate in comparison to the previous terms.

How does it work

Let \(f(x)\) be the function whose root we are looking for.
Let \(x_0\) be our initial guess for the root.
Let \(x_n\) be our latest guess for the root.

In each step we take our best guess, \(x_n\), and try to make it more accurate.
To do so, we draw the tangent in the point \((x_n, f(x_n))\) and find its root, which we than call \(x_{n+1}\).
\(x_{n+1}\) will be more accurate (usually).

A demonstration: (click on the image to enlarge it)

The math behind this is not very difficult.
The equation of the tangent line is: \(y-f(x_n)=f’(x_n)(x_{n+1}-x_n)\).
We look for \(x_{n+1}\) when \(y=0\), hence
\(0-f(x_n)=f’(x_n)(x_{n+1}-x_n)
\\\Rightarrow -f(x_n)=x_{n+1}f’(x_n)-x_nf’(x_n)
\\\Rightarrow x_{n+1}f’(x_n)=x_nf’(x_n)-f(x_n)
\\\Rightarrow x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}\)

Example – Square Root

Say we want to calculate the square root of \(a\).
We need to find a value of \(x\) such that \(x=\sqrt{a}\Rightarrow x^2=a\Rightarrow x^2-a=0\).
So, we are looking for the non-negative root (\(x=\sqrt{a}\ge0\)) of the function \(f(x)=x^2-a\).
The derivative of this function is \(f’(x)=2x\).
And therefore:
\(x_{n+1}=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{x_n}{2}+\frac{a}{2x_n}\)

Calculating \(\sqrt{2}\)

Let’s try and find an approximation for \(\sqrt{2}\) with initial guess \(x_0=1\).
\(x_1=\frac{1}{2}+\frac{2}{2\times1}=\frac{3}{2}
\\ x_2=\frac{3}{2\times2}+\frac{2\times2}{2\times3}=\frac{17}{12}
\\ x_3=\frac{17}{2\times12}+\frac{2\times12}{2\times17}=\frac{577}{408}
\\ x_4=\frac{577}{2\times408}+\frac{2\times408}{2\times577}=\frac{665857}{470832}\approx1.414213562\)
The error from the real value is lower than \(0.0000000000016\)!
We have got this amazing result with only four steps!

Calculating further will produce very accurate massive fractions:
\(|x_5-\sqrt{2}|<9\times10^{-25}
\\ |x_6-\sqrt{2}|<2.9\times10^{-49}
\\ |x_7-\sqrt{2}|<2.9\times10^{-98}\)

Implementation

The C# implementation is super easy.

The parameters are \(a\), which is the number whose square root we are looking for, and \(times\), which determines the number of calculations.

public double Sqrt(double a, int times)
{
	if (a < 0)
		throw new Exception("Can not sqrt a negative number");
	double x = 1;
	while (times-- > 0)
		x = x / 2 + a / (2 * x);
	return x;
}

Conclusions

Newton’s method is a very efficient way to find roots of functions, including square roots of numbers.
It is much more efficient than the method I introduced in my article Square Root Algorithm.

Further Reading

You can read more about Newton’s method in Wikipedia.
There is more great information in Math World.