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

Алгоритм нахождения нулей функций

Иллюстрация метода Ньютона.

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

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

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

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

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

Описание

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

x _{n +1} является лучшим приближением, чем x _n для корня x функции f (синяя кривая)

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

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

Решение для x _{n +1} дает

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

Итерация обычно улучшает аппроксимацию

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если кратность корня m конечна, то g ( x ) = ⁠ж ( х )/ф ′ ( х )⁠ будет иметь корень в том же месте с кратностью 1. Применение метода Ньютона для нахождения корня g ( x ) восстанавливает квадратичную сходимость во многих случаях, хотя обычно это включает вторую производную f ( x ) . В особенно простом случае, если f ( x ) = x ^m , то g ( x ) = ⁠х/м⁠ и метод Ньютона находит корень за одну итерацию с

$${\displaystyle 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 ₀ в этой окрестности последовательность ( x _n ) будет сходиться к α . ^[5]

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

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

где

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

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

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

На практике эти результаты локальны, и окрестность сходимости заранее неизвестна. Но есть также некоторые результаты о глобальной сходимости: например, если задана правая окрестность U ₊ точки α , если f дважды дифференцируема в U ₊ и если f ′ ≠ 0 , f · f ″ > 0 в U ₊ , то для каждого x ₀ в U ₊ последовательность x _k монотонно убывает к α .

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

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

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

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

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

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

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

Помня, что x _{n + 1} определяется как

можно обнаружить, что

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

То есть,

Взяв абсолютное значение обеих сторон, получаем

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

1. f ′ ( x ) ≠ 0 ; для всех x ∈ I , где I — интервал [ α − | ε ₀ |, α + | ε ₀ |] ;
2. f ″ ( x ) непрерывна для всех x ∈ I ;
3. М | ε ₀ | < 1

где M определяется как

$${\displaystyle 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).\,}$$

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

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

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

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

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

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

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

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

