Метод ньютона для решения нелинейных уравнений кратко

Обновлено: 30.06.2024

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

Поскольку левые части этих выражений должны обращаться в нуль, то можно приравнять к нулю и правые части:

в матричном виде:

Значения и их производные вычисляются при .

Определителем последней системы является якобиан:

Для существования единственного решения системы якобиан должен быть отличным от нуля на каждой итерации.

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

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

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

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

Предположим, что якобиан системы при и отличен от нуля:

Тогда значения и можно найти, используя матричный способ следующим образом:

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

Величины, стоящие в правой части, вычисляются при и .

Критерий окончания. Будем считать, что заданная точность достигнута, если или .

Пример.Методом Ньютона решить систему двух уравнений:

с точностью до 0,001.

Поскольку левые части этих выражений должны обращаться в нуль, то можно приравнять к нулю и правые части:

в матричном виде:

Значения и их производные вычисляются при .

Определителем последней системы является якобиан:

Для существования единственного решения системы якобиан должен быть отличным от нуля на каждой итерации.

Предположим, что якобиан системы при и отличен от нуля:

Тогда значения и можно найти, используя матричный способ следующим образом:

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

Величины, стоящие в правой части, вычисляются при и .

Критерий окончания. Будем считать, что заданная точность достигнута, если или .

где f(x) — заданная алгебраическая или трансцендентная функция.

Решить уравнение — значит найти все его корни, то есть те значения x , которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня x_ПP , которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε , то есть

│x* – x_пр │ ε также называют допустимой ошибкой , которую можно задать по своему усмотрению.

Этапы приближенного решения нелинейных уравнений

Приближенное решение уравнения состоит из двух этапов:

Отделение корней, то есть нахождение интервалов из области определения функции f(x) , в каждом из которых содержится только один корень уравнения f(x)=0 .
Уточнение корней до заданной точности.

Отделение корней

Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x) . Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.

Для примера рассмотрим задачу решения уравнения

где угол x задан в градусах. Указанное уравнение можно переписать в виде

Для графического отсечения корней достаточно построить график функции

Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8) .

Аналитическое отделение корней

Аналитическое отделение корней основано на следующих теоремах.
Теорема 1 . Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е.

то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2 . Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0 .

Уточнение корней

Для уточнения корней может использоваться один из следующих методов:

Метод последовательных приближений (метод итераций)

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

Функцию f(x) называют сжимающим отображением .

Последовательность чисел x₀, x₁ ,…, x_n называется итерационной , если для любого номера n>0 элемент x_n выражается через элемент x_n-1 по рекуррентной формуле

а в качестве x₀ взято любое число из области задания функции f(x) .

Реализация на C++ для рассмотренного выше примера

Уравнение может быть записано в форме

Метод Ньютона (метод касательных)

Если известно начальное приближение x₀ корня уравнения f(x)=0, то последовательные приближения находят по формуле

Графическая интерпретация метода касательных имеет вид

Реализация на C++
Для заданного уравнения

производная будет иметь вид

Результат выполнения

Метод секущих (метод хорд)

Если x₀ , x₁ - приближенные значения корня уравнения f(x) = 0 и выполняется условие

то последующие приближения находят по формуле

Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(x) = 0 производят по формулам:

Геометрическая интерпретация метода хорд:

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

Результат выполнения

Метод половинного деления (метод дихотомии)

Если x₀ , x₁ - приближенные значения корня уравнения f(x) = 0 и выполняется условие

то последующие приближения находятся по формуле

и вычисляется f(x_i) . Если f(x_i)=0 , то корень найден. В противном случае из отрезков выбирается тот, на концах которого f(x) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.

Геометрическая интерпретация метода дихотомии

Реализация на C++

Результат выполнения

Для численного поиска решения также можно использовать генетические алгоритмы.

Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной

