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

 

Змінимо індексацію в системі (1.12). В результаті отримаємо:

(1.13)

де

- невідомі системи лінійних  рівнянь(1.13)

- коефіцієнти системи лінійних рівнянь(1.13).

- вільні члени системи лінійних  рівнянь (1.13),

(x_i, y_i) - координати вузлових точок табличної функції, ,

N - кількість вузлових точок,

m - степінь апроксимуючого многочлена виду:

(1.14)

 

 

2 Розробка алгоритму роботи обчислювальної задачі

 

2.1 Розробка функціональної  структури програми (перелік та  призначення її режимів та  структури діалогу задачі)

 

Повинно бути створено програму за методом найменших квадратів. Базова структура програми буде складатися з трьох головних блоків:

– інтерфейсу для введення початкових даних;

– безпосередньо вирішення поставленої  задачі;

– інтерфейсу для виведення отриманих  результатів.

При введенні початкових даних користувачу  потрібно буде дотримуватись підказок щодо введення необхідних даних.

Загальна функціональна структура  програми наведена на рисунку 1.

 

 

2.2 Розробка алгоритму виконання задачі за методом найменших квадратів

1. Будуємо систему лінійних рівнянь (1.13). Визначаємо коефіцієнти c_k,j і вільні члени d_k. Так як система (1.13) симетрична відносно головної діагоналі, то достатньо визначити лише наддиагональні элементи системи.
2. Розв’язуємо систему (1.13) методом Гаусса. Знаходим коэфіцієнти aj многочлена (1.14).
3. Будуємо апроксимуючий многочлен (1.14) и знаходимо його значення в кожній вузловій точці P_i = P_m(x_i).
4. Знаходимо відхилення кожної вузлової точки .
5. Знаходимо суму квадратів відхилень по всім вузловим точкам .
6. Знаходимо остаточну дисперсію .

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

(2.1)

Тоді для знаходження значення многочлена (2.1) зручно користуватись схемою Горнера. Рекуррентна формула по схемі Горнера має вид:

Схема алгоритму МНК представлена на рисунку 1.1 . Схеми алгоритмів основних блоків представлені на рисунках 1.2 – 1.4.

 
Рисунок. 1.1-  Схема алгоритму апроксимації методом найменших квадратів

Позначення в блоці 2:

m - степінь апроксимуючого многочлена,

N - кількість вузлових точок,

X, Y - масиви значень x и y.

 
Рисунок 1.2 - Схема алгоритма блоку 3. Визначення коефіцієнтів системи (1.13)

 
Рисунок 1.3 - Схема алгоритма блоку 4. Визначення вільних членів системи (1.13)

 
Рисунок 1.4 - Схема алгоритму блока 6. Схема Горнера

 

3 Розробка програми за запропонованим алгоритмом

 

Усі блок-схеми алгоритмів, що розробленні  у курсовій роботі, приведені для  загального випадку.

 

3.1 Розробка програми за методом апроксимації функції поліномом методом найменших квадратів

Опишемо спочатку, що таке апроксимація і як ця задача вирішена в даному випадку.  
 Нехай на деякому відрізку в точках x0, x1, x2, ... xN нам відомі значення деякої функції f (x), а саме y0, y1, y2, ... yN.  
Потрібно визначити параметри ai многочлена виду  
F (x) = a0 + ax + a2x2 + ... + Akxk, де k <N  
такого, що сума квадратів відхилень значень y від значень функції F (y) у заданих точках x була мінімальною, тобто  
S = Σ [yi - F (xi, a0, a1 ... ak)] 2 -> min  
 Геометрично це означає, що потрібно знайти криву y = F (x), поліном, який проходить як можна ближче до кожної з заданої точок.  
 Таке завдання може бути вирішена, якщо вирішити систему рівнянь виду, який представлений у таблиці 2 :

Таблиця 2 – Система рівнянь

a0n +	a1Σ xi +	a2Σ xi2 +	... +	akΣ xik =	Σ yi
a0Σ xi +	a1Σ xi2 +	a2Σ xi3 +	... +	akΣ xik+1 =	Σ xiyi
...
a0Σ xik +	a1Σ xik+1 +	a2Σ xik+2 +	... +	akΣ xi2k =	Σ xikyi

