Численное решение нелинейных уравнений.

Стр 1 из 5Следующая ⇒

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

Кафедра прикладной математики

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

Часть 1

Методические указания к лабораторным и самостоятельным работам

по курсам «Информатика» и «Вычислительная математика»

Казань

УДК 621.313: 518.6

ББК 32.81

А95 Численные методы. Часть 1: Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». / Сост.: Ф.Г.Ахмадиев, Ф.Г.Габбасов, Р.Ф.Гиззятов, И.В.Маланичев. – Казань: Изд-во Казанск. гос. архитект.-строит. ун-та, 2013. – 34 с.

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

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

Рецензент

Доктор физико-математических наук, профессор КГАСУ

Р.Б.Салимов

УДК 621.313: 518.6

ББК 32.81

ã	Казанский государственный архитектурно-строительный университет, 2013

ã	Ахмадиев Ф.Г., Габбасов Ф.Г., Гиззятов Р.Ф., Маланичев И.В.,

Численное решение нелинейных уравнений.

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

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

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

а) отыскания приближенного значения корня или содержащего его отрезка;

б) уточнения значения до некоторой степени точности.

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

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

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

Для использования этого метода исходное нелинейное уравнение необходимо привести к виду .

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

или . (1.5)

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

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

, ,. .., , k = 1, 2,..., n.

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

Геометрическая интерпретация метода простой итерации. Построим графики функций и . Корнем уравнения является абсцисса пересечения кривой с прямой (рис. 1.9). Взяв в качестве начальной точки , строим ломаную линию. Абсциссы вершин этой ломаной представляют собой последовательные приближения корня . Из рисунка видно, что если на отрезке (рис. 1.9а), то последовательные приближения колеблются около корня. Если же производная (рис. 1.9б), то последовательные приближения сходятся монотонно.


а)	б)
Рис. 1.9. Геометрическая интерпретация метода простой итерации.

Пример 1.4. Решить уравнение на отрезке методом простой итерации c точностью .

Решение. Из условия сходимости (1.5) , при определяем .Пусть .

Подставляя каждый раз новое значение корня в уравнение

получаем последовательность значений:

, но , поэтому продолжаем вычисления.

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

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

Исходные данные	Результаты
A	B	C	D	E
x0	e	M	x	F(x)
	0, 001		0, 683335	0, 002416

Function F(x) F = x ^ 3 + x - 1 End Function Sub program3() x = Cells(2, 1) e = Cells(2, 2) M = Cells(2, 3) 1 xk = x - F(x) / M If Abs(xk - x) > = e Then x = xk: GoTo 1 Cells(2, 4) = xk Cells(2, 5) = F(xk) End Sub

Рис. 1.10. Программа решения уравнения методом простой итерации на языке VBA.

Пример 1.4. Решить уравнение на отрезке методом простой итерации c точностью с помощью программы Excel.

Порядок решения (рис. 1.11).

1) Ввести в ячейки A1: D1 заголовки столбцов.

2) В ячейку A2 – значение начального приближения

3) В ячейку B3 – формулу функции =A2^3+A2-1

4) В ячейку C2 – значение M 5

5) В ячейку A3 – формулу первого приближения =A2-B3/$C$2

6) В ячейку D3 – погрешность =ABS(A3-A2)

7) Выделить ячейки A3: D3 и скопировать формулы в соседние ячейки расположенных ниже строк A4: D4, A5: D5, и т.д. при помощи маркера заполнения. Каждая новая строка содержит результаты очередного приближения.

8) В столбце A найти значение корня, соответствующее заданной точности.

Приближенное решение данного уравнения содержится в ячейке A9 (погрешность в ячейке D9 ).

	A	B	C	D
	x	f(x)	M	погрешность

	0, 8			0, 2
	0, 7376	0, 312		0, 0624
	0, 70982	0, 13889		0, 02777881
	0, 69633	0, 06746		0, 01349237
	0, 68954	0, 03396		0, 00679209
	0, 68606	0, 01738		0, 0034769
	0, 68427	0, 00897		0, 00179463
Рис.1.11. Решение уравнения методом простой итерации с помощью программы Excel.

Метод Гаусса.

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

