Козенко, Галанина Информатика_ч2

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

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

ИНФОРМАТИКА

Методические указания к выполнению курсовой работы

Часть 2

Санкт-Петербург 2014

Составители: кандидат технических наук С. Л. Козенко, кандидат технических наук В. А. Галанина

Рецензент – кандидат технических наук А. Ю. Гулевитский

Приводятся методические указания к выполнению курсовой работы по дисциплинам «Информатика» и «Информатика и программирование» для студентов, обучающихся по следующим направлениям и специальностям: 16110165, 20010062, 20040062, 20100062, 21010062, 21040062, 22170062, 23070062, 28070062.

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

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

Подготовлены к публикации кафедрой прикладной математики и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения

Публикуется в авторской редакции Компьютерная верстка И. Н. Мороз

Сдано в набор 10.06.2014. Подписано к печати 00.06.14. Формат 60×841/16. Бумага офсетная. Усл. печ. л. 1,51. Уч.-изд. л. 1,63.

Тираж 100 экз. Заказ № .

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

©Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2014

ПРЕДИСЛОВИЕ

Вметодических указаниях приводятся рекомендации к практическому решению задачи аппроксимации функции методом наименьших квадратов (МНК), математическое описание которой приведено в [1].

Приводится пример задания на курсовую работу. Для этого примера рассчитываются вручную (без использования ЭВМ) параметры аппроксимирующей функции одним из прямых методов (методом­ Гаусса) и одним из итерационных методов (методом простых итераций). Для расчетов коэффициентов системы нормальных уравнений и вычисления значения критерия аппроксимации рассматриваются примеры схем алгоритмов и их реализация на ЭВМ с использованием среды программирования C. Приведенные в методических указаниях схемы алгоритмов выполнены в соответствии с требованиями ГОСТ [2].

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

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

2. Представление исходных данных (табличное).

3. Описание критерия аппроксимации и способа его минимизации.

4. Описание заданного метода вычисления коэффициентов нормальных уравнений.

5. Расчет параметров аппроксимирующей функции (ручной счет). 6. Схемы алгоритмов и их описание.

7. Текст программы и результаты расчета на ЭВМ.

8. Графическое сопоставление исходной и аппроксимирующей (ϕ*(x) и ϕ**(x)) функциональных зависимостей.

9. Оценка погрешности аппроксимации. 10. Выводы.

3

1.МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

КВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ

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

Исходными данными являются функциональная зависимость между X и Y, заданная таблично в n точках, и набор базисных функций.

Требуется, используя МНК, найти аппроксимирующую функцию ϕ(x) из заданного класса функций и оценить степень ее отклонения от исходной функции.

1.2.Задание аппроксимирующей функции

Вкурсовой работе задан исходный набор базисных аппроксими-

рующих функций ϕ1(x), ϕ2(x), ϕ3(x) и тем самым определено число коэффициентов (C1, C2, C3), подлежащих определению (m = 3). Таким образом, аппроксимирующая функция имеет вид

ϕ(x) =C1ϕ1(x) +C2ϕ2(x) +C3ϕ3(x).

(1.1)

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

1.3.Формулировка критерия аппроксимации

исоставление системы нормальных уравнений

Всоответствии с вариантом задания формируется критерий аппроксимации (1.2).

