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.

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.

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

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

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.

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``````

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.

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

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.

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.