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?

notice that the method newton() will return after one while loop whatever happens! — Hemmer
FYI, stackoverflow is not a homework answer site. If you are getting errors, please highlight exactly what the errors are. Tracebacks are always good. Qualify what 'totally wrong' means. Perhaps give some input, expected output and what your algorithm is producing. — William Denman
So, is this a question about how to implement the algorithm (which makes it a homework question, and not a good candidate for SO), or a question about why your specific implementation of the algorithm in Python does not work (maybe not a great question, but better)? If the former, ask your TA. :) If the latter, could you please provide the following: the code for the function f (you leave it out but it is the most important part!), and also what version of Python are you working in? — selllikesybok
What in the world are you doing in this line? fprime(x) = derivative(f, x) As far as I can tell, that's invalid syntax for Python since you can't assign to function calls. Maybe you meant to just have x = x - f(x) / derivative(f, x). Then when the while loop is done, return x? According to the algorithm, you're supposed to modify x which you aren't doing in your current newton function. — Shashank

itdxer itdxer · Accepted Answer · 2013-11-18T14:52:23

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

Python - Newton Method

1 Answers