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

 

Пусть дано уравнение

,                               (7.5.2)

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

Будем предполагать, что уравнение (7.5.2) имеет лишь изолированные корни, т.е. такие корни , для которых существует окрестность, не содержащая других корней этого уравнения.

Численное решение уравнения (7.5.2) обычно проводят в два этапа:

1) отделение корней – определение таких интервалов изменения переменной , где находится только один корень;

2) определение корня уравнения с заданной точностью .

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

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

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

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

,

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

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

,

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

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

которая является нулем функции

.

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

,

где  – очередная точка деления отрезка на два. Эти же критерии можно использовать и для определения начального приближения .

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

,

каждую из которых можно достаточно просто изобразить графически. Тогда за  принимают абсциссу точки пресечения функций  и .

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

 

Метод простой итерации

Сначала требуется привести заданное уравнение  к канонической форме:

,                          (7.5.2)

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

Пример. Пусть исходное уравнение имеет вид:

.

Функции  канонических форм для этого уравнения будут следующими:

Итерационное правило метода простых итераций имеет вид:

.                      (7.5.3)

Геометрически это правило означает следующее (рис 7.5.1). Точное решение  является точкой пересечения кривой  с биссектрисой . За очередное приближение  берется точка, значение которой равно . Это значение получается следующим образом: на кривой  отмечается точка с координатами  и проводится прямая параллельная оси абсцисс до пересечения с биссектрисой. Учитывая, что биссектриса – это множество точек, равноудаленных от осей, опускают перпендикуляр на ось абсцисс и находят точку .

 

Рис. 7.5.1

 

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

Теорема. Пусть выполняются условия:

1) функция  определена на отрезке ;

2) непрерывна там и удовлетворяет условию Липшица с коэффициентом , меньшим единицы, т.е. для любых точек :

;                 (7.5.4)

3) для начального значения  верно неравенство:

;                        (7.5.5)

4) для чисел  и  выполнено требование:

.                              (7.5.6)

Тогда

1) уравнение  на отрезке  имеет решение;

2) итерационная последовательность приближений  может быть построена, принадлежит отрезку  и является сходящейся, т.е. , при этом  является решением уравнения ;

3) для  выполняется неравенство:

,                           (7.5.7)

которое характеризует скорость сходимости метода простой итерации.

Теорема (о единственности решения). Уравнение  на всяком множестве точек, на котором для  выполняется неравенство

,        (7.5.8)

может иметь не более одного решения.

При практическом применении метода простой итерации часто проверяют достаточные условия сходимости итерационного процесса.

Теорема. Пусть функция  определена и дифференцируема на отрезке , причем все ее значения принадлежат этому отрезку. Тогда, если существует  такое, что

                              (7.5.9)

для всех , то

1) итерационный метод (7.5.3) сходится независимо от начального приближения ;

2) предельное значение  является единственным корнем уравнения  на отрезке .

Замечания.

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

Зависимость погрешности на -м шаге  от погрешности на -м шаге  выражается соотношением

,

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

.

Метод простой итерации является одношаговым, т.е. для построения итерационного правила достаточно одного приближения .

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

,

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

.

Введем следующие обозначения:

.

Тогда параметр  можно определить следующим образом.

1) , при этом ;

2) , при этом .

Действительно, так как , то в первом случае , а во втором .

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

1) метод секущих (правило линейной интерполяции)

 . (7.5.10)

2) метод Стеффенсена

 .    (7.5.11)

 

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

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

Пусть требуется найти точное решение  уравнения  при заданном начальном приближении . Итерационное правило Ньютона имеет вид:

                 (7.5.12)

Геометрически метод Ньютона означает следующее (рис. 7.5.2): точное решение  является точкой пересечения кривой  с осью абсцисс. За очередное приближение  принимается точка пересечения касательной к кривой в точке  с осью абсцисс.

 

Рис. 7.5.2

 

Для проверки сходимости метода Ньютона используются следующие теоремы.

Теорема. Пусть выполнены условия:

1) функция  определена и дважды непрерывно дифференцируема на отрезке , при этом  для всех  на этом отрезке;

2)  и ;

3) ;

4) для  соблюдено условие ;

5) верно неравенство .

Тогда:

1) последовательность  может быть построена и является сходящейся, т.е. ;

2) предельное значение  есть решение уравнения ;

3) верна оценка скорости сходимости:

,

где  – ньютонова последовательность приближений

к меньшему корню  уравнения

,

построенная при .

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

.                (7.5.13)

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

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

,

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

Замечание. Зависимость погрешности на -м шаге  от погрешности на -м шаге  в методе Ньютона выражается соотношением

,

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

Наиболее известными видоизменениями метода Ньютона, которые уменьшают объем вычислений, являются следующие.

1) метод секущих

;        (7.5.14)

2) видоизменение с постоянным значением производной

.          (7.5.15)

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: