метод Ньютона

В численном анализе метод Ньютона , также известный как метод Ньютона-Рафсона , названный в честь Исаака Ньютона и Джозефа Рафсона , представляет собой алгоритм поиска корня , который производит последовательно лучшие приближения к корням нулям) действительной функции ( или . Самая базовая версия начинается с функции $f$ , ее производной $f'$ и начального предположения $x 0$ для корня f $вещественной$ . Если $f$ удовлетворяет определенным предположениям и начальное предположение близко, то

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$

является лучшим приближением корня, чем $x 0$ . Геометрически $(x 1 0)$ — это х точка пересечения с касательной графика 1 f $,$ в $(x 0, f (x 0))$ : то есть улучшенное предположение $x является$ уникальным корнем линейного аппроксимация f $,$ при первоначальном предположении $x 0$ . Процесс повторяется как

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

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

Описание

Идея состоит в том, чтобы начать с начального предположения, затем аппроксимировать функцию ее касательной линией и, наконец, вычислить точку $пересечения x$ этой касательной линии. Этот $x$ -перехват обычно будет лучшим приближением к корню исходной функции, чем первое предположение, и метод можно повторять .

Если касательная линия к кривой $f (x)$ в точке $x = x n$ пересекает $ось x$ в точке $x n +1$ , то наклон равен

$f'(x_{n})={\dfrac {f(x_{n})-0}{x_{n}-x_{n+1}}}.$

Решение для $x n +1$ дает

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.$

Мы начинаем процесс с некоторого произвольного начального значения $x 0$ . (Чем ближе к нулю, тем лучше. Но в отсутствие какой-либо интуиции относительно того, где может находиться ноль, метод «угадай и проверь» может сузить возможности до разумно малого интервала, обратившись к теореме о промежуточном значении .) Метод обычно сходится при условии, что это начальное предположение достаточно близко к неизвестному нулю и что $f' (x 0) \neq 0$ . Более того, для нуля кратности 1 сходимость как минимум квадратичная (см. Скорость сходимости ) в окрестности нуля, что интуитивно означает, что количество правильных цифр примерно удваивается на каждом шаге. Более подробную информацию можно найти в § Анализ ниже.

Методы Хаусхолдера аналогичны, но имеют более высокий порядок для еще более быстрой сходимости. Однако дополнительные вычисления, необходимые для каждого шага, могут замедлить общую производительность по сравнению с методом Ньютона, особенно если $оценка f$ или его производных требует больших вычислительных затрат.

История

Название «метод Ньютона» происходит от описания Исааком Ньютоном частного случая метода в De analysi per aequationes numero terminorum infinitas (написано в 1669 году, опубликовано в 1711 году Уильямом Джонсом ) и в De metodis fluxionum et serierum infinitarum ( написано в 1671 году, переведено и опубликовано под названием «Метод флюксий» в 1736 году Джоном Колсоном ). Однако его метод существенно отличается от современного метода, приведенного выше. Ньютон применил этот метод только к полиномам, начиная с первоначальной оценки корня и извлекая последовательность исправлений ошибок. Он использовал каждую поправку, чтобы переписать полином с точки зрения оставшейся ошибки, а затем решил новую поправку, пренебрегая членами более высокой степени. Он не связал метод явно с производными и не представил общей формулы. Ньютон применил этот метод как к численным, так и к алгебраическим задачам, получив ряд Тейлора в последнем случае .

Ньютон, возможно, заимствовал свой метод из аналогичного, менее точного метода Виеты . Суть метода Виеты можно найти в работах персидского математика Шарафа ад-Дина ат-Туси , в то время как его преемник Джамшид аль-Каши использовал форму метода Ньютона для решения $х. П - N = 0,$ чтобы найти корни $N$ (Ypma 1995). Частный случай метода Ньютона для вычисления квадратных корней был известен с древних времен и часто называется вавилонским методом .

Метод Ньютона использовался японским математиком 17-го века Секи Кова для решения уравнений с одной переменной, хотя связь с исчислением отсутствовала. ^[1]

Метод Ньютона был впервые опубликован в 1685 году в «Трактате об алгебре, как исторической, так и практической», написанном Джоном Уоллисом . ^[2] В 1690 году Джозеф Рафсон опубликовал упрощенное описание в «Анализ универсальных уравнений» . ^[3] Рафсон также применил этот метод только к полиномам, но избежал утомительного процесса переписывания Ньютона, извлекая каждую последующую поправку из исходного полинома. Это позволило ему получить многократно используемое итеративное выражение для каждой проблемы. Наконец, в 1740 году Томас Симпсон описал метод Ньютона как итерационный метод решения общих нелинейных уравнений с помощью исчисления, по сути дав описание, приведенное выше. В той же публикации Симпсон также дает обобщение на системы двух уравнений и отмечает, что метод Ньютона можно использовать для решения задач оптимизации, установив градиент равным нулю.

Артур Кэли в 1879 году в книге «Воображаемая задача Ньютона – Фурье» первым заметил трудности при обобщении метода Ньютона на комплексные корни многочленов со степенью больше 2 и комплексными начальными значениями. Это открыло путь к изучению теории итераций рациональных функций.

Практические соображения

Метод Ньютона — мощный метод: в целом сходимость является квадратичной: по мере того, как метод сходится к корню, разница между корнем и приближением возводится в квадрат (количество точных цифр примерно удваивается) на каждом шаге. Однако метод имеет некоторые трудности.

Сложность вычисления производной функции

Метод Ньютона требует, чтобы производная могла быть вычислена напрямую. Аналитическое выражение для производной может быть нелегко получить, или его оценка может оказаться дорогостоящей. В таких ситуациях может оказаться целесообразным аппроксимировать производную, используя наклон линии, проходящей через две близлежащие точки функции. Использование этого приближения приведет к чему-то вроде метода секущих , сходимость которого медленнее, чем у метода Ньютона.

Неспособность метода сходиться к корню

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

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

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

Медленная сходимость для корней кратности больше 1

Если искомый корень имеет кратность больше единицы, скорость сходимости является просто линейной (ошибки уменьшаются в постоянном коэффициенте на каждом шаге), если не предпринимаются специальные шаги. Когда есть два или более корня, расположенных близко друг к другу, может потребоваться много итераций, прежде чем итерации подойдут достаточно близко к одному из них, чтобы квадратичная сходимость стала очевидной. Однако, если кратность $m$ корня известна, следующий модифицированный алгоритм сохраняет квадратичную скорость сходимости: ^[4]

$x_{n+1}=x_{n}-m{\frac {f(x_{n})}{f'(x_{n})}}.$

Это эквивалентно использованию последовательного чрезмерного расслабления . С другой стороны, если кратность $m$ корня неизвестна, можно оценить $m$ после проведения одной или двух итераций, а затем использовать это значение для увеличения скорости сходимости.

Если кратность $m$ корня конечна, то $g ( x ) = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ f ( x ) / f ′ ( x ) ⁠$ будет иметь корень в том же месте с кратностью 1. Применение метода Ньютона для нахождения корня $g (x)$ во многих случаях восстанавливает квадратичную сходимость, хотя обычно это включает в себя вторую производную от $ж (Икс)$ . В особенно простом случае, если $f (x) = x м$ тогда $г (Икс) = ⁠ x / m ⁠$ и метод Ньютона находит корень за одну итерацию с

$x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {\;{\frac {x_{n}}{m}}\;}{\frac {1}{m}}}=0\,.$

Анализ

Предположим, что функция $f$ имеет нуль в точке $α$ , т.е. $f (α) = 0$ , и $f$ дифференцируема в окрестности точки $α$ .

Если $f$ непрерывно дифференцируема и ее производная не равна нулю в точке $α$ , то существует окрестность точки $α$ такая, что для всех начальных значений $x 0$ в этой окрестности последовательность $(x n)$ будет сходиться к $α$ . ^[5]

Если $f$ непрерывно дифференцируема, ее производная отлична от нуля в точке $α$ и . имеет вторую производную в точке $α$ , то сходимость является квадратичной или более быстрой Если вторая производная не равна 0 в точке $α$ , то сходимость просто квадратичная. Если третья производная существует и ограничена в окрестности точки $α$ , то:

$\Delta x_{i+1}={\frac {f''(\alpha )}{2f'(\alpha )}}\left(\Delta x_{i}\right)^{2}+O\left(\Delta x_{i}\right)^{3}\,,$

где

$\Delta x_{i}\triangleq x_{i}-\alpha \,.$

Если производная равна 0 при $α$ , то сходимость обычно только линейная. В частности, если $f$ дважды непрерывно дифференцируема, $f' (α) = 0$ и $f ″ (α) \neq 0$ , то существует окрестность $α$ такая, что для всех начальных значений $x 0$ в этой окрестности последовательность итераций сходится линейно, со скоростью ⁠ 1 / 2 ⁠ . ^[6] Альтернативно, если $f' (α) = 0$ и $f' (x) \neq 0$ для $x \neq α$ , $x$ в окрестности $U$ точки $α$ , $α$ является нулем кратности $r$ , и если $f \in C р (U)$ , то существует окрестность $α$ такая, что для всех начальных значений $x 0$ в этой окрестности последовательность итераций сходится линейно.

Однако даже линейная конвергенция не гарантируется в патологических ситуациях.

На практике эти результаты локальны, и окрестность сходимости заранее не известна. Но есть также некоторые результаты о глобальной сходимости: например, для правой окрестности $U +$ точки $α$ , если $f$ дважды дифференцируема в $U +$ и если $f' \neq 0$ , $f \cdot f ″ > 0$ в $U +$ , то для для каждого $x 0$ в $U +$ последовательность $x k$ монотонно убывает до $α$ .

Доказательство квадратичной сходимости итерационного метода Ньютона.

Согласно теореме Тейлора , любая функция $f (x),$ имеющая непрерывную вторую производную, может быть представлена разложением относительно точки, близкой к корню $f (x)$ . Предположим, что этот корень равен $α$ . Тогда разложение $f (α)$ относительно $x n$ будет следующим:

f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+R_{1}\,

( 1 )

где форма Лагранжа остатка разложения в ряд Тейлора равна

$R_{1}={\frac {1}{2!}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,,$

где $ξ n$ находится между $x n$ и $α$ .

Поскольку $α$ является корнем, ( 1 ) становится:

0=f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+{\tfrac {1}{2}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,

( 2 )

Разделив уравнение ( 2 ) на $f' (x n)$ и переставив, получим

{\frac {f(x_{n})}{f'(x_{n})}}+\left(\alpha -x_{n}\right)={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\left(\alpha -x_{n}\right)^{2}

( 3 )

Помня, что $x n + 1$ определяется формулой

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,,

( 4 )

человек обнаруживает, что

$\underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}{(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)}^{2}\,.$

То есть,

\varepsilon _{n+1}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\cdot \varepsilon _{n}^{2}\,.

( 5 )

Взятие абсолютного значения обеих сторон дает

\left|{\varepsilon _{n+1}}\right|={\frac {\left|f''(\xi _{n})\right|}{2\left|f'(x_{n})\right|}}\cdot \varepsilon _{n}^{2}\,.

( 6 )

Уравнение ( 6 ) показывает, что порядок сходимости не ниже квадратичного, если выполняются следующие условия:

$ж' (Икс) \neq 0$ ; для всех $x \in I$ , где $I$ — интервал $[α - | ε 0 |, α + | ε 0 |]$ ;
$f ″ (x)$ непрерывен для всех $x \in I$ ;
$М | ε 0 | < 1$

где $M$ определяется выражением

$M={\frac {1}{2}}\left(\sup _{x\in I}\vert f''(x)\vert \right)\left(\sup _{x\in I}{\frac {1}{\vert f'(x)\vert }}\right).\,$

Если эти условия выполняются,

$\vert \varepsilon _{n+1}\vert \leq M\cdot \varepsilon _{n}^{2}\,.$

Условия Фурье

Предположим, что $f (x)$ — вогнутая функция на интервале, строго возрастающая . Если он отрицателен в левой конечной точке и положителен в правой конечной точке, теорема о промежуточном значении существует ноль $ζ$ функции $f$ гарантирует, что где-то в интервале . Из геометрических принципов видно, что итерация Ньютона $xi,$ начинающаяся с левой конечной точки, монотонно возрастает и сходится обязательно к $ζ$ . ^[7]

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

y_{i+1}=y_{i}-{\frac {f(y_{i})}{f'(x_{i})}}.

Эта последовательность монотонно убывает и сходится. Переходя к пределу в этом определении, можно увидеть, что предел $y i$ также должен быть нулем $ζ$ . ^[7]

Итак, в случае вогнутой возрастающей функции с нулем инициализация во многом неактуальна. Итерация Ньютона, начинающаяся где-нибудь левее нуля, будет сходиться, как и модифицированная итерация Ньютона Фурье, начинающаяся где-то справа от нуля. Точность на любом шаге итерации можно определить непосредственно по разнице между расположением итерации слева и расположением итерации справа. Если $f$ можно доказать дважды непрерывно дифференцируемо, с помощью теоремы Тейлора , что

\lim _{i\to \infty }{\frac {y_{i+1}-x_{i+1}}{(y_{i}-x_{i})^{2}}}=-{\frac {1}{2}}{\frac {f''(\zeta )}{f'(\zeta )}},

показывая, что эта разница в местоположениях квадратично сходится к нулю. ^[7]

Все вышесказанное можно распространить на системы уравнений со многими переменными, хотя в этом контексте соответствующие концепции монотонности и вогнутости сформулировать сложнее. ^[8] В случае одиночных уравнений с одной переменной описанная выше монотонная сходимость метода Ньютона также может быть обобщена для замены вогнутости условиями положительности или отрицательности для произвольной производной высшего порядка $f$ . Однако в этом обобщении итерация Ньютона модифицируется так, чтобы основываться на полиномах Тейлора, а не на касательной линии . В случае вогнутости эта модификация совпадает со стандартным методом Ньютона. ^[9]

Примеры

Использование метода Ньютона для вычисления квадратных корней

Метод Ньютона — один из многих известных методов вычисления квадратных корней . Учитывая положительное число $a$ , задача найти число $x$ такое, что $x 2 = a$ эквивалентно нахождению корня функции $f (x) = x 2 - а$ . Итерация Ньютона, определенная этой функцией, определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right).

Это случайно совпадает с «вавилонским» методом нахождения квадратных корней в замене приближенного корня $x n$ средним арифметическим x $n, который заключается$ и $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}а ⁄ х п$ . Выполняя эту итерацию, можно вычислить квадратный корень с любой желаемой точностью, используя только основные арифметические операции .

В следующих трех таблицах показаны примеры результата этого вычисления для нахождения квадратного корня из 612, при этом итерация инициализируется значениями 1, 10 и –20. Каждая строка в столбце « $x n$ » получается путем применения предыдущей формулы к записи над ней, например

306.5={\frac {1}{2}}\left(1+{\frac {612}{1}}\right).

$х н$	$ж (Икс п)$	$х н$	$ж (Икс п)$	$х н$	$ж (Икс п)$
1	−611	10	−512	−2 0	−212
306.5	9.3330 × 10 ⁴	35.6	655.36	−2 5.3	28.09
154.2483686786	2.3180 × 10 ⁴	2 6.3955056180	84.722	−24.7 448616601	0.30818
79.1079978644	5.6461 × 10 ³	24.7 906354925	2.5756	−24.73863 45374	3.8777 × 10 ⁻⁵
43.4221286822	1.2735 × 10 ³	24.7386 882941	2.6985 × 10 ⁻³	−24.7386337537	6.1424 × 10 ⁻¹³
2 8.7581624288	215.03	24.738633753 8	2.9746 × 10 ⁻⁹
2 5.0195385369	13.977
24.7 402106712	7.8024 × 10 ⁻²
24.738633 8040	2.4865 × 10 ⁻⁶
24.7386337537	2.5256 × 10 ⁻¹⁵

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

При вычислении любого ненулевого квадратного корня первая производная $f$ должна быть ненулевой в корне, и что $f$ является гладкой функцией. Итак, еще до каких-либо вычислений известно, что любая сходящаяся итерация Ньютона имеет квадратичную скорость сходимости. В приведенных выше таблицах это отражено в том факте, что как только итерация Ньютона приближается к корню, количество правильных цифр примерно удваивается с каждой итерацией.

Решение $cos(x) = x 3$ используя метод Ньютона

Рассмотрим задачу нахождения положительного числа $x$ с $cos x = x 3$ . Мы можем перефразировать это как поиск нуля $f (x) = cos (x) - x 3$ . У нас есть $f' (x) = -sin(x) - 3 x 2$ . Поскольку $cos(x) \leq 1$ для всех $x$ и $x 3 > 1$ для $x > 1$ , мы знаем, что наше решение лежит между 0 и 1.

Начальное значение 0 приведет к неопределенному результату, что иллюстрирует важность использования начальной точки, близкой к решению. Например, при первоначальном предположении $x 0 = 0,5$ последовательность, заданная методом Ньютона, следующая:

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$

В приведенном выше примере правильные цифры подчеркнуты. В частности, $x 6$ соответствует 12 десятичным знакам. Мы видим, что количество правильных цифр после запятой увеличивается с 2 (для $x 3$ ) до 5 и 10, иллюстрируя квадратичную сходимость.

Медленная конвергенция

Функция $f (x) = x 2$ имеет корень в 0. ^[10] Поскольку $f$ непрерывно дифференцируема в своем корне, теория гарантирует, что метод Ньютона, инициализированный достаточно близко к корню, будет сходиться. Однако, поскольку производная $f'$ равна нулю в корне, квадратичная сходимость не обеспечивается теорией. В этом конкретном примере итерация Ньютона определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {1}{2}}x_{n}.

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

Функция $f (x) = x + x 4/3$ также имеет корень в 0, где оно непрерывно дифференцируемо. Хотя первая производная $f'$ отлична от нуля в корне, вторая производная $f'$ там не существует, так что квадратичная сходимость не может быть гарантирована. Фактически итерация Ньютона определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {x^{4/3}}{3+4x^{1/3}}}.

Отсюда видно, что скорость сходимости суперлинейная, но субквадратичная. Это можно увидеть в следующих таблицах, слева от которых показан метод Ньютона, примененный к вышеизложенному $f (x) = x + x 4/3$ и справа от него показан метод Ньютона, примененный к $f (x) = x + x 2$ . Квадратичная сходимость при итерации, показанная справа, иллюстрируется примерно удвоением порядков расстояния от итерации до истинного корня (0,1,2,3,5,10,20,39,...). из ряда в ряд. Хотя сходимость слева суперлинейная, порядок величины умножается всего примерно на 4/3 от строки к строке (0,1,2,4,5,7,10,13,...).

$х н$	$х + х 4/3 н$	$х н$	$х + х 2 н$
1	2	1	2
1.4286 × 10 ⁻¹	2.1754 × 10 ⁻¹	3.3333 × 10 ⁻¹	4.4444 × 10 ⁻¹
1.4669 × 10 ⁻²	1.8260 × 10 ⁻²	6.6666 × 10 ⁻²	7.1111 × 10 ⁻²
9.0241 × 10 ⁻⁴	9.8961 × 10 ⁻⁴	3.9216 × 10 ⁻³	3.9369 × 10 ⁻³
2.5750 × 10 ⁻⁵	2.6511 × 10 ⁻⁵	1.5259 × 10 ⁻⁵	1.5259 × 10 ⁻⁵
2.4386 × 10 ⁻⁷	2.4539 × 10 ⁻⁷	2.3283 × 10 ⁻¹⁰	2.3283 × 10 ⁻¹⁰
5.0366 × 10 ⁻¹⁰	5.0406 × 10 ⁻¹⁰	5.4210 × 10 ⁻²⁰	5.4210 × 10 ⁻²⁰
1.3344 × 10 ⁻¹³	1.3344 × 10 ⁻¹³	2.9387 × 10 ⁻³⁹	2.9387 × 10 ⁻³⁹

Скорость сходимости отличается от количества итераций, необходимых для достижения заданной точности. Например, функция $f (x) = x 20 - 1$ имеет корень в точке 1. Поскольку $f'(1) \neq 0$ и $f$ гладкая, известно, что любая итерация Ньютона, сходящаяся к 1, сходится квадратично. Однако при инициализации значением 0,5 первые несколько итераций метода Ньютона составляют примерно 26214, 24904, 23658, 22476, медленно уменьшаясь, и только 200-я итерация равна 1,0371. Следующие итерации: 1,0103, 1,00093, 1,0000082 и 1,00000000065, иллюстрирующие квадратичную сходимость. Это подчеркивает, что квадратичная сходимость итерации Ньютона не означает, что требуется всего несколько итераций; это применимо только в том случае, если последовательность итераций достаточно близка к корню. ^[11]

Сходимость, зависящая от инициализации

Функция $f (x) = x (1 + x 2) -1/2$ имеет корень в 0. Итерация Ньютона определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=-x_{n}^{3}.

Отсюда видно, что для итерации Ньютона возможны три явления. Если инициализировать строго между $\pm1$ , итерация Ньютона будет сходиться (супер-)квадратично к 0; если инициализироваться точно в $1$ или $-1$ , итерация Ньютона будет бесконечно колебаться между $\pm1$ ; если инициализировать где-нибудь еще, итерация Ньютона будет расходиться. ^[12] Такая же трихотомия происходит для $f (x) = arctan x$ . ^[10]

В случаях, когда рассматриваемая функция имеет несколько корней, может быть трудно контролировать посредством выбора инициализации, какой корень (если таковой имеется) идентифицирован методом Ньютона. Например, функция $f (x) = x (x 2 - 1)(х - 3)е -(х - 1) 2 /2$ имеет корни в точках -1, 0, 1 и 3. ^[13] Если инициализировано значением -1,488, итерация Ньютона сходится к 0; если инициализировано значением -1,487, оно расходится до $\infty$ ; если инициализировано значением -1,486, оно сходится к -1; если инициализировано значением -1,485, оно расходится до $-\infty$ ; если инициализировано значением -1,4843, оно сходится к 3; если инициализировано значением -1,484, оно сходится к $1$ . Такая тонкая зависимость от инициализации не является редкостью; его часто изучают в комплексной плоскости в форме фрактала Ньютона .

Расхождение, даже когда инициализация близка к корню

Рассмотрим задачу нахождения корня $f (x) = x 1/3$ . Итерация Ньютона

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{1/3}}{{\frac {1}{3}}x_{n}^{-2/3}}}=-2x_{n}.

Если метод Ньютона не инициализирован точным корнем 0, видно, что последовательность итераций не сможет сходиться. Например, даже если инициализироваться с достаточно точным предположением 0,001, первые несколько итераций будут равны -0,002, 0,004, -0,008, 0,016, достигая 1048,58, -2097,15,... к 20-й итерации. Эта неудача сходимости не противоречит аналитической теории, поскольку в этом случае $f$ не дифференцируема в своем корне.

В приведенном выше примере неудача сходимости отражается неспособностью $f (x n)$ приблизиться к нулю по мере $увеличения n$ , а также тем фактом, что последовательные итерации становятся все дальше и дальше друг от друга. Однако функция $f (x) = x 1/3 и - х 2$ также имеет корень в 0. Итерация Ньютона определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}\left(1-{\frac {3}{1-6x_{n}^{2}}}\right).

В этом примере, где $f$ снова не дифференцируемо в корне, любая итерация Ньютона, не начинающаяся точно с корня, будет расходиться, но при этом как $x n + 1 - x n$ , так и $f (x n)$ будут стремиться к нулю. ^[14] Это видно из следующей таблицы, показывающей итерации с инициализацией 1:

$х н$	$ж (Икс п)$
1	0.36788
1.6	9.0416 × 10 ⁻²
1.9342	2.9556 × 10 ⁻²
2.2048	1.0076 × 10 ⁻²
2.4396	3.5015 × 10 ⁻³
2.6505	1.2307 × 10 ⁻³
2.8437	4.3578 × 10 ⁻⁴
3.0232	1.5513 × 10 ⁻⁴

Хотя сходимость $x n + 1 - x n$ в этом случае происходит не очень быстро, ее можно доказать с помощью итерационной формулы. Этот пример подчеркивает возможность того, что критерий остановки метода Ньютона, основанный только на малости $x n + 1 - x n$ и $f (x n),$ может ошибочно идентифицировать корень.

Колебательное поведение

Касательные линии $x 3 - 2 x + 2$ в точках 0 и 1 пересекают $ось x$ в точках 1 и 0 соответственно, иллюстрируя, почему метод Ньютона колеблется между этими значениями для некоторых начальных точек.

Легко найти ситуации, в которых метод Ньютона бесконечно колеблется между двумя различными значениями. Например, для того, чтобы метод Ньютона, примененный к функции $f$ , колебался между 0 и 1, необходимо только, чтобы касательная линия к $f$ в точке 0 пересекала $ось x$ в точке 1, а касательная линия к $f$ в точке 1 пересекала ось $x.$ -ось в положении 0. ^[14] Это имеет место, например, если $f (x) = x 3 - 2 х + 2$ . Для этой функции даже возможен случай, когда итерация Ньютона, инициализированная достаточно близко к 0 или 1, будет асимптотически колебаться между этими значениями. Например, метод Ньютона, инициализированный значением 0,99, дает итерации 0,99, -0,06317, 1,00628, 0,03651, 1,00196, 0,01162, 1,00020, 0,00120, 1,000002 и так далее. Такое поведение присутствует, несмотря на наличие корня $f,$ примерно равного -1,76929.

Неопределенность метода Ньютона

В некоторых случаях невозможно даже выполнить итерацию Ньютона. Например, если $f (x) = x 2 - 1$ , то итерация Ньютона определяется формулой

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {x_{n}^{2}+1}{2x_{n}}}.

Таким образом, метод Ньютона не может быть инициализирован значением 0, так как это сделало бы $x 1$ неопределенным. Геометрически это связано с тем, что касательная линия к $f$ в точке 0 горизонтальна (т. е. $f'(0) = 0$ ), никогда не пересекая $ось x$ .

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

Если $f$ имеет неполный домен, метод Ньютона может отправить итерации за пределы домена, так что продолжить итерацию будет невозможно. ^[14] Например, натурального логарифма функция $f (x) = ln x$ имеет корень в 1 и определяется только для положительных $x$ . Итерация Ньютона в этом случае определяется выражением

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}(1-\ln x_{n}).

Таким образом, если итерация инициализируется в $e$ , следующая итерация будет равна 0; если итерация инициализируется значением, большим, чем $e$ , то следующая итерация будет отрицательной. В любом случае, метод не может быть продолжен.

Многомерные составы

Системы уравнений

$k$ переменных, $k$ функций

Можно также использовать метод Ньютона для решения систем $k$ уравнений, что означает нахождение (одновременных) нулей $k$ непрерывно дифференцируемых функций. $f:\mathbb {R} ^{k}\to \mathbb {R} .$ Это эквивалентно нахождению нулей одной вектор-функции. $F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}.$ В приведенной выше формулировке скаляры $x n$ заменяются векторами $x n,$ и вместо деления функции $f (x n)$ на ее производную $f' (x n)$ вместо этого нужно умножить функцию $F (x n)$ слева на обратная $k \times k$ матрице якобиана размера $J F (x n)$ . ^[15]^[16]^[17] Это приводит к выражению

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-J_{F}(\mathbf {x} _{n})^{-1}F(\mathbf {x} _{n}).$

или, решив систему линейных уравнений

$J_{F}(\mathbf {x} _{n})(\mathbf {x} _{n+1}-\mathbf {x} _{n})=-F(\mathbf {x} _{n})$

для неизвестного $Икс п + 1 - Икс п$ . ^[18]

$k$ переменных, $m$ уравнений, где $m > k$

k $(нелинейных) уравнений ,$ -мерный вариант метода Ньютона $можно использовать для решения систем, состоящих более чем из k$ также если в алгоритме используется обобщенная обратная неквадратная Якоби матрица $J + = (Дж Т Дж) -1 Дж Т$ вместо обратного $J$ . Если нелинейная система не имеет решения, метод пытается найти решение в смысле нелинейного метода наименьших квадратов . Для получения дополнительной информации см. Алгоритм Гаусса – Ньютона .

Пример

Например, для вектора точек необходимо решить следующий набор уравнений: $\ [\ x_{1},x_{2}\ ]\ ,$ учитывая вектор известных значений $\ [\ 2,3\ ]~.$ ^[19]

${\begin{array}{lcr}5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})&=\quad 2\\e^{2\ x_{1}-x_{2}}+4\ x_{2}&=\quad 3\end{array}}$

вектор функции, $\ F(X_{k})\ ,$ и матрица Якобиана, $\ J(X_{k})\$ для итерации k и вектор известных значений, $\ Y\ ,$ определены ниже.

${\begin{aligned}~&F(X_{k})~=~{\begin{bmatrix}{\begin{aligned}~&f_{1}(X_{k})\\~&f_{2}(X_{k})\end{aligned}}\end{bmatrix}}~=~{\begin{bmatrix}{\begin{aligned}~&5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})\\~&e^{2\ x_{1}-x_{2}}+4\ x_{2}\end{aligned}}\end{bmatrix}}_{k}\\~&J(X_{k})={\begin{bmatrix}~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{2}}}}~\\~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{2}}}}~\end{bmatrix}}_{k}~=~{\begin{bmatrix}{\begin{aligned}~&10\ x_{1}+x_{2}^{2}\ ,&&2\ x_{1}\ x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})\\~&2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4\end{aligned}}\end{bmatrix}}_{k}\\~&Y={\begin{bmatrix}~2~\\~3~\end{bmatrix}}\end{aligned}}$

Обратите внимание, что $\ F(X_{k})\$ можно было бы переписать, чтобы поглотить $\ Y\ ,$ и тем самым устранить $Y$ из уравнений. Уравнение, которое нужно решить для каждой итерации:

${\begin{aligned}{\begin{bmatrix}{\begin{aligned}~&~10\ x_{1}+x_{2}^{2}\ ,&&2x_{1}x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})~\\~&~2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4~\end{aligned}}\end{bmatrix}}_{k}{\begin{bmatrix}~c_{1}~\\~c_{2}~\end{bmatrix}}_{k+1}={\begin{bmatrix}~5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})-2~\\~e^{2\ x_{1}-x_{2}}+4\ x_{2}-3~\end{bmatrix}}_{k}\end{aligned}}$

и

$X_{k+1}~=~X_{k}-C_{k+1}$

Итерации следует повторять до тех пор, пока $\ {\Bigg [}\sum _{i=1}^{i=2}{\Bigl |}f(x_{i})_{k}-(y_{i})_{k}{\Bigr |}{\Bigg ]}<E\ ,$ где $\ E\$ — это значение, достаточно малое для удовлетворения требований приложения.

Если вектор $\ X_{0}\$ изначально выбрано $\ {\begin{bmatrix}~1~&~1~\end{bmatrix}}\ ,$ то есть, $\ x_{1}=1\ ,$ и $\ x_{2}=1\ ,$ и $\ E\ ,$ выбрано значение 1,10 ⁻³, то после четырех итераций пример сходится к значению $\ X_{4}=\left[~0.567297,\ -0.309442~\right]~.$

Итерации

В ходе решения были сделаны следующие итерации.

Сходящаяся последовательность итераций
Шаг	Переменная	Ценить
$0$	$х =$	${\begin{bmatrix}\ 1\ ,&1\end{bmatrix}}$
$0$	$ж (Икс) знак равно$	${\begin{bmatrix}\ 6.82682\ ,&6.71828\ \end{bmatrix}}$

$1$	$Дж =$	${\begin{bmatrix}\ 11~,&\quad 0.486395\\\ 5.43656\ ,&1.28172\end{bmatrix}}$
	$с =$	${\begin{bmatrix}\ 0.382211\ ,&1.27982\ \end{bmatrix}}$
	$х =$	${\begin{bmatrix}\ 0.617789\ ,&-0.279818\ \end{bmatrix}}$
	$ж (Икс) знак равно$	${\begin{bmatrix}\ 2.23852\ ,&3.43195\ \end{bmatrix}}$

$2$	$Дж =$	${\begin{bmatrix}\ 6.25618\ ,&-2.1453\\\ 9.10244\ ,&\quad -0.551218\end{bmatrix}}$
	$с =$	${\begin{bmatrix}0.0494549\ ,&0.0330411\ \end{bmatrix}}$
	$х =$	${\begin{bmatrix}\ 0.568334\ ,&-0.312859\ \end{bmatrix}}$
	$ж (Икс) знак равно$	${\begin{bmatrix}\ 2.01366\ ,&3.00966\ \end{bmatrix}}$

