Метод Ньютона - Newtons method

Эта статья о методе поиска корней Ньютона. О методе Ньютона для поиска минимумов см. Метод Ньютона в оптимизации.

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

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

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

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

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

Описание

Функция ж отображается синим цветом, а касательная - красным. Мы видим, что Икс_{п + 1} это лучшее приближение, чем Икс_п для корня Икс функции ж.

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

Более формально предположим ж : (а, б) → ℝ это дифференцируемый функция, определенная на интервал (а, б) со значениями в действительные числа  ℝ, и у нас есть некоторое текущее приближение Икс_п. Затем мы можем вывести формулу для лучшего приближения: Икс_{п + 1} обратившись к диаграмме справа. Уравнение касательная линия к кривой у = ж (Икс) в Икс = Икс_п является

${\displaystyle y=f'(x_{n})\,(x-x_{n})+f(x_{n}),}$

куда f ′ обозначает производная. В Икс-перехват этой строки (значение Икс что делает у = 0) берется в качестве следующего приближения, Икс_{п + 1}, к корню, так что уравнение касательной выполняется при ${\displaystyle (x,y)=(x_{n+1},0)}$:

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

Решение для Икс_{п + 1} дает

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Перескок

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

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

для которого корень будет перекрыт, и последовательность Икс будут расходиться. За а = 1/2, корень по-прежнему будет превышен, но последовательность будет колебаться между двумя значениями. За 1/2 < а < 1, корень по-прежнему будет перекрыт, но последовательность будет сходиться, а для а ≥ 1 корень вообще не будет перекрыт.

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

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

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

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

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

Смягчение несогласованности

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

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

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

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

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

Анализ

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

Если ж непрерывно дифференцируема и ее производная отлична от нуля в точкеα, то существует район из α так что для всех начальных значений Икс₀ в этом районе последовательность {Икс_п} буду сходиться к α.^[5]

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

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

куда

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

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

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

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

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

В соответствии с Теорема Тейлора, любая функция ж (Икс) который имеет непрерывную вторую производную, может быть представлен разложением вокруг точки, которая близка к корню ж (Икс). Предположим, что этот корень α. Тогда расширение ж (α) о Икс_п является:

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

(1)

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

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

куда ξ_п находится между Икс_п и α.

С α это корень, (1) становится:

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

(2)

Уравнение деления (2) к f ′(Икс_п) и перестановка дает

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

Вспоминая это Икс_{п + 1} определяется

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

(4)

можно найти, что

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

То есть,

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

(5)

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

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

(6)

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

1. f ′(Икс) ≠ 0; для всех Икс ∈ я, куда я это интервал [α − р, α + р] для некоторых р ≥ |α − Икс₀|;
2. f ″(Икс) непрерывно, для всех Икс ∈ я;
3. Икс₀ является достаточно близко к корню α.

Период, термин достаточно close в данном контексте означает следующее:

1. Приближение Тейлора достаточно точное, так что мы можем игнорировать члены более высокого порядка;
2. ${\displaystyle {\frac {1}{2}}\left|{\frac {f''(x_{n})}{f'(x_{n})}}\right|<C\left|{\frac {f''(\alpha )}{f'(\alpha )}}\right|,}$ для некоторых C < ∞;
3. ${\displaystyle C\left|{\frac {f''(\alpha )}{f'(\alpha )}}\right|\varepsilon _{n}<1,}$ за п ∈ ℤ, п ≥ 0 и C удовлетворяющее условию b.

Ну наконец то, (6) можно выразить следующим образом:

${\displaystyle \left|{\varepsilon _{n+1}}\right|\leq M{\varepsilon _{n}}^{2}\,}$

куда M это супремум переменного коэффициента ε_п² на интервале я определено в условии 1, то есть:

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

Начальная точка Икс₀ должен быть выбран таким образом, чтобы выполнялись условия с 1 по 3, где третье условие требует, чтобы M |ε₀| < 1.

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

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

2.35287527	сходится к	4;
2.35284172	сходится к	−3;
2.35283735	сходится к	4;
2.352836327	сходится к	−3;
2.352836323	сходится к	1.

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

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

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

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

Точка итерации неподвижна

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

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

Максимум на Икс = 0 и решения ж (Икс) = 0 в Икс = ±1. Если мы начнем итерацию с стационарный пункт Икс₀ = 0 (где производная равна нулю), Икс₁ будет неопределенным, поскольку касательная в точке (0,1) параллельна Икс-ось:

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

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

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

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

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

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

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

Производные выпуски

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

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

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

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

Для любой точки итерации Икс_п, следующей точкой итерации будет:

${\displaystyle 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 {1}{3}}-1}}}=x_{n}-3x_{n}=-2x_{n}.}$

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

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

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

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

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

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

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

В любой окрестности корня эта производная меняет знак при Икс приближается к 0 справа (или слева), а ж (Икс) ≥ Икс − Икс² > 0 за 0 < Икс < 1.

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

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

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

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

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

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

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

тогда f ′(Икс) = 2Икс и следовательно

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

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

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

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

Затем первые несколько итераций, начиная с Икс₀ = 1 находятся

Икс₀ = 1

Икс₁ = 0.500250376…

Икс₂ = 0.251062828…

Икс₃ = 0.127507934…

Икс₄ = 0.067671976…

Икс₅ = 0.041224176…

Икс₆ = 0.032741218…

Икс₇ = 0.031642362…

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

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

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

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

потом

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

И

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

кроме тех случаев, когда Икс = 0 где он не определен. Данный Икс_п,

${\displaystyle 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 раз больше точности, чем Икс_п имеет. Это меньше, чем в 2 раза больше, чем требуется для квадратичной сходимости. Таким образом, сходимость метода Ньютона (в данном случае) неквадратична, хотя: функция непрерывно дифференцируема всюду; производная не равна нулю в корне; и ж бесконечно дифференцируема, кроме желаемого корня.

Обобщения

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

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

Основная статья: Фрактал Ньютона

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

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

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

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

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

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

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

Можно также использовать метод Ньютона для решения систем k (нелинейные) уравнения, сводящиеся к нахождению нулей непрерывно дифференцируемых функций F : ℝ^k → ℝ^k. В приведенной выше формулировке нужно умножить слева на обратную величину k × k Матрица якобиана J_F(Икс_п) вместо деления на f ′(Икс_п):

${\displaystyle x_{n+1}=x_{n}-J_{F}(x_{n})^{-1}F(x_{n})}$

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

${\displaystyle J_{F}(x_{n})(x_{n+1}-x_{n})=-F(x_{n})}$

для неизвестного Икс_{п + 1} − Икс_п.

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

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

Нелинейные уравнения в банаховом пространстве

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

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

куда F ′(Икс_п) это Производная Фреше вычислено в Икс_п. Требуется, чтобы производная Фреше была ограниченно обратимой на каждом Икс_п для применимости метода. Условие существования и сходимости к корню задается Теорема Ньютона – Канторовича..^[11]

Нелинейные уравнения над п-адические числа

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

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

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

Предположить, что ж (Икс) дважды непрерывно дифференцируема на [а, б] и это ж содержит корень в этом интервале. Предположить, что f ′(Икс), f ″(х) ≠ 0 на этом интервале (это имеет место, например, если ж (а) < 0, ж (б) > 0, и f ′(Икс) > 0, и f ″(Икс) > 0 на этом интервале). Это гарантирует, что на этом интервале есть уникальный корень, назовите его α. Если он вогнут вниз, а не вверх, замените ж (Икс) к −ж (Икс) поскольку у них одни корни.

Позволять Икс₀ = б - правый конец интервала, и пусть z₀ = а быть левым концом интервала. Данный Икс_п, определять

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

что, как и прежде, является методом Ньютона. Затем определите

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

где знаменатель f ′(Икс_п) и нет f ′(z_п). Итерации Икс_п будет строго убывать к корню, а итерации z_п будет строго возрастать до корня. Также,

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

так что расстояние между Икс_п и z_п уменьшается квадратично.

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

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

q-аналог

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

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

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

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

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

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

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

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

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

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

Учитывать ${\displaystyle f\in {\mathcal {C}}^{1}(X)}$, куда ${\displaystyle X}$ является действительным интервалом, и предположим, что у нас есть расширение интервала ${\displaystyle F'}$ из ${\displaystyle f'}$, означающий, что ${\displaystyle F'}$ принимает в качестве входных данных интервал ${\displaystyle Y\subseteq X}$ и выводит интервал ${\displaystyle F'(Y)}$ такой, что:

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

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

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

куда ${\displaystyle m\in Y}$. Отметим, что гипотеза о ${\displaystyle F'}$ подразумевает, что ${\displaystyle N(Y)}$ корректно определено и является интервалом (см. интервальная арифметика для получения дополнительных сведений об интервальных операциях). Естественно, это приводит к следующей последовательности:

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

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

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

Приложения

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

Основная статья: Метод Ньютона в оптимизации

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

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

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

Важное приложение Деление Ньютона – Рафсона, с помощью которого можно быстро найти взаимный из числа а, используя только умножение и вычитание, то есть число Икс такой, что 1/Икс = а. Мы можем перефразировать это как нахождение нуля ж(Икс) = 1/Икс − а. У нас есть ж′(Икс) = −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}).}$

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

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

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

Много трансцендентные уравнения решается методом Ньютона. Учитывая уравнение

${\displaystyle g(x)=h(x),}$

с грамм(Икс) и / или час(Икс) а трансцендентная функция, один пишет

${\displaystyle f(x)=g(x)-h(x).}$

Ценности Икс которые решают исходное уравнение, тогда являются корнями ж (Икс), который можно найти с помощью метода Ньютона.

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

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

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

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

CFD моделирование

Итеративная процедура Ньютона-Рафсона использовалась для наложения стабильного граничного условия Дирихле в CFD в качестве довольно общей стратегии для моделирования распределения тока и потенциала для пакетов электрохимических ячеек.^[22]

Примеры

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

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

Например, чтобы найти квадратный корень из 612 с первоначальным предположением Икс₀ = 10, последовательность, заданная методом Ньютона:

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

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

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

${\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}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{n}}}{\Bigr )}}$

то есть среднее арифметическое догадки, Икс_п и а/Икс_п.

Решение cos (Икс) = Икс³

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

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

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

В приведенном выше примере правильные цифры подчеркнуты. Особенно, Икс₆ правильно до 12 знаков после запятой. Мы видим, что количество правильных цифр после десятичной точки увеличивается с 2 (для Икс₃) до 5 и 10, иллюстрирующих квадратичную сходимость.

Код

Ниже приведен пример реализации метода Ньютона в Юля язык программирования для поиска корня функции ж который имеет производную fprime.

Первоначальное предположение будет Икс₀ = 1 и функция будет ж(Икс) = Икс² − 2 так что ж′(Икс) = 2Икс.

Каждую новую итерацию метода Ньютона будем обозначать x1. Во время расчета мы проверим, равен ли знаменатель (yprime) становится слишком маленьким (меньше, чем эпсилон), что было бы, если бы ж′(Икс_п) ≈ 0, так как в противном случае может появиться большое количество ошибок.

x0            = 1         # Первоначальное предположениеж(Икс)          = Икс^2 - 2   # Функция, корень которой мы пытаемся найтиfprime(Икс)     = 2Икс        # Производная функциитолерантность     = 1e-7      # 7 желательна точностьэпсилон       = 1e-14     # Не делите на меньшее числомаксИтерации = 20        # Не позволять итерациям продолжаться бесконечнорешениеНайдено = ложный     # Еще не пришли к решениюза я = 1:максИтерации  у      = ж(x0)  yprime = fprime(x0)  если пресс(yprime) < эпсилон            # Остановить, если знаменатель слишком мал    перемена  конец  Глобальный x1 = x0 - у/yprime           # Выполните вычисление Ньютона  если пресс(x1 - x0) <= толерантность        # Остановить, когда результат находится в пределах желаемого допуска    Глобальный решениеНайдено = истинный    перемена  конец  Глобальный x0 = x1                      # Обновите x0, чтобы снова запустить процессконецесли решениеНайдено  println("Решение: ", x1)           # x1 - решение в пределах допуска и максимального количества итерацийеще  println(«Не сходился»)         # Метод Ньютона не сходилсяконец

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

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

Примечания

1. «Глава 2. Секи Такакадзу». Японская математика в период Эдо. Национальная диетическая библиотека. Получено 24 февраля 2019.
2. Уоллис, Джон (1685). Трактат по алгебре, как исторической, так и практической. Оксфорд: Ричард Дэвис. Дои: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. Денс, Томас (ноябрь 1997 г.). «Кубики, хаос и метод Ньютона». Математический вестник. 81 (492): 403–408. Дои:10.2307/3619617. JSTOR  3619617.
8. Хенрици, Питер (1974). «Прикладной и вычислительный комплексный анализ». 1.
9. Стрэнг, Гилберт (январь 1991). "Хаотичный поиск я". Математический журнал колледжа. 22: 3–12. Дои:10.2307/2686733. JSTOR  2686733.
10. Макмаллен, Курт (1987). «Семейства рациональных отображений и итерационных алгоритмов поиска корней» (PDF). Анналы математики. Вторая серия. 125 (3): 467–493. Дои:10.2307/1971408. JSTOR  1971408.
11. Ямамото, Тетсуро (2001). «Исторические достижения в области анализа сходимости методов Ньютона и ньютоноподобных методов». В Brezinski, C .; Wuytack, L. (ред.). Численный анализ: исторические события ХХ века. Северная Голландия. С. 241–263. ISBN  0-444-50617-9.
12. Райкович, Станкович и Маринкович, 2002 г. ошибка harvnb: цель отсутствует: CITEREFRajkovicStankovicMarinkovic2002 (помощь)^{[неполная короткая цитата ]}
13. Press et al. 1992 г. Ошибка harvnb: цель отсутствует: CITEREFPressTeukolskyVetterlingFlannery1992 (помощь)^{[неполная короткая цитата ]}
14. Stoer & Bulirsch, 1980 г. Ошибка harvnb: цель отсутствует: CITEREFStoerBulirsch1980 (помощь)^{[неполная короткая цитата ]}
15. Чжан и Цзинь 1996 Ошибка harvnb: цель отсутствует: CITEREFZhangJin1996 (помощь)^{[неполная короткая цитата ]}
16. Мурота, Кадзуо (1982). «Глобальная сходимость модифицированной итерации Ньютона для алгебраических уравнений». SIAM J. Numer. Анальный. 19 (4): 793–799. Дои:10.1137/0719055.
17. Мур, Р. Э. (1979). Методы и приложения интервального анализа (Том 2). Сиам.
18. Хансен, Э. (1978). Интервальные формы метода Ньютона. Вычисление, 20(2), 153–163.
19. Гил, Сегура и Темме (2007)^{[неполная короткая цитата ]}
20. Кахан  (1968 )^{[неполная короткая цитата ]}
21. Кравчик (1969) Ошибка harvtxt: нет цели: CITEREFKrawczyk1969 (помощь)^{[неполная короткая цитата ][неполная короткая цитата ]}
22. Colli, A. N .; Жиро, Х. Х. (июнь 2017 г.). «Компактная и общая стратегия решения проблемы распределения тока и потенциала в электрохимических ячейках, состоящих из массивных монополярных и биполярных электродов». Журнал Электрохимического общества. 164 (11): E3465 – E3472. Дои:10.1149 / 2.0471711jes. HDL:11336/68067.

Рекомендации

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

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

• Кендалл Э. Аткинсон, Введение в численный анализ(1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6
• Тьяллинг Дж. Ипма, Историческое развитие метода Ньютона – Рафсона, SIAM Обзор 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. Springer, Берлин, 2004 г. ISBN  3-540-21099-7.
• К. Т. Келли, Решение нелинейных уравнений методом Ньютона, № 1 в Основах алгоритмов, SIAM, 2003. ISBN  0-89871-546-6.
• Дж. М. Ортега, В. К. Райнбольдт, Итерационное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики, SIAM, 2000. ISBN  0-89871-461-3.
• Press, W. H .; Теукольский, С. А .; Vetterling, W. T .; Фланнери, Б. П. (2007). «Глава 9. Нахождение корня и выборка по важности нелинейных наборов уравнений». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.. См. Особенно разделы 9.4, 9.6, и 9.7.
• Авриэль, Мардохей (1976). Нелинейное программирование: анализ и методы.. Прентис Холл. С. 216–221. ISBN  0-13-623603-0.

внешняя ссылка

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