О курсе MIT 6.00 lec06 - метод Ньютона

Question

Я пытался кодировать по-своему, но обнаружил, что получил неправильный ответ.

Я прочитал эту страницу. И попробуйте запустить процесс:

Р (х) = х ^ 2-е

Математика:

Так вот мой код:

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)

Однако я получил неправильный ответ.

Вывод этой функции:

D: \ poc> python sq.py

0,0595177826557 100

Answer 1

Одним из важных навыков в программировании является знание, какая информация будет наиболее полезной.Если вы добавите некоторую простую отладочную информацию:

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

Вы можете видеть, что ваша программа быстро работает неправильно:

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

Кажется, что число уменьшается на две итерации до тех пор, пока не станет отрицательным, когдаповедение становится очень трудно определить с первого взгляда.Но вы, очевидно, можете сказать, что первые несколько итераций неверны.

Что-то, что мне кажется довольно подозрительным: (guess ** 2.0 + epsl)

На самом деле вы не должны использовать epsilon при оценке метода Ньютона для квадратакорни - в конце концов, вы пытаетесь убедиться, что ваша ошибка меньше, чем эпсилон.

Answer 2

Похоже, вы ищете нули функции f = x ^ 2 + eps1. Если eps1 положительный, реальных нулей не будет. Это означает, что ваша программа будет колебаться около 0 навсегда после определенной точки, как вы видели. Если вы установите eps1 в отрицательное значение, я ожидаю, что вы найдете корень.

Метод Ньютона не является пуленепробиваемым, и в некоторых случаях он может расходиться.

Answer 3

Вы также можете использовать guess = 0.5 * (guess + num/guess)

Answer 4

Измените (guess ** 2.0 + epsl) на (guess ** 2 - num) в вашем уравнении.Вы хотите корректировать свою оценку каждый шаг на величину, пропорциональную вашей ошибке, т.е.ваша diff переменная.