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

ЧИСЛЕННЫЕ МЕТОДЫ

Учебное пособие

Омск

Издательство ОмГТУ

УДК 519.61(075)

ББК 22.193я73

К 73

 

 

Рецензенты:

Е. Е. Макаров, к. ф.-м. н. доц., зав. каф «Математическое моделирование» ОмГУ им. Ф.М. Достоевского;

Ю. Б. Никитин, к. ф.-м. н., зав. каф. медицинской биологической физики ОмГМА

 

 

Котюргина, А.С.

К 73 Численные методы: учеб. пособие / А. С. Котюргина. – Омск: Изд-во
ОмГТУ, 2010. – 84 с.

ISBN 978-5-8149-0898-8

 

Данное пособие рассматривает основные разделы курса лекций по вычислительной математике, читаемых на потоках ИВТ-2 и Риб-3.

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

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

 

Печатается по решению редакционно-издательского совета

Омского госу­дар­ственного технического университета

 

УДК 519.61(075)

ББК 22.193я73

 

ISBN 978-5-8149-0898-8 © ГОУ ВПО «Омский государственный

технический университет», 2010

ВВЕДЕНИЕ

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

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

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

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

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

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

Пример 3.

Применим метод простой итерации для решения системы уравнений

.

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

, ,

, .

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

Приведем систему к виду:

Величина равна 0,1179, т. е. выполняется условие и можно пользоваться критерием окончания итерационного процесса (8). В качестве начального приближения возьмем элементы столбца свободных членов: . Вычисления будем вести до тех пор, пока все величины , , а следовательно, и не станут меньше .

Последовательно вычисляем:

при

при

.

при

.

при

.

Вычисляем модули разностей значений при и :

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

При

.

Вычисляем модули разностей значений при и :

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

.

Для сравнения приведем точные значения переменных:

.

Метод Зейделя

Модификацией метода простой итерации можно считать метод Зейделя.

В методе простой итерации на -ой итерации значения , вычисляются подстановкой в правую часть (6) вычисленных на предыдущей итерации значений. В методе Зейделя при вычислении используются значения , , , уже найденные на -ой итерации, а не , , …, , как в методе простой итерации, т.е. -е приближение строится следующим образом:

(9)

Эти формулы являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

 

и .

 

Матричная запись расчетных формул (9) имеет вид: . Так как , точное решение исходной системы удовлетворяет равенству: .

Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:

. (10)

Неравенство (10) означает, что для сходимости метода Зейделя достаточно, чтобы любая норма матрицы был меньше единицы.

Если выполнено условие (10), то справедлива следующая оценка погрешности:

, (11)

где – норма матрицы .

Критерий окончания. Если требуется найти решение с точностью , итерационный процесс следует закончить, как только на -ом шаге выполнится неравенство: . Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство , где . Если выполняется условие

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

.

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

Пример. Применим метод Зейделя для решения системы уравнений из предыдущего примера. Первые шаги полностью совпадают с процедурой решения по методу простых итераций. Проведем теперь итерации методом Зейделя.

При

.

При вычислении используем уже полученное значение :

.

При вычислении используем уже полученные значения и :

.

При вычислении используем уже полученные значения , , :

.

Аналогичным образом проведем вычисления при и .

Получим:

при

.

при

.

Известны точные значения переменных:

.

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

 

Постановка задачи

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

, иначе .

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

В общем случае для решения систем нелинейных уравнений обычно используются итера­ци­онные методы.

Решение.

1) Начальные приближения можно определить графическим способом. Для этого перепи­шем систему в виде:

Первое из преобразованных уравнений определяет эллипс, а второе – гиперболу. Данная сис­те­ма имеет два решения. Для уточнения выбирают одно из них, принадлежащее области и .

За начальное приближение принимают и .

2) Находим

 

0,5	-0,1052		-8,76	49,32
-0,46	-0,3848		2,76
0,5742	0,0114	2,2968	-8,7306	51,2203
-0,4551	0,0052	5,1484	2,7306
0,5727	0,00006	2,2908	-8,7252	51,1375
-0,4542	-0,00011	5,1454	2,7252
0,5727
-0,4542

