Згладжування функцій за методом найменших квадратів

Міністерство  освіти і науки України

Вінницький  національний технічний університет

Інститут  автоматики, електроніки та комп’ютерних систем управління 

Факультет ФЕЛТ

Кафедра ЛОТ 

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

Пояснювальна  записка

з дисципліни ”Обчислювальна техніка та програмування”

до курсової роботи за спеціальністю

“Лазерна  та оптоелектронна техніка ”

08-36.ОТІП.008.00.011 ПЗ 
 

Керівник  курсової роботи

                     к.т.н.     

      __________________________                                                                                               

«____» _______________2009 р.

Розробив: студент групи О - 08

«____» _______________2009 р. 
 
 
 

Вінниця ВНТУ 2009

Анотація

     В даній курсовій роботі було розглянуто згладжування функцій методом найменших квадратів та розроблено програму для реалізації даного методу. Програма написана на мові C++ в програмному середовищі Borland C++ 3.1. У курсовій роботі приведений алгоритм розв’язання задачі та інструкція користувача. Програма протестована на працездатність та конкретним прикладом перевірена правильність результату. 

Аннотация

  В данной курсовой работе было рассмотрено сглаживание функций методом наименьших квадратов и разработана программа для реализации данного метода. Программа написана на языке C++ в программной среде Borland C++ 3.1. В курсовой работе приведенный алгоритм решения задачи и инструкция пользователя. Программа протестирована на работоспособность и конкретным примером проверенная правильность результата. 

Annotation

   In this term paper, smoothing out of functions was considered a least-squares method and the program is developed for realization of this method. The program is written in language of C++ in the software environment of Borland C++ 3.1. There is the resulted algorithm of decision of task and instruction of user in a term paper. The program is tested on a capacity and by a concrete example the tested rightness of result. 
 
 
 
 
 

ЗМІСТ

ВСТУП…………………………………………………………………………….…4

1 ТЕОРЕТИЧНІ ВІДОМОСТІ…………………………………………...……….....6

  1.1 Область застосування задачі………………………………………......…7

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

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

     2.1 Розробка блок-схеми прямого ходу  розв’язання СЛАР для згладжування функцій за методом найменших квадратів…………………..……9

3 РОЗРОБКА ПРОГРАМИ………………………………………………………....12

4 РОЗРОБКА ІНСТРУКТИВНИХ ДОКУМЕНТІВ ПО РОБОТІ З ПРОГРАМОЮ……………………………………………………………………....16

     4.1 Тестовий приклад………………………………………………………..16

     4.2 Оцінка ефективності розробленої програми…………………………..16

     4.3 Використані технічні засоби…………………………….…….………..17

     4.4 Інструкція користувачу…………………………….……………….…..17

ВИСНОВКИ…………………………………………………………………...… ..20

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ………………………………….......... .21 
 
 
 
 
 
 
 
 
 

                                                    ВСТУП

     Як  відомо, між величинами може існувати точний (функціональний) зв'язок, коли одному значенню аргументу відповідає одне певне значення, і менш точний (кореляційний) зв'язок, коли одному конкретному значенню аргументу відповідає наближене значення або деяка безліч значень функції, в тій або іншій мірі близьких один до одного. При веденні наукових досліджень, обробці результатів спостереження або експерименту зазвичай доводитися стикатися з другим варіантом. При вивченні кількісних залежностей різних показників, значення яких визначаються емпірично, як правило, є деяка їх вариабельность. Частково вона задається неоднорідністю самих об'єктів, що вивчаються, неживої і, особливо, живої природи, частково обумовлюються погрішністю спостереження і кількісній обробці матеріалів. Останню складову не завжди удається виключити повністю, можна лише мінімізувати її ретельним вибором адекватного методу дослідження і акуратністю роботи. Тому при виконанні будь-якої науково-дослідної роботи виникає проблема виявлення справжнього характеру залежності показників, що вивчаються, цій або іншій мірі замаскованих неврахованістю вариабельності значень.    Для цього і застосовується згладжування функцій - наближений опис кореляційної залежності змінних відповідним рівнянням функціональної залежності, передавальним основну тенденцію залежності (або її "тренд").

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

     1 ТЕОРЕТИЧНІ ВІДОМОСТІ 

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

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

     Після проведення достатньої кількості таких  операцій отримується 

     Якщо  з досліду визначаються значення деяких функцій невідомих величин , то для визначення цих величин необхідно вирішити систему умовних рівнянь:

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

     Якщо  похибки величин  мають нормальний закон розподілу (що зазвичай припускається), то для найбільш ймовірної системи значень невідомих сума квадратів відхилень буде найменшою. Умовні рівняння лінійні:

    (1.1)

     В теорії ймовірності та математичній статистиці для позначення підсумовування часто користуються позначеннями Гаусса: замість , замість , і.т.д..

     Наведена  вище система умовних лінійних рівнянь (1.1), та вимоги мінімуму суми квадратів відхилень приводять до системи нормальних рівнянь (наведено у позначеннях Гаусса):

   (1.2)

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

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

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

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

1.   Область застосування  задачі

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

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

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

     Вихідними даними розробленої програми є набір коефіцієнтів при параболічній інтерполяції вигляду .

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

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

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

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

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

2.1 Розробка блок-схеми  прямого ходу розв’язання  СЛАР для згладжування  функцій за методом  найменших квадратів 

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

     Алгоритм  роботи програмного модуля,  що виконує  згладжування функції за допомогою  методу найменших квадратів наведено на рисунку 1.1. 

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

Рисунок 1.1 – Схема роботи алгоритму згладжування функції 

3 РОЗРОБКА ПРОГРАМИ

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

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

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

void solve() {

      FILE *in;

      boolean isBreak=false;

      int oldColor=getcolor();

      int i,j,k,t,res;

      if ((in=fopen("DATA.TXT","rt"))==NULL) {

            fprintf(stderr, "Cannot open input file.\n");

      } else {

            cleardevice();

            fscanf(in,"%d",&N);

             points=new point[N];

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

                  fscanf(in,"%d%d",&(points[i].x),&(points[i].y));

                  showPixel(i);

             }

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

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

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

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

                              if (contain(i,j,k,t)==-1) {

                                    res=isRomb(i,j,k,t);

                              }

                        }

//   delete points;

                  int tmp,tmp2;

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

                        showPixel(tmp);

                        if (tmp!=0) {

                              line(points[tmp-1].x, points[tmp-1].y, points[tmp].x, points[tmp].y);

                        }

                  }

                  getch();

                  if (count1>0) {

                        setcolor(ROMB_COLOR);

                        for (tmp=0;tmp<count1;tmp++)

                              draw(rhombs[tmp][0],rhombs[tmp][1],

                                    rhombs[tmp][2],rhombs[tmp][3]);

                        getch();

                  } else {

                        settextstyle(0,0,2);

                        setcolor(RED);

                        getch();

                  }

                  cleardevice();

                  for (tmp=0;tmp<N;tmp++) showPixel(tmp);

                  if (count2>0) {

                        setcolor(SQUARE_COLOR);

                        for (tmp=0;tmp<count2;tmp++)

                              draw(squares[tmp][0],squares[tmp][1],

                                    squares[tmp][2],squares[tmp][3]);

                        getch();

                  } else {

                        settextstyle(0,0,2);

                        setcolor(RED);

                        getch();

                        cleardevice();

                        for (tmp=0;tmp<N;tmp++) showPixel(tmp);

                  }

                  cleardevice();

                  for (tmp=0;tmp<N;tmp++) showPixel(tmp);

                  if (count1>0) {

                        long sq=0;

                        for (tmp=0;tmp<count1;tmp++) sq+=square(tmp);

                        if (count1!=0) sq/=count1;

                        int bl=0;

                        setcolor(LIGHTBLUE);

                        for (tmp=1;tmp<count1;tmp++)

                              if ((square(tmp)-sq)<(square(bl)-sq)) bl=tmp;

                        draw(rhombs[bl][0],rhombs[bl][1],

                              rhombs[bl][2],rhombs[bl][3]);

                        getch();

                  }

      setcolor(oldColor);

      fclose(in);

   }

} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4 РОЗРОБКА ІНСТРУКТИВНИХ  ДОКУМЕНТІВ ПО  РОБОТІ З ПРОГРАМОЮ  

