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

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

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

является лучшим приближением корня, чем $x 0$ . Геометрически $(x 1, 0)$ — это точка пересечения с х касательной графика $f$ в $($ $x$ $0$ $,$ $f$ ( $x$ $0$ $))$ : то есть улучшенное предположение x $1$ $является$ $уникальным$ корнем линейного аппроксимация 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 году ). Однако его метод существенно отличается от современного метода, приведенного выше. Ньютон применил этот метод только к полиномам, начиная с первоначальной оценки корня и извлекая последовательность исправлений ошибок. Он использовал каждую поправку, чтобы переписать полином с точки зрения оставшейся ошибки, а затем решил новую поправку, пренебрегая членами более высокой степени. Он не связал метод явно с производными и не представил общей формулы. Ньютон применил этот метод как к численным, так и к алгебраическим задачам, получив в последнем случае ряд Тейлора .

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

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

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

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

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

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

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

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

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

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

Перерегулирование

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

f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}

для которого корень будет пропущен и последовательность $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,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2$ , корень все равно будет пропущен, но последовательность будет колебаться между двумя значениями. Для $1 / 2 < a < 1$ , корень все равно будет промахиваться, но последовательность будет сходиться, а при $a \geq 1$ корень вообще не будет промахиваться.

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

Стационарная точка

Если встречается стационарная точка функции, производная равна нулю, и метод завершится из-за деления на ноль .

Плохая первоначальная оценка

Большая ошибка в первоначальной оценке может способствовать несходимости алгоритма. Чтобы преодолеть эту проблему, часто можно линеаризовать оптимизируемую функцию с помощью исчисления, журналов, дифференциалов или даже с помощью эволюционных алгоритмов, таких как стохастическое туннелирование . Хорошие первоначальные оценки близки к окончательной глобально оптимальной оценке параметров. В нелинейной регрессии сумма квадратов ошибок (SSE) «близка» к параболе только в области окончательных оценок параметров. Найденные здесь первоначальные оценки позволят методу Ньютона–Рафсона быстро сходиться. Только здесь матрица Гессе СУС положительна, а первая производная СУС близка к нулю.

