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

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions.

- anonymous

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- TuringTest

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

- TuringTest

btw it should return the root x_0, not eval_poly(poly, x_0)

- anonymous

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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- TuringTest

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

- anonymous

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.

- TuringTest

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

- TuringTest

I will try to draw what is happening
something like|dw:1351214431286:dw|

- TuringTest

|dw:1351214499069:dw|

- TuringTest

|dw:1351214573121:dw|

- TuringTest

|dw:1351214610832:dw|and so we are see-sawing back and forth around a minimum, which keeps us from selling on a value

- TuringTest

settling*

- anonymous

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!

- TuringTest

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 ;)

- TuringTest

for the future, if you are gonna test a function you should already have an expected answer

- anonymous

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.

- TuringTest

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 :)

- TuringTest

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"

- anonymous

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?

- TuringTest

sure, just do something like
deriv = compute_deriv(poly)
numguess = 0
iters=0
while abs(eval_poly(poly, x_0)) >= epsilon and iters= epsilon:
print 'method failed'
else: print (eval_poly(poly, x_0), numguess)
return
when iters gets over some value n the loop stops

- anonymous

Oh, I suppose you could add something like while numguess <= 40 to the conditions of the loop.

- TuringTest

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 :)

- anonymous

Well, that's encouraging. My math's a little rusty but it's coming by quickly by necessity. Gotta run but thanks again!

- TuringTest

see, I didn't even need to ad the iters vairable, I forgot we already had the equivalent variable numguesses
welcome!

- TuringTest

deriv = compute_deriv(poly)
numguess = 0
while abs(eval_poly(poly, x_0)) >= epsilon and numguess= epsilon:
print 'method failed'
else: print (eval_poly(poly, x_0), numguess)
return

- anonymous

@Turing Test
http://www.youtube.com/watch?v=x2KbdoxrQ6o

Looking for something else?

Not the answer you are looking for? Search for more explanations.