де скрізь під символом Σ мається на увазі підсумовування по i від 0 до N.  
 Для вирішення системи скористаємося методом Гаусса в якому система рівнянь приводиться до трикутного виду. Я вже описував цей метод. Описувана в даному розділі програма заснована на вже згаданій, тому я не буду детально зупинятися на сутності методу Гауса, лише наведу текст програми і коротко опишу методику роботи з нею, а також її структуру, а саме, для чого служить така велика кількість підпрограм в цій програмі.  
 Коротко опишемо, для чого служить така велика кількість підпрограм і змінних в даній програмі:  
• a - невідомі коефіцієнти полінома  
• b - стовпець вільних членів (у правій частині рівнянь)  
• x - координати, задані у файлі  
• y - координати, задані у файлі  
• sums - суми ступенів x, y при невідомих коефіцієнти полінома  
• N - число заданих точок у файлі  
• K - ступінь апроксимує полінома

• void count_num_lines() - підраховує кількість точок, де задана функція
• void allocmatrix() - виділяє пам’ять для масивів a, b, x, y, sums
• void readmatrix() - прочитує з файла координати точок и знаходить sums_ij
• void diagonal() - робить так, щоб на головній діагоналі не було нулів, щоб не довелось ділити на нуль в процесі доведення системи до трикутного виду
• void printresult() - роздруковує отриманий стовпець роз’вязку
• void freematrix() - звільняє пам’ять, яка була виділена раніше
• void cls() - зтирає экран на початку роботи програми
• void main() - основна функція з якої послідовно викликаються всі вишеперераховані функції, і проходить процес доведення системи рівнянь до трикутного виду и “обратная прогонка”.

 

3.2 Результати роботи програми

 

Рисунок 2.1 - Знайдені значення функції (степінь полінома=3)

 

 

Рисунок 2.2 – Знайдені значення функції(степінь полінома=7)

 

 

 

3.3 Перевірка роботи в Math Cad

Для степення полінома = 3

 

 

 

 

 

 

 

 

    

    

 

 

 

 

 

4 Інструкція користувача

Розроблена вище програма написана на мові C [3,8], з використанням компілятора Borland C 3.0  та скомпільовані у *.exe файли. Для роботи програм та запуску файлів рекомендується середовище Windows сумісних операційних систем.

Розроблений програмний комплекс досить зручний у користуванні. Щоб запустити  програму потрібно запустити *.exe файл із назвою, яка відповідає обраному інтерполяційному многочлену. Для рядового користувача потрібно лише запустити виконуваний файл та ввести : кількість відомих значень x та y, таблицю значень x та y, потрібне йому значення x, в якому йому потрібно буде знайти значення у.

Щоб скористатися цією програмою, потрібно запустити скомпільований виконуваний файл. В першу чергу програма запитає, звідки їй брати дані для інтерполяції. Створіть у будь-якому текстовому редакторі (але тільки не в Word-е а, наприклад в notepad-е) файл, де напишіть значення xi, yi, підрядник через пробіл, приблизно так як показано в таблиці 3:

Таблиця 3 – таблиця значень хі, уі 

x0	y0
x1	y1
x2	y2
...
xN	yN

Наприклад:

Таблиця 4 – Приклад до таблиці 3

1	5.95
2	20.95
3	51.9
4	105
5	186
6	301
7	456.1
8	657.1

Цей файл необхідно створити в тій директорії, де лежить програма, інакше вона його не знайде. 
 Програма запитає ступінь полінома, яким ви хочете апроксимувати дані. При цьому ступінь полінома повинна бути менше числа заданих точок (у даному випадку восьми). Введіть, наприклад, 3. У результаті роботи програми, вона видасть щось на кшталт: 
 a[0] = 0.996902  
 a[1] = 1.938750  
 a[2] = 2.016942  
 a[3] = 0.999054

ВИСНОВКИ

 

Використовуючи  відомі математичні формули розроблено блок-схеми алгоритмів апроксимації табличних функцій за методом найменших квадратів. За допомогою мови програмування С було створено програми, що реалізують відповідні алгоритми.

 Під час  створення програм краще засвоєно як саму мову програмування так і методи та підходи для вирішення подібних задач, а також правильну структуру та оформлення курсової роботи.

Розроблену  у курсовій роботі програму можна  використовувати також для екстраполяції  функцій, але точність обчислень у даному випадку буде меншою, так як не використовуються оптимізовані формули.

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

За допомогою цієї програми можна полегшити обрахунки в великомасштабних задачах.

 

 

 

Перелік посилань

1. Щуп Т. Решение инженерных задач на ЕВМ. – М.: Мир, 1982. – 235с.

2. Демидович Б. П., Марон И. А. Основы вычислительной математики. – М.: Наука, 1970. – 664 с.