$3$	$Дж =$	${\begin{bmatrix}\ 5.78122\ ,&-2.25449\\\ 8.52219\ ,&\quad -0.261095\ \end{bmatrix}}$
	$с =$	${\begin{bmatrix}0.00102862\ ,&-0.00342339\ \end{bmatrix}}$
	$х =$	${\begin{bmatrix}\ 0.567305\ ,&-0.309435\ \end{bmatrix}}$
	$ж (Икс) знак равно$	${\begin{bmatrix}\ 2.00003\ ,&3.00006\ \end{bmatrix}}$

$4$	$Дж =$	${\begin{bmatrix}\ 5.7688~,&~-2.24118\\\ 8.47561\ ,&\quad -0.237805\end{bmatrix}}\$
	$с =$	${\begin{bmatrix}\ 7.73132\!\times \!10^{-6}~,&~6.93265\!\times \!10^{-6}\ \end{bmatrix}}$
	$х =$	${\begin{bmatrix}\ 0.567297\ ,&-0.309442\ \end{bmatrix}}$
	$ж (Икс) знак равно$	${\begin{bmatrix}~2\ ,~&~3~\end{bmatrix}}$

Сложные функции

При работе со сложными функциями метод Ньютона можно применять непосредственно для нахождения их нулей. ^[20] У каждого нуля есть область притяжения в комплексной плоскости — набор всех начальных значений, которые заставляют метод сходиться к этому конкретному нулю. Эти наборы можно сопоставить, как показано на изображении. Для многих сложных функций границы бассейнов притяжения являются фракталами .

