Численные методы (стр. 1 )

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

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

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

Омск

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

УДК 519.61(075)

ББК 22.193я73

К 73

Рецензенты:

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

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

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

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

ISBN 0898-8

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

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

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

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

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

УДК 519.61(075)

ББК 22.193я73

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

1. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

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

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

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

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

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

Рис. 1

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

1.2. Основные этапы отыскания решения

В процессе приближенного отыскания корней уравнения обычно выделяют два этапа: локализация (или отделение) корня и уточнение корня.

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

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

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

1.3. Метод половинного деления

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

Разделим отрезок пополам. Получим точку . Вычислим значение функции в этой точке: . Если , то – искомый корень, и задача решена. Если , то – число определённого знака: либо . Тогда либо на концах отрезка , либо на концах отрезка значения функции имеют разные знаки. Обозначим такой отрезок . Очевидно, что и длина отрезка в два раза меньше, чем длина отрезка . Поступим аналогично с отрезком . В результате получим либо корень , либо новый отрезок и т. д. (рис. 2).

Рис. 2

Середина -го отрезка . Очевидно, что длина отрезка будет равна , а так как , то

. (1)

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

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

.

Следовательно, не позднее 6-го деления найдем с требуемой точностью, . Результаты вычислений представлены в таблице 1.

Таблица 1

	0	1	2	3	4	5	6
	1,0000	1,0000	1,0000	1,1250	1,1250	1,1406	1,1406
	2,0000	1,5000	1,2500	1,2500	1,1875	1,1875	1,1562
	1,5000	1,2500	1,1250	1,1875	1,1406	1,1562	1,1484
Зн	-	-	-	-	-	-	-
Зн	+	+	+	+	+	+	+
	5,5938	0,7585	-0,2959	0,1812	-0,0691	0,0532	-0,0078
–	1,0000	0,5000	0,2500	0,1250	0,0625	0,0312	0,0156

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

Пусть уравнение можно заменить эквивалентным ему уравнением

. (2)

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

. (3)

Формула (3) является расчетной формулой метода простой итерации.

Если последовательность сходится при , т. е. существует

(4)

и функция непрерывна, то, переходя к пределу в (3) и учитывая (4), получим: .

Таким образом, , следовательно, – корень уравнения (2).

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

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

1) процесс итерации сходится независимо от начального значения ;

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

Доказательство. Так как и , то можно записать

.

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

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

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

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

или и тогда .

Вывод неравенства. Рассмотрим два последовательных приближения: и . Отсюда .

Используя теорему о среднем, получим:

,

тогда на основании условия можно записать: