Аппроксимация функции методом наименьших квадратов
Критерий аппроксимации. Система нормальных уравнений, расчет их параметров методом Зейделя. Расчет максимального по модулю отклонения аппроксимирующей функции. Схемы алгоритмов и их описание. Программа и результаты расчётов параметров на компьютере.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 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