4.1 Тестовий приклад 

     Для тестування розробленої програми задамо вхідними даними набір наступний точок:

1 1

2 -10

10 20

18 9

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

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

     4.2 Оцінка ефективності розробленої програми 

     Програма  призначені для розв’язання заданого інтегралу та розроблена в середовищі Borland C++ 3.1 за допомогою власних функцій.

     Ефективність  функціонування програми підвищена  за рахунок наступних засобів:

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

     Вимоги  до ЕОМ для використання даної  програми:

• IBM PC або еквівалентний комп'ютер та монітор з розширенням 600 x 800 або краще.
• Microsoft Windows 95 або вище.
• мінімум 8МВ ОЗП.
• мінімум 1МВ вільного місця на твердому диску.

     Отже, програма може використовуватись для  вирішення задач такого типу . 

4.3 Використані технічні засоби 

     Для написання  програми використовувалась програмне середовище Borland C++ версії 3.1. Скомпільована програма вимагає наявності середовища Windows чи DOS, проте не потребує великих системних ресурсів. Щоб забезпечити нормальне функціонування програми, необхідна наявність в робочому каталозі, звідки виконується завантаження програми, файлів egavga.bgi (для забезпечення роботи у графічному режимі) та keyrus.com (для підтримки відображення українських літер у графічному режимі). Результати програми виводяться на монітор, що не потребує додаткових ресурсів пам’яті. 

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

     Для роботи програми потрібні наступні файли :

• data.txt, в ньому знаходяться вхідні дані для розв’язку задачі;
• autor.txt, в цьому файлі знаходяться відомості про автора програми, що можуть виводитись під час виконання програми, при виборі відповідного пункту меню;
• egavga.bgi, необхідний для підтримки графічного режиму (EGA чи VGA);
• index.exe, власне програма;
• reyrus.com, драйвер, що забезпечує коректне виведення на екран у графічному режимі (EGA, VGA) українських літер;
• run.bat, пакетний файл, що запускає драйвер keyrus.com, а потім саму програму.

     Виконання програми складається з таких  етапів :

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

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

     Для того, щоб дізнатися умову задачі та відомості про автора курсової роботи та програми необхідно відповідно вибрати пункти меню „Автор” та „Умова”. Для перегляду розв’язку задачі для прикладів, записаних у вхідному файлі даних потрібно вибрати пункт меню „Задача”.

     Вихід з програми відбувається при натисканні клавіші „Esc” (відбувається в будь-який момент виконання програми) чи при виборі пункту меню „Вихід”.

     Дані  для розв’язку задачі потрібно задавати в файлі data.txt. у такому вигляді:

     кількість блоків вхідних даних M;

     кількість точок  для 1–ого тесту;

     абсциса та ордината першої точки першого  тесту;

     ...

     абсциса та ордината N–ої точки 1–ого тесту;

           ...

     кількість точок  для M–ого тесту;

     абсциса та ордината першої точки першого  тесту;

     ...

     абсциса та ордината –ої точки M–ого тесту;

     Кількість тестів, точок в кожному з них та координати точок вводяться в окремій стрічці. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ВИСНОВКИ 

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

     Розв’язання оформлено з графічним інтерфейсом та використанням мишки, невибагливе до апаратних ресурсів.

     В процесі роботи набуто досвіду розв’язання  поставлених задач з подальшим  їх оформленням та документуванням. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ 

1.Самарський  А.А. Вступ в чисельні методи. - М.: Наука, 1987. – 286 с.

2.Квєтний  Р.Н., Маліков В.Т. Обчислювальні методи та використання ЕОМ. Вища школа, 1989 – 55 с., 104 с.

3. Гусев В.А., Мордковіч А.Г. - Математика: Справ. матеріали. - М.: Освіта, 1990. - 416 с.

4. Б. Страустрап, „Справочное руководство по С++”.

5. Ал. Стивенс, „Техника программирования на турбо Си”.

6. Д. Элджер, „C++”.

7. Г. Шилдт, „Си для профессиональных программистов ”.