n
J=min å(yi -(C1ϕ1(xi) +C2ϕ2(xi) +C3ϕ(xi))2.	(1.2)
i=1

Для нахождения значений коэффициентов C1, C2 и C3 составляется система из трех уравнений, исходя из условия минимума функции J:

n

¶¶CJ1 =åi=1 2(yi -(C1ϕ1(xi) +C2ϕ2(xi) +C3ϕ3(xi))´(-ϕ1(xi) =0,

	¶J				n
			=	å2(yi -(C1ϕ1(xi) +C2ϕ2(xi) +C3ϕ3(xi))´(-ϕ2(xi) =0, (1.3)
	¶C
	2				i=1
		¶J			n
					=å2(yi -(C1ϕ1(xi) +C2ϕ2(xi) +C3ϕ3(xi))´(-ϕ3(xi) =0.
		¶C
	1				i=1

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

a11С1 + a12С2 + a13С3 = b1
a21 С1 + a22С2 + a23С3 = b2	(1.4)
a31С1 + a32С2 + a33С3 = b3

Коэффициенты akl и bk вычисляются непосредственно по формулам (1.3) при проведении контрольных расчетов вручную.

При расчетах на ЭВМ эти коэффициенты рассчитываются по формулам:

n	n
akl=åϕk(xi)´ϕl(xi ) bk =åyi´ϕk(xi),		(1.5)
i=1	i=1
k=1, ,3;	l=1, ,3.

Схемы алгоритмов вычисления коэффициентов akl и bk в соответствии с (1.5) приведены на рис. 1.1.

В схемах алгоритмов используются следующие обозначения: m – количество базисных функций;

n – количество точек аппроксимации;

FI – функция, вычисляющая значение k-й базисной функции в точке xi (k = 0, …, m – 1; i = 0, …, n – 1).

При вычислении коэффициентов akl и bk (1.5) базисные функции jk(xi) вычисляются в соответствии со схемой алгоритма, приведенного на рис. 1.2.

1.4.Определение параметров аппроксимирующей функции

икритерия аппроксимации

Систему нормальных уравнений (1.4) решаем способом, который приведен в задании. В результате решения находим значения коэффициентов C*1, C*2, C*3.

4

5

а)

Начало

б)

Начало

k = 0…m – 1

k = 0…m – 1

l = 0…m – 1

Bk = 0

Akl = 0

i = 0…n – 1

i = 0…n – 1

Bk = Bk + yi ×

FI(k, xi)

Akl = Akl + FI(k, xi) ×

FI(l, xi)

i

i

k

l

Конец

k

Конец

Рис. 1.1. Схемы алгоритмов вычисления коэффициентов Akl (а) и Bk (б) системы нормальных уравнений

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

Найденные значения коэффициентов (для ручного счета – Ci*, для машинного – C**i ) подставляем в выражение аппроксимирующей функции и получаем соответственно

ϕ* (x) =C1*ϕ1	(x) +C2*ϕ2(x) +C3*ϕ3(x)	(1.6)
ϕ**(x) =C1**ϕ1	(x) +C2**ϕ2(x) +C3**ϕ3(x)	(1.7)

В соответствии с (1.6) и (1.7) строим графики аппроксимирующей функции с целью сравнения их с графиком исходных данных

Начало
k = 0	Да
Нет	Возврат φ0(xi)
k = 1	Да
Нет	Возврат φ1(xi)
Возврат φ2(xi)
Конец
Рис. 1.2. Схема алгоритма функции FI(k, x[i])

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

Количественная оценка аппроксимации осуществляется с помощью вычисления значения критерия J* для ручного счета и J** для машинного:

m

J* =å(yi -ϕ* (xi))2 i=1

m

J** =å(yi -ϕ** (xi))2 i=1

соответственно.

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

∆* = max|di*| = max |yi – ϕ*(xi)| ∆** = max|di**| = max |yi – ϕ**(xi)|

Схема алгоритма вычисления значения критерия J** и максимального отклонения ∆** приведена на рис. 1.3.

6

7

Начало

Kr = 0

k = 0

i = 0…n – 1

Y1i = C0 × FI(k, xi) +

+ C1 × FI(k + 1, xi) + C1 × FI(k + 2, xi)

Di = yi – Y1i

Kr = Kr + Di×Di

i

Dmax = D0

IM = 0

i = 1…n –1

Нет

|Di| > |Dmax|

Да

Dmax = Di

IM = i

i

Конец

Вычисление значений аппроксимирующей функции в заданных точках

Определение отклонений значений yi от значений аппроксимирующей функции Y1i

Вычисление значения критерия аппроксимации

Начало цикла по i

Определение максимального по модулю отклонения и его координаты

Конец цикла по i

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

Начало

Вывод (“Диалоговый комментарий”)

i = 0…n – 1

Ввод (xi, yi)

i

Расчет значений

коэффициентов системы уравнений

Решение системы

уравнений заданным методом

Вычисление значений Y1, D и Kr

Вычисление Dmax

и IM

Вывод (“Диалоговый комментарий”)

i = 0…n – 1

Вывод (Y1i)

i

α

Ввод значений X и Y в соответствии с

вариантом задания к курсовой работе

Выполнение действий в соответствии со схемой алгоритма (рис. 1.1)

Решение системы нормальных уравнений [1] методом, определенным заданием на курсовую работу

Выполнение действий в соответствии со схемой алгоритма (рис. 1.3)

Вывод значений аппроксимирующей функции (Y1i)

Рис. 1.4. Схема обобщенного алгоритма решения задачи аппроксимации функции (начало)

8

9

α

Вывод (“Диалоговый комментарий”)

i = 0…n – 1

Вывод (Di)

i

Вывод (Dmax,

xIM)

Вывод (Kr)

Конец

Вывод значений отклонений (Di) в заданных точках (xi)

Вывод максимального отклонения (Dmax) и соответствующего значения xIM

Вывод значения критерия аппроксимации (Kr)

Рис. 1.4. Схема обобщенного алгоритма решения задачи аппроксимации функции (окончание)

В схеме алгоритма использованы следующие обозначения: Kr – критерий аппроксимации J**;

Y1i – значение аппроксимирующей функции в точке xi (ϕ**(xi)); Di – значение отклонения аппроксимирующей функции от за-

данного в точке xi (δ(xi));

Dmax – максимальное отклонение значений аппроксимирующей функции Y1i от заданных величин yi (∆**);

IM – порядковый номер xi, для которого получено максимальное отклонение Dmax.

При вычислении значений аппроксимирующей функции (Y1i) базисные функции jk(xi) определяются в соответствии со схемой алгоритма, приведенной на рис. 1.2.

Схема обобщенного алгоритма представлена на рис. 1.4.

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

2. ПРИМЕР ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ

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

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

Пусть задание на курсовую работу имеет вид, представленный в табл. 2.1 (n = 5, m = 2).

Рассмотрим этапы выполнения курсовой работы.

Этап 1. Ручной счет

1. Выражение для аппроксимирующей функции будет иметь следующий вид [1]:

ϕ*(x) = C1 × j1(x) + C2 × j2(x) = C1 × 1 + C2 × cos(x). 2. Запишем выражения для критерия аппроксимации:

5	5
J=å(yi -ϕ(xi))2	=å[yi -C1´ϕ1(xi) -C2´ϕ2(xi)]2=
i=1	i=1

5

=å[yi -C1 -C2´cos(xi)]2. i=1

3. В соответствии с условиями локального минимума функции

J(C1, C2) найдем частные производные

¶J

,

¶J

и приравняем их

¶C

¶C

к нулю:

1

2

Таблица 2.1

Базисные

Метод решения

Номер

Таблица значений

функции

системы

варианта

нормальных

j1(x)

j2(x)

уравнений

31

xi

0,0

0,79

1,57

2,36

3,14

1

cos(x)

Метод Гаусса

yi

2,0

6,0

7,0

3,0

0,0

10

11

¶J

5

=å2(yi -C1 -C2´cos(xi))´(-1) =

¶C

1

i=1

5

5

5

=-2(åyi -5åC1 -C2åcos(xi)) =0,

i=1

i=1

i=1

¶J

5

=å(yi -C1 -C2´cos(xi))´(-cos(xi)) =

¶C

æ

2

i=1

ö

5

5

5

ç

å

å

÷

çå

2

÷

ç

yi

´cos(xi) -C1

cos(xi) -C2

cos

÷

=0.

=-2ç

(xi)÷

ç

i=1

i=1

÷

è i=1

ø

Таким образом, получим два уравнения:

æ 5

5

ö

ç

÷

ç

÷

-2çåyi -5C1 -C2åcos(xi)÷=0,

ç

i=1

÷

èi=1

ø

æ 5

5

5

ö

ç

2

÷

÷

ç

-2çåyi´cos(xi) -C1åcos(xi) -C2åcos (xi)÷=0.

ç

i=1

i=1

÷

èi=1

ø

4. Приведем полученную систему уравнений к нормальному виду, перенеся свободные члены вправо и поделив обе части уравнений на 2.

		5	5
	5C1 +C2åcos(xi) =åyi
		i=1	i=1	(2.1)
	5	5	5
	C1åcos(xi) +C2	åcos2(xi) =åyi´cos(xi)
	i=1	i=1	i=1

5. Для удобства представим промежуточные результаты вычислений в соответствии с (2.1) в табл. 2.2.

Используя значения из табл. 2.2, запишем систему уравнений (2.1) в окончательном виде:

5С1 – 0,0052С2 = 18
–0,0052C1 + 2,999С2 = 4,0999	(2.2)

Введем обозначения

a11 = 5; a12 = –0,0052; b1 =18,

a21 = –0,00052; a22 = 2,999; b2 = 4,0996.

Таблица 2.2

№ п/п	x	i	y	i	cos(x	)	cos2(x	)	y	×cos(x	)
					i		i		i	i
1	0,0		2,0		1,0		1,0			2,0
2	0,79		6,0		0,704		0,496		4,224
3	1,57		7,0		0,0008		0,00000064		0,0056
4	2,36		3,0		–0,71		0,504		–2,13
5	3,14		0,0		–0,999		0,998			0
S	7,86		18		–0,0052		2,999		4,0996

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

Тогда систему нормальных уравнений можно записать в матричном виде, следующим образом [1]:

é	5		ù		é		ù		é	18	ù
ê		-0,0052ú		´	êC1		ú	=	ê		ú
ê		2,998	ú		ê	C	ú		ê	4,0999	ú.
-0,0052			û		ë		û		ë		û
ë						2

6. Полученную систему уравнений решаем тем способом, который указан в задании.

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

Определяем множитель, на который необходимо умножить второе уравнение

q21 = a21/a11 = – 0,0052/5 = – 0,00104.

Умножаем на этот множитель первое уравнение и вычитаем его из второго.

(–0,0052 + 0,00104 × 5)C1 + (2,999 + 0,00104 × 0,0052)C2 = = 4,0999 + 0,00104 × 18

или

0С1 + (2,999 + 0,0000054)С2 = (4,0999 + 0,018772) После преобразования система уравнений будет иметь вид

5С1 – 0,0052С2 = 18 0С1 + 2,999С2 = 4,118672.

12

13

Из второго уравнения находим С*2 = 1,373.

Подставляя это значение в первое уравнение, находим C1* = 3,601. 6.2. Метод простых итераций

Определим сходимость итерационного метода, исходя из условия

n
| aii | ³å| aij | .	(2.3)

i¹j

Очевидно, для системы (2.2) выполняется условие сходимости (2.3), так как

 для первого уравнения

|5| > |–0,0052|.

 для второго уравнения

|2,999| > |–0,0052|.

Пусть значение точности вычислений eps равно 0,001. Выполним следующие преобразования.

Из первого уравнения выразим C1, а из второго – C2. В результате получим:

	C1	=	18+0,0052C2
				5
C2	=	4,0999+0,0052C1
			2,999

или

C1 = 3,6 + 0,00104C2

C2 = 1,36709 + 0,00173C1. Запишем эту систему в матричном виде

é

1

ù

é

3,6

ù

é

0

ù

é

0

ù

êC1

ú

ê

ú

ê

0,00104ú

êC1

ú

ê

1

ú

=

ê

ú

+

ê

0

ú

´ê

0

ú.

êC

ú

ë1,36709û

ë0,00173

û

êC

ú

ë

2

û

ë

2

û

Выберем в качестве нулевых приближений С10 = 3,6, C20 = 1,36709. В этом случае первое приближение будет равно

é 1	ù	é		ù	é			ù	é		ù
êêC11	úú	=êê	3,6	úú	+êê	0	0,00104úú		´êê	3,6	úú
êC	ú	ë1,36709û			ë0,00173		0	û	ë1,36709û
ë 2	û

14

é	1	ù		é		3,6		ù		é	ù
êC1		ú	=	ê				ú	+	ê	0,001422ú
ê	1	ú		ê				ú		ê	ú
êC		ú		ë1,36709û						ë0,006228û
ë	2	û
				éC1		ù	é3,601422ù
				êê	11	úú	=êê				úú
				êC		ú	ë1,373318û
				ë	2	û

Используя найденное первое приближение, находим второе приближение

é

2

ù

é

3,6

ù

é

0

ù

é

ù

êC1

ú

=

ê

ú

+

ê

0,00104ú

´

ê3,601422ú

ê

2

ú

ê

ú

ê

0

ú

ê

ú

êC

ú

ë1,36709û

ë0,00173

û

ë1,373318û

ë

2

û

é

2

ù

é

3,6

ù

é

ù

êC1

ú

=

ê

ú

+

ê0,001428ú

ê

2

ú

ê

ú

ê

ú

êC

ú

ë1,36709û

ë0,006230û

ë

2

û

é

2

ù

é3,601428ù

êC1

ú

ê

2

ú

=ê

ú

êC

ú

ê

ú

ë1,373320û

ë

2

û

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

||С(2) – C(1)|| = (0,00006 + 0,00002) ≤ ε.

Таким образом, второе приближение можно принять за решение системы уравнений (1.2).

В результате получим: C1* = 3,601 и С*2= 1,373, то есть такие же значения, вычисленные методом Гаусса.

7. В результате решения исходной системы линейных уравнений и нахождения значений C1* и С*2 получаем запись искомой аппроксимирующей функции в следующем виде

ϕ*(x) = 3,601 + 1,373 × cos(x).

(2.4)

8. Оценка погрешности аппроксимации.

Рассчитаем по формуле (2.4) значения аппроксимирующей функции в заданных точках xi (i = 1, …, 5) и соответствующие отклонения di (табл. 2.3).

В соответствии с табл. 2.3 построим графики исходной и аппроксимирующей функций (рис. 2.1).

15

					Таблица 2.3	Начало
xi		yi		ϕ(xi)	di = |ϕ(xi) – yi|
								int sсhod(float A[m][m] )
0,0		2,0		4,9	2,9	Flag = 0
								{
0,79		6,0		4,6	1,6
								float Ad, Sd;
1,57		7,0		7,03	0,03	i = 0	– 1	int i, j, Flag, Key;
2,36		3,0		2,63	0,37	i=0…m-1		Flag = 0;
3,14		0,0		2,23	2,23	Ad = |Aii|		for(i = 0; I < m; i++)
Y								{
						Sd = 0		Ad = fabs( A[i][i]);
								Sd = 0;
6				– значения исходной		j = 0…m – 1		for(j = 0; j < m; j++ )
							Нет
				функции				if ( j != i )
4				– значения аппроксимирующей		j ≠ i		Sd+ = fabs(A[i][j]);
				функции		Да
								if (Ad > Sd)
2						Sd = Sd + |Aij|
								Flag++;
				δi
								}
	1	2	3	4	X	jj		// end i
Рис. 2.1. Графики исходной yi и аппроксимирующей ϕ(xi)								if (Flag == m)
							Нет	Key = 0;
		функций
						Ad >Sd		else
						Да		Key = 1;
Вычислим значение критерия аппроксимации, подставив в (1.1)						Flag = Flag + 1		return Key;
данные из табл. 2.3:								}
J	= J(C*, C*) = (2,9)2		+ (1,6)2 + (0,03)2		+ (0,37)2 +	i
min	1	2
		+ (2,23)2 = 16,0807.					Нет
Максимальное по модулю отклонение |dmax| = 2,9 при x1 = 0,0.
						Flag = m

Этап 2. Вычисления с использованием ЭВМ.

После выполнения контрольных расчетов вручную, необходимо составить алгоритм и написать программу решения задачи. Для написания программы можно воспользоваться обобщенным алгоритмом, представленным на рис. 1.4, а также соответствующими алгоритмами, описанными в [1]. При написании текста программы необходимо использовать принципы структурного программирования. Пример схемы алгоритма и текст программы функции опреде-

Да

Key = 0				Key = 1

Возврат Key

Рис. 2.2. Схема алгоритма и текст Конец программы функции определения сходимости итерационного процесса

16

17

# include < stdlib.h >

…

void iter (float A[m][m])

{

int Key1;

…

// вызов функции определения сходимости итерационного процесса

Key1 = sсhod(A);

if ( Key1 ==m )

{

printf(“ Процесс расходится \n “); abort ();

}

…

}

Рис. 2.3. Фрагмент текста программы функции iter

ления сходимости итерационного процесса с использованием среды программирования C [3] приводится на рис. 2.2.

Использование этой функции в итерационных методах решения системы линейных уравнений может иметь следующий вид (рис. 2.3).

В функции iter(…) использована стандартная функция abort( ) из библиотеки <stdlib.h>. Эта функция вызывает аварийное завершение работы всей программы (в данном случае аварийное завершение происходит, когда итерационный процесс расходится).

На рис. 2.4 представлен текст программы на языке С основной функции в соответствии с алгоритмом, приведенным на рис. 1.4.

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

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

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include < stdlib.h >

int const n=6, m=3;

int main( ) // главная функция

{

…

printf( “Введите значения X \n”); VVOD ( x );

printf( “Введите значения Y \n”); VVOD ( y );

koeff( x, y, A, B );

prgauss ( A, B ); // или obrmatr (A,B,C), или iter(A,B,C), или zeid(A,B,C) obgauss (A, B, C); //

approcs( C, Y1);

krappr( y, Y1, D, &Maxd, &IM, &Kr );

printf( “Значения аппроксимирующей функции: \n” ); VYVOD ( Y1 );

printf( “Значения отклонений: \n”); VYVOD ( D );

printf( “Максимальное отклонение = %f при X= %f \n ”, Maxd, x[IM] ); printf( “Значение критерия = %f\n“, Kr);

getch (); return 0;

}

Рис. 2.4. Фрагмент программной реализации главной функции

Полученные в результате выполнения программы данные необходимо сравнить с результатами контрольного расчета (см. Этап 1). При совпадении результатов (с точностью до 0,01) задача считается выполненной.

18

19