Python - Newton Method

Question

I am new to Python and I need to do a Newton Method script.

I have been trying to do it, but I keep getting errors or no returns...

Here is the assignment:

---

A function newton(f, x, feps, maxit) which takes:

• a function f(x),
• an initial guess x for the root of the function f(x),
• an allowed tolerance feps,
• and the maximum number of iterations that are allowed maxit.

The newton function should use the following Newton-Raphson algorithm:

while |f(x)| > feps, do
   x = x - f(x) / fprime(x)

where fprime(x) is an approximation of the first derivative (df(x)/dx) at position x. You should use the derivative function from the training part of this lab.

Make sure you copy the derivative function definition from training7.py into lab7.py (there are more elegant ways of doing this, but for the purpose of the assessment, this is the most straightforward way we recommend).

If maxit or fewer iterations are necessary for |f(x)| to become smaller than feps, then the value for x should be returned:

In [ ]: def f(x):
   ....:     return x ** 2 - 2
   ....:

In [ ]: newton(f, 1.0, 0.2, 15)
Out[ ]: 1.4166666666783148

In [ ]: newton(f, 1.0, 0.2, 15) - math.sqrt(2)
Out[ ]: 0.002453104305219611

In [ ]: newton(f, 1.0, 0.001, 15)
Out[ ]: 1.4142156862748523

In [ ]: newton(f, 1.0, 0.001, 15) - math.sqrt(2)
Out[ ]: 2.1239017571339502e-06

In [ ]: newton(f, 1.0, 0.000001, 15) - math.sqrt(2)
Out[ ]: 1.5949463971764999e-12

---

This is what I tried to do but it is totally wrong:

def derivative(f, x):
    """A function derivative(f, x) which computes a numerical approximation of
    the first derivative of the function f(x) using central differences."""
    R = (f(x + (10 ** -6) / 2.0) - f(x - (10 ** -6) / 2.0)) / (10 ** -6)
    return R


def newton(f, x, feps):
    """A function newton(f, x, feps, maxit) which takes a function f(x) and
    an initial guess x for the root of the function f(x), an allowed tolerance
    feps and the maximum number of iterations that are allowed maxit. The
    newton function should use the following Newton-Raphson algorithm:
    while |f(x)| > feps, do
    x = x - f(x) / fprime(x)
    where fprime(x) is an approximation of the first derivative (df(x)/dx) at
    position x."""
    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
        return Result

What should I doto make it work?

Answer 1

see this example used to your functions - pass ff & df to your newton-function, like there:

from scipy.optimize import approx_fprime

def f(x):
    return x ** 2 - 2

##def derivative(f, x):
##    """A function derivative(f, x) which computes a numerical approximation of
##    the first derivative of the function f(x) using central differences."""
##    R = (f(x + (10 ** -6) / 2.0) - f(x - (10 ** -6) / 2.0)) / (10 ** -6)
##    return R

def derivative(f, x):
    return approx_fprime(x, f, epsilon = 1e-8)

# https://patrickwalls.github.io/mathematicalpython/root-finding/newton/
def newton(f,Df,x0,epsilon,max_iter):
    # Approximate solution of f(x)=0 by Newton's method.
    xn = x0
    for n in range(0,max_iter):
        fxn = f(xn)
        if abs(fxn) < epsilon:
            print('Found solution after',n,'iterations.')
            return xn
        Dfxn = Df(f, xn)
        if Dfxn == 0:
            print('Zero derivative. No solution found.')
            return None
        xn = xn - fxn/Dfxn
    print('Exceeded maximum iterations. No solution found.')
    return None

##f = lambda x: x**3 - x**2 - 1
##Df = lambda x: 3*x**2 - 2*x
approx = newton(f,derivative,1,1e-10,10)
print(approx)

Newtons Method require to elaborate 𝑓′(𝑥)/𝑓′′(𝑥) 𝑓𝑜𝑟 𝑓′(𝑥) = 𝑓′′(𝑥) = 0, mean the program will stop with a division by zero error.

as I remember, Newton-method also needs fprime2 (as is hessian), as well as jacobian, pseudo-Newton needs only frime (as is jacobian)

p.s. usefullness in ML (though is costy because of 2nd-order derivation) :

how we can use a second-order method to choose \optimal learning rates.: if our error function is quadratic, this will find the global optimum in one step!

e.g. in ridge-regression, I suppose, - as is loss of quadratic form - thus fisher score (as based on Newton's method) can be implemented with hessian

Answer 2

You return result after first step in your while loop

    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
        return Result

Do it like this

    while abs(f(x) > feps):
        fprime(x) = derivative(f, x)
        Result = x - f(x) / fprime(x)
    return Result

P.S. But I'm not sure that your code is working fprime(x) = derivative(f, x) - this is't correct syntax for python

I think this code must b more correctly

    while abs(f(x) > feps):
        x = x - f(x) / derivative(f, x)
    return x

For newton method you must get result like recursive and check the best approximation.

            f(x)
Xn+1 = Xn - -----
            f'(x)

And you check in loop when your would be most better for you

P.S. Sorry for my pseudo-math-code