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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 11.09.2017
Размер файла 360,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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)) его уже полученные компоненты x1(k+1), ...,xi - 1(k+1) сразу же используются для вычисления xi(k+1).

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

x1(k+1) = c11x1(k) + c12x2(k) + ... + c1n-1xn-1(k) + c1nxn(k) + d1 x2(k+1) = c21x1(k+1) + c22x2(k) + ... + c2n-1xn-1(k) + c2nxn(k) + d2 ...xn(k+1) = cn1x1(k+1) + cn2x2(k+1) + ... + cnn-1xn-1(k+1) + cnnxn(k) + dn

где x(0) - некоторое начальное приближение к решению.

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

xi(k+1) = ? j=1i-1 cijxj(k+1) + ? nj=i cijxj(k) + di , 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


Подобные документы

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

    курсовая работа [749,3 K], добавлен 08.06.2019

  • Построение эмпирических формул методом наименьших квадратов. Линеаризация экспоненциальной зависимости. Элементы теории корреляции. Расчет коэффициентов аппроксимации, детерминированности в Microsoft Excel. Построение графиков функций, линии тренда.

    курсовая работа [590,9 K], добавлен 10.04.2014

  • Отделение корней методом простых интеграций. Дифференцирование и аппроксимация зависимостей методом наименьших квадратов. Решение нелинейного уравнения вида f(x)=0 методом Ньютона. Решение системы линейных уравнений методом Зейделя и методом итераций.

    курсовая работа [990,8 K], добавлен 23.10.2011

  • Аппроксимация – процесс замены таблично заданной функции аналитическим выражением кривой. Алгоритм нахождения зависимости между заданными переменными. Условия сходимости итераций к решению системы уравнений. Методы Якоби и Гаусса. Тестирование программы.

    курсовая работа [1,4 M], добавлен 28.08.2012

  • Построение эмпирических формул методом наименьших квадратов. Линеаризация экспоненциальной зависимости. Элементы теории корреляции. Расчет аппроксимаций в табличном процессоре Excel. Описание программы на языке Turbo Pascal; анализ результатов ее работы.

    курсовая работа [390,2 K], добавлен 02.01.2015

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

    курсовая работа [550,5 K], добавлен 13.03.2013

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

    курсовая работа [1,5 M], добавлен 16.02.2013

  • Разработка алгоритма аппроксимации данных методом наименьших квадратов. Средства реализации, среда программирования Delphi. Физическая модель. Алгоритм решения. Графическое представление результатов. Коэффициенты полинома (обратный ход метода Гаусса).

    курсовая работа [473,6 K], добавлен 09.02.2015

  • Решения алгебраических уравнений методом выделения корней. Аппроксимация функций методом наименьших квадратов; дихотомия, бисекция. Одномерная оптимизация многоэкстремальных функций; метод золотого сечения. Многомерная оптимизация градиентным методом.

    курсовая работа [956,7 K], добавлен 04.03.2013

  • Развитие навыков работы с табличным процессором Microsoft Excel и программным продуктом MathCAD и применение их для решения задач с помощью электронно-вычислительных машин. Схема алгоритма. Назначение функции Линейн и метода наименьших квадратов.

    курсовая работа [340,4 K], добавлен 17.12.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.