kursovaya_rabota (1)

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

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

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

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ

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

РУКОВОДИТЕЛЬ

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ

АППРОКСИМАЦИЯ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ (МНК)

по дисциплине: ИНФОРМАТИКА И ПРОГРАММИРОВАНИЕ

Курсовую работу выполнил:
	студент группы 2435				О.Е. Васильева
			подпись, дата		инициалы,фамилия

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

2015

СОДЕРЖАНИЕ

1.Цель работы…………………………………………………………………………3

2.Постановка задачи……………………………………………………………….....3

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

4.Описание метода выбора аппроксимирующей функции………………………..4

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

6.Описание метода Гаусса……………………………………………………………5

7.Контрольный расчет параметров аппроксимирующей функции (без использования компьютера) и график…………………………………………….9

8.Схемы алгоритмов и их описание………………………………………………...12

9.Программа и результаты расчетов параметров на компьютере………………..16

10.Вывод ………………………………………………………………………………19

2

1) Цель работы

Настоящая курсовая работа является завершающим этапом изучения дисциплин «Информатика» и «Информатика и программирование» и её цель - закрепление навыков алгоритмизации и программирования.

Выполнение курсовой работы требует решения следующих задач:

•практическое освоение типовых вычислительных методов прикладной математики;

•совершенствование навыков разработки алгоритмов и построение программ на языке высокого уровня;

•освоение принципов модульного программирования и техники использования библиотек на Dev

C++.

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

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

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

разностью	y x ,	x .
Значения y = yi	заданы для конечного множества (n) значений xi , (i=1, 2,…, n). Тогда для каждого из
этих значений определена и ошибка (см.рисунок)
		i = (xi ) = yi –	(xi) , ( i =1, 2, …, n) .

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

Это требование принимает вид

n

i2 min .

i1

Внастоящей курсовой работе исходные данные заданы в виде табличной зависимости yi (xi). Уточним условия МНК для этой задачи.

3

y ( x )

Задача. Зависимость между переменными x и y задана их значениями в отдельных точках ( xi , yi ) , (i 1, n) . Требуется найти функцию ( x ), наилучшим образом (МНК) аппроксимирующую указанную зависимость.

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

J n yi ( xi ) 2 min . (1)

i 1

Подобное задание исходных данных встречается в задачах технических измерений и их статистической обработки, когда для каждого из задаваемых значений xi осуществляется измерение

величины yi (сопровождающееся возможными ошибками). Аппроксимация позволяет представить

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

оценивать значения переменной в точках x интервала x1 , xn , не совпадающих с заданными (т.е. решать задачу интерполяции).

3) Представление исходных данных

			Заданные точки				Базисные функции			Метод
										решения
	Xi	0,79	1,57	2,36	3,12	3,81	1	x	2	Метод
										Гаусса
	Yi	2,5	1,2	1,12	2,25	4,28

4)Описание метода выбора аппроксимирующей функции

Аппроксимирующую функцию φ(x) выбирают из некоторого семейства функций, для которого задан вид функции, но остаются неопределенными (и подлежат определению) ее параметры С1, С2, …, Сm , т.е.

(x) = (x, С1, С2,…, Сm) . (2)

Для решения задачи подставим выражение (2) в выражение (1) и проведем необходимые операции суммирования. В результате величина J , критерий аппроксимации, представится функцией искомых параметров

J = J(С1, С2, …, Сm) . (3)

Последующие действия сводятся к отысканию минимума этой функции J переменных Сk . Определение значений Сk = Сk*, k = 1, 2, …, m , соответствующих этому минимуму J, и является целью решаемой задачи.

Поскольку величина J неотрицательна (как сумма квадратов) и нижняя ее граница есть 0 (J=0), то, если существующее решение системы единственно, оно отвечает именно минимуму J.

Уравнения, встречающиеся в МНК, называются нормальными, поэтому описываемый способ решения задачи условимся называть методом нормальных уравнений.

Структура этих уравнений получается более простой в том важном частном случае, когда аппроксимирующая функция (x) выбирается линейной функцией искомых параметров Сk и выражение

(2) имеет вид

	m
( x ) Ck		k ( x ) ,	(4)
	k 1
где Сk – определяемые параметры; 1(x),	2(x),…,	m(x) – система некоторых линейно-независимых
функций, называемых в курсовой работе базисными функциями.
Замечание. Функции 1(x),	2(x),…,	m(x) называются линейно-независимыми,
если при любых x равенство
	4

m

Ck k ( x ) 0

k 1

справедливо только тогда, когда все Сk =0.