Рассмотрим систему из трех уравнений с тремя неизвестными:

(2.2)

Система уравнений (2.2) приводится к эквивалентной системе с треугольной матрицей:

(2.3)

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

Процесс приведения системы (2.2) к системе (2.3) называется прямым ходом, а нахождение неизвестных , , из системы (2.3) называется обратным ходом.

Прямой ход исключения: Исключаем из уравнений (II) и (III) системы (2.2). Для этого умножаем уравнение (I) на и складываем со вторым, затем умножаем на и складываем с третьим.

В результате получаем следующую систему:

(2.4)

Из полученной системы (2.4) исключаем . Для этого, умножая новое уравнение на и складывая со вторым уравнением, получим уравнение:

(2.5)

Взяв из каждой системы (2.2), (2.4) и (2.5) первые уравнения, получим систему уравнений с треугольной матрицей.

Обратный ход: Из уравнения (III² ) находим . Из уравнения (II¢ ) находим . Из уравнения (I) находим . Коэффициенты , называются ведущими элементами 1-го и 2-го шагов исключения неизвестных. Они должны быть отличны от нуля. Если они равны нулю, то, меняя местами строки, необходимо на их место вывести ненулевые элементы.

Аналогичным путем методом Гаусса решаются системы уравнений с неизвестными.

Пример 2.1. Решить систему уравнений методом Гаусса:

Решение: Удалить члены с из 2-го и 3-го уравнений можно, вычитая из 2-й строки 1-ую, умноженную на , а из 3-й - первую, умноженную на :

2-я строка делится на :

2-я строка умножается на и вычитается из 3-й:

3-я строка делится на :

Процедура обратного хода дает решение:

; ;

Метод обратной матрицы.

Систему (2.1) можно представить в матричном виде как

где

Решение можно выразить, используя умножение на матрицу , обратную к :

Пример 2.2. Решить систему уравнений методом обратной матрицы с помощью программы Excel:

Порядок решения.

1) Ввести матрицу и вектор в рабочий лист Excel (рис. 2.1).

2) Выделить ячейки для хранения обратной матрицы ; например, ячейки A8: D11.

3) Вызвать мастер функций, в категории «Математические» выбрать функцию вычисления обратной матрицы МОБР. В диалоговом окне аргументов функции заполнить поле ввода «Массив» - указать диапазон ячеек матрицы - в нашем случае A2: D5. Нажать кнопку OK. В первой ячейке выделенного под обратную матрицу диапазона ( A8 ) появится число.

4) Чтобы получить всю обратную матрицу, нажать клавишу F2 для перехода в режим редактирования, а затем одновременно клавиши Ctrl+Shift+Enter. В ячейках A8: D11 появятся значения обратной матрицы .

5) Выделить ячейки для хранения вектора-столбца ; например, ячейки F8: F11.

6) Вызвать мастер функций, в категории «Математические» выбрать функцию матричного умножения МУМНОЖ. В диалоговом окне аргументов функции в поле ввода «Массив1» указать диапазон ячеек матрицы - в нашем случае A8: D11, в поле ввода «Массив2» указать диапазон ячеек вектора - в нашем случае F2: F5. Нажать кнопку OK. В первой ячейке выделенного под результат диапазона ( F8 ) появится число.

7) Чтобы получить весь вектор , нажать клавишу F2 для перехода в режим редактирования, а затем одновременно клавиши Ctrl+Shift+Enter. В ячейках F8: F11 появятся значения решения системы уравнений:

; ; ;

	A	B	C	D	E	F	G
	A					B
		-2		-4
			-3			-7
		-1
		-5		-4		-5

	1/A					X
	0, 098005	-0, 09214	0, 071009	-0, 0534	X1=	1, 767019
	0, 201878	-0, 85446	0, 403756	-0, 3615	X2=	9, 807512
	0, 019366	-0, 31162	0, 163732	-0, 04049	X3=	2, 702465
	-0, 02758	0, 049883	0, 069836	-0, 00293	X4=	-0, 48533

Рис. 2.1. Решение системы линейных уравнений методом обратной матрицы с помощью программы Excel.

Метод прогонки.

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

, (2.6)

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

