Newton's Method

[Mouche]

So, I'm trying to make a program that works with Newton's method. I want the program to take in two formulas and a guess and then follow this pattern.

This is the pseudocode/python (I kinda did both):

[B]def[/B] newtonIterationFunction(x) 
    [B]return[/B]  x - (function1) / (function2)
 
get function1
get function2

x = guess

99 times
     print "Iteration: " + i
     print "Guess: " + x
     xold = x
     x = newtonIterationFunction(x) 
     [B]if[/B] x == xold 
         print "Solution found!"
         [B]break out of loop[/B]

How could I parse the functions they enter? If they type in 3x^2 I need the function to be the actually multiplication of 3 times x squared.

[vegaseat]

Just to make things clear, you want to use Newton's method to solve a system of 2 nonlinear equations. Is that what you have in mind?

Your real problem is to parse the user input to something that Python can work with. So 3x^2 becomes 3*(x**2). This could get pretty involved if you want to cover all sorts of user input. A real challenge!

Work with simple cases first. How would you convert "3x^2" to "3*(x**2)"? Converting the whole input string into a list of charaters would be my first step.

Replacing the '^' with '**' would be easy, putting the missing '*' in '3x' takes more thinking. You will have to detect the boundary of digit and alpha. Actually sounds like a fun project. Let us know what you are doing.

[mawe]

Hi!

putting the missing '*' in '3x' takes more thinking.

Hmm, maybe a regex can help:

In [1]: import re
In [2]: pattern = re.compile("(\d)([A-Za-z])")
In [3]: formula = "6x+3x^2"
In [4]: re.sub(pattern, r"\1*\2", formula)
Out[4]: '6*x+3*x^2'
In [5]: formula = "a+3b-22.5c"
In [6]: re.sub(pattern, r"\1*\2", formula)
Out[6]: 'a+3*b-22.5*c'

Regards, mawe

[jrcagle]

If you're talking about Newton's Method to find a zero of a function, I recommend the following:

def deriv(f , c, dx = 0.0001):
   """
deriv(f,c,dx) --> float

Returns f'(c), computed as a symmetric difference quotient.  Make dx smaller for more precise results.
"""

   return (f(c+dx) - f(c - dx))/ (2*dx)


def fuzzyequals(a,b,tol=0.0001):
   """
fuzzyequals(a,b,tol) --> Bool

Returns True if a is within tol of b.
"""
   return abs(a-b) < tol


def Newton(f, c):

   """
Newton(f,c) --> float

Returns the x closest to c such that f(x) = 0.
"""

 if fuzzyequals(f(c),0,tol):
        return c

 else:
        # catch recursion limit errors, division by zero errors
        try:
            # x_n+1 = x_n - f(x_n)/f'(x_n)
            return newton(f, c - f(c)/deriv(f,c,tol), tol)
        except:
            # We've either hit a horizontal tangent or else
            # haven't been able to find one within the recursion depth.
            return None

Hope it helps,
Jeff

[Mouche]

Just to make things clear, you want to use Newton's method to solve a system of 2 nonlinear equations. Is that what you have in mind?

Yes.

Your real problem is to parse the user input to something that Python can work with. So 3x^2 becomes 3*(x**2). This could get pretty involved if you want to cover all sorts of user input. A real challenge!

I realized that.

Work with simple cases first. How would you convert "3x^2" to "3*(x**2)"? Converting the whole input string into a list of charaters would be my first step.

Replacing the '^' with '**' would be easy, putting the missing '*' in '3x' takes more thinking. You will have to detect the boundary of digit and alpha. Actually sounds like a fun project. Let us know what you are doing.

I'm pretty new to complicated problems like this problem. I've mostyl been doing basic stuff. This sounded like a fun thing to do. My friend in Calculus asked me if I could make it just for fun. I can take a string and stick it into a list and make numbers integers...any other help?

Thank you Mawe and Jeff, but I need a way to take the formula into the program.

[bumsfeld]

Expanding on mawe's formula builder, this is my contribution to the equation solver:

# evaluate equation like 3x^2+2(3x-2) = 0

import re

# look for digit before alpha and '('
pattern = re.compile("(\d)([A-Za-z(])")

formula_raw = "3x^2+2(3x-2)"
# insert '*' between digit and alpha or '('
formula = re.sub(pattern, r"\1*\2", formula_raw)

print formula  # '3*x^2+2*(3*x-2)'

# take care of power symbol ^
if '^' in formula:
    formula = formula.replace('^', '**')

print
print "formula =", formula  # '3*x**2+2*(3*x-2)'

# test it with for loop ...
for x in range(-5, 5):
    if 'x' in formula:
        formula2 = formula.replace('x', str(x))
    #print formula2  # test
    print "x = %s  --> %s" % (str(x), eval(formula2))

print

# narrow x value down ...
for x in range(0, 100):
    x = x/100.0
    if 'x' in formula:
        formula2 = formula.replace('x', str(x))
    result = eval(formula2)
    # when result crosses zero line stop
    if result > 0.0:
        print "x = %s  --> %s" % (str(x), result)
        break

[jrcagle]

You can do exactly that with the code above, coupled with this:

def convert(s):
    """
Converts a string into a function.
"""
    return lambda x:eval(s)

So the usage would be as follows:

s = raw_input("Enter a function to find the zero of: ")
f = convert(s)

c = float(raw_input("Enter an estimate of the zero: "))
print "The zero of your function is", Newton(f,c)

This code will break if the user gives invalid syntax. A more friendly version:

while True:
   
       s = raw_input("Enter a function to find the zero of: ")
       
        try:
            f = convert(s)
            f(0)
       except SyntaxError:
            print "Invalid function syntax!"
       except:
            break
       else:
            break
while True:
       c = raw_input("Enter an estimate of the zero: ")
       try:
           c = float(c)
       except:
            print "Enter a valid float, please!"
       else:
            break

print "The zero of your function:", Newton(f,c)

Hope it helps,
Jeff Cagle

P.S. You could also couple this with Bumsfeld's code to allow for algebraic syntax.

[jrcagle]

Just curious: is this intended to be used with sin(x), arctan(x), ln(x)?

[Mouche]

Wow. Thanks a LOT for your input. I wasn't aware of eval()'s function before this. Also, I looked into regex. Thanks. Yeah, trig functions will be used.

[Mouche]

Mawe, could you explain this piece by piece?

In [1]: import re
In [2]: pattern = re.compile("(\d)([A-Za-z])")
In [3]: formula = "6x+3x^2"
In [4]: re.sub(pattern, r"\1*\2", formula)
Out[4]: '6*x+3*x^2'

Thanks.