Смягчение неконвергенции

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

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

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

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) = Икс / м$ а метод Ньютона находит корень за одну итерацию с

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 r (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$ будет следующим:

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

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$ определяется формулой

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

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

То есть,

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

Уравнение ( 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} \,.

Бассейны притяжения

Непересекающиеся подмножества бассейнов притяжения — областей действительной числовой линии, внутри каждой из которых итерация из любой точки приводит к одному конкретному корню — могут быть бесконечными по числу и сколь угодно малыми. Например, ^[7] для функции $f (x) = x 3 - 2 x 2 - 11 x + 12 = (x - 4)(x - 1)(x + 3)$ следующие начальные условия находятся в последовательных бассейнах привлекательности:

Анализ отказов

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

Плохие стартовые точки

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

Точка итерации стационарна

Рассмотрим функцию:

f(x)=1-x^{2}.

Он имеет максимум при $x = 0$ и решения $f (x) = 0$ при $x = \pm1$ . Если мы начнем итерацию от стационарной точки $x 0 = 0$ (где производная равна нулю), $x 1$ будет неопределенным, поскольку касательная в точке $(0, 1)$ параллельна оси $x$ :

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

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

Начальная точка входит в цикл

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

Для некоторых функций некоторые начальные точки могут входить в бесконечный цикл, препятствуя сходимости. Позволять

f(x)=x^{3}-2x+2\!

и возьмем 0 в качестве отправной точки. Первая итерация дает 1, а вторая итерация возвращает 0, поэтому последовательность будет чередоваться между ними, не сходясь к корню. Фактически, этот 2-цикл стабилен: существуют окрестности вокруг 0 и вокруг 1, из которых все точки асимптотически переходят к 2-циклу (и, следовательно, не к корню функции). В общем, поведение последовательности может быть очень сложным (см. Фрактал Ньютона ). Действительное решение этого уравнения есть−1,769 292 35 ...

Производные проблемы

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

Производная не существует в корне

Простой пример функции, в которой метод Ньютона расходится, — это попытка найти кубический корень из нуля. Кубический корень непрерывен и бесконечно дифференцируем, за исключением $x = 0$ , где его производная не определена:

f(x)={\sqrt[{3}]{x}}.

Для любой точки итерации $x n$ следующей точкой итерации будет:

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

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

Фактически, итерации расходятся до бесконечности для каждого $f (x) = | х | α$ , где $0 < α < 1 / 2$ . В предельном случае $α = 1 / 2$ (квадратный корень), итерации будут бесконечно чередоваться между точками $x 0$ и $- x 0$ , поэтому и в этом случае они не сходятся.

Разрывная производная

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

f(x)={\begin{cases}0&{\text{if }}x=0,\\x+x^{2}\sin {\frac {2}{x}}&{\ text{if }}x\neq 0.\end{cases}}

Его производная:

f'(x)={\begin{cases}1&{\text{if }}x=0,\\1+2x\sin {\frac {2}{x}}-2\cos {\ frac {2}{x}}&{\text{if }}x\neq 0.\end{cases}}

В любой окрестности корня эта производная продолжает менять знак, когда $x$ приближается к 0 справа (или слева), в то время как $f (x) \geq x - x 2 > 0$ для $0 < x < 1$ .

Так $е (х) / ж' (Икс)$ неограничен вблизи корня, и метод Ньютона будет расходиться почти всюду в любой его окрестности, даже если:

функция дифференцируема (и, следовательно, непрерывна) всюду;
производная в корне не равна нулю;
$f$ бесконечно дифференцируема, за исключением корня; и
производная ограничена в окрестности корня (в отличие от $е (х) / ж' (Икс)$ ).

Неквадратичная сходимость

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

Нулевая производная

Если первая производная в корне равна нулю, то сходимость не будет квадратичной. Позволять

f(x)=x^{2}\!

тогда $f' (x) = 2 x$ и, следовательно,

x- {\frac {f(x)}{f'(x)}}={\frac {x}{2}}.

Таким образом, сходимость не является квадратичной, хотя функция всюду бесконечно дифференцируема.

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

f(x)=x^{2}(x-1000)+1.

Тогда первые несколько итераций, начиная с $x 0 = 1$ , будут

х 0

= 1

х 1

=0,500 250 376 ...

х 2

=0,251 062 828 ...

х 3

=0,127 507 934 ...

х 4

=0,067 671 976 ...

х 5

=0,041 224 176 ..

х 6

=0,032 741 218 ...

х 7

=0,031 642 362 ...

требуется шесть итераций, чтобы достичь точки, в которой сходимость становится квадратичной.

Нет второй производной

Если в корне нет второй производной, то сходимость может не быть квадратичной. Позволять

f(x)=x+x^{\frac {4}{3}}.

Затем

f'(x)=1+{\tfrac {4}{3}}x^{\frac {1}{3}}.

f''(x)={\tfrac {4}{9}}x^{- {\frac {2}{3}}}

кроме случаев, когда $x = 0$ , где он не определен. Учитывая $x n$ ,

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

который имеет примерно4/3раз больше бит точности, чем имеет $x n$ . Это меньше, чем в 2 раза больше, чем потребовалось бы для квадратичной сходимости. Итак, сходимость метода Ньютона (в данном случае) не является квадратичной, хотя: функция всюду непрерывно дифференцируема; производная не равна нулю в корне; и $f$ бесконечно дифференцируема, за исключением желаемого корня.

Обобщения

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

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

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

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

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

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

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

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

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

\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 - Икс п$ .

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

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

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

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

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

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

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

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

Метод Ньютона – Фурье

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

Предположим, что $f (x)$ дважды непрерывно дифференцируемо на $[a, b]$ и что $f$ содержит корень в этом интервале. Предположим, что $f' (x), f ″ (x) \neq 0$ на этом интервале (это имеет место, например, если $f (a) < 0$ , $f (b) > 0$ и $f' (x) > 0$ и $f ″ (x) > 0$ на этом интервале). Это гарантирует, что на этом интервале существует уникальный корень; назовите это $α$ . Если он вогнут вниз, а не вогнут вверх, замените $f (x)$ на $- f (x),$ поскольку они имеют одинаковые корни.

Пусть $x0 = b —$ правый конец интервала, а $z0 = a —$ левый конец интервала. Учитывая $x n$ , определите

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

это просто метод Ньютона, как и раньше. Затем определите

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

где знаменатель равен $f' (x n)$ , а не $f' (z n)$ . Итерации $x n$ будут строго убывать к корню, а итерации $z n$ будут строго возрастать к корню. Также,

\lim _{n\to \infty }{\frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={\frac {f''(\alpha )}{2f'(\alpha )}}

так что расстояние между $x n$ и $z n$ уменьшается квадратично.

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим $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)$ , поэтому, в частности, f $имеет$ не более одного корня в $X.$ Затем мы определяем интервальный оператор Ньютона следующим образом:

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)$ . Производная равна нулю в минимуме или максимуме, поэтому локальные минимумы и максимумы можно найти, применив к производной метод Ньютона. Итерация становится:

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}).

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

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

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

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

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

Получение нулей специальных функций

Метод Ньютона применяется к отношению функций Бесселя, чтобы получить его корень. ^[20]

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

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

Примеры

Квадратный корень

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

Например, для нахождения квадратного корня из 612 с начальным предположением $x 0 = 10$ последовательность, заданная методом Ньютона, следующая:

{\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}

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

Перестановка формулы следующим образом дает вавилонский метод нахождения квадратных корней :

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{n}}}{\Bigr )}

