Scipy: быстрее ли метод Ньютона с числовыми производными, чем метод секущей

Я пытаюсь найти корень уравнения, используя Newton-Raphson, предоставленный SciPy (scipy.optimize.newton).

На данный момент у меня нет значений fprime, которые советует использовать документация, и, насколько мне известно, это означает, что для поиска корней используется метод Secant.

Поскольку метод Ньютона-Рафсона имеет более быструю сходимость, чем метод Секанта, моя интуиция подсказывает, что, возможно, мне следует численно аппроксимировать fprime и обеспечить его, чтобы использовался метод Ньютона.

Какой из них обычно приводит к более быстрой конвергенции / более быстрому фактическому вычислению моих корней?

  1. Просто используя scipy.optimize.newton без указания fprime (т. е. метод секущей или
  2. Использование численного дифференцирования для вычисления fprime (например, с помощью numpy.diff) и предоставление его scipy.optimize.newton, чтобы использовался метод Ньютона-Рафсона.

python numpy scipy numerical-methods newtons-method
person Joel Biffin    schedule 09.03.2019    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В книге Численные рецепты в C, 2-е издание, в разделе «9.4 Метод Ньютона-Рафсона с использованием производной» на странице 365 говорится:

Формула Ньютона-Рафсона также может быть применена с использованием числовой разности для аппроксимации истинной локальной производной,

f'(x) ≈ (f(x + dx) - f(x)) / dx .

Однако это не рекомендуемая процедура по следующим причинам: (i) Вы выполняете два вычисления функции за шаг, поэтому в лучшем случае суперлинейный порядок сходимости будет только sqrt(2). (ii) Если вы возьмете dx слишком маленьким, вы будете уничтожены округлением, а если вы возьмете слишком большое, ваш порядок сходимости будет только линейным, не лучше, чем при первоначальной оценке f'(x_0) для всех последующих шагов. Таким образом, в методе Ньютона-Рафсона с числовыми производными (в одном измерении) всегда доминирует метод секущих из раздела 9.2.

(Это было отредактировано, чтобы соответствовать ограничениям этого сайта.) Выбор другого метода для повышения точности числовой производной увеличил бы количество вычислений функции и, таким образом, еще больше уменьшил бы порядок сходимости. Поэтому вы должны выбрать свой первый метод, который заканчивается использованием метода секущих для поиска корня.

person Rory Daulton    schedule 09.03.2019