В численном анализе , метод Ньютона , также известный как метод Ньютона-Рафсона , названный в честь Исаака Ньютона и Джозефа Рафсона , является корнем найти алгоритм , который производит последовательно более приближения к корням (или нулей) от реальной значной функции . Самые основные версии начинается с одной переменной функцией F , определенная для вещественных переменных х , функции по производному е ' и начальное приближение х 0 для корня изf . Если функция удовлетворяет достаточным предположениям и первоначальное предположение близко, то
является лучшим приближением корня, чем x 0 . Геометрический ( х 1 , 0) является пересечением х осей х и касательная из графика из F в ( х 0 , F ( х 0 )) : то есть, улучшенное предположением является единственным корнем линейной аппроксимации в начальной точке. Процесс повторяется как
пока не будет достигнуто достаточно точное значение. Этот алгоритм является первым в классе методов Хаусхолдера , за ним следует метод Галлея . Метод также может быть распространен на сложные функции и системы уравнений .
Описание
Идея состоит в том, чтобы начать с первоначального предположения, которое достаточно близко к истинному корню, затем аппроксимировать функцию ее касательной с помощью исчисления и, наконец, вычислить точку пересечения оси x этой касательной с помощью элементарной алгебры . Этот x -перехват обычно будет лучшим приближением к корню исходной функции, чем первое предположение, и метод может быть повторен .
Более формально предположим, что f : ( a , b ) → ℝ - дифференцируемая функция, определенная на интервале ( a , b ) со значениями в действительных числах ℝ , и у нас есть некоторое текущее приближение x n . Затем мы можем вывести формулу для лучшего приближения x n + 1 , обратившись к диаграмме справа. Уравнение касательной к кривой y = f ( x ) при x = x n имеет вид
где f ′ обозначает производную . Х -intercept этой линии (значение х , что делает у = 0 ) берется в качестве следующего приближения, х п + 1 , к корню, так что уравнение касательной удовлетворяется , когда:
Решение относительно x n + 1 дает
Начнем процесс с произвольным начальным значением x 0 . (Чем ближе к нулю, тем лучше. Но при отсутствии какой-либо интуиции относительно того, где может находиться ноль, метод «угадать и проверить» может сузить возможности до разумно небольшого интервала, обратившись к теореме о промежуточном значении .) Метод обычно сходится при условии, что это первоначальное предположение достаточно близко к неизвестному нулю и что f ′ ( x 0 ) ≠ 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 и комплексными начальными значениями. Это открыло путь к изучению теории итераций рациональных функций.
Практические соображения
Метод Ньютона - мощная техника - в целом сходимость квадратичная: по мере того, как метод сходится к корню, разница между корнем и приближением возводится в квадрат (количество точных цифр примерно удваивается) на каждом шаге. Однако с этим методом возникают некоторые трудности.
Сложность вычисления производной функции
Метод Ньютона требует, чтобы производная могла быть вычислена напрямую. Аналитическое выражение для производной может быть нелегко получить или его оценка может быть дорогостоящей. В этих ситуациях может оказаться целесообразным аппроксимировать производную, используя наклон прямой, проходящей через две близлежащие точки функции. Использование этого приближения привело бы к чему-то вроде метода секущих , сходимость которого медленнее, чем у метода Ньютона.
Неспособность метода сойтись к корню
Важно просмотреть доказательство квадратичной сходимости метода Ньютона перед его реализацией. В частности, следует пересмотреть предположения, сделанные при доказательстве. В ситуациях, когда метод не сходится , это происходит потому, что предположения, сделанные в этом доказательстве, не выполняются.
Перескок
Если первая производная плохо себя ведет в окрестности определенного корня, метод может выйти за пределы допустимого диапазона и отклониться от этого корня. Примером функции с одним корнем, для которой производная плохо себя ведет в окрестности корня, является
для которого корень будет перевыполнен, а последовательность x будет расходиться. Для a =1/2, корень все равно будет перевыполнен, но последовательность будет колебаться между двумя значениями. Для1/2< a <1 , корень все равно будет перекрыт, но последовательность будет сходиться, а при a ≥ 1 корень вообще не будет перекрыт.
В некоторых случаях метод Ньютона может быть стабилизирован с помощью последовательной сверхрелаксации , или скорость сходимости может быть увеличена с помощью того же метода.
Стационарная точка
Если обнаруживается стационарная точка функции, производная равна нулю, и метод завершается из-за деления на ноль .
Плохая первоначальная оценка
Большая ошибка в начальной оценке может способствовать несходимости алгоритма. Чтобы преодолеть эту проблему, часто можно линеаризовать оптимизируемую функцию с помощью исчисления, журналов, дифференциалов или даже с использованием эволюционных алгоритмов, таких как стохастическое туннелирование . Хорошие начальные оценки лежат близко к окончательной глобально оптимальной оценке параметров. В нелинейной регрессии сумма квадратов ошибок (SSE) только "близка" к параболической в области окончательных оценок параметров. Найденные здесь первоначальные оценки позволят методу Ньютона – Рафсона быстро сойтись. Только здесь матрица Гессе SSE положительна, а первая производная SSE близка к нулю.
Смягчение несогласованности
В надежной реализации метода Ньютона обычно устанавливают ограничения на количество итераций, связывают решение с интервалом, который, как известно, содержит корень, и комбинируют метод с более надежным методом поиска корня.
Медленная сходимость для корней кратности больше 1
Если искомый корень имеет кратность больше единицы, скорость сходимости будет просто линейной (ошибки уменьшаются на постоянный коэффициент на каждом шаге), если не будут предприняты специальные шаги. Когда есть два или более корня, которые расположены близко друг к другу, может потребоваться много итераций, прежде чем итерации приблизятся к одному из них, чтобы квадратичная сходимость стала очевидной. Однако если кратностькорня известен, следующий модифицированный алгоритм сохраняет скорость квадратичной сходимости: [4]
Это эквивалентно использованию последовательного чрезмерного расслабления . С другой стороны, если кратность корня m неизвестна, можно оценить после выполнения одной или двух итераций, а затем используйте это значение для увеличения скорости сходимости.
Если кратность корня m конечна, то g ( x ) = f ( x ) / f ′ ( x ) будет иметь корень в том же месте с кратностью 1. Применение метода Ньютона для нахождения корня g ( x ) восстанавливает квадратичная сходимость во многих случаях, хотя обычно она включает в себя вторую производную от f ( x ) . В особенно простом случае, если f ( x ) = x m, то g ( x ) = x / m и метод Ньютона находит корень за одну итерацию с
Анализ
Предположим , что функция F имеет нуль в & alpha ; , то есть F ( & alpha ; ) = 0 , и е дифференцируема в окрестности из альфа .
Если F непрерывно дифференцируема и ее производная равна нулю при & alpha ; , то существует окрестность из α такой , что для всех начальных значений х 0 в этом районе, последовательность { х п } будет сходится к α . [5]
Если функция непрерывно дифференцируема и ее производная отлична от 0 в точке α и имеет вторую производную в точке α, то сходимость будет квадратичной или более быстрой. Если вторая производная не равна 0 в точке α, то сходимость просто квадратичная. Если третья производная существует и ограничена в окрестности α , то:
где
Если производная равна 0 при α , то сходимость обычно только линейная. В частности, если f дважды непрерывно дифференцируема, f ′ ( α ) = 0 и f ″ ( α ) ≠ 0 , то существует такая окрестность α , что для всех начальных значений x 0 в этой окрестности последовательность итераций сходится линейно с частотой 1/2 [6] в качестве альтернативы, если F ' ( & alpha ; ) = 0 и F' ( х ) ≠ 0 для х ≠ & alpha ; , х в окрестности U из & alpha ; , & alpha ; быть нуль кратности г , и если f ∈ C r ( U ) , то существует такая окрестность α , что для всех начальных значений x 0 в этой окрестности последовательность итераций сходится линейно.
Однако даже линейная сходимость в патологических ситуациях не гарантируется.
На практике эти результаты являются локальными, и окрестность сходимости заранее не известна. Но есть также некоторые результаты о глобальной конвергенции: например, учитывая правую окрестность U + из альфа , если е дважды дифференцируема в U + и если F ' ≠ 0 , ф · ф " > 0 в U + , то для для каждого x 0 в U + последовательность x k монотонно убывает до α .
Доказательство квадратичной сходимости итерационного метода Ньютона.
Согласно теореме Тейлора , любая функция f ( x ), которая имеет непрерывную вторую производную, может быть представлена разложением вокруг точки, которая близка к корню f ( x ) . Предположим, что этот корень равен α . Тогда разложение f ( α ) вокруг x n :
( 1 )
где форма Лагранжа остатка разложения в ряд Тейлора имеет вид
где ξ n находится между x n и α .
Поскольку α является корнем, ( 1 ) принимает вид:
( 2 )
Разделив уравнение ( 2 ) на f ′ ( x n ) и переставив, получим
( 3 )
Помня, что x n + 1 определяется как
( 4 )
каждый обнаруживает, что
Это,
( 5 )
Взяв абсолютное значение обеих сторон, получаем
( 6 )
Уравнение ( 6 ) показывает, что скорость сходимости не меньше квадратичной, если выполняются следующие условия:
- f ′ ( x ) ≠ 0 ; для всех x ∈ I , где I интервал [ α - r , α + r ] для некоторого r ≥ | α - x 0 | ;
- f ″ ( x ) непрерывна для всех x ∈ I ;
- х 0 является достаточно близко к корню альфа .
Термин достаточно близко в данном контексте означает следующее:
- Приближение Тейлора достаточно точное, так что мы можем игнорировать члены более высокого порядка;
- для некоторого C <∞ ;
- для n ∈ ℤ , n ≥ 0 и C, удовлетворяющего условию b.
Наконец, ( 6 ) можно выразить следующим образом:
где M - верхняя грань переменного коэффициента ε n 2 на интервале I, определенном в условии 1, то есть:
Начальная точка x 0 должна быть выбрана так, чтобы выполнялись условия с 1 по 3, где третье условие требует, чтобы M | ε 0 | <1 .
Бассейны притяжения
Непересекающиеся подмножества бассейнов притяжения - области прямой действительной числовой линии, такие, что внутри каждой области итерация из любой точки приводит к одному конкретному корню, - могут быть бесконечными по количеству и сколь угодно малыми. Например, [7] для функции f ( x ) = x 3 - 2 x 2 - 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 стремится к ∞ или −∞ . В таких случаях следует использовать другой метод, например деление пополам , чтобы получить лучшую оценку нуля, который будет использоваться в качестве начальной точки.
Точка итерации стационарна
Рассмотрим функцию:
Он имеет максимум при x = 0 и решения f ( x ) = 0 при x = ± 1 . Если мы начнем итерацию от стационарной точки x 0 = 0 (где производная равна нулю), x 1 будет неопределенным, поскольку касательная в точке (0,1) параллельна оси x :
Та же проблема возникает, если вместо начальной точки неподвижна любая точка итерации. Даже если производная мала, но не равна нулю, следующая итерация будет гораздо худшим приближением.
Начальная точка входит в цикл
Для некоторых функций некоторые начальные точки могут входить в бесконечный цикл, препятствуя сходимости. Позволять
и возьмем 0 в качестве отправной точки. Первая итерация дает 1, а вторая итерация возвращается к 0, поэтому последовательность будет чередоваться между двумя без схождения к корню. Фактически, этот 2-цикл является стабильным: есть окрестности около 0 и около 1, из которых все точки асимптотически повторяются до 2-цикла (и, следовательно, не до корня функции). В общем, поведение последовательности может быть очень сложным (см. Фрактал Ньютона ). Настоящее решение этого уравнения есть−1,769 292 35 ….
Производные выпуски
Если функция не является непрерывно дифференцируемой в окрестности корня, тогда возможно, что метод Ньютона всегда будет расходиться и терпеть неудачу, если решение не будет угадано с первой попытки.
Производная не существует в корне
Простой пример функции, в которой метод Ньютона расходится, пытается найти кубический корень из нуля. Кубический корень непрерывен и бесконечно дифференцируем, за исключением x = 0 , где его производная не определена:
Для любой точки итерации x n следующей точкой итерации будет:
Алгоритм выходит за пределы решения и приземляется на другой стороне оси y , дальше, чем это было изначально; применение метода Ньютона фактически удваивает расстояния от решения на каждой итерации.
Фактически, итерации расходятся до бесконечности для любого f ( x ) = | х | α , где 0 < α < 1/2. В предельном случае α = 1/2(квадратный корень), итерации будут бесконечно чередоваться между точками x 0 и - x 0 , поэтому и в этом случае они не сходятся.
Разрывная производная
Если производная не является непрерывной в корне, то сходимость может не произойти ни в какой окрестности корня. Рассмотрим функцию
Его производная:
В любой окрестности корня эта производная продолжает менять знак, когда x приближается к 0 справа (или слева), в то время как f ( x ) ≥ x - x 2 > 0 для 0 < x <1 .
Так f ( x )/f ′ ( x ) неограничен около корня, и метод Ньютона будет расходиться почти везде в любой его окрестности, даже если:
- функция дифференцируема (а значит, непрерывна) всюду;
- производная в корне отлична от нуля;
- f бесконечно дифференцируема, кроме корня; а также
- производная ограничена в окрестности корня (в отличие от f ( x )/f ′ ( x )).
Неквадратичная сходимость
В некоторых случаях итерации сходятся, но не сходятся так быстро, как обещано. В этих случаях более простые методы сходятся так же быстро, как и метод Ньютона.
Нулевая производная
Если первая производная в корне равна нулю, сходимость не будет квадратичной. Позволять
тогда f ′ ( x ) = 2 x и, следовательно,
Таким образом, сходимость не является квадратичной, хотя функция бесконечно дифференцируема всюду.
Подобные проблемы возникают даже тогда, когда корень только «почти» удваивается. Например, пусть
Тогда первые несколько итераций, начиная с 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 …
требуется шесть итераций, чтобы достичь точки, в которой сходимость оказывается квадратичной.
Без второй производной
Если в корне нет второй производной, то сходимость может не быть квадратичной. Позволять
потом
А также
кроме случая, когда x = 0, где он не определен. Учитывая x n ,
который примерно 4/3раз больше точности, чем у x n . Это меньше, чем в 2 раза больше, чем требуется для квадратичной сходимости. Таким образом, сходимость метода Ньютона (в данном случае) не является квадратичной, хотя: функция непрерывно дифференцируема всюду; производная не равна нулю в корне; и f бесконечно дифференцируема, кроме желаемого корня.
Обобщения
Сложные функции
При работе со сложными функциями можно напрямую применить метод Ньютона для нахождения их нулей. [8] У каждого нуля есть область притяжения в комплексной плоскости, набор всех начальных значений, которые приводят к тому, что метод сходится к этому конкретному нулю. Эти наборы можно сопоставить, как показано на изображении. Для многих сложных функций границы областей притяжения - фракталы .
В некоторых случаях в комплексной плоскости есть области, которые не находятся ни в одной из этих областей притяжения, что означает, что итерации не сходятся. Например, [9], если для поиска корня из x 2 + 1 используется реальное начальное условие , все последующие итерации будут действительными числами, и поэтому итерации не могут сходиться ни к одному из корней, поскольку оба корня не являются действительными. В этом случае почти все реальные начальные условия приводят к хаотическому поведению , в то время как некоторые начальные условия повторяются либо до бесконечности, либо к повторяющимся циклам любой конечной длины.
Курт МакМаллен показал, что для любого возможного чисто итеративного алгоритма, подобного методу Ньютона, алгоритм будет расходиться в некоторых открытых областях комплексной плоскости при применении к некоторому полиному степени 4 или выше. Однако Макмаллен дал в общем сходящийся алгоритм для многочленов степени 3. [10]
Метод третьего порядка Чебышева
Итерация Нэша – Мозера
Нелинейные системы уравнений
k переменных, k функций
Можно также использовать метод Ньютона для решения систем k (нелинейных) уравнений, что сводится к нахождению нулей непрерывно дифференцируемых функций F : ℝ k → ℝ k . В приведенной выше формулировке, один , то есть налево многократно с обратным из K × K матрица Якоби J Р ( х п ) вместо деления на Р ' ( х п ) :
Вместо того, чтобы фактически вычислять обратную матрицу Якоби, можно сэкономить время и повысить численную стабильность, решив систему линейных уравнений
для неизвестного x n + 1 - x n .
k переменных, m уравнений, при m > k
К - мерный вариант метода Ньютона может быть использован для решения систем большей , чем к (нелинейных) уравнений, а если алгоритм использует обобщенный обратный из не квадратный якобиевой матрицы J + = ( J Т J ) -1 J Т вместо обратного к J. Если у нелинейной системы нет решения, метод пытается найти решение в смысле нелинейных наименьших квадратов . См. Алгоритм Гаусса-Ньютона для получения дополнительной информации.
Нелинейные уравнения в банаховом пространстве.
Другое обобщение - это метод Ньютона для нахождения корня функционала F, определенного в банаховом пространстве . В этом случае формулировка
где 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 0 = b - правая конечная точка интервала, а z 0 = a - левая конечная точка интервала. Для данного x n определим
which is just Newton's method as before. Then define
where the denominator is f ′(xn) and not f ′(zn). The iterations xn will be strictly decreasing to the root while the iterations zn will be strictly increasing to the root. Also,
so that distance between xn and zn decreases quadratically.
Quasi-Newton methods
When the Jacobian is unavailable or too expensive to compute at every iteration, a quasi-Newton method can be used.
q-analog
Newton's method can be generalized with the q-analog of the usual derivative.[12]
Modified Newton methods
Maehly's procedure
A nonlinear equation has multiple solutions in general. But if the initial value is not appropriate, Newton's method may not converge to the desired solution or may converge to the same solution found earlier. When we have already found N solutions of , then the next root can be found by applying Newton's method to the next equation:[13][14]
This method is applied to obtain zeros of the Bessel function of the second kind.[15]
Hirano's modified Newton method
Hirano's modified Newton method is a modification conserving the convergence of Newton method and avoiding unstableness.[16] It is developed to solve complex polynomials.
Interval Newton's method
Combining Newton's method with interval arithmetic is very useful in some contexts. This provides a stopping criterion that is more reliable than the usual ones (which are a small value of the function or a small variation of the variable between consecutive iterations). Also, this may detect cases where Newton's method converges theoretically but diverges numerically because of an insufficient floating-point precision (this is typically the case for polynomials of large degree, where a very small change of the variable may change dramatically the value of the function; see Wilkinson's polynomial).[17][18]
Consider , where is a real interval, and suppose that we have an interval extension of , meaning that takes as input an interval and outputs an interval such that:
We also assume that , so in particular has at most one root in . We then define the interval Newton operator by:
where . Note that the hypothesis on implies that is well defined and is an interval (see interval arithmetic for further details on interval operations). This naturally leads to the following sequence:
The mean value theorem ensures that if there is a root of in , then it is also in . Moreover, the hypothesis on ensures that is at most half the size of when is the midpoint of , so this sequence converges towards , where is the root of in .
If strictly contains , the use of extended interval division produces a union of two intervals for ; multiple roots are therefore automatically separated and bounded.
Приложения
Minimization and maximization problems
Newton's method can be used to find a minimum or maximum of a function . The derivative is zero at a minimum or maximum, so local minima and maxima can be found by applying Newton's method to the derivative. The iteration becomes:
Multiplicative inverses of numbers and power series
An important application is Newton–Raphson division, which can be used to quickly find the reciprocal of a number a, using only multiplication and subtraction, that is to say the number x such that 1/x = a. We can rephrase that as finding the zero of f(x) = 1/x − a. We have f′(x) = − 1/x2.
Newton's iteration is
Therefore, Newton's iteration needs only two multiplications and one subtraction.
This method is also very efficient to compute the multiplicative inverse of a power series.
Solving transcendental equations
Many transcendental equations can be solved using Newton's method. Given the equation
with g(x) and/or h(x) a transcendental function, one writes
The values of x that solve the original equation are then the roots of f (x), which may be found via Newton's method.
Obtaining zeros of special functions
Newton's method is applied to the ratio of Bessel functions in order to obtain its root.[19]
Numerical verification for solutions of nonlinear equations
A numerical verification for solutions of nonlinear equations has been established by using Newton's method multiple times and forming a set of solution candidates.[20][21]
CFD modeling
An iterative Newton-Raphson procedure was employed in order to impose a stable Dirichlet boundary condition in CFD, as a quite general strategy to model current and potential distribution for electrochemical cell stacks.[22]
Примеры
Square root
Consider the problem of finding the square root of a number a, that is to say the positive number x such that x2 = a. Newton's method is one of many methods of computing square roots. We can rephrase that as finding the zero of f(x) = x2 − a. We have f′(x) = 2x.
For example, for finding the square root of 612 with an initial guess x0 = 10, the sequence given by Newton's method is:
where the correct digits are underlined. With only a few iterations one can obtain a solution accurate to many decimal places.
Rearranging the formula as follows yields the Babylonian method of finding square roots:
i.e. the arithmetic mean of the guess, xn and a/xn.
Solution of cos(x) = x3
Consider the problem of finding the positive number x with cos(x) = x3. We can rephrase that as finding the zero of f(x) = cos(x) − x3. We have f′(x) = −sin(x) − 3x2. Since cos(x) ≤ 1 for all x and x3 > 1 for x > 1, we know that our solution lies between 0 and 1.
For example, with an initial guess x0 = 0.5, the sequence given by Newton's method is (note that a starting value of 0 will lead to an undefined result, showing the importance of using a starting point that is close to the solution):
The correct digits are underlined in the above example. In particular, x6 is correct to 12 decimal places. We see that the number of correct digits after the decimal point increases from 2 (for x3) to 5 and 10, illustrating the quadratic convergence.
Код
The following is an implementation example of the Newton's method in the Julia programming language for finding a root of a function f
which has derivative fprime
.
The initial guess will be x0 = 1 and the function will be f(x) = x2 − 2 so that f′(x) = 2x.
Each new iteration of Newton's method will be denoted by x1
. We will check during the computation whether the denominator (yprime
) becomes too small (smaller than epsilon
), which would be the case if f′(xn) ≈ 0, since otherwise a large amount of error could be introduced.
x0 = 1 # The initial guessf(x) = x^2 - 2 # The function whose root we are trying to findfprime(x) = 2x # The derivative of the functiontolerance = 1e-7 # 7 digit accuracy is desiredepsilon = 1e-14 # Do not divide by a number smaller than thismaxIterations = 20 # Do not allow the iterations to continue indefinitelysolutionFound = false # Have not converged to a solution yetfor i = 1:maxIterations y = f(x0) yprime = fprime(x0) if abs(yprime) < epsilon # Stop if the denominator is too small break end global x1 = x0 - y/yprime # Do Newton's computation if abs(x1 - x0) <= tolerance # Stop when the result is within the desired tolerance global solutionFound = true break end global x0 = x1 # Update x0 to start the process againendif solutionFound println("Solution: ", x1) # x1 is a solution within tolerance and maximum number of iterationselse println("Did not converge") # Newton's method did not convergeend
Смотрите также
- Aitken's delta-squared process
- Bisection method
- Euler method
- Fast inverse square root
- Fisher scoring
- Gradient descent
- Integer square root
- Kantorovich theorem
- Laguerre's method
- Methods of computing square roots
- Newton's method in optimization
- Richardson extrapolation
- Root-finding algorithm
- Secant method
- Steffensen's method
- Subgradient method
Заметки
- ^ "Chapter 2. Seki Takakazu". Japanese Mathematics in the Edo Period. National Diet Library. Retrieved 24 February 2019.
- ^ Wallis, John (1685). A Treatise of Algebra, both Historical and Practical. Oxford: Richard Davis. doi:10.3931/e-rara-8842.
- ^ Raphson, Joseph (1697). Analysis Æequationum Universalis (in Latin) (2nd ed.). London: Thomas Bradyll. doi:10.3931/e-rara-13516.
- ^ "Accelerated and Modified Newton Methods". Archived from the original on 24 May 2019. Retrieved 4 March 2016.
- ^ Ryaben'kii, Victor S.; Tsynkov, Semyon V. (2006), A Theoretical Introduction to Numerical Analysis, CRC Press, p. 243, ISBN 9781584886075.
- ^ Süli & Mayers 2003, Exercise 1.6
- ^ Dence, Thomas (November 1997). "Cubics, chaos and Newton's method". Mathematical Gazette. 81 (492): 403–408. doi:10.2307/3619617. JSTOR 3619617.
- ^ Henrici, Peter (1974). "Applied and Computational Complex Analysis". 1. Cite journal requires
|journal=
(help) - ^ Strang, Gilbert (January 1991). "A chaotic search for i". The College Mathematics Journal. 22: 3–12. doi:10.2307/2686733. JSTOR 2686733.
- ^ McMullen, Curt (1987). "Families of rational maps and iterative root-finding algorithms" (PDF). Annals of Mathematics. Second Series. 125 (3): 467–493. doi:10.2307/1971408. JSTOR 1971408.
- ^ Yamamoto, Tetsuro (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.
- ^ Rajkovic, Stankovic & Marinkovic 2002incomplete short citation] [
- ^ Press et al. 1992incomplete short citation] [
- ^ Stoer & Bulirsch 1980incomplete short citation] [
- ^ Zhang & Jin 1996incomplete short citation] [
- ^ Murota, Kazuo (1982). "Global Convergence of a Modified Newton Iteration for Algebraic Equations". SIAM J. Numer. Anal. 19 (4): 793–799. doi:10.1137/0719055.
- ^ Moore, R. E. (1979). Methods and applications of interval analysis (Vol. 2). Siam.
- ^ Hansen, E. (1978). Interval forms of Newtons method. Computing, 20(2), 153–163.
- ^ Gil, Segura & Temme (2007)[incomplete short citation]
- ^ Kahan (1968)[incomplete short citation]
- ^ Krawczyk (1969)incomplete short citation][incomplete short citation] [
- ^ Colli, A. N.; Girault, H. H. (June 2017). "Compact and General Strategy for Solving Current and Potential Distribution in Electrochemical Cells Composed of Massive Monopolar and Bipolar Electrodes". Journal of the Electrochemical Society. 164 (11): E3465–E3472. doi:10.1149/2.0471711jes. hdl:11336/68067.
Рекомендации
- Gil, A.; Segura, J.; Temme, N. M. (2007). Numerical methods for special functions. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-634-4.
- Süli, Endre; Mayers, David (2003). An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1.
дальнейшее чтение
- Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
- Tjalling J. Ypma, Historical development of the Newton–Raphson method, SIAM Review 37 (4), 531–551, 1995. doi:10.1137/1037125.
- Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
- P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.
- C. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.
- J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, SIAM, 2000. ISBN 0-89871-461-3.
- Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations Importance Sampling". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. See especially Sections 9.4, 9.6, and 9.7.
- Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. pp. 216–221. ISBN 0-13-623603-0.
Внешние ссылки
- "Newton method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Weisstein, Eric W. "Newton's Method". MathWorld.
- Newton's method, Citizendium.
- Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
- Wu, X., Roots of Equations, Course notes.