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

з Обчислювальної техніки та програмування до задач фотоніки та лазерної інженерії
(назва дисципліни)
на тему Згладжування функцій методом найменших квадратів


ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
До курсової роботи з дисципліни
«Обчислювальна техніка та основи програмування»

Назва: Згладжування функцій методом найменших квадратів.
Мета: розробити програму на мові С, яка розв’язує задачу методом найменших квадратів, обраховує похибку та виводить значення обрахунків.
Що відомо: згладжування функцій метод розв’язання – метод найменших квадратів.
Що зробити: проаналізувати метод найменших квадратів, розробити алгоритм для виконання задачі, створити програму, яка за вхідними даними розв’яже цю задачу, видасть результати та похибку обчислень.
Проаналізувати: після знаходження результатів розв’язання та похибки, порівняти їх.
Література:
1. Т.П.Щуп Решение инженерных задач – М.: Мир, 1982. – 235с.
2. Б. П. Демидович. Основы вычислительной математики. / Демидович Б. П., Марон И. А. – М.: Наука, 1970. – 664 с.
Отримав: ст. гр. О-12 Олійник А.М. ”_____”_____________2013р. Керівник: к.т.н., доцент Кожем’яко А.В

АНОТАЦІЯ

У даній курсовій роботі виконується розробка алгоритму та програми на мові програмування С, для розв’язання задачі методом найменших квадратів.
До даної програми також подано математичну модель розв’язку, наведено блок-схему порядку розв’язання програмою поставленої задачі, текст програми та інструкцію користувача, в якій описано для чого призначена програма і як нею користуватися, починаючи з запуску.

АННОТАЦИЯ

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

THE SUMMARY
This course work is carried out of an algorithm and program for the C programming language, for solving the least squares method.
Before this program also provides a mathematical model solution, are flowchart software solutions of the task, the text of the program and user manual, which explains why the program is and how to use it since launch.

ЗМІСТ
ВСТУП……………………………………………………………………...……7
РОЗДІЛ 1 Математичні аспекти методу найменших квадратів ……..............8
1.1 Область застосування задачі…………………………………………8
1.2 Математичне обґрунтування задачі….……………………………..10
РОЗДІЛ 2 Розробка алгоритму роботи обчислювальної задачі………….....16
2.1 Розробка функціональної структури програми…………………....16
2.2 Розробка алгоритму виконання задачі найменших квадратів …...16
РОЗДІЛ 3 Розробка програми за запропонованим алгоритмом………….....20
3.1 Розробка програми за методом найменших квадратів …...…….…20
3.2 Результати роботи програми…………………….…………………..22
3.3 Розробка програми в Math Cad……………………….……………..23
РОЗДІЛ 4 Інструкція користувача…………………….…..……...……….….24
Висновки……………………………………………………..……….………....26
Перелік посилань ……………….............................................……………..…..27
Додаток А. Блок-схема згладжування за методом найменших квадратів…...25
Додаток Б. Текст програми згладжування за методом найменших квадратів26













ВСТУП


Задача про згладжування функцій є однією з основних задач чисельного аналізу та використовується повсякчас для різноманітних інженерних обрахунків наприклад: для поліпшення обрахунку деяких задач(звичайно використання згладжування не обмежується лише вищезазначеним прикладом). [1]
Потрібно вказати, що ж саме являє собою згладжування: Згладжування - в обчислювальній математиці спосіб полегшення розв’язання задач.
Мета курсовій роботі це: розробка программного забезпечення для згладжування функції методом найменших квадратів.
Для виконання вищезазначеного завдання потрібно розробити алгоритм вирішення задачі, та забезпечити його реалізацію, використовуючи засоби мови програмування С.
Програму, яка має бути розроблена у курсовій роботі можна буде використовувати у навчальних цілях для знаходження значень функції у невідомих точках для побудови графіків функцій, або деяких інженерних обчислень.

РОЗДІЛ 1МАТЕМАТИЧНІ АСПЕКТИ МЕТОДУ НАЙМЕНШИХ КВАДРАТІВ