т.е. среднее арифметическое предположения, $x n$ и $а / х н$ .

Решение cos( x ) = x 3

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

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

{\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, иллюстрируя квадратичную сходимость.

Код

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

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

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

защита  f ( х ): вернуть  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: максимальное количество итераций для вычисления. """ для  i  в  диапазоне ( max_iterations ): у  =  ж ( х0 ) yprime  =  f_prime ( x0 ) if  abs ( yprime )  <  epsilon :  # Откажитесь, если знаменатель слишком мал перерыв x1  =  x0  -  y  /  yprime  # Выполняем вычисления Ньютона if  abs ( x1  -  x0 )  <=  допуск :  # Остановитесь, когда результат окажется в пределах желаемого допуска return  x1  # x1 — решение в пределах допуска и максимального количества итераций x0  =  x1  # Обновите x0, чтобы начать процесс заново return  None  # Метод Ньютона не сходился

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

Примечания

^ «Глава 2. Секи Такакадзу». Японская математика в период Эдо . Национальная парламентская библиотека . Проверено 24 февраля 2019 г.
^ Уоллис, Джон (1685). Трактат по алгебре, как исторической, так и практической. Оксфорд: Ричард Дэвис. doi : 10.3931/e-rara-8842.
^ Рафсон, Джозеф (1697). Анализ Æequationum Universalis (на латыни) (2-е изд.). Лондон: Томас Брэдилл. дои : 10.3931/e-rara-13516.
^ «Ускоренные и модифицированные методы Ньютона». Архивировано из оригинала 24 мая 2019 года . Проверено 4 марта 2016 г.
^ Рябенький, Виктор С.; Цынков, Семен В. (2006), Теоретическое введение в численный анализ, CRC Press, с. 243, ISBN 9781584886075.
^ Сюли и Майерс 2003, Упражнение 1.6.
^ Денс, Томас (ноябрь 1997 г.). «Кубики, хаос и метод Ньютона». Математический вестник . 81 (492): 403–408. дои : 10.2307/3619617. JSTOR 3619617. S2CID 125196796.
^ Хенрици, Питер (1974). «Прикладной и вычислительный комплексный анализ». 1 . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
^ Стрэнг, Гилберт (январь 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.
^ Райкович, Станкович и Маринкович 2002 ^[^{неполная короткая цитата}^]
^ Пресс и др. 1992 ^[^{неполная короткая цитата}^]
^ Stoer & Bulirsch 1980 ^[^{неполная короткая цитата}^]
^ Чжан и Цзинь, 1996 ^[^{неполная короткая цитата}^]
^ Мурота, Кадзуо (1982). «Глобальная сходимость модифицированной итерации Ньютона для алгебраических уравнений». SIAM Journal по численному анализу . 19 (4): 793–799. Бибкод : 1982SJNA...19..793M. дои : 10.1137/0719055.
^ Мур, RE (1979). Методы и приложения интервального анализа (Том 2). Сиам.
^ Хансен, Э. (1978). Интервальные формы метода Ньютона. Компьютерные технологии , 20(2), 153–163.
^ Гил, Сегура и Темме (2007) ^{[ неполная короткая цитата ]}
^ Кахан (1968) ^{[ неполная короткая цитата ]}
^ Кравчик (1969) ^[^{неполная короткая цитата}^]^[^{неполная короткая цитата}^]

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

Кендалл Э. Аткинсон, Введение в численный анализ , (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
Тьяллинг Дж. Ипма, Историческое развитие метода Ньютона-Рафсона, SIAM Review 37 (4), 531–551, 1995. doi : 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 .
Дж. М. Ортега, В. К. Рейнбольдт, Итерационное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики, SIAM, 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.

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

Викискладе есть медиафайлы по теме метода Ньютона .

Список слов, относящихся к методу Ньютона, см. в статье «Метод Ньютона» в Wikibooks .

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