Here's the question you clicked on:
claralucia
I need help on the Newton question (#3) on the problem set 2! I use the eval_poly and compute_deriv function from the first few questions. Those check out, but I just can't get the while loop to work. It runs forever, for reasons I don't understand. Here's the code: deriv = compute_deriv(poly) numguess = 0 while abs(eval_poly(poly, x_0)) >= epsilon: numguess += 1 x_0 = x_0 - (eval_poly(poly, x_0))/(eval_poly(deriv, x_0)) else: print (eval_poly(poly, x_0), numguess) return
not sure, looks okay to me try inserting a print statement or two: deriv = compute_deriv(poly) numguess = 0 while abs(eval_poly(poly, x_0)) >= epsilon: numguess += 1 x_0 = x_0 - (eval_poly(poly, x_0))/(eval_poly(deriv, x_0)) print x_0, (eval_poly(poly, x_0)), (eval_poly(deriv, x_0)) else: print (eval_poly(poly, x_0), numguess) return that ought to be enlightening
btw it should return the root x_0, not eval_poly(poly, x_0)
Thanks for your help! I put in the print command and I found that the values don't seem to be converging. 0.373076923077 0.671405325444 -0.238461538462 2.44249379653 23.7823154313 16.6549627792 1.01455212253 6.11705227303 8.08731273516 0.25817574964 1.71631565239 3.54905449784 -0.225422249047 0.701601073002 0.647466505718 -1.30903208339 3.52263081924 -5.85419250033 -0.707304207333 1.08622931047 -2.243825244 -0.223207099783 0.703050028615 0.660757401303 -1.28721338595 3.39632813098 -5.72328031567 -0.693790044146 1.05645378778 -2.16274026488 This is using the test values: poly = (1, 2, 3) x_0 = .1 epsilon = .0001 Weirdly enough, though, when I put in the original test values from the problem: poly = (-13.39, 0.0, 17.5, 3.0, 1.0) x_0 = 0.1 epsilon = .0001 the program works. I'm not sure what to make of this, because I don't quite understand Newtons formula (x_1 = f(x_0)/f'(x_0) itself.
if it works with the test values then there is a mathematical explanation to why the other one is not working: newton's method fails for certain initial values of x_0 let me try it in my program and see what happens...
Thanks. I suspected it was an issue with restricted application of the formula itself. I need to read up on it, since the problem set provides no info.
yes, the same exact thing happens to mine, I even get the same print values for x_0 it is a result of the fallibility of newtons method, and has to do with having a bad initial choice for x_0 If you want to understand what is happening you could look at the section on Newton's method in the single variable calc section of OCW
I will try to draw what is happening something like|dw:1351214431286:dw|
|dw:1351214499069:dw|
|dw:1351214573121:dw|
|dw:1351214610832:dw|and so we are see-sawing back and forth around a minimum, which keeps us from selling on a value
Ah, I think I see - so that's why the x guesses kept cycling up and down and not converging. In any case, this has been really informative, thanks so much!
actually, your problem in this case is much simpler: the function you chose has no real zeroes :P http://www.wolframalpha.com/input/?i=plot%20y%3D1%2B2x%2B3x%5E2&t=crmtb01 so of course you will never get a final answer it also could have been what I said though, just for the record ;)
for the future, if you are gonna test a function you should already have an expected answer
Ha, why didn't I think of that... I wonder if there would be any way to built a "no root" answer into the program.
That sounds like a darn good wuestion, but I suppose you could use some logic and say that if x_0 oscillates around its initial value some limit of n times, the loop stops and claims there is no zero to be found it wouldn't be fool proof though, maybe there's a better way :)
newtons method usually only requires 5 iterations to get within 0.00001 or so of a root, so at 40 iterations it would be logical to stop the program and say "cannot find root"
Sounds right. I'm a total beginner by the way, so this is very helpful. Is there a way to tell the loop to terminate after a certain number of iterations?
sure, just do something like deriv = compute_deriv(poly) numguess = 0 iters=0 while abs(eval_poly(poly, x_0)) >= epsilon and iters<n: numguess += 1 iters+1 x_0 = x_0 - (eval_poly(poly, x_0))/(eval_poly(deriv, x_0)) if abs(eval_poly(poly, x_0)) >= epsilon: print 'method failed' else: print (eval_poly(poly, x_0), numguess) return when iters gets over some value n the loop stops
Oh, I suppose you could add something like while numguess <= 40 to the conditions of the loop.
exactly btw I'm a total beginner too. I'm doing this course for edX right now, that's why I could check your answer against mine so quickly. I have a good math background though, so I may have the edge on a few things like this :)
Well, that's encouraging. My math's a little rusty but it's coming by quickly by necessity. Gotta run but thanks again!
see, I didn't even need to ad the iters vairable, I forgot we already had the equivalent variable numguesses welcome!
deriv = compute_deriv(poly) numguess = 0 while abs(eval_poly(poly, x_0)) >= epsilon and numguess<n: numguess += 1 x_0 = x_0 - (eval_poly(poly, x_0))/(eval_poly(deriv, x_0)) if abs(eval_poly(poly, x_0)) >= epsilon: print 'method failed' else: print (eval_poly(poly, x_0), numguess) return
@Turing Test http://www.youtube.com/watch?v=x2KbdoxrQ6o