1.1 Область застосування задачі
Інженеру звичайно приходиться працювати з великими масивами даних, тому методи обробки числових даних мають для нього особливе значення. Часто шляхом до правильного розуміння багатьох задач служить продумане уявлення початкових даних. До речі невдале уявлення експериментальних даних буває причиною помилок в розв’язанні складних задач.Для того щоб отримати аналітичні залежності, що описують великі масиви даних, використовують методи згладжування, які основані на тому, що масив даних замінюють простою функцією (лінійною або квадратичною або кубічною або іншою), яка не обов’язково проходить через всі експериментальні точки, але описує тенденції зміни цих даних та забезпечує мінімум суми квадратів відхилень експериментальних даних від цією функції.Припустимо, що в результаті інженерного або наукового експерименту отримана система точок . Необхідно знайти аналітичну залежність , таку, яка найкращим чином описує задану систему точок. [4]
Поняття "найкращим чином" означає розв’язання задачі по заданому критерію. Найбільш відомим критерієм для задач апроксимації є критерій середньоквадратичних відхилень (СКВ), який являє собою мінімізацію суми квадратів відхилень експериментальних даних від аналітичної функції і визначається на заданій множині точок як
- ) min, (1.1)

однак при такій постановці задача згладжування експериментальних даних має багато розв’язків. Для отримання єдиного розв’язку цієї задачі потрібно задавати значення певного вигляду, наприклад:
степеневим поліномом
+ x+ +…+ ,(1.2)
тригонометричним поліномом
+ coskx+ sinks), (1.3)
ортогональним поліномом
(x)+ (x)+…+ (), (1.4)
сплайн-функцією та інш.
Розглянемо загальні математичні моделі, які можна отримати при згладжувані табличних функцій степеневим поліномом. В результаті інженерного або наукового експерименту отримана система точок . Необхідно знайти степеневий поліном виду:
, (1.5)
такий, щоб сума квадратів відхилень полінома від заданої системи експериментальних точок була би мінімальною. Така задача зводиться до визначення коефіцієнтів поліному . Метод, що дозволяє розв’язати її називається методом найменших квадратів (МНК). Критерій середньо квадратичного відхилення (СКО) в даному випадку має вигляд:
(1.5)

1.2 Математичне обґрунтування задачі

У цьому методі при згладжуванні досвідчених даних апроксимуючої криву F (x) прагнуть провести так, щоб її відхилення від табличних даних по всім вузловим точкам були мінімальними, тобто

, (1.6)
Позбудемося знака ухилення. Тоді умова (1.6) буде мати вигляд:
, (1.7)

