So for an assignment, I'm supposed to write a function that evaluates two other functions that I previously defined in the program. How, the intricacies of this next function I must define is confusing me how I should set it up. Basically, I have determined that I have to write a while loop, but I can't decide whether to have three different conditions or if statements to evaluate this function. The thing is, the loop must end after one of the three conditions is met; I just don't know how to lay it out currently. These are the three conditions (where only one must be met in order for the loop/function to terminate):
This is currently what I have as my code (and it hasn't been running obviously):
def newtonsMethod(poly, x_, epislon, timeout):
"""Calculating root of polynomial using newton's Method."""
estimate = 0
epislon = 1e-20
while (abs(evaluatePoly(poly, x_)) < epislon and \
abs(evaluatePoly(findDerivative(poly), x_)) and estimate > timeout):
estimate = x_ - (evaluatePoly(poly) / evaluatePoly(findDerivative(poly)))
x_ = estimate
print(x_)
How should I go about this? The function name is a requirement of the assignment so it cannot be changed. Also, I am a complete beginner at this stuff (just started last month) and I'm only basically required to have knowledge of data structures, loops, and if statements (and functions). So please keep your responses as simple/dumby proof as possible.
This is all the code I have before that pertains to this question:
def findDerivative(poly):
"""Find the derivative of the polynomial and return it as a list of
coefficents"""
count = 0
polyList = []
for nn in poly:
polyList += [nn * count]
count += 1
return polyList[1:]
def evaluatePoly(poly, x_):
"""Evaluates the polynomial at x = x_ and returns the result as a floating-
point number using Horner's rule"""
#http://mathworld.wolfram.com/HornersRule.html
count = 0
polyEval = []
for nn in poly:
xVal = x_**count
polyEval += [xVal * nn]
count += 1
polySum = sum(polyEval)
return float(polySum)
Edit: 10/23/2016
I should have mentioned this before or explained the assignment in more detail, but estimate is a parameter for the function because it is given as a list later on in the assignment. I have understood that timeout represents that the loop can run through so many times before it "breaks" or ends. The function is to return a two-part tuple where the first variable of the tuple is the refined x_ value and the second variable is a boolean value saying whether the method was successful or not. Using advice from both @Blckknght and @David Bowling , I was able to refine my code to the following:
def newtonsMethod(poly, x_, epsilon, timeout):
"""Calculating root of polynomial using newton's Method."""
deriv_poly = findDerivative(poly)
deriv = evaluatePoly(deriv_poly, x_)
value = evaluatePoly(poly, x_)
count = 1
while True:
x_ -= value / deriv
if abs(value) < epsilon:
boolean = abs(value) < epsilon
xTuple = (x_, boolean)
return xTuple
if abs(deriv) < epsilon or count > timeout:
boolean = abs(deriv) < epsilon or count > timeout
xTuple = (x_, boolean)
return xTuple
count += 1
However, I am still experiencing crashing problems when I run the code. I realized belatedly that I cannot have both boolean variables to equal to True (for my following code, I need boolean to equal True or False) but in order for the loop to stop, one of the if statements must equal True. I apologize for all the confusion and specifications this code requires; I hope this explanation helps understanding what I need.
The advice given by others to break up your complicated conditional into simpler statements is very good. The logic in your original conditional was faulty, but could be adjusted to work. Yet there were other problems in your function.
There is no need to assign epsilon a value before the loop, because this value is supplied as a function parameter. estimate should be functioning as a counter, but then confusingly gets assigned the value to be used for x_ in the next iteration. I have renamed estimate as iterations in my code below.
You should have used:
abs(evaluatePoly(poly, x_)) > epsilon
since you want the loop to continue so long as the value of the polynomial evaluated at x_ is larger than epsilon. And, to avoid difficulties in the statement that updates the value of x_, you want to continue looping only if:
abs(evaluatePoly(findDerivative(poly), x_)) > epsilon
There was a missing conditional here in your original code. Finally, you want to continue looping if the number of iterations has not yet reached the timeout value. You only want to loop if all of the above conditions are met, so your conditional expression should be:
while abs(evaluatePoly(poly, x_)) > epsilon and \
abs(evaluatePoly(findDerivative(poly), x_)) > epsilon and \
iterations < timeout:
I changed your next assignment statement in two ways. First, the assignment is now made to x_ instead of the old, confusing estimate variable. Second, you were missing the second argument in both of the evaluatePoly() functions. I added a line to increment the iterations counter, and moved the print() out of the loop so that you only see the final result.
Here is the modified code:
def newtonsMethod(poly, x_, epsilon, timeout):
"""Calculating root of polynomial using newton's Method."""
iterations = 0
while abs(evaluatePoly(poly, x_)) > epsilon and \
abs(evaluatePoly(findDerivative(poly), x_)) > epsilon and \
iterations < timeout:
x_ = x_ - (evaluatePoly(poly, x_) / evaluatePoly(findDerivative(poly), x_))
iterations += 1
print(x_)
Here is a sample run using the findDerivative() and evaluatePoly() functions that you provided:
>>> xpr = [0, 0, 5]
>>> newtonsMethod(xpr, -1, 1e-20, 1000)
-2.91038304567e-11
>>> evaluatePoly(xpr, -2.91038304567e-11)
4.235164736261692e-21
I have looked at the new function definition that you posted, and found the problem. The fundamental problem in your code is that value and deriv are evaluated only once, outside the loop. You need to move these two statements inside of the loop so that they can be updated after each iteration. Also, I would move the assigment to x_ to the end of the loop so that your first guess gets tested before it is updated. You can simplify the bodies of your if statements a bit also. As it is, when you escape the function due to an unacceptably small value for deriv or a timeout, your function reports True. I assume that you want it to report False. Here is how I modified your code:
def newtonsMethod(poly, x_, epsilon, timeout):
"""Calculating root of polynomial using newton's Method."""
deriv_poly = findDerivative(poly)
count = 1
while True:
deriv = evaluatePoly(deriv_poly, x_)
value = evaluatePoly(poly, x_)
if abs(value) < epsilon:
boolean = True
return (x_, boolean)
if abs(deriv) < epsilon or count > timeout:
boolean = False
return (x_, boolean)
x_ -= value / deriv
count += 1
Here is a sample run:
>>> xpr = [0, 0, 5]
>>> newtonsMethod(xpr, -1, 1e-20, 1000)
(-2.9103830456733704e-11, True)
>>> evaluatePoly(xpr, -2.9103830456733704e-11)
4.235164736271502e-21
I am guessing that the slight difference between these results and the earlier results is due to rounding errors and the differing procedures for calculation.