В этом случае, подставляя (4) в выражение (1) и выполняя дифференцирование, получим систему уравнений относительно искомых Сk .

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

Раскроем выражение аппроксимирующей функции
	(x) = С1 1(x) + С2 2(x) +…+ Сm			m(x)
и подставим его в формулу критерия аппроксимации.
n			) 2 .
J yi C1 1 ( xi ) C2 2 ( xi ) ... Cm		m ( xi
i 1
Применим операцию дифференцирования к параметру С1 :
n	) C2 2 ( xi ) ... Cm m ( xi ) 2
2 yi C1 1 ( xi			( 1 ( xi )) 0
i 1
и, выполняя необходимые алгебраические преобразования, получим уравнение
n	n			n
C1 1 ( xi	) 1 ( xi ) ... Cm 1 ( xi	) m ( xi )		yi	1 ( xi ) .
i 1	i 1			i 1

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

Аналогичные уравнения можно получить, применяя описанные выше операции по отношению к переменным С2 ,…,Сm . Эти уравнения образуют систему нормальных уравнений:

a11 С1 + a12	С2 +…+ a1m Сm = b1
a21 С1 + a22	С2 +…+ a2m Сm = b2	(5)

……………………………………………………………..

am1 С1 + am2 С2 +…+ am m Сm = bm ,

где коэффициенты ak l и величины bk (k, l = 1, 2,…, m) определяются выражениями

n		n
ak l k ( xi	) l ( xi ) ,	bk yi	k ( xi ) .
i 1		i 1

Уравнения (5) представляют собой систему линейных алгебраических уравнений.

Преимущество использования линейного представления аппроксимирующей функции (x) состоит в том, что в этом случае однозначно решается вопрос о минимуме величины J. Действительно, если решение системы линейных уравнений (9) существует, то оно единственно, поэтому необходимые условия являются в данном случае и достаточными условиями минимума функции J(С1, С2 ,…, Сm).

6)Описание метода Гаусса

Для решения системы нормальных уравнений был выбран метод Гаусса.

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

Систему n линейных уравнений общего вида (где через xk обозначены искомые параметры Сk аппроксимирующей функции)

a11 x1 + a12 x2 +…+ a1n xn = b1 a21 x1 + a22 x2 +…+ a2n xn = b2

5

…………………………………………..

an1 x1 + an2 x2 +…+ an n xn = bn

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

									A*X = B,				где
a		a		...	a				x				b
	11		12			1n				1			1
A a 21		a22		....	a2 n			,	X x2			,	B b2	.
		...		...	....
...									...				...
an1		an2		...	ann				xn				bn

Квадратная матрица A называется матрицей системы, вектор X – вектором-столбцом неизвестных системы, а вектор B – вектором-столбцом свободных членов. В матричном представлении

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

a	a	...	a			x
11	12		1n			1
a21	a22	....	a2n			x2
		...	....
... ...						...
an1	an 2	...	ann			xn

b1b2 .

...

bn

Решение системы линейных уравнений сводится к отысканию значений элементов векторастолбца (xi), называемых корнями системы. Для получения единственного решения системы входящие в нее n уравнений должны быть линейно независимыми. Необходимым и достаточным условием этого является неравенство нулю определителя данной системы, т.е. det A 0.

Для решения был выбран метод Гаусса. Согласно этому методу, исходная система линейных уравнений преобразуется путем последовательного исключения неизвестных в эквивалентную систему уравнений, имеющую так называемый «треугольный» вид. Последнее уравнение «треугольной» системы содержит лишь одно неизвестное (xn), предпоследнее – два (xn, xn-1) и т.д. Решение полученной системы уравнений осуществляется последовательным («снизу вверх») определением xn из последнего уравнения «треугольной» системы, xn-1 из предпоследнего и т.д. Применительно к системе уравнений преобразование к «треугольному» виду осуществляется за (n – 1) шагов.

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

a21 x1 + a22 x2 + …+ a2 n xn = b2

необходимо из него вычесть ведущее уравнение, умноженное на коэффициент q21 = a21 / a11. Действительно, результат вычитания имеет вид

(a21 – q21 a11) x1 + (a22 – q21 a12) x2 + …+ (a2n – q21 a1n) xn =

= b2 – q21 b1 .
Очевидно, что коэффициент (a21 –	q21 a11 ) при x1	равен нулю. Вводя новые обозначения для
коэффициентов
a2( 1k ) a2k	q21 a1k ,	k=(2, …, n) ,
	6

и свободного члена

b2( 1 ) b2 q21 b1 ,

можно переписать уравнение в виде

a22( 1 ) x2 a32( 1 ) x3 .... a2( 1n ) xn b2( 1 ) .

Аналогичную процедуру можно проделать с третьим уравнением системы. Умножая ведущее уравнение на q31=a31 /a11 и вычитая результат умножения из третьего уравнения, получим эквивалентное уравнение

a( 1 )

x

2

a

( 1 )

x

3

.... a( 1 )

x

n

b( 1 )

и т.д.

32

33

3n

3

В результате рассмотренного первого шага исходная система уравнений превратится в

эквивалентную систему уравнений, причем неизвестное x1 входит только в первое уравнение:

a11 x1 a12 x2

...

a1n

xn b1

0 x

1

a( 1 ) x

2

...

a( 1 ) x

n

b( 1 )

22

2n

2

0 x

1

a( 1 ) x

2

...

a( 1 ) x

n

b( 1 )

32

33

3

.......... .......... .......... .......... .......

0 x

1

a( 1 ) x

2

...

a( 1 ) x

n

b( 1 )

n2

nn

n

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

q32 a32( 1 ) / a22( 1 )

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

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

q

42

a( 1 )

/ a( 1 )

42

22

a11 x1 a12 x2

a13 x3 ...

a1n xn

b1

0

x a(1)

x

2

a(1) x

... a(1) x

n

b(1)

1

22

23

3

2n

2

0

x

0 x

2

a(2)

x

... a(1)

x

n

b(2)

1

33

3

3n

3

.......... .......... .......... .......... .......

0

x

0 x

2

a(2)

x

... a(2)

x

n

b(2)

,

1

n3

3

nn

n

где введены новые обозначения

a( 2 )

, b( 2 )

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

i j

i

что неизвестное x1 входит только в первое уравнение, а неизвестное x2 в первое и второе уравнения.

На (n 1) шаге исключается неизвестное xn-1 из последнего n-го уравнения, и в результате система уравнений принимает окончательный «треугольный» вид

7

a11 x1 a12 x2

a13 x3

... a1n xn b1

0 x

1

a( 1 )

x

2

a( 1 )

x

3

...

a( 1 )

x

n

b( 1 )

22

23

2n

2

0 x

1

0 x

2

a( 2 )

x

3

...

a( 1 )

x

n

b( 2 )

33

3n

3

.......... .......... .......... .......... .......... .......... ........

0 x

1

0 x

2

0 x

3

...

a( n 1 ) x

n

b

( n 1 )

nn

n

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

Определим обобщенные формулы для расчета коэффициентов системы в процессе прямого хода метода Гаусса. На i-м шаге неизвестное xi исключается из всех уравнений с номерами k, где i+1 k n, при этом ведущее уравнение (с номером i) умножается на

qki aki( i 1 ) / aii( i 1 ) ,

и результат умножения вычитается из k-го уравнения. Новые номером k) при неизвестных xj, (i+1 j n) равны

akj( i ) akj( i 1 ) qki aij( i 1 )

новое значение свободного члена

b( i ) b( i 1 ) q		b( i 1 )	.
k	k	ki i

значения коэффициентов (в уравнении с

,

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

x

n

b( n 1 ) a( n 1 ) .

n

nn

Значение xn-1 получается при решении предпоследнего уравнения

a( n 2 )

x

a( n 2 )

x

b( n 2 )

n 1, n 1

n 1

n 1,n

n

n 1 .

Так как xn уже определено, то

b( n 2 ) a( n 2 )

x

n 1

x

n

a( n 2 )

.

n 1

n 1, n

n 1, n 1

Эта процедура применяется последовательно ко всем уравнениям, включая и первое, из которого

определяется

x1 b1 a12 x2

... a1n xn a11 .

Обобщенная формула вычисления xi

имеет вид

x

i

b( i 1 ) a( i 1 )

x

i 1

... a( i 1 )

x

n

a( i 1 ) .

i , i 1

i , n

i , i

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

8

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

7) Контрольный расчет параметров аппроксимирующей функции (без использования компьютера) и график

		1. Выражение для аппроксимирующей функции будет иметь вид:
		( ) = С1* 1(x) + С2* 2(x) + С3* 3(x)= С1*1 + С2*x+ С3* 2=С1+С2*x+ +С3* 2
		2. Выражение для критерия аппроксимации:
		= ∑5				( − ( ))2=∑5																[ − С ( )										− С			2						( )		− С	3	( )]2=
		=∑5		=1													=1									1		1										2							3
					[ − С − С							2	− С								3			2]2
		=1					1
		3. В соответствии с условиями локального минимума функции
		J = J(С1, С2, С3) найду частные производные																																;					;			и приравняю их к нулю:
	5																															1					2				3
		= ∑ 2	[ − С				− С				+ С										2] (−1) = 0
										2									3
1						1
		=1
	5
		= ∑ 2	[ − С				− С					− С									2] (− ) = 0
										2									3
2						1
		=1
	5
		= ∑ 2	[ − С				− С					+ С									2] (− 2) = 0
										2									3
3						1
		=1
		4. Преобразую уравнения и подставлю в них данные:
	5						5												5									5
		= −2(∑ − ∑ С										− С					∑ − С											∑ 2 ) = 0
																2											3
1										1
		=1				=1												=1										=1
5										5															5
− ∑ + 5 + С								2	∑ + С											3		∑					2	) = 0
						1
=1										=1															=1
−11,35 + 5 1 + 11,65 С2 + 32,91 С 3 = 0
5 1 + 11,65 С2 + 32,91 С 3 = 11,35
		а11 = 5; а12 = 11,65;															а13 = 32,91;											1 = 11,35
	5										5														5							5
		= − ∑				+ С				∑ + С												∑					2	+ С		∑							3	= 0
																				2									3
2									1
		=1								=1															=1							=1
	5					5											5								5
С ∑ + С				2	∑			2 + С					3	∑								3		= ∑
1
=1						=1										=1									=1
		11,65* 1+32,91*С2+103,185* С 3=29,829
		а21 = 11,65;							а22 = 32,91;														а23 = 103,185;										2 = 29,829
	5												5												5							5
		= − ∑				2	+ С				∑						2	+ С							∑			3 + С				∑						4		= 0
																							2								3
3										1
		=1										=1													=1								=1
	5					5											5								5
С ∑ 2 + С					2	∑			3 + С					3	∑									4 = ∑							2
1
=1						=1											=1								=1
		32,91* 1+103,185*С2+342,961* С 3=94,787
		а31 = 32,91;							а32 = 103,185; а33 = 342,961;																										3 = 94,787
		5. Запишу в матричном виде:
	5					11,65									32,91										1				11,35
	(11,65					32,91							103,185) × (С2 )=(29,829)
	32,91					103,185							342,961												С 3				94,787

9

6. Полученную систему уравнений решаем методом Гаусса:

5	11,65	32,91	11,35
(11,65	32,91	103,185 |29,829)
32,91	103,185	342,961	94,787
1-ую строку делю на 5
1	2,33	6,582	2,27
(11,65	32,91	103,185 |29,829)
32,91	103,185	342,961	94,787

от 2-ой строки отниму 1-ую строку, умноженную на 11,65; от 3-ей строки отниму 1-ую строку,

умноженную на 32,91
			1				2,33					6,582		2,27
			(0				5,7655				26,5047 | 3,3835 )
			0				26,5047				126,34738 20,0813
2-ую строку поделю на 5,7655
		1	2,33								6,582			2,27
		(0				1				265047⁄57655 |6767⁄11531)
		0	26,5047						126,34738					20,0813
от 1-ой строки отниму 2-ую строку, умноженную на 2,33; от 3-ей строки отнимаем 2-ую строку,
умноженную на 26,5047
1		0	−2380743⁄576550											520413⁄576550
(0		1			265047⁄57655							|			6767⁄11531		)
0		0	259566973⁄57655000 261000827⁄57655000
3-ю строку делю на	259566973
57655000														520413⁄576550
1		0	−2380743⁄576550
(0		1		265047⁄57655								|		6767⁄11531			)
0		0							1			261000827⁄259566973
к 1-ой строке добавляем 3-ю строку, умноженную на															2380743	; от 2-ой строки отнимаем
															576550
3-ю строку, умноженную на				265047
			57655						6560210901⁄1297834865
			1			0	0
		(0				1	0 |−5237623594⁄1297834865)
			0			0	1			261000827⁄259566973
Из первого уравнения выражу 1, из второго- 2, а из третьего- 3. В результате получу:
							=			6560210901				≈ 5,055
							1		1297834865

52376235942 = − 1297834865 ≈ −4,036

2610008273 = 259566973 ≈ 1,001

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

( ) = С1* 1(x) + С2* 2(x) + С3* 3(x)= С1*1 + С2*x+ С3* 2=С1+С2*x+ +С3* 2

( ) = 5,055 − 4,036 + +1,001 2

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

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

		( )	=| ( )		− |
0,79	2,5	2,49		0,01
1,57	1,2	1,19		0,01
2,36	1,12	1,11		0,01
3,12	2,25	2,21		0,04
3,81	4,28	4,21		0,07

10