, (2.7)

Уменьшим в формуле (2.7) индекс на единицу: и подставим в (2.6):

Выразим :

(2.8)

Сравнивая (2.7) и (2.8), получим:

(2.9)

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

, (2.10)

Теперь по формулам (2.9) и (2.10) можно вычислить прогоночные коэффициенты и ( ). Это прямой ход прогонки. Зная прогоночные коэффициенты, по формулам (2.7), можно вычислить все ( ) (обратный ход прогонки). Поскольку , то и . Далее вычисляем , , ..., , .

Пример 2.3. Решить систему уравнений методом прогонки:

Решение. Коэффициенты записываем в виде таблицы 2.1.

		Таблица 2.1


-2		-1
0, 1	-1	-5
-1

Прямой ход прогонки. По формулам (2.9) и (2.10) определяем прогоночные коэффициенты и ( ).

, т.к.

Обратный ход прогонки. По формулам (2.7) вычисляем все ( ). Поскольку , то .

Далее вычисляем:

Вычисляем невязки ( )

Пример 2.4. Решить систему уравнений из примера (2.3) методом прогонки с помощью программы Excel.

Порядок решения.

1) Ввести в ячейки A1: G1 заголовки столбцов (рис. 2.3).

2) В ячейки A3: D6 – коэффициенты . Строки выше и ниже данных оставить пустыми.

3) В ячейку E3 – формулу =-C3/(A3*E2+B3)

4) В ячейку F3 – формулу =(D3-A3*F2)/(A3*E2+B3)

5) В ячейку G3 – формулу =G4*E3+F3

6) Выделить ячейки E3: G3 и скопировать формулы в соседние ячейки E4: G4 … E6: G6 при помощи маркера заполнения.

7) В ячейках G3: G6 появятся значения решения системы уравнений.

	A	B	C	D	E	F	G	H
	a	b	c	d	u	v	x

					-0, 1	0, 5	0, 5
	-2			-1	-0, 1087
	0, 1		-1	-5	0, 250681	-1, 25341
	-1

Рис. 2.3. Решение системы линейных алгебраических уравнений методом прогонки с помощью программы Excel.

На рис. 2.2 приведена программа решения методом прогонки.

A	B	C	D	E	F	G
a	b	c	d		x	r
					0, 5
-2			-1
0, 1		-1	-5
-1

Sub program4()

Const n = 4

Dim a(n), b(n), c(n), d(n), u(n), v(n), x(n+1), r(n)

For i = 1 To n

a(i) = Cells(i + 1, 1)

b(i) = Cells(i + 1, 2)

c(i) = Cells(i + 1, 3)

d(i) = Cells(i + 1, 4)

u(i) = -c(i)/(a(i)*u(i-1)+b(i))

v(i) = (d(i)-a(i)*v(i-1))/(a(i)*u(i-1)+b(i))

Next i

For i = n To 1 Step -1

x(i) = u(i)*x(i+1)+v(i)

Next i

For i = 1 To n

r(i) = d(i)-a(i)*x(i-1)-b(i)*x(i)-c(i)*x(i+1)

Cells(i + 1, 6) = x(i)

Cells(i + 1, 7) = r(i)

Next i

End Sub

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

Порядок решения.

1) Представить систему в виде (2.16);

2) Ввести в ячейки A1: C1 заголовки столбцов (рис. 2.4);

3) В ячейки A2: C2 – начальное приближение 0, 0, 0;

4) В ячейку A3 – формулу =(7-4*B2+C2)/7

5) В ячейку B3 – формулу =(-2-2*A2-3*C2)/6

6) В ячейку C3 – формулу =(4+A2-B2)/4

7) Выделить столбцы A, B, C, вызвать контекстное меню Формат ячеек, установить формат числовой и указать число десятичных знаков, соответствующее необходимой точности, т.е. 2;

8) Выделить ячейки A3: C3 и скопировать формулы в соседние ячейки расположенных ниже строк A4: C4, A5: C5 и т.д.при помощи маркера заполнения. Каждая новая строка содержит результаты очередного приближения;

9) Продолжать копирование, пока результат не перестанет меняться;

