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

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

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

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

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

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ: ИНФОРМАТИКА И ПРОГРАММИРОВАНИЕ

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

Студент

Соловьев Д.М.

Доцент

Прокушев Л.А.

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



Содержание

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

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

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

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

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

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

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

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

9. График

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

11. Анализ результатов. Выводы



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

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

Пусть изучается связь между величинами и , из которых первая рассматривается в качестве независимой переменной, а вторая - ее функции. Исходные данные представлены значениями , заданными на некотором множестве значений 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, принимаемых во внимание.

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

.

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

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

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

.

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

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

Заданные точки	Базисные функции	Метод решения
Xi	2	3	4	5	6	1	ln(x)	x	Метод Гаусса
Yi	2,41	2,85	3,91	5.2	9,8

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

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

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

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

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

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

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

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

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

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

Замечание. Функции 1(x), 2(x),…, m(x) называются линейно-независимыми, если при любых x равенство

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

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

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

(x) = С1 1(x) + С2 2(x) +…+ Сm m(x)

и подставим его в формулу критерия аппроксимации.



.

Применим операцию дифференцирования к параметру С1 :

и, выполняя необходимые алгебраические преобразования, получим уравнение

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

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

a11 С1 + a12 С2 +…+ a1m Сm = b1

a21 С1 + a22 С2 +…+ a2m Сm = b2

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

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



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

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

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

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

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

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

a11 x1 + a12 x2 +…+ a1n xn = b1

a21 x1 + a22 x2 +…+ a2n xn = b2

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

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



A X = B, где

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

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

Решение системы линейных уравнений сводится к отысканию значений элементов вектора-столбца (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 равен нулю. Вводя новые обозначения для коэффициентов

k=(2, …, n) ,

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

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

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

и т.д.

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

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

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

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

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

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

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

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



,

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

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

.

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

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

.

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



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

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

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

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

Подпрограмма функции fi



Алгоритм подпрограммы нахождения матриц А и В:



Алгоритм подпрограммы вывода матрицы А:

Алгоритм подпрограммы вывода вектора В:

· Алгоритм подпрограммы решения системы линейных уравнений методом Гаусса:



Основная программа:

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

Xi	Yi	Y(x)	ДY-Y(x)
2	2.41	2.64	-0.23
3	2.85	2.31	0.54
4	3.91	3.76	0.15
5	5.2	6.2	-1
6	9.8	9.26	0.54

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

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<alloc.h>

#define n 3

#define m 5

void writematri(float A[n][n]);

void writevector(float B[n]);

float fi(int k,float x);

void gauss(float B[n],float A[n][n], float E[n]);

void main()

{ float A[n][n], B[n], C[n][n+1], Y[m],d[m],E[n],J,S,x[m]={0.3,0.5,0.7,0.9,1.1},y[m]={1.2,0.7,0.3,0.9,1.5};

int k,l,i;

clrscr();

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

{for(l=0;l<n;l++)

{S=0;

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

S=S+fi(k,x[i])*fi(l,x[i]);

A[k][l]=S;

}

S=0;

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

S=S+y[i]*fi(k,x[i]);

B[k]=S;

}

printf("matrica A[%i][%i]:\n",n,n);

writematri(A);

printf("vector B[%i]:\n",n);

writevector(B);

gauss(B,A,E);

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

{ S=0;

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

S=S+E[k]*fi(k, x[i]);

Y[i]=S;

d[i]=y[i]-Y[i];

}

puts("Num Xi\t\tYi\tY(Xi) Di=Yi-Y(Xi)");

puts("----------------------------------------------------------------");

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

{ printf("%2i %5.2f %5.2f\t%5.2f\t%5.2f\n", i+1, x[i],y[i],Y[i],d[i]);

}

puts("----------------------------------------------------------------");

S=0;

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

{ S=S+d[i]*d[i];

}

J=S;

printf("Kriteriy approksimacii J:");

printf("%5.2f", J);

float max=d[0];

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

if((fabs(d[i]))>max)

max=fabs(d[i]);

printf("\n\n|d| max:");

printf("%5.2f", max);

getch();

}

void writematri(float A[n][n])

{ int i,j;

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

{for(j=0;j<n;j++)

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

printf("\n");

}

}

void writevector(float B[n])

{ int i;

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

printf("%5.2f ",B[i]);

}

float fi(int k,float x)

{ if (k==0)

return 1;

if (k==1)

return x;

else return x*x*x;

}

void gauss(float B[n],float A[n][n],float E[n])

{

float t,C[n][n+1];

int k,i,j;

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

{

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

C[i][j]=A[i][j];

C[i][3]=B[i];

}

printf("\n\n Isxodnaya matrica: \n \n");

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

{

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

printf("%6.2f\t", C[j][i]);

printf("\n");

E[j] = 0;

}

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

if (C[j][i] == 0)

{

k = j;

while ((C[k+1][j] == 0) && (k < n))

k++;

if (C[k+1][j] != 0)

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

{

t = C[j][i];

C[j][i] = C[k+1][i];

C[k+1][i] = t;

}

else

printf("Matrica imeet mnojestvo reshenii");

}

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

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

{

if (C[k][k] !=0)

{

t = C[j][k] / C[k][k];

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

C[j][i] = C[k][i] * t - C[j][i];

}

else

printf("Ne imeet reshenii");

}

/* printf("\n Matrica privedena k treygolnomy vidy:\n\n");

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

{

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

printf("%6.2f\t", C[j][i]);

printf("\n");

} */

for (j = n - 1 ; j >= 0; j--)

{

t = C[j][n];

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

t= t - C[j][i] * E[i];

E[j] = t / C[j][j];

}

printf("\n Korni:\n\n");

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

printf("C%d = %6.2f\n", i, E[i]);

}



9. График

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

11. Анализ результатов. Выводы

Введя исходные данные (набор координат X и Y), мы получаем матрицу 3х3 из коэффициентов линейных уравнений и вектор из свободных членов. Методом Гаусса мы нашли искомые коэффициенты для аппроксимирующей функции. На всех этапах работы мы сверяли значения со значениями, полученными в ручном счете, и удостоверялись в их правильности.

Далее мы вычислили все отклонения, определили максимальное и вывели критерий аппроксимации.

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

В ходе данной работы мы освоили:

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

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

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

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

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

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