В некоторых случаях на комплексной плоскости есть области, которые не входят ни в один из этих бассейнов притяжения, что означает, что итерации не сходятся. Например, ^[21] если использовать реальное начальное условие для поиска корня $x 2 + 1$ , все последующие итерации будут действительными числами, поэтому итерации не могут сходиться ни к одному из корней, поскольку оба корня недействительны. В этом случае почти все реальные начальные условия приводят к хаотическому поведению , а некоторые начальные условия повторяются либо до бесконечности, либо до повторяющихся циклов любой конечной длины.

Курт МакМаллен показал, что для любого возможного чисто итерационного алгоритма, подобного методу Ньютона, алгоритм будет расходиться в некоторых открытых областях комплексной плоскости при применении к некоторому полиному степени 4 или выше. Однако Макмаллен дал общесходящийся алгоритм для полиномов степени 3. ^[22] Кроме того, для любого полинома Хаббард, Шлейхер и Сазерленд предложили метод выбора набора начальных точек так, что метод Ньютона обязательно сходится хотя бы в одной из них. ^[23]

В банаховом пространстве

Другим обобщением является метод Ньютона, позволяющий найти корень функционала F $,$ определенного в банаховом пространстве . В этом случае формулировка

$X_{n+1}=X_{n}-{\bigl (}F'(X_{n}){\bigr )}^{-1}F(X_{n}),\,$

где $F' (X n)$ — производная Фреше , вычисленная в точке $X n$ . необходимо, чтобы производная Фреше была ограниченно обратимой при каждом $X n$ Для применимости метода . Условие существования и сходимости к корню дает теорема Ньютона–Канторовича . ^[24]

Итерация Нэша – Мозера

В 1950-х годах Джон Нэш разработал версию метода Ньютона для применения к проблеме построения изометрических вложений общих римановых многообразий в евклидово пространство . Проблема потери производных , присутствующая в этом контексте, сделала стандартную итерацию Ньютона неприменимой, поскольку ее нельзя было продолжать бесконечно (а тем более сходиться). Решение Нэша включало введение сглаживания в итерацию операторов . Ему удалось доказать сходимость своего сглаженного метода Ньютона с целью доказательства теоремы о неявной функции для изометрических вложений. В 1960-х годах Юрген Мозер показал, что методы Нэша достаточно гибки, чтобы применяться к проблемам, выходящим за рамки изометрического встраивания, особенно в небесной механике . С тех пор ряд математиков, в том числе Михаил Громов и Ричард Гамильтон , нашли обобщенные абстрактные версии теории Нэша – Мозера. ^[25]^[26] В формулировке Гамильтона теорема Нэша – Мозера образует обобщение метода Ньютона в банаховом пространстве, который имеет место в некоторых пространствах Фреше .

Модификации

Квазиньютоновские методы

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

Метод Чебышева третьего порядка.

Над $p$ -адическими числами

В $p$ -адическом анализе стандартным методом показать, что полиномиальное уравнение с одной переменной имеет $p$ -адический корень, является лемма Гензеля , которая использует рекурсию из метода Ньютона для $p$ -адических чисел. Из-за более устойчивого поведения сложения и умножения в $p$ -адических числах по сравнению с действительными числами (в частности, единичный шар в $p$ -адических числах представляет собой кольцо), сходимость в лемме Гензеля может быть гарантирована при гораздо более простых гипотезах, чем в классический метод Ньютона на действительной прямой.

$q$ -аналоговый

Метод Ньютона можно обобщить с помощью $q$ -аналога обычной производной. ^[27]

Модифицированные методы Ньютона

Процедура Мэйли

Нелинейное уравнение вообще имеет несколько решений. Но если начальное значение не подходит, метод Ньютона может не сходиться к желаемому решению или может сходиться к тому же решению, найденному ранее. Когда мы уже нашли $N$ решений $f(x)=0$ , то следующий корень можно найти, применив метод Ньютона к следующему уравнению: ^[28]^[29]

$F(x)={\frac {f(x)}{\prod _{i=1}^{N}(x-x_{i})}}=0.$

Этот метод применяется для получения нулей функции Бесселя второго рода. ^[30]

Модифицированный метод Ньютона Хирано.

Модифицированный метод Ньютона Хирано представляет собой модификацию, сохраняющую сходимость метода Ньютона и позволяющую избежать нестабильности. ^[31] Он разработан для решения сложных полиномов.

Интервальный метод Ньютона

Сочетание метода Ньютона с интервальной арифметикой очень полезно в некоторых контекстах. Это обеспечивает более надежный критерий остановки, чем обычные (которые представляют собой малое значение функции или небольшое изменение переменной между последовательными итерациями). Кроме того, это может выявить случаи, когда метод Ньютона сходится теоретически, но расходится численно из-за недостаточной точности операций с плавающей запятой (обычно это случается для полиномов большой степени, когда очень небольшое изменение переменной может резко изменить значение функции ; см. полином Уилкинсона ). ^[32]^[33]

Рассмотрим $f \to C 1 (X)$ , где $X$ — действительный интервал, и предположим, что у нас есть интервальное расширение $F'$ для $f'$ , что означает, что $F'$ принимает в качестве входных данных интервал $Y \subseteq X$ и выводит интервал $F' (Y)$ такой, что:

${\begin{aligned}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\mid y\in Y\}.\end{aligned}}$

Мы также предполагаем, что $0 \notin F' (X)$ , поэтому, в частности, $имеет$ не более одного корня в $X.$ f Затем мы определяем интервальный оператор Ньютона следующим образом:

$N(Y)=m-{\frac {f(m)}{F'(Y)}}=\left\{\left.m-{\frac {f(m)}{z}}~\right|~z\in F'(Y)\right\}$

где $м € Y$ . Обратите внимание, что гипотеза о $F'$ подразумевает, что $N (Y)$ корректно определен и является интервалом ( см. В интервальной арифметике более подробную информацию об интервальных операциях ). Это естественным образом приводит к следующей последовательности:

${\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}.\end{aligned}}$

Теорема о среднем значении гарантирует, что если есть корень $f$ в $X k$ , то он также находится в $X k + 1$ . Более того, гипотеза о $F'$ гарантирует, что $X k + 1$ не превышает половины размера $X k,$ когда $m$ является средней точкой $Y$ , поэтому эта последовательность сходится к $[x*, x*]$ , где $x*$ является корнем $е$ в $X.$

Если $F' (X)$ строго содержит 0, использование расширенного интервального разделения приводит к объединению двух интервалов для $N (X)$ ; поэтому несколько корней автоматически разделяются и ограничиваются.

Приложения

Задачи минимизации и максимизации

Метод Ньютона можно использовать для нахождения минимума или максимума функции $f (x)$ . Производная равна нулю в минимуме или максимуме, поэтому локальные минимумы и максимумы можно найти, применив к производной метод Ньютона. ^[34] Итерация становится:

$x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}}.$

Мультипликативные обратные числа и степенные ряды

Важным применением является деление Ньютона-Рафсона , которое можно использовать для быстрого нахождения обратного числа $a$ , используя только умножение и вычитание, то есть число $x$ такое, что $⁠ 1 / Икс ⁠ знак равно а$ . Мы можем перефразировать это как поиск нуля $f (x) = ⁠ 1 / Икс ⁠ - а$ . У нас есть $f' (x) = - ⁠ 1 / х 2 ⁠$ .

Итерация Ньютона

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{\frac {{\frac {1}{x_{n}}}-a}{\frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).$

Следовательно, итерация Ньютона требует всего двух умножений и одного вычитания.

Этот метод также очень эффективен для вычисления мультипликативного обратного степенного ряда .

Решение трансцендентных уравнений

Многие трансцендентные уравнения можно решить с любой точностью, используя метод Ньютона. Например, поиск кумулятивной функции плотности вероятности , такой как нормальное распределение, соответствующей известной вероятности, обычно включает в себя интегральные функции, для которых неизвестны средства решения в замкнутой форме. Однако общеизвестно вычисление производных, необходимых для их численного решения с помощью метода Ньютона, что делает возможным численное решение. Для примера см. численное решение обратного нормального кумулятивного распределения .

Численная проверка решений нелинейных уравнений

Численная проверка решений нелинейных уравнений была установлена путем многократного использования метода Ньютона и формирования набора кандидатов на решение. ^{[ нужна ссылка ]}

Код

Ниже приведен пример реализации метода Ньютона на языке программирования Python (версия 3.x) для поиска корня функции. f который имеет производную f_prime.

Первоначальное предположение будет $x 0 = 1$ , а функция будет $f (x) = x. 2 - 2$ так что $ж' (Икс) знак равно 2 Икс$ .

Каждую новую итерацию метода Ньютона будем обозначать x1. В ходе вычислений проверим, равен ли знаменатель ( yprime) становится слишком маленьким (меньше, чем epsilon), что было бы так, если бы $f' (x n) \approx 0$ , поскольку в противном случае может быть внесено большое количество ошибок.

def f(x):             
	return x**2 - 2   # f(x) = x^2 - 2

def f_prime(x):
	return 2*x        # f'(x) = 2x

def newtons_method(x0, f, f_prime, tolerance, epsilon, max_iterations):
    """Newton's method

    Args:
      x0:              The initial guess
      f:               The function whose root we are trying to find
      f_prime:         The derivative of the function
      tolerance:       Stop when iterations change by less than this
      epsilon:         Do not divide by a number smaller than this
      max_iterations:  The maximum number of iterations to compute
    """
    for _ in range(max_iterations):
        y = f(x0)
        yprime = f_prime(x0)

        if abs(yprime) < epsilon:       # Give up if the denominator is too small
            break

        x1 = x0 - y / yprime            # Do Newton's computation

        if abs(x1 - x0) <= tolerance:   # Stop when the result is within the desired tolerance
            return x1                   # x1 is a solution within tolerance and maximum number of iterations

        x0 = x1                         # Update x0 to start the process again

    return None                         # Newton's method did not converge

См. также

Примечания

^ «Глава 2. Сэки Такакадзу» . Японская математика в период Эдо . Национальная парламентская библиотека . Проверено 24 февраля 2019 г.
^ Уоллис, Джон (1685). Трактат по алгебре, как исторической, так и практической . Оксфорд: Ричард Дэвис. doi : 10.3931/e-rara-8842 .
^ Рафсон, Джозеф (1697). Анализ универсальных уравнений (на латыни) (2-е изд.). Лондон: Томас Брэдилл. дои : 10.3931/e-rara-13516 .
^ «Ускоренные и модифицированные методы Ньютона» . Архивировано из оригинала 24 мая 2019 года . Проверено 4 марта 2016 г.
^ Рябенький, Виктор С.; Цынков, Семен В. (2006), Теоретическое введение в численный анализ , CRC Press, с. 243, ISBN 9781584886075 .
^ Süli & Mayers 2003 , Упражнение 1.6.
^ Перейти обратно: ^а ^б ^с Островский, AM (1973). Решение уравнений в евклидовом и банаховом пространствах . Чистая и прикладная математика. Том. 9 (Третье издание оригинальной редакции 1960 г.). Нью-Йорк – Лондон: Academic Press . МР 0359306 . Збл 0304.65002 .
^ Ортега и Рейнбольдт, раздел 13.3.
^ Трауб, Дж. Ф. (1964). Итерационные методы решения уравнений . Серия Прентис-Холла по автоматическим вычислениям. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. MR 0169356 . Збл 0121.11204 .
^ Перейти обратно: ^а ^б Дж. Э. Деннис-младший и Роберт Б. Шнабель. Численные методы безусловной оптимизации и нелинейных уравнений. СИАМ
^ Энтони Ралстон и Филип Рабиновиц. Первый курс численного анализа, второе издание
^ Юрий Нестеров. Лекции по выпуклой оптимизации, второе издание. Оптимизация Springer и ее приложения, том 137.
^ Сюли и Майерс 2003 .
^ Перейти обратно: ^а ^б ^с Кеннет Л. Джадд. Численные методы в экономике. Массачусетский технологический институт Пресс
^ Перейти обратно: ^а ^б Берден, Бертон; Ярмарки, Дж. Дуглас; Рейнольдс, Альберт С. (июль 1981 г.). Численный анализ (2-е изд.). Бостон, Массачусетс, США: Приндл, Вебер и Шмидт. стр. 448–452. ISBN 0-87150-314-Х . OCLC 1036752194 .
^ Эванс, Гвинн А. (1995). Практический численный анализ . Чичестер: Джон Уайли и сыновья. стр. 30–33. ISBN 0471955353 . OCLC 1319419671 .
^ Демидович Борис Павлович; Марон, Исаак Абрамович (1981). Вычислительная математика (Третье изд.). Москва: Издательство МИР. стр. 460–478. ISBN 9780828507042 .
^ Киусалас, Яан (март 2013 г.). Численные методы в инженерии с использованием Python 3 (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. стр. 175–176. ISBN 978-1-107-03385-6 .
^ Этот пример аналогичен приведенному в ссылке, ^[15] страницы 451 и 452, но упрощены до двух уравнений вместо трех.
^ Хенрици, Питер (1974). Прикладной и вычислительный комплексный анализ . Том. 1. ISBN 9780471598923 .
^ Стрэнг, Гилберт (январь 1991 г.). «Хаотический поиск $я$ ». Математический журнал колледжа . 22 (1): 3–12. дои : 10.2307/2686733 . JSTOR 2686733 .
^ Макмаллен, Курт (1987). «Семейства рациональных карт и итеративные алгоритмы поиска корней» (PDF) . Анналы математики . Вторая серия. 125 (3): 467–493. дои : 10.2307/1971408 . JSTOR 1971408 .
^ Хаббард, Джон; Шлейхер, Дирк; Сазерленд, Скотт (октябрь 2001 г.). «Как найти все корни комплексных многочленов методом Ньютона» . Математические изобретения . 146 (1): 1–33. Бибкод : 2001InMat.146....1H . дои : 10.1007/s002220100149 . ISSN 0020-9910 . S2CID 12603806 .
^ Ямамото, Тетсуро (2001). «Историческое развитие анализа сходимости методов Ньютона и ньютоновских методов». В Брезинском, К.; Вуйтак, Л. (ред.). Численный анализ: историческое развитие в 20 веке . Северная Голландия. стр. 241–263. ISBN 0-444-50617-9 .
^ Гамильтон, Ричард С. (1982). «Теорема Нэша и Мозера об обратной функции» . Бюллетень Американского математического общества . Новая серия. 7 (1): 65–222. дои : 10.1090/s0273-0979-1982-15004-2 . МР 0656198 . Збл 0499.58003 .
^ Громов, Михаил (1986). Частные дифференциальные отношения . Результаты математики и ее пограничные области (3). Том 9. Берлин: Springer-Verlag . дои : 10.1007/978-3-662-02267-2 . ISBN 3-540-12177-3 . МР 0864505 .
^ Райкович, Предраг М.; Станкович, Миомир С.; Маринкович, Сладана Д. (2002). "Теоремы о среднем в $q$-исчислении" . Математический журнал . 54 (3–4): 171–178.
^ Пресс и др. 2007 год
^ Стер, Йозеф; Булирш, Роланд (1980). Введение в численный анализ . п. 279. OCLC 1244842246 .
^ Цзинь, Цзяньмин (1996) Чжан , Шаньцзе ; . 9780471119630 . ^{[ нужна страница ]}
^ Мурота, Кадзуо (1982). «Глобальная сходимость модифицированной итерации Ньютона для алгебраических уравнений». SIAM Journal по численному анализу . 19 (4): 793–799. Бибкод : 1982SJNA...19..793M . дои : 10.1137/0719055 .
^ Мур, RE (1979). Методы и приложения интервального анализа (Том 2). Сиам.
^ Хансен, Э. (1978). Интервальные формы метода Ньютона. Компьютерные технологии , 20(2), 153–163.
^ Бойд, Стивен ; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . дои : 10.1017/CBO9780511804441 . ISBN 0-521-83378-7 . МР 2061575 . Збл 1058.90049 .

Ссылки

Гил, А.; Сегура, Дж.; Темме, Нью-Мексико (2007). Численные методы для специальных функций . Общество промышленной и прикладной математики. ISBN 978-0-89871-634-4 .
Сюли, Эндре ; Майерс, Дэвид (2003). Введение в численный анализ . Издательство Кембриджского университета. ISBN 0-521-00794-1 .

Дальнейшее чтение

Кендалл Э. Аткинсон, Введение в численный анализ , (1989) John Wiley & Sons, Inc., ISBN 0-471-62489-6
Тьяллинг Дж. Ипма, Историческое развитие метода Ньютона-Рафсона, SIAM Review 37 (4), 531–551, 1995. дои : 10.1137/1037125 .
Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: Теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. дои : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-Х . МР 2265882 .
Дойфлхард П. «Методы Ньютона для решения нелинейных задач». Аффинная инвариантность и адаптивные алгоритмы. Серия Спрингера по вычислительной математике, Vol. 35. Шпрингер, Берлин, 2004. ISBN 3-540-21099-7 .
К. К. Келли, Решение нелинейных уравнений методом Ньютона , № 1 в «Основах алгоритмов», SIAM, 2003. ISBN 0-89871-546-6 .
Дж. М. Ортега, В. К. Рейнбольдт, Итерационное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики, СИАМ, 2000. ISBN 0-89871-461-3 .
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Глава 9. Нахождение корня и выборка по важности нелинейных наборов уравнений» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8 . . См. особенно разделы 9.4 , 9.6 и 9.7 .
Авриэль, Мордехай (1976). Нелинейное программирование: анализ и методы . Прентис Холл. стр. 216–221. ISBN 0-13-623603-0 .

Внешние ссылки

[1] «Глава 2. Сэки Такакадзу» . Японская математика в период Эдо . Национальная парламентская библиотека . Проверено 24 февраля 2019 г.

[2] Уоллис, Джон (1685). Трактат по алгебре, как исторической, так и практической . Оксфорд: Ричард Дэвис. doi : 10.3931/e-rara-8842 .

[3] Рафсон, Джозеф (1697). Анализ универсальных уравнений (на латыни) (2-е изд.). Лондон: Томас Брэдилл. дои : 10.3931/e-rara-13516 .

[4] «Ускоренные и модифицированные методы Ньютона» . Архивировано из оригинала 24 мая 2019 года . Проверено 4 марта 2016 г.

[5] Рябенький, Виктор С.; Цынков, Семен В. (2006), Теоретическое введение в численный анализ , CRC Press, с. 243, ISBN 9781584886075 .

[6] Süli & Mayers 2003 , Упражнение 1.6.

[ostrowski-7] Перейти обратно: ^а ^б ^с Островский, AM (1973). Решение уравнений в евклидовом и банаховом пространствах . Чистая и прикладная математика. Том. 9 (Третье издание оригинальной редакции 1960 г.). Нью-Йорк – Лондон: Academic Press . МР 0359306 . Збл 0304.65002 .

[8] Ортега и Рейнбольдт, раздел 13.3.

[9] Трауб, Дж. Ф. (1964). Итерационные методы решения уравнений . Серия Прентис-Холла по автоматическим вычислениям. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. MR 0169356 . Збл 0121.11204 .

[dennis-10] Перейти обратно: ^а ^б Дж. Э. Деннис-младший и Роберт Б. Шнабель. Численные методы безусловной оптимизации и нелинейных уравнений. СИАМ

[11] Энтони Ралстон и Филип Рабиновиц. Первый курс численного анализа, второе издание

[12] Юрий Нестеров. Лекции по выпуклой оптимизации, второе издание. Оптимизация Springer и ее приложения, том 137.

[FOOTNOTESüliMayers2003-13] Сюли и Майерс 2003 .

[judd-14] Перейти обратно: ^а ^б ^с Кеннет Л. Джадд. Численные методы в экономике. Массачусетский технологический институт Пресс

[:3-15] Перейти обратно: ^а ^б Берден, Бертон; Ярмарки, Дж. Дуглас; Рейнольдс, Альберт С. (июль 1981 г.). Численный анализ (2-е изд.). Бостон, Массачусетс, США: Приндл, Вебер и Шмидт. стр. 448–452. ISBN 0-87150-314-Х . OCLC 1036752194 .

[16] Эванс, Гвинн А. (1995). Практический численный анализ . Чичестер: Джон Уайли и сыновья. стр. 30–33. ISBN 0471955353 . OCLC 1319419671 .

[17] Демидович Борис Павлович; Марон, Исаак Абрамович (1981). Вычислительная математика (Третье изд.). Москва: Издательство МИР. стр. 460–478. ISBN 9780828507042 .

[18] Киусалас, Яан (март 2013 г.). Численные методы в инженерии с использованием Python 3 (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. стр. 175–176. ISBN 978-1-107-03385-6 .

[19] Этот пример аналогичен приведенному в ссылке, ^[15] страницы 451 и 452, но упрощены до двух уравнений вместо трех.

[20] Хенрици, Питер (1974). Прикладной и вычислительный комплексный анализ . Том. 1. ISBN 9780471598923 .

[21] Стрэнг, Гилберт (январь 1991 г.). «Хаотический поиск $я$ ». Математический журнал колледжа . 22 (1): 3–12. дои : 10.2307/2686733 . JSTOR 2686733 .

[22] Макмаллен, Курт (1987). «Семейства рациональных карт и итеративные алгоритмы поиска корней» (PDF) . Анналы математики . Вторая серия. 125 (3): 467–493. дои : 10.2307/1971408 . JSTOR 1971408 .

[23] Хаббард, Джон; Шлейхер, Дирк; Сазерленд, Скотт (октябрь 2001 г.). «Как найти все корни комплексных многочленов методом Ньютона» . Математические изобретения . 146 (1): 1–33. Бибкод : 2001InMat.146....1H . дои : 10.1007/s002220100149 . ISSN 0020-9910 . S2CID 12603806 .

[24] Ямамото, Тетсуро (2001). «Историческое развитие анализа сходимости методов Ньютона и ньютоновских методов». В Брезинском, К.; Вуйтак, Л. (ред.). Численный анализ: историческое развитие в 20 веке . Северная Голландия. стр. 241–263. ISBN 0-444-50617-9 .

[25] Гамильтон, Ричард С. (1982). «Теорема Нэша и Мозера об обратной функции» . Бюллетень Американского математического общества . Новая серия. 7 (1): 65–222. дои : 10.1090/s0273-0979-1982-15004-2 . МР 0656198 . Збл 0499.58003 .

[26] Громов, Михаил (1986). Частные дифференциальные отношения . Результаты математики и ее пограничные области (3). Том 9. Берлин: Springer-Verlag . дои : 10.1007/978-3-662-02267-2 . ISBN 3-540-12177-3 . МР 0864505 .

[27] Райкович, Предраг М.; Станкович, Миомир С.; Маринкович, Сладана Д. (2002). "Теоремы о среднем в $q$-исчислении" . Математический журнал . 54 (3–4): 171–178.

[28] Пресс и др. 2007 год

[29] Стер, Йозеф; Булирш, Роланд (1980). Введение в численный анализ . п. 279. OCLC 1244842246 .

[30] Цзинь, Цзяньмин (1996) Чжан , Шаньцзе ; . 9780471119630 . ^{[ нужна страница ]}

[31] Мурота, Кадзуо (1982). «Глобальная сходимость модифицированной итерации Ньютона для алгебраических уравнений». SIAM Journal по численному анализу . 19 (4): 793–799. Бибкод : 1982SJNA...19..793M . дои : 10.1137/0719055 .

[32] Мур, RE (1979). Методы и приложения интервального анализа (Том 2). Сиам.

[33] Хансен, Э. (1978). Интервальные формы метода Ньютона. Компьютерные технологии , 20(2), 153–163.

[34] Бойд, Стивен ; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . дои : 10.1017/CBO9780511804441 . ISBN 0-521-83378-7 . МР 2061575 . Збл 1058.90049 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

v т и сэр Исаак Ньютон
Publications	Fluxions (1671) De Motu (1684) Principia (1687) Opticks (1704) Queries (1704) Arithmetica (1707) De Analysi (1711)
Other writings	Quaestiones (1661–1665) "standing on the shoulders of giants" (1675) Notes on the Jewish Temple (c. 1680) "General Scholium" (1713; "hypotheses non fingo" ) Ancient Kingdoms Amended (1728) Corruptions of Scripture (1754)
Contributions	Calculus fluxion Impact depth Inertia Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Spectrum Structural coloration
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation post-Newtonian expansion parameterized gravitational constant Newton–Cartan theory Schrödinger–Newton equation Newton's laws of motion Kepler's laws Newtonian dynamics Newton's method in optimization Apollonius's problem truncated Newton method Gauss–Newton algorithm Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method generalized Gauss–Newton method Newton fractal Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number kissing number problem Newton's quotient Parallelogram of force Newton–Puiseux theorem Absolute space and time Luminiferous aether Newtonian series table
Personal life	Woolsthorpe Manor (birthplace) Cranbury Park (home) Early life Later life Apple tree Religious views Occult studies Scientific Revolution Copernican Revolution
Relations	Catherine Barton (niece) John Conduitt (nephew-in-law) Isaac Barrow (professor) William Clarke (mentor) Benjamin Pulleyn (tutor) Roger Cotes (student) William Whiston (student) John Keill (disciple) William Stukeley (friend) William Jones (friend) Abraham de Moivre (friend)
Depictions	Newton by Blake (monotype) Newton by Paolozzi (sculpture) Isaac Newton Gargoyle Astronomers Monument
Namesake	Newton (unit) Newton's cradle Isaac Newton Institute Isaac Newton Medal Isaac Newton Telescope Isaac Newton Group of Telescopes XMM-Newton Sir Isaac Newton Sixth Form Statal Institute of Higher Education Isaac Newton Newton International Fellowship
Categories	Isaac Newton

v т и Алгоритмы поиска корня
Bracketing (no derivative)	Bisection method Regula falsi ITP method
Householder	Newton's method Halley's method
Quasi-Newton	Broyden's method Secant method Steffensen's method
Hybrid methods	Brent's method Ridders' method
Polynomial methods	Aberth method Bairstow's method Durand–Kerner method Graeffe's method Jenkins–Traub algorithm Lehmer–Schur algorithm Laguerre's method Splitting circle method
Other methods	Fixed-point iteration Inverse quadratic interpolation Muller's method Sidi's generalized secant method