3. Демидович Б. П., Марон И. А., Шувалова Е. З. Численные методы анализа. – М.: Мир, 1967. - 359 с.

4. Мак – Кракен Д., Дрон У. Численные методы и програмирование на фортране. – М.: Мир, 1977. – 584 с.

5. Бахвалов Н. С. Численные методы . Т. И. Анализ, алгебра, обычные диференциальные уравнения. – М.: Наука, 1975. – 631 с.

6. Краскевич В. Є., Зеленський К. Х., Гречко В. И. Численные методы в инженерных исследованиях. – К.: Высшая шк.., 1986. – 263 с.

7. Рисс Ф., Секефальви – Надь Б. Лекции по функциональному анализу – М.: Мир, 1979. - 428 с.

8. Плис А.И., Сливина Н.А. Mathcad. Математический практикум для инженеров и экономистов: – М.: Финансы и статистика, 2003. – 656с.

9. Тихомиров В. М. Некоторые вопросы теории приближений. – М.: МГУ, 1976. - 507 с.

10. Ахиезер Н. И. Лекции по теории апроксимации. – М.: Наука, 1965. - 365 с.

11. В.И. Бердышев, Ю.Н. Субботин. Численные методы приближения функций. – Средне-Уральское книжное книжное издательство, 1979. - 605 с.

 

ДОДАТОК А.

БЛОК-СХЕМА АПРОКСИМАЦІЇ ЗА МЕТОДОМ

НАЙМЕНШИХ КВАДРАТІВ

 

 

 

 

Додаток Б

Текст програми апроксимації за методом найменших квадратів

#include <stdio.h>

#include <process.h>

#include <math.h>

float *a, *b, *x, *y, **sums;

int N, K;

//N - number of data points

//K - polinom power

//K<=N

char filename[256];

FILE* InFile=NULL;

void count_num_lines(){

   //count number of lines in input file - number of equations

   int nelf=0;       //non empty line flag

   do{

       nelf = 0;

       while(fgetc(InFile)!='\n' && !feof(InFile)) nelf=1;

       if(nelf) N++;

   }while(!feof(InFile));

}

 

void freematrix(){

   //free memory for matrixes

   int i;

   for(i=0; i<K+1; i++){

       delete [] sums[i];

   }

   delete [] a;

   delete [] b;

   delete [] x;

   delete [] y;

   delete [] sums;

}

 

void allocmatrix(){

   //allocate memory for matrixes

   int i,j,k;

   a = new float[K+1];

   b = new float[K+1];

   x = new float[N];

   y = new float[N];

   sums = new float*[K+1];

   if(x==NULL || y==NULL || a==NULL || sums==NULL){

       printf("\nNot enough memory to allocate. N=%d, K=%d\n", N, K);

       exit(-1);

   }

   for(i=0; i<K+1; i++){

       sums[i] = new float[K+1];

       if(sums[i]==NULL){

   printf("\nNot enough memory to allocate for %d equations.\n", K+1);

       }

   }

   for(i=0; i<K+1; i++){

       a[i]=0;

       b[i]=0;

       for(j=0; j<K+1; j++){

   sums[i][j] = 0;

       }

   }

   for(k=0; k<N; k++){

       x[k]=0;

       y[k]=0;

   }

}

 

void readmatrix(){

   int i=0,j=0, k=0;

   //read x, y matrixes from input file

   for(k=0; k<N; k++){

       fscanf(InFile, "%f", &x[k]);

       fscanf(InFile, "%f", &y[k]);

   }

   //init square sums matrix

   for(i=0; i<K+1; i++){

       for(j=0; j<K+1; j++){

   sums[i][j] = 0;

   for(k=0; k<N; k++){

       sums[i][j] += pow(x[k], i+j);

   }

       }

   }

   //init free coefficients column

   for(i=0; i<K+1; i++){

       for(k=0; k<N; k++){

   b[i] += pow(x[k], i) * y[k];

       }

   }

}

 

void printresult(){

   //print polynom parameters

   int i=0;

   printf("\n");

   for(i=0; i<K+1; i++){

       printf("a[%d] = %f\n", i, a[i]);

   }

}

void diagonal(){

   int i, j, k;

   float temp=0;

   for(i=0; i<K+1; i++){

       if(sums[i][i]==0){

   for(j=0; j<K+1; j++){

       if(j==i) continue;

       if(sums[j][i] !=0 && sums[i][j]!=0){

   for(k=0; k<K+1; k++){

       temp = sums[j][k];

       sums[j][k] = sums[i][k];

       sums[i][k] = temp;