Newton's Method

Tags: [math], [newton's_method]

The Newton's method is for finding the one of the solutions of the given equation, and it can be applied on any dimension equations. Actually, the Newton's method is an efficient way to approach to the solution. (Newton's method 是一种高效的逼近算法，每次迭代不断逼近所要求的真实解)

For example:

We want to get the square root of n, we can use the Newton's method to solve this problem, see the following steps:

1. Write the equation: f(x) = x^2 - n = 0, and our goal is what is x can make the equation x^2 - n to be equal to 0.
2. We guess an approximate of x, this approximate can be any number, but it's better that it's close to the real x. Here we can just generate a random int in the range[0, n] as our first approximate.
3. We put this approximate back into equation, so we get f(approximate) = approximate^2 - n, so we can calculate the f(approximate), recording as f_approximate, now we have one point on the curve (x^2 - n = 0), and this point(x, y) is (approximate, f_approximate).
4. Try to get the tangent (切线) at this point of the curve. To get the tangent, we need first get the slope of this tangent. To get the slope, we need find the derivative of the equation (求导), because f(x) = x^2 - n, so f'(x) = 2x. And we know x here is approximate, so the slope = 2 * x = 2 * approximate. Then we can write out the tangent, which is y = slope * x + c, which is y = (2 * approximate) * x + c. Now we put the point (x, y), which is (approximate, f_approximate) back to the tangent to get the c. So f_approximate = (2 * approximate) * approximate + c, so c = f_approximate - (2 * approximate) * approximate. So the tangent is y = (2 * approximate) * x + (f_approximate - (2 * approximate) * approximate).
5. For tangent, Let y = 0, calculate x, so 0 = (2 * approximate) * x + (f_approximate - (2 * approximate) * approximate), so x = (0 - (f_approximate - (2 * approximate) * approximate)) / 2 * approximate.
6. Now this x is our improved approximate for next round.
7. We keep iterating, until the approximate == improved_approximate, then we can stop. If the given equation has solution or solutions, this iterating must can convergent (收敛). And if the given equation has solutions, the Newton's method can convergent very fast.

The following picture will illustrate the above processes:

Note:

• The first approximate can be any number, but the good first approximate will speed up the convergence.
• From the equation or the picture above, we know actually there exist two solutions. If our first approximate is close to the right side solution, the Newton's method will find the right side solution. If our first approximate is more close to the left side solution, the Newton's method will find the left side solution.
• Newton's method can be applied to any dimensional equations, such as f(x, y) = x^5 + y^7 = 0, or f(x, y, z) = x^3 + y^9 + z^7 = 0.

import random


def get_sqrt(n):
    # the reason here we don't let approximate be 0,
    # is that the approximate will be divisor in the improve_approximate function.
    approximate = random.randint(1, n)
    better = improve_approximate(n, approximate)

    while abs(better - approximate) > 0.0001:
        approximate = better
        better = improve_approximate(n, approximate)

    return better

def improve_approximate(n, approximate):
    n = float(n)
    approximate = float(approximate)

    # f(x) = x^2 - n = 0
    # here x = approximate, f(approximate) = approximate^2 - n
    f_approximate = approximate ** 2 - n

    # f'(x) = 2 * x, which is the tangent's slope
    # here x = approximate
    tangent_slope = 2 * approximate

    # tangent: y = slope * x + c
    #          c = y - slope * x
    # here y = f_approximate, slope = 2 * approximate, x = approximate
    c = f_approximate - tangent_slope * approximate

    # tangent: y = (2 * approximate) * x + (f_approximate - tangent_slope * approximate)
    # let y = 0, to get x.
    # so x = (0 - (f_approximate - tangent_slope * approximate)) / (2 * approximate)
    x = (0 - (f_approximate - tangent_slope * approximate)) / (2 * approximate)

    # x is the improved_approximate
    improved_approximate = x
    return improved_approximate

if __name__ == '__main__':
    print 'Program is working'

    n = 5
    sqrt = get_sqrt(n)

    print sqrt

    print 'Program is end'

Note:

• When we use the Newton's method to find the square root, we usually use (n / 2.0) as the first approximate, but we can use any number, so here we just randomly pick up an integer.
• Time complexity can be found here: http://www.tau.ac.il/~tsirel/dump/Static/knowino.org/wiki/Newton's\_method.html

Follow up:

We can simplify the whole processes, following the below steps:

• The first approximate is recored as X0, and we try to derive the next round better approximate, recording as x.
• f(X0) = (X0)^2 - n
• f'(X0) = 2 * (X0), f'() 是导数的意思
• y = k*x + c, k = 2 * (X0), y = f(X0), x = X0, so c = -(X0)^2 - n, so the tangent is y = (2 * X0) * x - (X0)^2 - n
• Let y = 0, so x = ((X0) ^ 2 + n) / 2 * (X0) = (2 * (X0)^2 - ((X0)^2 - n)) / 2 * (X0) = (X0) - (((XO)^2 - n) / 2 * (X0)), because f(X0) = (X0)^2 - n, and f'(X0) = 2 * (X0), so x = (X0) - (f(X0) / f'(X0)), which means if the current round approximate is (X0), so the improved_approximate is (X0) - (f(X0) / f'(X0)).

import random

def get_sqrt(n):
    approximate = random.randint(1, n)
    better = improve_approximate(n, approximate)

    while abs(better - approximate) > 0.0001:
        approximate = better
        better = improve_approximate(n, approximate)

    return better

def improve_approximate(n, x_0):
    n = float(n)
    x_0 = float(x_0)

    # f(x) = x^2 - n = 0
    f_x_0 = x_0 ** 2 - n

    # f'(x) = 2 * x
    f_derivative_x_0 = 2 * x_0

    # x = x_0 - (f(x_0) / f'(x_0))
    x = x_0 - (f_x_0 / f_derivative_x_0)

    # x is the improved approximate
    return x

if __name__ == '__main__':
    print 'Program is working'

    n = 5
    sqrt = get_sqrt(n)
    print sqrt

    print 'Program is end'