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

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

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

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

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

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

Описание [ править ]

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

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

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

где f ′ обозначает производную . Х -intercept этой линии (значение х , что делает у = 0 ) берется в качестве следующего приближения, х _{п + 1} , к корню, так что уравнение касательной удовлетворяется , когда :${\ Displaystyle (х, у) = (х_ {п + 1}, 0)}$

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

Решение относительно 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 году, переведено и опубликовано как Метод флюксий в 1736 году Джоном Колсоном.). Однако его метод существенно отличается от современного, приведенного выше. Ньютон применил этот метод только к многочленам, начиная с начальной оценки корня и извлекая последовательность исправлений ошибок. Он использовал каждую поправку, чтобы переписать многочлен в терминах оставшейся ошибки, а затем решил для новой поправки, пренебрегая членами более высокой степени. Он не связывал явно метод с производными и не приводил общую формулу. Ньютон применил этот метод как к числовым, так и к алгебраическим задачам, получив в последнем случае ряды Тейлора .

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

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

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

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

Практические соображения [ править ]

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

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

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

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

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

Превышение [ править ]

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

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

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

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

Стационарная точка [ править ]

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

Плохая первоначальная оценка [ править ]

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

Смягчение несогласованности [ править ]

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

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

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

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

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

Анализ [ править ]

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

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

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

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

где

${\ Displaystyle \ Дельта х_ {я} \ треугольник х_ {я} - \ альфа \ ,.}$

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

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

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

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

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

${\ Displaystyle е (\ альфа) = е (x_ {n}) + f '(x_ {n}) (\ alpha -x_ {n}) + R_ {1} \,}$

( 1 )

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

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

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

Поскольку α является корнем, ( 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 ′ ( x _n ) и переставив, получим

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

Помня, что x _{n + 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 ′ ( x ) ≠ 0 ; для всех x ∈ I , где I интервал [ α - r , α + r ] для некоторого r ≥ | α - x ₀ | ;
2. f ″ ( x ) непрерывна для всех x ∈ I ;
3. х ₀ является достаточно близко к корню альфа .

Термин достаточно близко в данном контексте означает следующее:

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

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

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

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

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

Бассейны притяжения [ править ]

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

2,352 875 27	сходится к	4;
2,352 841 72	сходится к	−3;
2,352 837 35	сходится к	4;
2,352 836 327	сходится к	−3;
2,352 836 323	сходится к	1.

Анализ отказов [ править ]

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

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

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

Точка итерации стационарна [ править ]

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

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

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

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

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

Начальная точка входит в цикл [ править ]

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

${\ Displaystyle е (х) = х ^ {3} -2x + 2 \!}$

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

Производные выпуски [ править ]

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

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

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

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

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

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

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

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

Разрывная производная [ править ]

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

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

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

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

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

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

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

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

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

Нулевая производная [ править ]

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

${\ Displaystyle е (х) = х ^ {2} \!}$

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

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

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

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

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

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

х ₀ = 1

х ₁ =0,500 250 376 …

х ₂ =0,251 062 828 …

х ₃ =0,127 507 934 …

х ₄ =0,067 671 976 …

х ₅ =0,041 224 176 …

х ₆ =0,032 741 218 …

х ₇ =0,031 642 362 …

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

Без второй производной [ править ]

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

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

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

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

Обобщения [ править ]

Сложные функции [ править ]

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

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

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

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

Итерация Нэша – Мозера [ править ]

Нелинейные системы уравнений [ править ]

k переменных, k функций[ редактировать ]

Можно также использовать метод Ньютона для решения систем k (нелинейных) уравнений, что сводится к нахождению нулей непрерывно дифференцируемых функций F  : ℝ ^k → ℝ ^k . В приведенной выше формулировке, один , то есть налево многократно с обратным из K × K матрица Якоби J _Р ( х _п ) вместо деления на Р ' ( х _п ) :

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

для неизвестного x _{n + 1} - x _n .

k переменных, m уравнений, где m > k [ править ]

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

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

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

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

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

Нелинейные уравнения над p -адическими числами [ править ]

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

Метод Ньютона – Фурье [ править ]

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

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

Пусть x ₀ = b - правая конечная точка интервала, а z ₀ = a - левая конечная точка интервала. Для данного x _n определим

${\ 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 ′ ( x _n ), а не f ′ ( z _n ) . Итерации x _n будут строго уменьшаться к корню, а итерации z _n будут строго возрастать к корню. Также,

${\displaystyle \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-аналога обычной производной. ^[12]

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

Процедура Мэли [ править ]

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

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

где . Обратите внимание, что гипотеза on подразумевает, что это хорошо определено и является интервалом (см. Интервальную арифметику для получения дополнительных сведений об операциях с интервалом). Это, естественно, приводит к следующей последовательности:${\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}}}$

Теорема о среднем значении гарантирует, что если есть корень из in , то он также находится из . Более того, гипотеза on гарантирует, что это не более половины размера, когда является серединой , поэтому эта последовательность сходится к , где - корень in .${\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})}}.}$

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

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

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

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

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

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

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

с г ( х ) и / или ч ( х ) в трансцендентной функции , пишут

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

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

Получение нулей специальных функций [ править ]

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

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

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

CFD моделирование [ править ]

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

Примеры [ править ]

Квадратный корень [ править ]

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

Например, для нахождения квадратного корня из 612 с начальным предположением x ₀ = 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 )}}$

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

Решение cos ( x ) = x ³ [ править ]

Рассмотрим задачу нахождения положительного числа 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.

Например, при начальном предположении x ₀ = 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}}}$

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

Код [ править ]

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

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

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

x0  =  1  # Начальное предположение f ( x )  =  x ^ 2  -  2  # Функция, корень которой мы пытаемся найти fprime ( x )  =  2 x  # Производная от допуска  функции =  1e-7  # 7-значная точность равна желаемый epsilon  =  1e-14  # Не делить на число меньше этого maxIterations  =  20  # Не позволять итерациям продолжаться бесконечно solutionFound  =  false  # Еще не пришли к решениюдля  i  =  1 : maxIterations  y  =  f ( x0 )  yprime  =  fprime ( x0 ) if  abs ( yprime )  <  epsilon  # Остановить, если знаменатель слишком мал  break  end global  x1  =  x0  -  y / yprime  # Выполнить вычисление Ньютона if  abs ( x1  -  x0 )  <=  толерантность  # Остановить, когда результат находится в пределах желаемого допуска  global  solutionFound  =  true  break  end global  x0  =  x1  # Обновить x0, чтобы снова запустить процесс endif  solutionFound  println ( "Решение:" ,  x1 )  # x1 - это решение в пределах допуска и максимального количества итераций else  println ( "Не сходилось" )  # Метод Ньютона не сходился end

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

• 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 Review 37 (4), 531–551, 1995. doi : 10.1137 / 1037125 .
• Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. DOI : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. Руководство по ремонту  2265882 .
• Деуфлхард П. Методы Ньютона для нелинейных задач. Аффинная инвариантность и адаптивные алгоритмы. Серия Спрингера по вычислительной математике, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7 . 
• CT Келли, Решение нелинейных уравнений методом Ньютона , № 1 в Основах алгоритмов, SIAM, 2003. ISBN 0-89871-546-6 . 
• JM Ortega, WC Rheinboldt, Итерационное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики, SIAM, 2000. ISBN 0-89871-461-3 . 
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, ВР (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., Корни уравнений, Примечания к курсу.