10) Ячейки A21, B21, C21 содержат решение системы уравнений, соответствующее заданной точности.

Приближенное решение системы с точностью :

, ,

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

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

, (2.17)

Сходимость и точность достигаются условиями (2.13) и (2.14).

Пример 2.7. Задать итерационный процесс Зейделя для нахождения решений системы уравнений (2.15).

Решение. Достаточное условие сходимости (2.13) выполняется, поэтому начальное приближение может быть любым.

Используя (2.16) получим:

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

Результаты первой итерации подставляют в правую часть и получают результаты второй итерации:

Результаты второй итерации подставляют в правую часть и получают результаты третьей итерации:

Погрешность решения:

Порядок решения.

1) Подключить надстройку «Поиск решения» через Кнопка «Офис»-Параметры Excel-Надстройки-Надстройки Excel-Перейти (рис. 3.3);

2) Ввести в ячейки A1, B1, C1, D1 заголовки столбцов (рис. 3.4а);

3) В ячейку A2 – начальное приближение для :

4) В ячейку B2 – начальное приближение для :

5) В ячейку C2 – формулу =2*SIN(A2+1)-B2-0, 5

6) В ячейку D2 – формулу =10*COS(B2-1)-A2+0, 4

7) Вызвать диалоговое окно «Поиск решения»: Данные-Поиск решения (рис. 3.5)

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

9) Для решения уравнения значение , поэтому выбираем переключатель «значение», а в соответствующее поле вводим 0

10) Установив курсор в поле «Изменяя ячейки», выделяем ячейки незвестных , , т.е. A2: B2

11) Остальные уравнения системы рассматриваются как дополнительные ограничения ( ). Нажимаем кнопку «Добавить», отмечаем мышью ячейку D2 и вводим =0

12) Нажимаем кнопку «Выполнить». Если решение найдено, появляется окно сообщения (рис. 3.6). Нажимаем кнопку ОК.

13) В ячейках A2: B2 - решение системы (рис. 3.4б), т.е ,

		а) б)
Рис. 3.3. Подключения надстройки «Поиск решения».		Рис. 3.4. Рабочий лист до и после выполнения поиска решения.


Рис. 3.5. Параметры окна «Поиск решения».

Рис. 3.6. Сообщение о завершении поиска решения.

ЛИТЕРАТУРА

1. Калиткин Н.П. Численные методы. М.: Наука, 1978. - 512 с.

2. Турчак Л.И., Плотников П.В. Основы численных методов: Учебное пособие. М.: ФИЗМАТЛИТ, 2003. – 304 с.

3. Васильев А.Н. Научные вычисления в Microsoft Excel. М.: Издательский дом " Вильямс", 2004. – 512 с.

4. Ларсен У.Р. Инженерные расчеты в Excel. М.: Издательский дом " Вильямс", 2004. – 544 с.

5. Попов В.И. Численные методы расчета мостовых конструкций на ЭВМ. М.: 1981. – 78 с.

6. Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». Численные методы. Часть 1. / Сост.: Ф.Г.Ахмадиев, Ф.Г.Габбасов, Р.Ф.Гиззятов, И.В.Маланичев. Казань: КГАСУ, 2011. – 32 с.

7. Методические указания к лабораторным и самостоятельным работам по курсам «Информатика» и «Вычислительная математика». Численные методы. Часть 2. / Сост.: Ф.Г.Ахмадиев, Ф.Г.Габбасов, Р.Ф.Гиззятов, И.В.Маланичев. Казань: КГАСУ, 2011. – 36 с.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

Кафедра прикладной математики

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

Часть 1

Методические указания к лабораторным и самостоятельным работам

по курсам «Информатика» и «Вычислительная математика»

Казань

УДК 621.313: 518.6

ББК 32.81

Рецензент

Доктор физико-математических наук, профессор КГАСУ

Р.Б.Салимов

УДК 621.313: 518.6

ББК 32.81

ã	Казанский государственный архитектурно-строительный университет, 2013

ã	Ахмадиев Ф.Г., Габбасов Ф.Г., Гиззятов Р.Ф., Маланичев И.В.,

Численное решение нелинейных уравнений.

12 3 4 5 Следующая ⇒