${\displaystyle \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 ² = a, эквивалентна нахождению корня функции f ( x ) = x ² − a . Итерация Ньютона, определяемая этой функцией, задается как

${\displaystyle 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 и a ⁄ x _n . Выполняя эту итерацию, можно вычислить квадратный корень с любой желаемой точностью, используя только основные _{арифметические} операции .

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

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

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

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

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

Рассмотрим задачу нахождения положительного числа x с cos x = x ³ . Мы можем перефразировать это как нахождение нуля f ( x ) = cos( x ) − x ³ . Мы имеем f ′ ( x ) = −sin( x ) − 3 x ² . Поскольку cos( x ) ≤ 1 для всех x и x ³ > 1 для x > 1 , мы знаем, что наше решение лежит между 0 и 1.

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

$${\displaystyle {\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 ₆ верно до 12 знаков после запятой. Мы видим, что количество правильных цифр после запятой увеличивается с 2 (для x ₃ ) до 5 и 10, что иллюстрирует квадратичную сходимость.

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

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

${\displaystyle 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 ′′ там не существует, так что квадратичная сходимость не может быть гарантирована. Фактически итерация Ньютона задается как

${\displaystyle 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 ² . Квадратичная сходимость в итерации, показанная справа, иллюстрируется порядками величины в расстоянии от итерации до истинного корня (0,1,2,3,5,10,20,39,...), которые приблизительно удваиваются от строки к строке. В то время как сходимость слева сверхлинейна, порядок величины умножается только примерно на 4/3 от строки к строке (0,1,2,4,5,7,10,13,...).

Скорость сходимости отличается от количества итераций, необходимых для достижения заданной точности. Например, функция f ( x ) = x ²⁰ − 1 имеет корень в 1. Поскольку f ′(1) ≠ 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 ² ) ^−1/2 имеет корень в 0. Итерация Ньютона задается формулой

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

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

В случаях, когда рассматриваемая функция имеет несколько корней, может быть сложно контролировать с помощью выбора инициализации, какой корень (если таковой имеется) идентифицируется методом Ньютона. Например, функция f ( x ) = x ( x ² − 1)( x − 3)e ^{−( x − 1) 2 /2} имеет корни в точках −1, 0, 1 и 3. ^[13] При инициализации в точке −1,488 итерация Ньютона сходится к 0; при инициализации в точке −1,487 она расходится к ∞ ; при инициализации в точке −1,486 она сходится к −1; при инициализации в точке −1,485 она расходится к −∞ ; при инициализации в точке −1,4843 она сходится к 3; если инициализировано при −1,484, оно сходится к 1. Этот вид тонкой зависимости от инициализации не является чем-то необычным; он часто изучается в комплексной плоскости в форме фрактала Ньютона .

Расхождение даже при инициализации близкой к корню

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

${\displaystyle 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 e ^{− x 2} также имеет корень в 0. Итерация Ньютона задается как

${\displaystyle 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:

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

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

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

Легко найти ситуации, для которых метод Ньютона бесконечно колеблется между двумя различными значениями. Например, для того, чтобы метод Ньютона, примененный к функции f , колебался между 0 и 1, необходимо только, чтобы касательная к f в точке 0 пересекала ось x в точке 1, а касательная к f в точке 1 пересекала ось x в точке 0. ^[14] Это имеет место, например, если f ( x ) = x ³ − 2 x + 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 ² − 1 , то итерация Ньютона определяется как

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

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

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

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

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

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

Многомерные формулировки

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

кпеременные,кфункции

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

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

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

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

для неизвестного x _{n + 1} − x _n . ^[18]

кпеременные,муравнения, см > к

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

Пример

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

и

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

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

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

Итерации

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

Комплексные функции

Области притяжения для x ⁵ − 1 = 0 ; более темный цвет означает большее количество итераций для сходимости.

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

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

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

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

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

$${\displaystyle 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 -адике является кольцом), сходимость в лемме Гензеля может быть гарантирована при гораздо более простых гипотезах, чем в классическом методе Ньютона на действительной прямой.

д-аналоговый

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

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

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

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

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

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

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

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

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

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

Рассмотрим f → C ¹ ( X ) , где X — действительный интервал, и предположим, что у нас есть расширение интервала F ′ функции f ′ , то есть F ′ принимает в качестве входных данных интервал Y ⊆ X и выводит интервал F ′ ( Y ) такой, что:

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

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

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

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

$${\displaystyle {\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* — корень f в X .

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

Приложения

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

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

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

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

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

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

$${\displaystyle 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 ₀ = 1 , а функция будет f ( x ) = x ² − 2, так что f ′ ( x ) = 2 x .

Каждая новая итерация метода Ньютона будет обозначаться как x1. Мы будем проверять во время вычислений, не станет ли знаменатель ( yprime) слишком малым (меньше epsilon), что имело бы место, если бы f ′ ( x _n ) ≈ 0 , поскольку в противном случае может быть внесено большое количество ошибок.

определение  f ( x ): вернуть  x ** 2  -  2  # f(x) = x^2 - 2определение  f_prime ( x ):вернуть  2 * x  # f'(x) = 2xdef  newtons_method ( x0 ,  f ,  f_prime ,  допуск ,  эпсилон ,  max_iterations ): """Метод Ньютона Аргументы: x0: Первоначальная догадка f: Функция, корень которой мы пытаемся найти f_prime: Производная функции допуск: Остановитесь, когда итерации изменятся меньше, чем на это значение эпсилон: Не делить на число меньше этого max_iterations: максимальное количество итераций для вычисления """ для  _  в  диапазоне ( max_iterations ): у  =  f ( х0 ) yprime  =  f_prime ( x0 ) если  abs ( yprime )  <  epsilon :  # Отказаться, если знаменатель слишком мал перерыв x1  =  x0  -  y  /  yprime  # Выполнить вычисления Ньютона если  abs ( x1  -  x0 )  <=  допуск :  # Остановиться, когда результат окажется в пределах желаемого допуска return  x1  # x1 — это решение в пределах допуска и максимального числа итераций x0  =  x1  # Обновите x0, чтобы начать процесс заново return  None  # Метод Ньютона не сошёлся

Смотрите также

• Дельта-квадратный процесс Эйткена
• Метод деления пополам
• метод Эйлера
• Быстрое обратное вычисление квадратного корня
• Оценка Фишера
• Градиентный спуск
• Целый квадратный корень
• Теорема Канторовича
• Метод Лагерра
• Методы вычисления квадратных корней
• Метод Ньютона в оптимизации
• Экстраполяция Ричардсона
• Алгоритм поиска корня
• Метод секущей
• Метод Стеффенсена
• Метод субградиента

Примечания

1. "Глава 2. Сэки Такакадзу". Японская математика в период Эдо . Национальная парламентская библиотека . Получено 24 февраля 2019 г.
2. Уоллис, Джон (1685). Трактат алгебры, как исторический, так и практический. Оксфорд: Ричард Дэвис. doi :10.3931/e-rara-8842.
3. Рафсон, Джозеф (1697). Анализ Æequationum Universalis (на латыни) (2-е изд.). Лондон: Томас Брэдилл. дои : 10.3931/e-rara-13516.
4. "Ускоренные и модифицированные методы Ньютона". Архивировано из оригинала 24 мая 2019 года . Получено 4 марта 2016 года .
5. Рябенький, Виктор С.; Цынков, Семен В. (2006), Теоретическое введение в численный анализ, CRC Press, стр. 243, ISBN 9781584886075.
6. Сюли и Майерс 2003, Упражнение 1.6.
7. Островский, AM (1973). Решение уравнений в евклидовых и банаховых пространствах . Чистая и прикладная математика. Т. 9 (Третье издание 1960 г., оригинальное издание). Нью-Йорк–Лондон: Academic Press . MR  0359306. Zbl  0304.65002.
8. Ортега и Рейнбольдт, раздел 13.3.
9. Трауб, Дж. Ф. (1964). Итерационные методы решения уравнений . Ряды Прентиса-Холла в автоматических вычислениях. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. MR  0169356. Zbl  0121.11204.
10. JE Dennis, Jr. и Robert B. Schnabel. Численные методы для безусловной оптимизации и нелинейных уравнений. SIAM
11. Энтони Ралстон и Филип Рабинович. Первый курс численного анализа, второе издание
12. Юрий Нестеров. Лекции по выпуклой оптимизации, второе издание. Springer Optimization and its Applications, том 137.
13. Сюли и Майерс 2003.
14. Кеннет Л. Джадд. Численные методы в экономике. MIT Press
15. Burden, Burton; Fairs, J. Douglas; Reunolds, Albert C (июль 1981 г.). Numerical Analysis (2-е изд.). Бостон, Массачусетс, США: Prindle, Weber & Schmidt. стр. 448–452. ISBN 0-87150-314-X. OCLC  1036752194.
16. Эванс, Гвинн А. (1995). Практический численный анализ . Чичестер: John Wiley & Sons. стр. 30–33. ISBN 0471955353. OCLC  1319419671.
17. Демидович, Борис Павлович; Марон, Исаак Абрамович (1981). Вычислительная математика (Третье изд.). Москва: Издательство МИР. стр. 460–478. ISBN 9780828507042.
18. Киусалаас, Яан (март 2013 г.). Численные методы в инженерии с Python 3 (3-е изд.). Нью-Йорк: Cambridge University Press. С. 175–176. ISBN 978-1-107-03385-6.
19. Этот пример похож на пример в ссылке ^[15] на страницах 451 и 452, но упрощен до двух уравнений вместо трех.
20. Хенричи, Питер (1974). Прикладной и вычислительный комплексный анализ . Т. 1. Wiley. ISBN 9780471598923.
21. Стрэнг, Гилберт (январь 1991). «Хаотический поиск i ». The College Mathematics Journal . 22 (1): 3–12. doi :10.2307/2686733. JSTOR  2686733.
22. МакМаллен, Курт (1987). «Семейства рациональных отображений и итеративные алгоритмы поиска корней» (PDF) . Annals of Mathematics . Вторая серия. 125 (3): 467–493. doi :10.2307/1971408. JSTOR  1971408.
23. Хаббард, Джон; Шлейхер, Дирк; Сазерленд, Скотт (октябрь 2001 г.). «Как найти все корни комплексных многочленов методом Ньютона». Inventiones Mathematicae . 146 (1): 1–33. Bibcode : 2001InMat.146....1H. doi : 10.1007/s002220100149. ISSN  0020-9910. S2CID  12603806.
24. Ямамото, Тетсуро (2001). «Исторические разработки в анализе сходимости для методов Ньютона и подобных Ньютону». В Brezinski, C.; Wuytack, L. (ред.). Численный анализ: исторические разработки в 20 веке . North-Holland. стр. 241–263. ISBN 0-444-50617-9.
25. Гамильтон, Ричард С. (1982). «Теорема об обратной функции Нэша и Мозера». Бюллетень Американского математического общества . Новая серия. 7 (1): 65–222. doi : 10.1090/s0273-0979-1982-15004-2 . MR  0656198. Zbl  0499.58003.
26. Громов, Михаил (1986). Частные дифференциальные отношения . Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Том. 9. Берлин: Шпрингер-Верлаг . дои : 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). Вычисление специальных функций . Уайли. ISBN 9780471119630.^{[ нужна страница ]}
31. Мурота, Казуо (1982). «Глобальная сходимость модифицированной итерации Ньютона для алгебраических уравнений». Журнал SIAM по численному анализу . 19 (4): 793–799. Bibcode : 1982SJNA...19..793M. doi : 10.1137/0719055.
32. Мур, Р. Э. (1979). Методы и приложения интервального анализа (т. 2). Siam.
33. Хансен, Э. (1978). Интервальные формы метода Ньютона. Вычислительная техника , 20(2), 153–163.
34. Boyd, Stephen ; Vandenberghe, Lieven (2004). Выпуклая оптимизация . Кембридж: Cambridge University Press . doi :10.1017/CBO9780511804441. ISBN 0-521-83378-7. MR  2061575. Zbl  1058.90049.

Ссылки

• Gil, A.; Segura, J.; Temme, NM (2007). Численные методы для специальных функций. Общество промышленной и прикладной математики. ISBN 978-0-89871-634-4.
• Süli, Endre ; Mayers, David (2003). Введение в численный анализ . Cambridge University Press. ISBN 0-521-00794-1.

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

• Кендалл Э. Аткинсон, Введение в численный анализ , (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6 
• Тьяллинг Дж. Ипма, Историческое развитие метода Ньютона–Рафсона, SIAM Review 37 (4), 531–551, 1995. doi :10.1137/1037125.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе пересмотренное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. МР  2265882.
• P. Deuflhard, Newton Methods for Nonlinear Problems. Аффинная инвариантность и адаптивные алгоритмы. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7 . 
• CT Kelley, Решение нелинейных уравнений методом Ньютона , № 1 в «Основах алгоритмов», SIAM, 2003. ISBN 0-89871-546-6 . 
• JM Ortega, WC Rheinboldt, Итеративное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики, SIAM, 2000. ISBN 0-89871-461-3 . 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Глава 9. Поиск корней и выборка по важности нелинейных наборов уравнений". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.. См. особенно разделы 9.4, 9.6 и 9.7.
• Avriel, Mordecai (1976). Нелинейное программирование: анализ и методы . Prentice Hall. стр. 216–221. ISBN 0-13-623603-0.

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

• «Метод Ньютона», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Метод Ньютона». MathWorld .
• Метод Ньютона, Citizendium.
• Мэтьюз, Дж., Ускоренные и модифицированные методы Ньютона, Заметки к курсу.
• У, X., Корни уравнений, Курсовые заметки.