Поскольку , то .

Окончательный ответ: и .

Сходимость метода

Теорема. Пусть в некоторой замкнутой окрестности имеется одно и толь­ко одно решение и приведенной системы.

Тогда если:

1) функции и определены и непрерывно дифференцируемы в ;

2) начальные приближения , и все последующие приближения , при­над­лежат ;

3) в выполнены неравенства или

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

Оценка погрешности -го приближения определяется неравенством:

,

где – наибольшее из чисел и , входящих в эти неравенства.

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

Пример. Методом итерации решить систему с точностью до .

Решение.

1) Приведем систему к форме:

 

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

3) Проверим приведенную систему на сходимость итерационного процесса:

Следовательно,

и т.е. условия сходимости выполняются.

 

4) Для поиска последовательных приближений используют формулы:

Выберем следующие начальные значения: .

 

	0,15	0,1616	0,1508	0,1539	0,1510	0,1519	0,1510
	-2	-2,035	-2,0245	-0,0342	-2,0313	-2,0341	-2,0333

Поскольку , то и .

ПРИБЛИЖЕНИЕ ФУНКЦИЙ

Метод наименьших квадратов

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

Рис. 12

 

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

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

Получим систему уравнений

или , .

Эту систему уравнений перепишем в следующем виде:

, .

Введем обозначения: . Последняя система может быть записана так: , .

Её можно переписать в развернутом виде:

.

 

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

Погрешность приближения в соответствии с исходной формулой составит

. Рассмотрим частные случаи и .

Линейная аппроксимация .

.

;

, .

Отсюда система для нахождения коэффициентов имеет вид:

.

Её можно решить методом Крамера.

Квадратичная аппроксимация .

.

.

.

, .

Или в развёрнутом виде

Решение системы уравнений находится по правилу Крамера.

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

	-1

Вычислим коэффициенты по формулам для линейной и квадратичной аппроксимация ; .

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

.

Решая эту систему, получим:

.

.

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

.

И коэффициенты равны:

. Тогда

.

Сравним значения, рассчитанные для функциональной зависимости, с исходными данными. Результаты приведены в табл. 3.

Таблица 3

	-1
	-1	0,7	2,4	4,1	5,8
	-1	0,62	2,24		6,9

Погрешность приближения в соответствии с исходными формулами составит:

.

.

Многочлен Лагранжа

Будем искать многочлен в виде линейной комбинации множеств степени : .

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

.

Действительно, . При числитель выражения равен 0. По аналогии получим:

,

.

Подставив эти формулы в исходный многочлен, получим:

.

Эта формула называется интерполяционным многочленом Лагранжа.

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

.

Решение. Составим таблицу

х	-2	-4/3		4/3
у

 

Подставляя эти значения в формулу Лагранжа, получим:

Если функция непрерывно дифференцируема до -го порядка включительно, то остаточный член интерполяционного многочлена в форме Лагранжа имеет вид

,

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

 

Решение.

х	у
	1,6990
		0,0414
	1,7404		-0,0036
		0,0378		0,0005
	1,7782		-0,0031
		0,0347
	1,8129

 

Здесь ; .

Вычисляя погрешность, получим:

.

 

Действительно, .

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

Постановка задачи Коши

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

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

Рис. 13

 

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

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

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

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

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

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

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

Численный метод решения задачи Коши называется сходящимся, если для него при . Говорят, что метод имеет -ый порядок точности, если для погрешности справедлива оценка , – константа, .

Метод Эйлера

Простейшим методом решения задачи Коши является метод Эйлера. Будем решать задачу Коши

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

Эти формулы и начальное условие являются расчетными формулами метода Эйлера.

Геометрическая интерпретация одного шага метода Эйлера заключается в том, что решение на отрезке заменяется касательной , проведенной в точке к интегральной кривой, проходящей через эту точку. После выполнения шагов неизвестная интегральная кривая заменяется ломаной линией (ломаной Эйлера).

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

Теорема. Пусть функция удовлетворяет условиям:

.

Тогда для метода Эйлера справедлива следующая оценка погрешности: , где – длина отрезка . Мы видим, что метод Эйлера имеет первый порядок точности.

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

.