Информация о материале Обновлено: 11.05.2017, 19:45 Категория: Системы уравнений и задачи оптимизации

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

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas ( лат .О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum ( лат.Метод флюксий и бесконечные ряды) или Geometria analytica ( лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения x_n , а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений x_n вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.

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

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

Рис.1 . График изменение функции

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

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

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

Математическое обоснование

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

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

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

Производная сжимающего отображения определяется в следующем виде:

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

С учетом этого сжимающая функция прием следующий вид:

Таким образом, алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной

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

2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

3. Проверяем приближенное значение корня на предмет заданной точности, в случае:

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

- если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений

по методу Ньютона для уравнения с одной переменной

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

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

Рис.2 . Результаты расчета по методу Ньютона для уравнения с одной переменной

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

Рис.3 . Листинг программы в MathCad

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

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

Упрощенный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’( x_n ) в точке x_n в формуле на производную f’(x₀) в точке x₀. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:

Таким образом, на каждом шаге расчета строятся прямые , которые параллельны касательной к кривой y=f(x) в точке B₀ (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.

Разностный метод Ньютона

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

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

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

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

Ищется решение нелинейного уравнения $$ \begin \tag f(x) = 0, \end $$ где $ f(x) $ — заданная функция. Корни уравнения (1) могут быть комплексными и кратными. Выделяют как самостоятельную проблему разделения корней, когда проводится выделение области в комплексной плоскости, содержащей один корень. После этого на основе тех или иных итерационных процессов при выбранном начальном приближении находится решение нелинейного уравнения (1).

В более общем случае мы имеем не одно уравнение (1), а систему нелинейных уравнений $$ \begin \tag f_i(x_1, x_2, \ldots, x_n) = 0, \quad i = 1, 2, \ldots n. \end $$ Обозначим через $ \mathbf = (x_1, x_2, \ldots, x_n) $ вектор неизвестных и определим вектор-функцию $ \mathbf(\mathbf) = (f_1(\mathbf), f_2(\mathbf), \ldots, f_n(\mathbf)) $. Тогда система (2) записывается в виде $$ \begin \tag \mathbf(\mathbf) = 0. \end $$ Частным случаем (3) является уравнение (1) ($ n = 1 $). Второй пример (3) — система линейных алгебраических уравнений, когда $ \mathbf (\mathbf) = A \mathbf - \mathbf $.

Решение нелинейных уравнений

При итерационном решении уравнений (1), (3) задается некоторое начальное приближение, достаточно близкое к искомому решению $ x^* $. В одношаговых итерационных методах новое приближение $ x_ $ определяется по предыдущему приближению $ x_k $. Говорят, что итерационный метод сходится с линейной скоростью, если $ x_ - x^* = O(x_k - x^*) $ и итерационный метод имеет квадратичную сходимость, если $ x_ - x^* = O(x_k - x^*)^2 $.

В итерационном методе Ньютона (методе касательных) для нового приближения имеем $$ \begin \tag x_ = x_k + \frac, \quad k = 0, 1, \ldots, \end $$

Вычисления по (4) проводятся до тех пор, пока $ f(x_k) $ не станет близким к нулю. Более точно, до тех пор, пока $ |f_(x_k)| > \varepsilon $, где $ \varepsilon $ — малая величина.

Простейшая реализация метода Ньютона может выглядеть следующим образом:

Чтобы найти корень уравнения $ x^2 = 9 $ необходимо реализовать функции

Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение $ \tanh(x) = 0 $, точное решение которого $ x = 0 $. Если $ |x_0| \leq 1.08 $, то метод сходится за шесть итераций.

Теперь зададим $ x_0 $ близким к $ 1.09 $. Возникнет переполнение

Возникнет деление на ноль, так как для $ x_7 = -126055892892.66042 $ значение $ \tanh(x_7) $ при машинном округлении равно $ 1.0 $ и поэтому $ f^\prime(x_7) = 1 - \tanh(x_7)^2 $ становится равной нулю в знаменателе.

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

Еще один недостаток функции naive_Newton заключается в том, что функция f(x) вызывается в два раза больше, чем необходимо.

обрабатывать деление на ноль
задавать максимальное число итераций в случае расходимости метода
убрать лишний вызов функции f(x)

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

При реализации метода Ньютона нужно знать аналитическое выражение для производной $ f^\prime(x) $. Python содержит пакет SymPy, который можно использовать для создания функции dfdx . Для нашей задачи это можно реализовать следующим образом:

Решение нелинейных систем

Идея метода Ньютона для приближенного решения системы (2) заключается в следующем: имея некоторое приближение $ \pmb^ $, мы находим следующее приближение $ \pmb^ $, аппроксимируя $ \pmb(\pmb^) $ линейным оператором и решая систему линейных алгебраических уравнений. Аппроксимируем нелинейную задачу $ \pmb(\pmb^) = 0 $ линейной $$ \begin \tag \pmb(\pmb^) + \pmb(\pmb^)(\pmb^ - \pmb^) = 0, \end $$ где $ \pmb(\pmb^) $ — матрица Якоби (якобиан): $$ \pmb(\pmb^) = \begin \frac<\partial f_1(\pmb^)> <\partial x_1>& \frac<\partial f_1(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_1(\pmb^)> <\partial x_n>\\ \frac<\partial f_2(\pmb^)> <\partial x_1>& \frac<\partial f_2(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_2(\pmb^)> <\partial x_n>\\ \vdots & \vdots & \ldots & \vdots \\ \frac<\partial f_n(\pmb^)> <\partial x_1>& \frac<\partial f_n(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_n(\pmb^)> <\partial x_n>\\ \end $$ Уравнение (5) является линейной системой с матрицей коэффициентов $ \pmb $ и вектором правой части $ -\pmb(\pmb^) $. Систему можно переписать в виде $$ \pmb(\pmb^)\pmb = - \pmb(\pmb^), $$ где $ \pmb = \pmb^ - \pmb^ $.

Таким образом, $ k $-я итерация метода Ньютона состоит из двух стадий:

1. Решается система линейных уравнений (СЛАУ) $ \pmb(\pmb^)\pmb = -\pmb(\pmb^) $ относительно $ \pmb $.

2. Находится значение вектора на следующей итерации $ \pmb^ = \pmb^ + \pmb $.

Для решения СЛАУ можно использовать приближенные методы. Можно также использовать метод Гаусса. Пакет numpy содержит модуль linalg , основанный на известной библиотеке LAPACK, в которой реализованы методы линейной алгебры. Инструкция x = numpy.linalg.solve(A, b) решает систему $ Ax = b $ методом Гаусса, реализованным в библиотеке LAPACK.

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

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

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

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

Дано нелинейное уравнение:

$\varepsilon$

Найти корень на интервале [a,b] с точностью .

Метод Ньютона основан на замене исходной функции f(x) , на каждом шаге поиска касательной, проведенной к этой функции. Пересечение касательной с осью Х дает приближение корня (Рис. 4.8).

Выберем начальную точку x₀=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x₁ .

Читайте также: