Newton's Method

Newton's method is a iteration way to find zero points of . It is a widely used numerical algorithm and has many application.

Let's say we have a function . We'd like to find a real solution that let . To achieve that, we first make an initial guess of and start from it we performing iteration based on:

We repeat the iteration until desired precision is reached. That is where is a very small float number. It can be shown that .

To show the application of Newton's method, we take th root algorithm as an example. To get root of a positive rational number is equivalent to find zero point for . The derivative of is:

So we have:

Once we can find the th root of a rational number, we can implement program to get number's rational power. As any rational number can be represented as fraction of two integer . So we can transform a number 's power like:

Where and is the remainder of . Hence we can transform ration power into calculation of two integer power and one th root.

Newton's method is converging quite fast. It has square convergence which means after each iteration the number of effective digits can be doubled. So we can generally regard our th root program to be a algorithm. However, there are cases in which this method may not converge at all.

For more detailed discussion of this algorithm, refer to Wikipedia.