Суть методу найменших квадратів полягає в наступному: для табличних даних, отриманих у результаті експерименту, відшукати аналітичну залежність F (x), сума квадратів ухилень якої від табличних даних по всіх вузловим точкам була б мінімальною, тобто
, (1.8)
Для визначеності завдання шукану функцію F (x) будемо вибирати з класу алгебраїчних многочленів ступеня m:
= + + +…+ , (1.9)
Назвемо многочлен (1.9) згладжувальним многочленом. Згладжувальний многочлен не проходить через всі вузлові точки таблиці. Тому його ступінь m не залежить від числа вузлових точок. При цьому завжди m Якщо m = 1, то ми згладжуємо табличну функцію прямою лінією. Така задач називається лінійної регресією.
Якщо m = 2, то ми згладжуємо табличну функцію квадратичної параболою. Така задача називається квадратичною згладжувальністю.
Якщо m = 3, то ми згладжуємо табличну функцію кубічною параболою. Така задача називається кубічної згладжувальністю. [8]
Уточнимо метод найменших квадратів: для табличної функції, отриманої в результаті експерименту, побудувати згладжувальної многочлен (1.9) ступеня m, для якого сума квадратів відхилень за всіма вузловим точкам мінімальна, тобто
S= ( )- )−min, (1.10) (1.10)
(1.10
Змінимо вигляд многочлена Pm. Поставимо на останнє місце складові, які містять xm. На передостаннє - складові, які містять xm-1 і т.д. У результаті отримаємо:
+ + +…+ ,
(1.11)
або

,
При цьому змінимо індекси коефіцієнтів многочлена. Тоді умова (1.8) буде мати вигляд:
-min де
xi і yi-координати вузлових точок таблиці,
aj, J=0,m- невідомі коефіцієнти многочлена (1.11).
- коефіцієнти системи лінійних рівнянь (1.11),
- вільні члени системи лінійних рівнянь (1.12),
Порядок системи дорівнює m +1. [3]
При ручному рахунку коефіцієнти ck і вільні члени dj зручно визначати, користуючись таблицею 1.1:












Таблиця 1.1- таблиця для розрахунку коефіцієнтів і вільних членів системи
i xi0 xi1 xi2 ... xi2m xi0 yi xi1 yi ... xim
0 1
1 1
2 1
... ...
N 1

c0 c1 c2 ... c2m d0 d1 ... dm



(1.13)


Змінимо індексацію в системі (1.12). В результаті отримаємо:
невідомі системи лінійних рівнянь(1.13)
1,(m+1) вільні члени системи лінійних рівнянь (1.13), (xi, yi) - координати вузлових точок табличної функції, i=1,N,
N - кількість вузлових точок,
m - степінь згладжувального многочлена виду:
(x)= + + +…+ , (1.14)




РОЗДІЛ 2 РОЗРОБКА АЛГОРИТМУ РОБОТИ ОБЧИСЛЮВАЛЬНОЇ ЗАДАЧІ


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

Повинно бути створено програму за методом найменших квадратів. Базова структура програми буде складатися з трьох головних блоків:
– інтерфейсу для введення початкових даних;
– безпосередньо вирішення поставленої задачі;
– інтерфейсу для виведення отриманих результатів.
При введенні початкових даних користувачу потрібно буде дотримуватись підказок щодо введення необхідних даних.
Загальна функціональна структура програми наведена на рисунку 1. [7]

2.2 Розробка алгоритму виконання задачі за методом найменших квадратів
1. Будуємо систему лінійних рівнянь (1.13). Визначаємо коефіцієнти ck,j і вільні члени dk. Так як система (1.13) симетрична відносно головної діагоналі, то достатньо визначити лише наддіагональні элементи системи.
2. Розв’язуємо систему (1.13) методом Гаусса. Знаходим коэфіцієнти aj многочлена (1.14).
3. Будуємо згладжувальний многочлен (1.14) и знаходимо його значення в кожній вузловій точці Pi = Pm(xi).
4. Знаходимо відхилення кожної вузлової точки = -
5. Знаходимо суму квадратів відхилень по всім вузловим точкам S= Знаходимо остаточну дисперсію D= .[3]

Для побудови згладжувального многочлена (1.11) і знаходження його значення в кожній вузловій точці використаємо раціональну форму многочлена:
(x)= +x ( )+x( )+…+x( )… (1.15)
(2.1)
Тоді для знаходження значення многочлена (2.1) зручно користуватись схемою Горнера. Рекуррентна формула по схемі Горнера має вид:
P= +1 , P= + P,j=m,1-1,i=1,N (1.16)














РОЗДІЛ 3 РОЗРОБКА ПРОГРАМИ ЗА ЗАПРОПОНОВАНИМ АЛГОРИТМОМ


3.1 Розробка програми за методом згладжування функції поліномом методом найменших квадратів
Опишемо спочатку, що таке згладжування і як ця задача вирішена в даному випадку.
Нехай на деякому відрізку в точках x0,x1,x2, ... xN нам відомі значення деякої функції f (x), а саме y0, y1, y2, ... yN. Потрібно визначити параметри ai многочлена виду F (x) = a0 + ax + a2x2 + ... + Akxk, де k min
Геометрично це означає, що потрібно знайти криву y = F (x), поліном, який проходить як можна ближче до кожної з заданої точок.
Таке завдання може бути вирішена, якщо вирішити систему рівнянь виду, який представлений у таблиці 3.1:
Таблиця 3.1– Система рівнянь
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.
Для вирішення системи скористаємося методом Гаусса в якому система рівнянь приводиться до трикутного виду. Я вже описувала цей метод. Описувана в даному розділі програма заснована на вже згаданій, тому я не буду детально зупинятися на сутності методу Гауса, лише наведу текст програми і коротко опишу методику роботи з нею, а також її структуру, а саме, для чого служить така велика кількість підпрограм в цій програмі.
Для створення програми потрібно використати алгоритм розв’язання певної задачі .Спочатку вводимо m,N,X,Y. Де m- це степінь згладжувального многочленна, N- кількість вузлових точок, X,Y- це масиви значень x та y та присвоюємо k=1,в результаті виконується цикл для значення з умовою m+1.Після цього присвоюємо j=k і тоді виконуємо операцію циклу m+1.Присвоюємо S=0 та i=1 і виконуємо цикл від 0 до N.Після цього,якщо k+j=2 ми отримаємо S=S+1,інакше .Так повторюється поки попередній цикл дійде до значення N.Після цього програма повертається до того циклу, коли j=k,це обчислюється при m від 0 до m+1,далі повертаємося до циклу, де k=1,який виконується від 0 до m+1.Далі присвоюємо S=0,виконуємо цикл j=1 до N,якщо k=1 то S=S+ інакше .Повертаємося до циклу j=1 до N.Далі присвоюємо d=S ,повертаємось до циклу k=1 до m+1.
Потім виводиться на екран повідомлення про вирішення системи методом Гауса, де присвоюємо значення S=0 та виконуємо цикл i=1,N. Присвоюємо цикл j=m,1,-1.Наступним кроком для виконання буде присвоювання ,після чого повертаємося до циклу j=m,1,-1,де присвоюємо .Після вище зробленого повертаємося до циклу i=1,N та присвоюємо P=S/(N-(m+1)).Останнім етапом буде введення даних обрахунків,де і закінчується дана програма.
Коротко опишемо, для чого служить така велика кількість підпрограм і змінних в даній програмі:
• a - невідомі коефіцієнти полінома
• b - стовпець вільних членів (у правій частині рівнянь)
• x - координати, задані у файлі
• y - координати, задані у файлі
• sums - суми ступенів x, y при невідомих коефіцієнти полінома
• N - число заданих точок у файлі
• K - ступінь згладжує полінома
• void count_num_lines() - підраховує кількість точок, де задана функція
• void allocmatrix() - виділяє пам’ять для масивів a, b, x, y, sums
• void readmatrix() - прочитує з файла координати точок и знаходить sumsij
• void diagonal() - робить так, щоб на головній діагоналі не було нулів, щоб не довелось ділити на нуль в процесі доведення системи до трикутного виду
• void printresult() - роздруковує отриманий стовпець роз’вязку
• void freematrix() - звільняє пам’ять, яка була виділена раніше
• void cls() - зтирає экран на початку роботи програми
• void main() - основна функція з якої послідовно викликаються всі вишеперераховані функції, і проходить процес доведення системи рівнянь до трикутного виду и “обратная прогонка”.[11]






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


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



3.3 Перевірка роботи в Math Cad
Для степення полінома = 3























При перевірці роботи в Math Cad буде видно сукупність точок для побудови графіка:

Для цього взято значення х,та відповідно до нього значення y.
Виходячи із цього було видно ,що результат програми та перевірка в Math Cad є ідентичними. Тобто робота методом найменших квадратів виконана вірно.

РОЗДІЛ 4 Інструкція користувача


Розроблена вище програма написана на мові C [3,8], з використанням компілятора Borland C 3.0 та скомпільовані у *.exe файли. Для роботи програм та запуску файлів рекомендується середовище Windows сумісних операційних систем.
Розроблений програмний комплекс досить зручний у користуванні. Щоб запустити програму потрібно запустити *.exe файл із назвою, яка відповідає обраному інтерполяційному многочлену. Для рядового користувача потрібно лише запустити виконуваний файл та ввести : кількість відомих значень x та y, таблицю значень x та y, потрібне йому значення x, в якому йому потрібно буде знайти значення у.
Щоб скористатися цією програмою, потрібно запустити скомпільований виконуваний файл. В першу чергу програма запитає, звідки їй брати дані для інтерполяції. Створіть у будь-якому текстовому редакторі (але тільки не в Word-е а, наприклад в notepad-е) файл, де напишіть значення xi, yi, підрядник через пробіл, приблизно так як показано в таблиці 4.1:
Таблиця 4.1 – таблиця значень хі, уі

x0 y0
x1 y1
x2 y2
...
xN yN

Таблиця 4.2 – Приклад до таблиці 4.1
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



ВИСНОВКИ


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



ПЕРЕЛІК ПОСИЛАНЬ

1. Щуп Т. Решение инженерных задач на ЕВМ. / Т.Щуп 1982. – 235с.
2. Демидович Б. П., Марон И. А. Основы вычислительной математики./Б. П.,Демидович , И. А Марон – М.: Наука, 1970. – 664 с.
3. Демидович Б. П. З. Численные методы анализа./ Б. П Демидович , И. А Марон , Е Шувалова . – М.: Мир, 1967. -¬¬¬ 359 с.
4. Кракен Д., Дрон У. Численные методы и програмирование на фортране./ Д. Кракен , У Дрон – М.: Мир, 1977. – 584 с.
5. Аналоп Т. И, Aлгебра, обычные диференциальные уравнения./ Т. И. Аналоп – М.: Наука, 1975. – 631 с.
6. Краскевич В.Є Численные методы в инженерных исследованиях./ В. Є Краскевич , К. Х., Зеленський , В. И. Гречко – К.: Высшая шк.., 1986. – 263 с.
7. Рисс Ф., Лекции по функциональному аналізу/ Ф Рисс , Б Секефальви – Надь – М.: Мир, 1979. - 428 с.
8. Петросян Л. А. Введение в математическую екологію / Л. А. Петросян, В.В. Захаров — Л.: Изд-во ЛГУ, 1986. — 222 с.







ДОДАТОК А.
БЛОК-СХЕМА ЗГЛАДЖУВАННЯ ЗА МЕТОДОМ
НАЙМЕНШИХ КВАДРАТІВ





ДОДАТОК Б
ТЕКСТ ПРОГРАМИ ЗГЛАДЖУВАННЯ ЗА МЕТОДОМ НАЙМЕНШИХ КВАДРАТІВ


#include
#include
#include
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 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=%dn", N, K);
exit(-1);
}
for(i=0; 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 a[i]=0;
b[i]=0;
for(j=0; j sums[i][j] = 0;
}}
for(k=0; 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 fscanf(InFile, "%f", &x[k]);
fscanf(InFile, "%f", &y[k]);
}
//init square sums matrix
for(i=0; i for(j=0; j sums[i][j] = 0;
for(k=0; k sums[i][j] += pow(x[k], i+j);
} } }
//init free coefficients column
for(i=0; i for(k=0; k b[i] += pow(x[k], i) * y[k];
}}}
void printresult(){
//print polynom parameters
int i=0;
printf("n");
for(i=0; i printf("a[%d] = %fn", i, a[i]);
} }
void diagonal(){
int i, j, k;
float temp=0;
for(i=0; i if(sums[i][i]==0){
for(j=0; j if(j==i) continue;
if(sums[j][i] !=0 && sums[i][j]!=0){
for(k=0; k temp = sums[j][k];
sums[j][k] = sums[i][k];
sums[i][k] = temp;
}
temp = b[j];
b[j] = b[i];
b[i] = temp;
break;
} }}}}
void cls(){
for(int i=0; i<25; i++) printf("n");
}
void main(){
int i=0,j=0, k=0;
cls();
do{
printf("nInput filename: ");
scanf("%s", filename);
InFile = fopen(filename, "rt");
}while(InFile==NULL);
count_num_lines();
printf("nNumber of points: N=%d", N);
do{
printf("nInput power of approximation polinom K=N);
allocmatrix();
rewind(InFile);
//read data from file
readmatrix();
//check if there are 0 on main diagonal and exchange rows in that case
diagonal();
fclose(InFile);
//printmatrix();
//process rows
for(k=0; k for(i=k+1; i if(sums[k][k]==0){
printf("nSolution is not exist.n");
return;
}
float M = sums[i][k] / sums[k][k];
for(j=k; j=0; i--){
float s = 0;
for(j = i; j s = s + sums[i][j]*a[j];
}
a[i] = (b[i] - s) / sums[i][i];
}
printresult();
freematrix();
}