Размещено на http://www.allbest.ru/

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

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

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

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

Пояснительная записка к курсовой работе

По дисциплине: «Информатика»

На тему: «Аппроксимация функции методом наименьших квадратов (МНК) »

Работу выполнил: студент группы М461

Пахомов В.А.

Руководитель: канд. техн. наук доцент

Галанина В.А.

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



Содержание

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

2. Методические указания

2.1 Методические рекомендации по аппроксимации методом наименьших квадратов

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

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

2.3 Общая методика решения

2.4 Методика решения нормальных уравнений

2.4.1 Методика вычислений методом Гаусса

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

3. Ручной счёт

3.1 Табличное представление исходных данных

3.2 Критерий аппроксимации

4. Схема алгоритма программы

5. Код программы

6. Результаты машинного счета

6.1 Исходные данные

6.2 Результаты

Выводы



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

Данная работа предназначена для закрепления учебного материала, изученного по курсу “Информатика и программирование”.

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

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

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



2. Методические указания

2.1 Методические рекомендации по аппроксимации методом наименьших квадратов

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

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

По данным таблицы можно построить график зависимости от (рис. 1.1). На графике отдельные точки соответствуют значениям в точках (i = 1,...,n).

Рис 1.1

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

(1.1)

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

(2)

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

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

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

Ц(x) = ц(x, C 1, C 2 … C m) (2.1)

Определение аппроксимирующей функции ц разделяется на два основных этапа:

1) Подбор подходящего вида функции ц(x);

2) Нахождение её параметров в соответствии с критерием МНК.

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

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

2.3 Общая методика решения

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

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

J =J(C 1, C 2 … C m) (2.2)

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

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

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

(2.3)

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

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

(2.4)

где - определяемые параметры; ?1(x), ?2(x), …, ?m(x) - система линейно-независимых функций, называемых в курсовой работе базисными функциями.

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

(2.5)

Применим операцию дифференцирования (2.3) к параметру, и, выполняя необходимые алгебраические преобразования, получим уравнение:

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

(2.6)

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

(2.7)

2.4 Методика решения нормальных уравнений

Уравнения (2.7) представляют собой систему линейных алгебраических уравнений , где квадратная матрица A называется матрицей системы, вектор C - вектором-столбцом неизвестных системы, а вектор B - вектором-столбцом свободных членов.

(2.8)

Решение системы линейных уравнений сводится к отысканию значений элементов вектора-столбца С, называемых корнями системы. для получения единственного решения системы, входящие в нее m уравнений должны быть линейно независимыми. необходимым и достаточным условием этого является неравенство нулю определителя данной системы, то есть detA ? 0.

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



2.4.1 Методика вычислений методом Гаусса

Одним из наиболее широко используемых прямых методов является метод последовательного исключения неизвестных, или метод Гаусса. Согласно этому методу, исходная система линейных уравнений (2.6) преобразуется путем последовательного исключения неизвестных в эквивалентную систему уравнений, имеющую так называемый «треугольный» вид.

Последнее уравнение «треугольной» системы должно содержать лишь одно неизвестное (), предпоследнее - два () и т.д. Решение полученной системы уравнений осуществляется последовательным («снизу-вверх») определением из последнего уравнения «треугольной» системы, из предпоследнего и т.д. Применительно к системе уравнений (2.6) преобразование к «треугольному» виду осуществляется за (m - 1) шагов.

Процедура описанного выше преобразования будет следующая:

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

Очевидно, что коэффициент при равен нулю. Аналогичную процедуру можно проделать с третьим уравнением системы. Для исключенияиз m-го уравнения необходимо умножить ведущее уравнение на и вычесть результат из m-го уравнения. Вводя новые обозначения для коэффициентов и свободного члена, можно представить систему уравнений (2.6) в виде (2.9)



(2.9)

Эту последовательность действий необходимо повторять до тех пор, пока матрица (2.9) не примет треугольный вид (2.10)

(2.10)

Этот процесс называется прямым методом Гаусса. А решение этой треугольной системы обратным методом Гаусса. Общая формула вычислений имеет вид (2.11):

(2.11)

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

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

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

+

,….,

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

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

(2.12)



3. Ручной счёт

3.1 Табличное представление исходных данных

Таблица 3.1

i	1	2	3	4	5	6
xi	3.0	4.0	5.0	6.0	7.0	8.0
yi	3.22	4.21	4.85	5.63	4.77	4.2

3.2. Критерий аппроксимации

1) Запишем выражение (3.1) для критерия аппроксимации:

J = min [yi - С1 - C2*ln(x_i) - C3*x_i]І (3.1)

2) В соответствии с условиями локального минимума функции J(C1, C2, C3) найдем частные производные

(18)

(19)

(20)

и приравняем их к нулю:

=2((y_i-С₁-ln(x_i-x_i*)Ч(-1))= -2(y_i-С₁-ln(x_i)*-x_i*)=0 (3.2)

=2((y_i-С1-ln(x_i)(-ln(x_i)))= -2(y_i*ln(x_i)-ln(х_i)*С1-ln²(x_i)-х_i*ln(x_i))=0 (3.3)

=2((y_i - С1- ln(x_i-x_i*)(-x_i))= -2(y_i*x_i - C₁*x_i - x_i*ln(x_i)- x_i²*)= 0 (3.4)

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

6C1 + C2ln(x_i)+ C3x_i = yi

C1ln(x_i)+ C2ln²(x_i)+ C3x_iЧln(x_i)= ln(x_i)yi (3.5)

C1x_i + C2ln( x_i)Чx_i + C3 x_i² = x_iyi

4) Для удобства представим промежуточные результаты вычислений в виде таблицы:

Таблица 3.2

x[i]	y[i]	ln(x[i])	x*x	y[i]*x[i]	x[i]*ln(x[i])	y*ln(x[i])	lnx[i]*lnx[i]
3	3,22	1,098612289	9	9,66	3,295836866	3,53753157	1,20694896
4	4,21	1,386294361	16	16,84	5,545177444	5,83629926	1,92181206
5	4,85	1,609437912	25	24,25	8,047189562	7,805773875	2,59029039
6	5,63	1,791759469	36	33,78	10,75055682	10,08760581	3,210402
7	4,77	1,945910149	49	33,39	13,62137104	9,281991411	3,78656631
8	4,2	2,079441542	64	33,6	16,63553233	8,733654475	4,32407713
33	26,88	9,911455722	199	151,52	57,89566406	45,2828564	17,0400968

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

6С1 + 9,911C2 + 33C3 =26,88

9,911C1 + 17,04C2 + 57,896C3 = 45,28 (3.6)

33C1 + 57,896C2 + 199C3 = 151,52

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

Таблица 3.3

Матрица 1
6,000	9,911	33	26,88
9,911	17,04	57,896	45,28
33	57,896	199	151,52

Таблица 3.4

Коэффициенты
С1	-4,056
С2	12,533
С3	-2,212

6) В результате решения исходной системы линейных уравнений и нахождения значений получаем запись искомой аппроксимирующей функции в следующем виде (3.7):

(3.7)

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

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

аппроксимация погрешность алгоритм программа



Таблица 3.5

xi	3,0	4,0	5,0	6,0	7,0	8,0
yi	3,22	4,21	4,85	5,63	4,77	4,2
ц(xi)	3,076	4,470	5,054	5,127	4,847	4,308
	0,143	0,260	0,205	0,501	0,078	0,109

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

Рис. 3.1

Вычислим значение критерия аппроксимации, подставив в (2.2) данные из табл. 3.5 получим (3.8)

(3.8)

Максимальное по модулю отклонение при .



4. Схема алгоритма программы

Схема алгоритма функции FI( k, x[i] )



5. Код программы

#include <stdio.h>

#include <math.h>

#include <conio.h>

#include <stdlib.h>

#define m 3

#define n 6

void Massiv(float *M,char *Name,int x)

{

int i,j;

printf("Array %s:\n",Name);

for (j=0;j<x;j++)

{

printf ("%5.3f\t",M[j]);

}

printf ("\n");

}

void znachenia (float X[n],float Y[n])

{

int i;

printf("vvedite:\n");

for (i=0;i<n;i++)

{

printf ("X[%i]=",i+1);

scanf ("%f",&X[i]);

printf ("Y[%i]=",i+1);

scanf ("%f",&Y[i]);

}

}

float F1(int k, float N)

{

if (k==0) return 1;

if (k==1) return log(N);

else

return N;

}

void koefficent (float A[m][m], float B[m], float X[n], float Y[n])

{

int i,l,k;

for (i=0;i<m;i++)

for (l=0;l<m;l++)

{

A[i][l] = 0;

for (k=0;k<n;k++)

A[i][l]=A[i][l] + F1(i,X[k]) * F1(l,X[k]);

}

for(k=0;k<m;k++)

{

B[k] = 0;

for (i=0;i<n;i++)

B[k]=B[k]+Y[i]*F1(k,X[i]);

}

}

int ved(float A[m][m], int i)

{

int g, h, k;

float MaxA;

h = -1;

MaxA = 0;

for(k=i;k<m;k++)

if(fabs(A[k][i])>fabs(MaxA))

{

MaxA = A[k][i];

h = k;

}

if(h == -1)

{

printf("Matrix virogdena\n");

abort ();

}

return h;

}

void perest (float A[m][m],float B [m],int i,int IM)

{

float temp; int j;

if(IM !=i)

{

for (j=i;j<m;j++)

{

temp = A[i][j];

A[i][j] = A[IM][j];

A[IM][j] = temp;

}

temp = B[i];

B[i] = B[IM];

B[IM] = temp;

}

}

void rkoef(float A[m][m],float B[m],int i,int l)

{

int j; float Q;

Q=A[l][i] / A[i][i];

A[l][i] = 0;

for (j=i+1;j<m;j++)

A[l][j] = A[l][j] - Q*A[i][j];

B[l]=B[l] - Q*B[i];

}

void prgauss(float A[m][m],float B[m])

{

int i, IM, l, j;float Q;

for(i=0;i<m;i++)

{

IM = ved(A, i);

perest(A, B, i, IM);

for(l=i+1;l<m;l++)

rkoef(A, B, i, l);

}

for (i=0;i<m;i++)

{

for (j=0;j<m;j++)

printf(" %f ", A[i][j]);

printf("\n");

}

}

void obrgauss(float A[m][m],float B[m],float C[m])

{

int k,j;float Sum;

C[m-1] = B[m-1] / A[m-1][m-1];

for(k = m - 2;k>=0;k--)

{

Sum = B[k];

for(j=k+1;j<m;j++)

Sum = Sum - A[k][j]*C[j];

C[k] = Sum / A[k][k];

}

}

void apr(float C[m],float X[n],float Y[n],float Y1[n],float D[n],float *Kr)

{

int i;

*Kr=0;

for (i=0;i<n;i++)

{

Y1[i]=C[0]*F1(0,X[i])+C[1]*F1(1,X[i])+C[2]*F1(2,X[i]);

D[i]=fabs(Y[i]-Y1[i]);

*Kr=*Kr+D[i]*D[i];

}

}

void krappr(float D[n],float *Dmax, int *IM)

{

int i;

*Dmax=D[0];

*IM=0;

for(i=0;i<n;i++)

if(fabs(D[i])>fabs(*Dmax))

{

*Dmax=D[i];

*IM=i;

}

}

void vivodvsego(float C[m],float X[n],float Y1[n],float D[n],float Kr,float Dmax,int IM)

{

Massiv(C, "C", m);

Massiv(Y1, "Y1", n);

Massiv(D, "D", n);

printf("Dmax = %5.3f pri X[%i] = %5.3f\n",Dmax,IM+1,X[IM]);

printf("Kr = %5.4f\n",Kr);

}

int main()

{

float X[n],Y[n],A[m][m],B[m],C[m],Y1[n],D[n],Dmax,Q,Kr,Sum;

int i, j, IM;

znachenia(X, Y);

koefficent(A, B, X, Y);

printf("Massiv A\n");

for(i=0; i<m; i++)

{

for(j=0; j<m; j++)

printf(" %f ", A[i][j]);

printf("\n");

}

Massiv(B, "B", m);

prgauss(A, B);

obrgauss(A, B, C);

apr(C, X, Y, Y1, D, &Kr);

krappr(D, &Dmax, &IM);

vivodvsego(C, X, Y1, D, Kr, Dmax, IM);

getch();

return 0;

}



6. Результаты машинного счета

6.1 Исходные данные

Таблица 6.1

x	3,0	4,0	5,0	6,0	7,0	8,0
y	3,22	4,21	4,85	5,63	4,77	4,2

6.2 Результаты

Коэффициенты:

С₁= -4,056

С₂ = 12,533

С₃ = -2,212

Таблица 6.2

Значения аппроксимирующей функции	Значения отклонений по абсолютному значению
3,076	0,144
0,469	0,259
5,054	0,204
5,127	0,503
4,846	0,076
4,308	0,108

Максимальное отклонение 0,503 при x₄=6,0, значение критерия аппроксимации 0,400.



Выводы

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

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

В ходе данной работы:

1. Освоены типовые вычислительные методы прикладной математики;

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

3. Усовершенствованы принципы модульного программирования и техники использования подпрограмм.

Размещено на Allbest.ru

...