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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

к лабораторным и самостоятельным работам

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

 

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

 

ЧАСТЬ 1

 

 

Казань

 

УДК 621.313: 518.6

 

 

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

 

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

 

 

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

 

 

Рецензент – Р.Б.Салимов, доктор физ.-мат. наук, профессор

 

Казанский государственный

ã архитектурно-строительный

университет, 2011г.

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

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

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

или . (1.5)

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

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

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

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

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

 

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

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

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

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

,

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

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

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

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

CLS DEF FNF(X)= X^3+X-1 INPUT X, E, M 1 X = X - FNF(X)/M PRINT X, FNF(X) IF ABS(FNF(X)/M)>E THEN 1 END

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

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

 

	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.

Порядок решения (рис. 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).

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

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

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

(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) вычисляем все (). Поскольку , то .

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

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

Алгоритм метода прогонки:

1. Ввести число уравнений

2. Ввести ().

3. Вычислить и ; ().

4. Вычислить ().

5. Вычислить невязки ().

6. Напечатать , ().

 

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

CLC

INPUT N

DIM A(N),B(N),C(N),D(N),U(N),V(N),X(N+1),R(N)

FOR I=1 TO N

INPUT A(I),B(I),C(I),D(I)

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)

PRINT ²X²;I; ²=²; X(I), ²R²; I; ²=²; R(I)

NEXT I

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

 

Пример 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.

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

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

2) Ввести в ячейки A1:G1, D2:G2 заголовки столбцов (рис. 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) В ячейку D3 – формулу погрешности =ABS(A3-A2)

8) Выделить ячейку D3 и скопировать формулу в соседние ячейки E3:F3 при помощи маркера заполнения;

9) В ячейку G3 – формулу максимальной погрешности =МАКС(D3:F3)

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

11) Ячейки A15, B15, C15 содержат решение системы уравнений, соответствующее заданной точности (G15).

 

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

, ,

 

	A	B	C	D	E	F	G
	x1	x2	x3	погрешности
				x1	x2	x3	max
		-0,333			0,3333
	1,3333	-1,167	1,3333	0,3333	0,8333	0,3333	0,8333
	1,8571	-1,444	1,625	0,5238	0,2778	0,2917	0,5238
	2,0575	-1,765	1,8254	0,2004	0,3204	0,2004	0,3204
	2,2693	-1,932	1,9556	0,2117	0,167	0,1302	0,2117
	2,3833	-2,068	2,0503	0,114	0,1357	0,0947	0,1357
	2,4744	-2,153	2,1127	0,0911	0,0854	0,0624	0,0911
	2,5321	-2,214	2,1568	0,0577	0,0616	0,0441	0,0616
	2,5735	-2,256	2,1866	0,0415	0,0413	0,0298	0,0415
	2,6014	-2,284	2,2073	0,0278	0,0287	0,0207	0,0287
	2,6208	-2,304	2,2215	0,0194	0,0196	0,0141	0,0196
	2,634	-2,318	2,2312	0,0132	0,0135	0,0098	0,0135
	2,6431	-2,327	2,2379	0,0091	0,0093	0,0067	0,0093
Рис. 2.4. Решение системы линейных алгебраических уравнений методом Якоби с помощью программы Excel.

 

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

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

, (2.17)

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

 

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

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

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

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

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

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

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

 

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

Метод Зейделя отличается от метода Якоби тем, что вычисления ведутся не по формулам (3.4), а по следующим формулам:

(3.6)

…

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

Сходимость метода Зейделя (Якоби тоже) зависит от вида функции в (3.2), вернее она зависит от матрицы, составленной из частных производных:

, (3.7)

где .

Итерационный процесс сходится, если сумма модулей каждой строки меньше единицы в некоторой окрестности корня:

,

или

Пример 3.1. Найти решение системы методом Зейделя с точностью :

(3.8)

Решение: Представим (3.8) в виде (3.5):

(3.9)

Задаем начальные приближения , .

Запишем достаточное условие сходимости и определяем , :

и

Определяем частныезначения , ,которые удовлетворяют неравенствам

и

Переходим к реализации итерационного процесса:

 

Определяем погрешностьпо формуле :

Таким образом, имеем решение: , .

Программа, реализующая решение данной задачи, представлена на рис. 3.1.

CLS

INPUT X,Y, M1,M2

1 X=X-(2*SIN(X+1)-Y - 0.5)/M1

Y=Y-(10*COS(Y-1)-X+0.4)/M2

PRINT X,Y

INPUT TT

GOTO 1

END

Рис. 3.1. Программа решения системы нелинейных уравнений методом Зейделя.

 

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

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

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

(3.10)

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

(3.11)

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

(3.12)

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

Таким образом, решение системы уравнений по методу Ньютона состоит в построении итерационной последовательности:

(3.13)

где , - решения систем линейных уравнений, вида (3.12) на каждом шаге итерации.

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

Пример 3.2. Найти решение системы (3.8) методом Ньютона с точностью .

(3.13)

Решение. Начальные приближения , . Определим частные производные:

;

и, используя (3.12), построим систему линейных уравнений относительно поправок

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

,

определяем поправки на первом шаге итерации

,

Далее начальное приближение уточняем по формулам (3.13)

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

,

определяем поправки на втором шаге итерации

,

Далее и уточняем по формулам (3.12)

Определяем погрешностьпо формуле :

Таким образом, имеем решение: , .

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

 

INPUT X, Y 1 F = 2*SIN(X+1)-Y - 0.5 G = 10*COS(Y-1)-X+0.4 Fx =2*COS(X+1) Fy =-1 Gx =-1 Gy =-10*SIN(Y-1) D = Fx*Gy - Gx*Fy DX=(G*Fy-F*Gy)/D DY=(F*Gx-G*Fx)/D X =X+DX Y =Y+DY PRINT X;Y; F;G;DX;DY; INPUT TT GOTO 1 END

Рис. 3.2. Программа, реализующая метод Ньютона.

 

 

Пример 3.3. Найти решение системы (3.8) с помощью программы Excel.

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

1) Подключить надстройку «Поиск решения» через Главное меню-Сервис-Надстройки (рис. 3.3);

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

3) В я