В численном анализе метод Ньютона , также известный как метод Ньютона - Рафсона , названный в честь Исаака Ньютона и Джозефа Рафсона , представляет собой алгоритм поиска корня , который производит последовательно лучшие приближения к корням (или нулям) действительной функции . Самая базовая версия начинается с вещественной функции f , ее производной f ′ и начального предположения x 0 для корня f . Если f удовлетворяет определенным предположениям и начальное предположение близко, то
является лучшим приближением корня, чем x 0 . Геометрически ( x 1 , 0) — это точка пересечения с х касательной графика f в ( x 0 , f ( x 0 )) : то есть улучшенное предположение x 1 является уникальным корнем линейного аппроксимация f при первоначальном предположении, x 0 . Процесс повторяется как
пока не будет достигнуто достаточно точное значение. Количество правильных цифр увеличивается примерно вдвое с каждым шагом. Этот алгоритм является первым в классе методов Хаусхолдера , на смену ему пришел метод Галлея . Метод может быть распространен также на комплексные функции и системы уравнений .
Идея состоит в том, чтобы начать с первоначального предположения, затем аппроксимировать функцию ее касательной линией и, наконец, вычислить точку пересечения с x этой касательной линией. Этот x -перехват обычно будет лучшим приближением к корню исходной функции, чем первое предположение, и метод можно повторить .
Если касательная к кривой f ( x ) в точке x = x n пересекает ось x в точке x n +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 ( Йпма 1995). Частный случай метода Ньютона для вычисления квадратных корней был известен с древних времен и часто называется вавилонским методом .
Метод Ньютона использовался японским математиком 17-го века Секи Кова для решения уравнений с одной переменной, хотя связь с исчислением отсутствовала. [1]
Метод Ньютона был впервые опубликован в 1685 году в «Трактате об алгебре, как исторической, так и практической», написанном Джоном Уоллисом . [2] В 1690 году Джозеф Рафсон опубликовал упрощенное описание в Analysis aequationum Universalis . [3] Рафсон также применил этот метод только к полиномам, но избежал утомительного процесса переписывания Ньютона, извлекая каждую последующую поправку из исходного полинома. Это позволило ему получить многократно используемое итеративное выражение для каждой проблемы. Наконец, в 1740 году Томас Симпсон описал метод Ньютона как итерационный метод решения общих нелинейных уравнений с помощью исчисления, по сути дав описание, приведенное выше. В той же публикации Симпсон также дает обобщение на системы двух уравнений и отмечает, что метод Ньютона можно использовать для решения задач оптимизации, установив градиент равным нулю.
Артур Кэли в 1879 году в книге «Воображаемая задача Ньютона – Фурье» первым заметил трудности при обобщении метода Ньютона на комплексные корни многочленов со степенью больше 2 и комплексными начальными значениями. Это открыло путь к изучению теории итераций рациональных функций.
Метод Ньютона — мощный метод: как правило, сходимость является квадратичной: по мере того, как метод сходится к корню, разница между корнем и приближением возводится в квадрат (количество точных цифр примерно удваивается) на каждом шаге. Однако метод имеет некоторые трудности.
Метод Ньютона требует, чтобы производная могла быть вычислена напрямую. Аналитическое выражение для производной может быть нелегко получить, или его оценка может оказаться дорогостоящей. В таких ситуациях может оказаться целесообразным аппроксимировать производную, используя наклон линии, проходящей через две близлежащие точки функции. Использование этого приближения приведет к чему-то вроде метода секущих , сходимость которого медленнее, чем у метода Ньютона.
Важно просмотреть доказательство квадратичной сходимости метода Ньютона перед его применением. В частности, следует рассмотреть предположения, сделанные при доказательстве. В ситуациях, когда метод не сходится, это происходит потому, что предположения, сделанные в этом доказательстве, не выполняются.
Если первая производная ведет себя некорректно вблизи определенного корня, метод может промахнуться и отклониться от этого корня. Примером функции с одним корнем, для которой производная ведет себя не очень хорошо вблизи корня, является
для которого корень будет пропущен и последовательность x будет расходиться. Для = _1/2, корень все равно будет пропущен, но последовательность будет колебаться между двумя значениями. Для1/2< a < 1 , корень все равно будет промахиваться, но последовательность будет сходиться, а при a ≥ 1 корень вообще не будет промахиваться.
В некоторых случаях метод Ньютона можно стабилизировать, используя последовательное чрезмерное расслабление , или можно увеличить скорость сходимости, используя тот же метод.
Если встречается стационарная точка функции, производная равна нулю, и метод завершится из-за деления на ноль .
Большая ошибка в первоначальной оценке может способствовать несходимости алгоритма. Чтобы преодолеть эту проблему, часто можно линеаризовать оптимизируемую функцию с помощью исчисления, журналов, дифференциалов или даже с помощью эволюционных алгоритмов, таких как стохастическое туннелирование . Хорошие первоначальные оценки близки к окончательной глобально оптимальной оценке параметров. В нелинейной регрессии сумма квадратов ошибок (SSE) «близка» к параболе только в области окончательных оценок параметров. Найденные здесь первоначальные оценки позволят методу Ньютона–Рафсона быстро сходиться. Только здесь матрица Гессе СУС положительна, а первая производная СУС близка к нулю.
В надежной реализации метода Ньютона принято устанавливать ограничения на количество итераций, привязывать решение к интервалу, который, как известно, содержит корень, и комбинировать этот метод с более надежным методом поиска корня.
Если искомый корень имеет кратность больше единицы, скорость сходимости является просто линейной (ошибки уменьшаются в постоянном коэффициенте на каждом шаге), если не предпринимаются специальные шаги. Когда есть два или более корня, расположенных близко друг к другу, может потребоваться много итераций, прежде чем итерации подойдут достаточно близко к одному из них, чтобы квадратичная сходимость стала очевидной. Однако, если кратность m корня известна, следующий модифицированный алгоритм сохраняет квадратичную скорость сходимости: [4]
Это эквивалентно использованию последовательного чрезмерного расслабления . С другой стороны, если кратность m корня неизвестна, можно оценить m после проведения одной или двух итераций, а затем использовать это значение для увеличения скорости сходимости.
Если кратность m корня конечна, то g ( x ) =е ( х )/ж ′ ( Икс )будет иметь корень в том же месте с кратностью 1. Применение метода Ньютона для нахождения корня g ( x ) восстанавливает квадратичную сходимость во многих случаях, хотя обычно это включает в себя вторую производную f ( x ) . В особенно простом случае, если f ( x ) = x m , то g ( x ) =Икс/ма метод Ньютона находит корень за одну итерацию с
Предположим, что функция f имеет нуль в точке α , т.е. f ( α ) = 0 , и f дифференцируема в окрестности точки α .
Если f непрерывно дифференцируема и ее производная не равна нулю в точке α , то существует окрестность точки α такая , что для всех начальных значений x 0 в этой окрестности последовательность ( x n ) будет сходиться к α . [5]
Если f непрерывно дифференцируема, ее производная отлична от нуля в точке α и имеет вторую производную в точке α , то сходимость является квадратичной или более быстрой. Если вторая производная не равна 0 в точке α , то сходимость просто квадратичная. Если третья производная существует и ограничена в окрестности точки α , то:
где
Если производная равна 0 при α , то сходимость обычно только линейная. В частности, если f дважды непрерывно дифференцируема, f ′ ( α ) = 0 и f ″ ( α ) ≠ 0 , то существует окрестность α такая, что для всех начальных значений x 0 в этой окрестности последовательность итераций сходится линейно, со скоростью 1/2. [6] Альтернативно, если f ′ ( α ) = 0 и f ′ ( x ) ≠ 0 для x ≠ α , x в окрестности U точки α , α является нулем кратности r , и если f ∈ C r ( U ) , то существует окрестность точки α такая, что для всех начальных значений x 0 в этой окрестности последовательность итераций сходится линейно.
Однако даже линейная конвергенция не гарантируется в патологических ситуациях.
На практике эти результаты локальны, и окрестность сходимости заранее не известна. Но есть также некоторые результаты о глобальной сходимости: например, для правой окрестности U + точки α , если f дважды дифференцируема в U + и если f ′ ≠ 0 , f · f ″ > 0 в U + , то для для каждого x 0 из U + последовательность x k монотонно убывает до α .
Согласно теореме Тейлора , любая функция f ( x ) , имеющая непрерывную вторую производную, может быть представлена разложением относительно точки, близкой к корню f ( x ) . Предположим, что этот корень равен α . Тогда разложение f ( α ) относительно x n будет следующим:
где форма Лагранжа остатка разложения в ряд Тейлора равна
где ξ n находится между x n и α .
Поскольку α является корнем, ( 1 ) становится:
Разделив уравнение ( 2 ) на f ′ ( x n ) и переставив, получим
Помня, что x n + 1 определяется формулой
человек обнаруживает, что
То есть,
Взятие абсолютного значения обеих сторон дает
Уравнение ( 6 ) показывает, что порядок сходимости не ниже квадратичного, если выполняются следующие условия:
где M определяется выражением
Если эти условия выполняются,
Непересекающиеся подмножества бассейнов притяжения — областей действительной числовой линии, внутри каждой из которых итерация из любой точки приводит к одному конкретному корню — могут быть бесконечными по числу и сколь угодно малыми. Например, [7] для функции f ( x ) = x 3 − 2 x 2 − 11 x + 12 = ( x − 4)( x − 1)( x + 3) следующие начальные условия находятся в последовательных бассейнах привлекательности:
Метод Ньютона гарантированно сходится только при выполнении определенных условий. Если предположения, сделанные при доказательстве квадратичной сходимости, выполняются, метод сходится. В следующих подразделах неспособность метода сходиться указывает на то, что предположения, сделанные при доказательстве, не были выполнены.
В некоторых случаях необходимые для сходимости условия на функцию выполняются, но точка, выбранная в качестве начальной, не попадает в интервал сходимости метода. Это может произойти, например, если функция, корень которой ищется, асимптотически приближается к нулю при переходе 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 ) = 2 x и, следовательно,
Таким образом, сходимость не является квадратичной, хотя функция всюду бесконечно дифференцируема.
Подобные проблемы возникают, даже если корень всего лишь «почти» двойной. Например, пусть
Тогда первые несколько итераций, начиная с x 0 = 1 , будут
требуется шесть итераций, чтобы достичь точки, в которой сходимость становится квадратичной.
Если в корне нет второй производной, то сходимость может не быть квадратичной. Позволять
Затем
И
кроме случаев, когда x = 0 , где он не определен. Учитывая x n ,
который имеет примерно4/3раз больше бит точности, чем имеет x n . Это меньше, чем в 2 раза больше, чем потребовалось бы для квадратичной сходимости. Итак, сходимость метода Ньютона (в данном случае) не является квадратичной, хотя: функция всюду непрерывно дифференцируема; производная не равна нулю в корне; и f бесконечно дифференцируема, за исключением желаемого корня.
При работе со сложными функциями метод Ньютона можно применять непосредственно для нахождения их нулей. [8] Каждый нуль имеет зону притяжения в комплексной плоскости, набор всех начальных значений, которые заставляют метод сходиться к этому конкретному нулю. Эти наборы можно сопоставить, как показано на изображении. Для многих сложных функций границы бассейнов притяжения являются фракталами .
В некоторых случаях на комплексной плоскости есть области, которые не входят ни в один из этих бассейнов притяжения, что означает, что итерации не сходятся. Например, [9] если использовать вещественное начальное условие для поиска корня из x 2 + 1 , все последующие итерации будут действительными числами, и поэтому итерации не могут сходиться ни к одному из корней, поскольку оба корня недействительны. В этом случае почти все реальные начальные условия приводят к хаотическому поведению , а некоторые начальные условия повторяются либо до бесконечности, либо до повторяющихся циклов любой конечной длины.
Курт МакМаллен показал, что для любого возможного чисто итерационного алгоритма, подобного методу Ньютона, алгоритм будет расходиться в некоторых открытых областях комплексной плоскости при применении к некоторому многочлену степени 4 или выше. Однако МакМаллен дал общесходящийся алгоритм для полиномов степени 3. [10] Кроме того, для любого полинома Хаббард, Шлейхер и Сазерленд предложили метод выбора набора начальных точек так, что метод Ньютона обязательно сходится в одной из них. по меньшей мере. [11]
Можно также использовать метод Ньютона для решения систем k уравнений, который сводится к нахождению (одновременных) нулей k непрерывно дифференцируемых функций. Это эквивалентно нахождению нулей одной вектор-функции. В приведенной выше формулировке скаляры x n заменяются векторами x n , и вместо деления функции f ( x n ) на ее производную f ′ ( x n ) вместо этого нужно умножить функцию F ( x n ) на обратную ее матрицу Якоби k × k . J F ( Икс п ) . Это приводит к выражению
Вместо того, чтобы фактически вычислять обратную матрицу Якоби, можно сэкономить время и повысить численную стабильность, решив систему линейных уравнений
для неизвестного Икс п + 1 - Икс п .
k -мерный вариант метода Ньютона также можно использовать для решения систем, состоящих из более чем k (нелинейных) уравнений, если в алгоритме используется обобщенная обратная неквадратная матрица Якоби J + = ( J T J ) −1 J T вместо обратного J . Если нелинейная система не имеет решения, метод пытается найти решение в смысле нелинейного метода наименьших квадратов . Для получения дополнительной информации см. Алгоритм Гаусса – Ньютона .
Другим обобщением является метод Ньютона, позволяющий найти корень функционала F , определенного в банаховом пространстве . В этом случае формулировка
где F ′ ( X n ) — производная Фреше , вычисленная в точке X n . Для применимости метода необходимо, чтобы производная Фреше была ограниченно обратимой при каждом X n . Условие существования и сходимости к корню дает теорема Ньютона–Канторовича . [12]
В 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 ), поскольку они имеют одинаковые корни.
Пусть x0 = b — правый конец интервала, а z0 = a — левый конец интервала. Учитывая x n , определите
это просто метод Ньютона, как и раньше. Затем определите
где знаменатель равен f ′ ( x n ) , а не f ′ ( z n ) . Итерации x n будут строго убывать к корню, а итерации z n будут строго возрастать к корню. Также,
так что расстояние между x n и z n уменьшается квадратично.
Когда якобиан недоступен или слишком дорог для вычисления на каждой итерации, можно использовать метод квазиньютона .
Метод Ньютона можно обобщить с помощью q -аналога обычной производной. [13]
Нелинейное уравнение вообще имеет несколько решений. Но если начальное значение не подходит, метод Ньютона может не сходиться к желаемому решению или может сходиться к тому же решению, найденному ранее. Когда мы уже нашли N решений уравнения , то следующий корень можно найти, применив метод Ньютона к следующему уравнению: [14] [15]
Этот метод применяется для получения нулей функции Бесселя второго рода. [16]
Модифицированный метод Ньютона Хирано представляет собой модификацию, сохраняющую сходимость метода Ньютона и позволяющую избежать нестабильности. [17] Он разработан для решения комплексных полиномов.
Сочетание метода Ньютона с интервальной арифметикой очень полезно в некоторых контекстах. Это обеспечивает более надежный критерий остановки, чем обычные (которые представляют собой малое значение функции или небольшое изменение переменной между последовательными итерациями). Кроме того, это может выявить случаи, когда метод Ньютона сходится теоретически, но расходится численно из-за недостаточной точности операций с плавающей запятой (обычно это происходит для полиномов большой степени, когда очень небольшое изменение переменной может резко изменить значение функции ; см. полином Уилкинсона ). [18] [19]
Рассмотрим f → C 1 ( X ) , где X — действительный интервал, и предположим, что у нас есть интервальное расширение F ′ для f ′ , что означает, что F ′ принимает в качестве входных данных интервал Y ⊆ X и выводит интервал F ′ ( Y ) такой, что:
Мы также предполагаем, что 0 ∉ F ′ ( X ) , поэтому, в частности, f имеет не более одного корня в X. Затем мы определяем интервальный оператор Ньютона следующим образом:
где м € Y . Обратите внимание, что гипотеза о F ′ подразумевает, что N ( Y ) корректно определен и является интервалом ( более подробную информацию об интервальных операциях см. В интервальной арифметике ). Это естественным образом приводит к следующей последовательности:
Теорема о среднем значении гарантирует, что если есть корень f в X k , то он также находится в X k + 1 . Более того, гипотеза о F' гарантирует, что X k + 1 не превышает половины размера X k , когда m является средней точкой Y , поэтому эта последовательность сходится к [ x* , x* ] , где x* является корнем е в X. _
Если F ′ ( X ) строго содержит 0, использование расширенного интервального разделения приводит к объединению двух интервалов для N ( X ) ; поэтому множественные корни автоматически разделяются и ограничиваются.
Метод Ньютона можно использовать для нахождения минимума или максимума функции f ( x ) . Производная равна нулю в минимуме или максимуме, поэтому локальные минимумы и максимумы можно найти, применив к производной метод Ньютона. Итерация становится:
Важным применением является деление Ньютона-Рафсона , которое можно использовать для быстрого нахождения обратного числа a , используя только умножение и вычитание, то есть число x такое, что1/Икс= а . Мы можем перефразировать это как поиск нуля f ( x ) =1/Икс− а . У нас есть f ′ ( x ) = −1/х 2.
Итерация Ньютона
Следовательно, итерация Ньютона требует всего двух умножений и одного вычитания.
Этот метод также очень эффективен для вычисления мультипликативного обратного степенного ряда .
Многие трансцендентные уравнения можно решить с любой точностью, используя метод Ньютона.
Когда метод Ньютона может быть применен к трансцендентному уравнению и сходится к решению уравнения, это означает, что решение представляет собой вычислимое число , которое точно представляется парой, образованной начальным приближением и алгоритмом повышения точности любого приближение.
Метод Ньютона применяется к отношению функций Бесселя, чтобы получить его корень. [20]
Численная проверка решений нелинейных уравнений была установлена путем многократного использования метода Ньютона и формирования набора кандидатов на решение. [21] [22]
Рассмотрим задачу нахождения квадратного корня из числа a , то есть такого положительного числа x , что x 2 = a . Метод Ньютона — один из многих методов вычисления квадратных корней . Мы можем перефразировать это как поиск нуля f ( x ) знак равно x 2 - a . У нас ж ′ ( Икс ) знак равно 2 Икс .
Например, для нахождения квадратного корня из 612 с начальным предположением x 0 = 10 последовательность, заданная методом Ньютона, следующая:
где правильные цифры подчеркнуты. Всего за несколько итераций можно получить решение с точностью до многих десятичных знаков.
Перестановка формулы следующим образом дает вавилонский метод нахождения квадратных корней :
т.е. среднее арифметическое предположения, x n иа/х н.
Рассмотрим задачу нахождения положительного числа x с cos x = x 3 . Мы можем перефразировать это как поиск нуля f ( x ) = cos ( x ) − x 3 . У нас есть ж ′ ( Икс ) знак равно - грех ( Икс ) - 3 Икс 2 . Поскольку cos( x ) ≤ 1 для всех x и x 3 > 1 для x > 1 , мы знаем, что наше решение лежит между 0 и 1.
Например, при исходном предположении x 0 = 0,5 последовательность, заданная методом Ньютона, следующая (обратите внимание, что начальное значение 0 приведет к неопределенному результату, что показывает важность использования начальной точки, близкой к решению):
В приведенном выше примере правильные цифры подчеркнуты. В частности, x 6 соответствует 12 десятичным знакам. Мы видим, что количество правильных цифр после запятой увеличивается с 2 (для x 3 ) до 5 и 10, иллюстрируя квадратичную сходимость.
Ниже приведен пример реализации метода Ньютона на языке программирования Python (версия 3.x) для поиска корня функции, f
которая имеет производную f_prime
.
Первоначальное предположение будет x 0 = 1 , а функция будет f ( x ) = x 2 − 2 , так что f ′ ( x ) = 2 x .
Каждую новую итерацию метода Ньютона будем обозначать x1
. Во время вычислений мы проверим, не yprime
становится ли знаменатель ( ) слишком маленьким (меньше epsilon
), что было бы в том случае, если f ′ ( x n ) ≈ 0 , поскольку в противном случае может быть внесено большое количество ошибок.
защита f ( х ): вернуть x ** 2 - 2 # f(x) = x^2 - 2защита f_prime ( x ):вернуть 2 * x # f'(x) = 2xdef newtons_method ( x0 , f , f_prime , толерантность , эпсилон , max_iterations ): """Метод Ньютона Аргументы: x0: первоначальное предположение f: функция, корень которой мы пытаемся найти. f_prime: производная функции допуск: Остановиться, когда итерации изменятся меньше этого значения. эпсилон: не делите на число меньше этого max_iterations: максимальное количество итераций для вычисления. """ для i в диапазоне ( max_iterations ): у = ж ( х0 ) yprime = f_prime ( x0 ) if abs ( yprime ) < epsilon : # Откажитесь, если знаменатель слишком мал перерыв x1 = x0 - y / yprime # Выполняем вычисления Ньютона if abs ( x1 - x0 ) <= допуск : # Остановитесь, когда результат окажется в пределах желаемого допуска return x1 # x1 — решение в пределах допуска и максимального количества итераций x0 = x1 # Обновите x0, чтобы начать процесс заново return None # Метод Ньютона не сходился
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )