About MIT 6.00 course lec06--Newton's method

Question

I have tried to code in my own way, but found I got the wrong answer.

I have read this page. And try to start the process:

f(x)=x^2-e

The math:

So there is my code:

def sqrtRootNR(num, count, epsl):
    """
    for test
    """
    num = float(num)
    guess = num / 2.0
    diff = guess ** 2.0 - num
    _cnt = 0
    while abs(diff) > epsl and _cnt < count:
        guess = guess - (guess ** 2.0 + epsl) / (guess * 2.0)
        diff = guess ** 2.0 - num
        _cnt = _cnt +1
    print guess, _cnt

sqrtRootNR(2, 100, 0.0001)

However, I got the wrong answer.

The output of this function is:

D:\poc>python sq.py

0.0595177826557 100

Answer 1

Change (guess ** 2.0 + epsl) to (guess ** 2 - num) in your equation. You want to adjust your estimate every step by an amount proportional to your error, ie. your diff variable.

Answer 2

One important skill in programming is knowing which information where will be most useful. If you add some simple debugging information:

while abs(diff) > epsl and _cnt < count:
    guess = guess - (guess ** 2.0 + epsl) / (guess * 2.0)
    diff = guess ** 2.0 - num
    print guess, _cnt
    _cnt = _cnt +1
print guess, _cnt

You can see that your program goes wrong quickly:

$ ./sqrt.py 
0.49995 0
0.249874989999 1
0.124737394941 2
0.0619678553654 3
0.0301770577385 4
0.0134316410297 5
0.00299326718803 6
-0.0152075217183 7
-0.00431591416548 8
0.00942707405618 9
-0.000590335594744 10
....

It appears to halve the number every iteration until it goes negative, when the behavior gets very difficult to tell just at a glance. But you can obviously tell that the very first few iterations are wrong.

Something that looks quite fishy to me: (guess ** 2.0 + epsl)

You shouldn't actually use epsilon when evaluating Newton's method for square roots -- after all, you're trying to make sure your error is less than epsilon.

Answer 3

It looks like you are looking for zeroes of the function f = x^2+eps1. If eps1 is positive, there will be no real zeroes. This means that your program will oscillate around 0 forever after a certain point, as you saw. If you set eps1 to a negative value, I expect you would find a root.

Newton's method isn't bullet-proof, and there are cases where it can diverge.

Answer 4

You also can use guess = 0.5 * (guess + num/guess)