Численные методы нахождения корней уравнения

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  100 Минут в мнр что это

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Alcatel one touch 808

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

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

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

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

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

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

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

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

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

Примеры приближенных решений нелинейных уравнений онлайн

Задача 1. Методом бисекции найти решение нелинейного уравнения на отрезке $[a;b]$ с точностью $varepsilon = 10^<-2>$. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью $varepsilon=10^<-4>$. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.

Задача 2. Отделить корни нелинейного уравнения аналитически $2 arcctg x -x+3=0$.

Задача 3. Отделить корни нелинейного уравнения аналитически и уточнить один из них методом проб с точностью до 0,01. $$3x^4-8x^3-18x^2+2=0.$$

Задача 4. Отделить корни нелинейного уравнения графически (например, в среде EXCEL) уточнить один из них методом проб с точностью до 0,01. $$x^2-20 sin x =0.$$

Задача 5. Отделите корни уравнения графически и уточните один из них методом хорд с точностью до 0,001. Уточните один из корней этого уравнения методом касательных с точностью до 0,001. $$ sqrt – cos 0.387 x =0.$$

Задача 6.Отделить корни уравнения графически и уточнить один из них методом итераций с точностью до 0,001. $$sqrt=frac<1>.$$

Задача 7. На отрезке $[0;2]$ методом Ньютона найти корень уравнения $-x^3-2x^2-4x+10=0$ с точностью 0,01.

Задача 8. Методом хорд найти отрицательный корень уравнения $x^3-2x^2-4x+7=0$ с точностью 0,0001. Требуется предварительное построение графика функции и отделение корней.

Задача 9. Решить нелинейные уравнения с точностью до 0.001. $$1), x^3-12x-5=0, (x gt 0), , 2), an x -1/x=0. $$

Нахождение корней уравнений – одна из наиболее часто встречающихся задач. Вместе с тем не всегда есть возможность найти аналитическое решение уравнения. В первую очередь это относится к большинству трансцендентных уравнений, т.е. уравнений, в которых неизвестная х находится под знаком трансцендентной функции, например, x 2 – sin 5x = 0.

Читайте также:  Почта майл вход моя страница mail ru

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

Для поиска корней таких уравнений используются численные (приближенные) методы, которые по своей сути являются способами уточнения корней [3-5].

В общем случае запись нелинейного уравнения имеет вида

Задача решения нелинейного уравнения состоит из двух этапов:

1) локализация корней, т.е. определение интервала изоляции (интервала неопределенности), в котором расположен корень;

2) определение с заданной точностью точности ε приближенного значения корня.

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

Теорема: Если непрерывная функция y=f(x) на концах отрезка [a, b] принимает значения разных знаков, т.е. f(a)·f(b)

Блок-схема метода половинного деления представлена на рисунке 12.

Рисунок 12 – Блок-схема алгоритма поиска корней уравнения методом половинного деления

Метод хорд

Идея метода хорд заключается в том, что кривая y=f(x) на участке [a, b] заменяется хордой и в качестве приближенного значения корня х * =xn принимается точка пересечения оси абсцисс с хордой (рисунок 13).

Рисунок 13 – Графическая интерпретация метода хорд

Запишем уравнение хорды, проходящей через точки С с координатами (a, f(a)) и D – (b, f(b)):

.

Абсцисса точки пересечения хорды с осью ОХ находится из этого выражения при y=0, т.е.

.

Выполнив преобразования, получаем выражение для нахождения приближенного корня:

. (35)

Полученное значение xn можно снова использовать для дальнейшего уточнения корня, рассматривая интервал [a, xn] или [xn , b] в зависимости от знака функции в точке xnf(xn).

Если значения функции при х=а и х=xn имеют разные знаки, т.е. выполняется условие

Рисунок 14 – Блок-схема алгоритма поиска корней уравнения методом хорд

Рисунок 15 – Графическая интерпретация метода Ньютона

Для графической иллюстрации (рисунок 15), где начальное приближение находится в точке D, т.е. x=b, запишем:

,

откуда или .

Тогда, в общем виде выражение для нахождения корня можно записать:

Итерационный процесс уточнения корня выполняется до тех пор, пока соблюдается условие

Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения 10 -5 – 10 -6 достигается через 5-6 итераций.

Блок-схема, реализующая метод Ньютона, приведена на рисунке 16.

Рисунок 16 – Блок-схема алгоритма поиска корня уравнения методом Ньютона

Комбинированные методы

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

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

На рисунке 17 приведена блок-схема комбинированного метода хорд-Ньютона.

Рисунок 17 – Блок-схема комбинированного метода хорд-Ньютона

Дата добавления: 2017-02-11 ; просмотров: 3204 | Нарушение авторских прав

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector