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

Аппроксимация функции методом наименьших квадратов

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

аппроксимация алгоритм программа

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

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

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

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

3. Освоение принципов модульного программирования и техники использования библиотек на DevC++.

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

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

Пусть изучается связь между величинами X и Y, из которых первая рассматривается в качестве независимой переменной, а вторая - её функции. Исходные данные представлены значениями Y, заданными на некотором множестве М значений X. Тогда ошибка приближения этой зависимости некоторой аппроксимирующей функции для каждого из значений Х может быть оценена разностью

Значения заданы для конечного множества (n) значений Тогда для каждого из этих значений определена и ошибка (см. рисунок)

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

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

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

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

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

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

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

Номер варианта	n	Значения	Базисные функции	Метод решения СЛАУ
9	5	Х	-0.9	-0.3	0.1	0.5	1	1	x		Зейделя
		У	-0.3	0.1	0	0.2	0.7

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

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

(2)

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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



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

где коэффициент и величины определяются выражением

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

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

6.Описание метода Зейделя

Метод Зейделя является модификацией метода простой итерации, заключающейся в том, что при вычислении очередного приближения x^(k+1)) его уже полученные компоненты x₁^(k+1), ...,x_{i - 1}^(k+1) сразу же используются для вычисления x_i^(k+1).

В координатной форме записи метод Зейделя имеет вид:

x₁^(k+1) = c₁₁x₁^(k) + c₁₂x₂^(k) + ... + c_1n-1x_n-1^(k) + c_1nx_n^(k) + d₁ x₂^(k+1) = c₂₁x₁^(k+1) + c₂₂x₂^(k) + ... + c_2n-1x_n-1^(k) + c_2nx_n^(k) + d₂ ...x_n^(k+1) = c_n1x₁^(k+1) + c_n2x₂^(k+1) + ... + c_nn-1x_n-1^(k+1) + c_nnx_n^(k) + d_n

где x⁽⁰⁾ - некоторое начальное приближение к решению.

Таким образом i-тая компонента (k+1)-го приближения вычисляется по формуле

x_i^(k+1) = ? _j=1^i-1 c_ijx_j^(k+1) + ? ⁿ_j=i c_ijx_j^(k) + d_i , i = 1, ..., n

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

Условие окончания итерационного процесса Зейделя при достижении точности е в упрощенной форме имеет вид:

|| x ^(k+1) - x ^(k) || ? е.

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

=+++…+

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

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

F(x)=

F(x)=(3)

Выражение для критерия аппроксимации:

J=

В соответствии с условиями локального минимума функции J() найдём частные производные ,, и приравняем их к нулю:

=()

=0

=()

=0

=()

=0

Получаем систему уравнений:

=

=

=

x	y
-0,9	-0,3	1,43	0,81	-1,287	2,0449	0,27	-0,429
-0,3	0,1	-0,73	0,09	0,219	0,5329	-0,03	-0,073
0,1	0	-0,97	0,01	-0,097	0,9409	0	0
0,5	0,2	-0,25	0,25	-0,125	0,0625	0,1	-0,05
1	0,7	2	1	2	4	0,7	1,4
0,4	0,7	1,48	2,16	0,71	7,5812	1,04	0,848

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

5+0,4+1,48=0,7

+2,16+0,71=1,04

1,48+0,71+7,5812=0,848

=

Ax=b

Решаем систему уравнений методом Зейделя

Ax=b или Cx=d

=

= Cx=d

Приведём к виду x=d

=

=

F(x)=0,0884+0,4473x+0,0546()

	-0,9	-0,3	0,1	0,5	1
	-0,3	0,1	0	0,2	0,7
F()	-0,236	-0,086	0,08	0,298	0,645
	0,064	0,186	-0,08	-0,098	0,055

J()==0,058

=0,186 при x=-0,3



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

Общая схема алгоритма:

Алгоритм функции koeff(x,y,A,B):

Алгоритм функции fi():

Алгоритм функции Zeidel():

Алгоритм функции Zeidel1():

Алгоритм функции value():

Алгоритм функции maxi():

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

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include <stdlib.h>

#include <locale.h>

#define n 5

#define m 3

float fi(float x,int g)

{

if(g==0)

return(1);

else

{

if(g==1)

return x;

else

return (3*x*x-1);

}

}

void koeff(float x[n],float y[n],float A[m][m],float B[m])

{

int i,j,l;

float S;

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

{

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

{

S=0;

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

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

A[i][j]=S;

}

S=0;

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

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

B[i]=S;

}

}

int Zeidel1(float A[m][m])

{

int Flag,i,j,Key;

float Ad,Sd;

Flag=0;

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

{

Ad=fabs(A[i][i]);

Sd=0;

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

if(j!=i)

Sd+=fabs(A[i][j]);

if(Ad>Sd)

Flag=1;

}

if (Flag==1)

Key=0;

else

Key=1;

return Key;

}

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

{

int i,j,Key;

float sum,test,bpx,eps;

printf("\neps=");

scanf("%f", &eps);

Key=Zeidel1(A);

if(Key==0)

{

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

C[i]=B[i]/A[i][i];

do

{

test = 0;

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

{

sum = 0;

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

if (j != i)

sum+=A[i][j] * C[j];

bpx = (B[i] - sum)/A[i][i];

test+=fabs(bpx - C[i]);

C[i] = bpx;

}

}

while (test>=eps);

}

}

void value(float C[m],float x[n],float y[n],float &Kr,float Yl[n],float D[n])

{

int k,i;

Kr=0;

k=0;

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

{

Yl[i]=C[0]*fi(x[i],k)+C[1]*fi(x[i],k+1)+C[2]*fi(x[i],k+2);

D[i]=y[i]-Yl[i];

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

}

}

void maxi(float D[n],float x[n],float &Dmax,int &IM)

{

int i;

Dmax=D[0];

IM=0;

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

{

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

{

Dmax=D[i];

IM=i;

}

}

}

int main()

{

int i,j,l,k,IM;

float A[m][m],B[m],C[m],Yl[n],D[n],Kr,Dmax,x[n],y[n];

printf ("Vvedite x[%i],y[%i]:\n",n,n);

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

{

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

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

}

koeff(x,y,A,B);

printf ("Matrix A[%i][%i],vektor B[%i]:\n",m,m,m);

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

{

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

{

printf ("%.3f\t",A[i][k]);

}

printf ("%.3f\n",B[i]);

}

Zeidel(A,B,C);

printf ("Vektor C[%i]:\n",m);

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

{

printf("C[%i]=%.3f\n",i,C[i]);

}

value(C,x,y,Kr,Yl,D);

maxi(D,x,Dmax,IM);

printf ("\nYl,D,Dmax,IM,Kr:\n\n");

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

{

printf ("%.3f\t%.3f\n",Yl[i],D[i]);

}

printf ("Dmax=%.3f\nx[%i]=%.3f\nKr=%.3f\n",Dmax,IM+1,x[IM],Kr);

getch();

return 0;

}



Заключение

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

· Подсчитанные вручную;

· Подсчитанные на ЭВМ, при помощи составленной программы;

Значение критерия аппроксимации отличается от результата, полученного при ручном счёте приблизительно на 0.1%.

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