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

 

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

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

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

 

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

Кафедра ЛОТ

АПРОКСИМАЦІЯ  ФУНКЦІЇ МЕТОДОМ НАЙМЕНШИХ КВАДРАТІВ

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

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

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

6.051004 - “Оптотехніка”

08-04.ОТП.006.00.026 ПЗ

 

 

 

 

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

      к.т.н., Кожем’яко А.В.

________________________

”____” ____________2011 р.

       Розробив студент гр.  О-10

Ковтуненко С.В.

________________________

”____” ____________2011 р.

 

 

 

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

 

ЗАТВЕРДЖЕНО

«___» ___________ 2010 р.

_____________________

д.т.н., проф. Кожем’яко В.П.

 

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

До курсової роботи з дисципліни

«Обчислювальна  техніка та основи програмування»

 

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

Мета: розробити  програму на мові С, яка розв’язує  задачу методом найменших квадратів, обраховує похибку та виводить значення обрахунків.

Що відомо: метод  розв’язання – метод найменших квадратів.

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

Проаналізувати: після знаходження  результатів розв’язання та похибки, порівняти їх.

Література:

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 с.

 

Отримав: ст. гр. О-10 Ковтуненко С.В.   ”_____” _____________2010 р.

Керівник: к.т.н., доцент Кожем’яко А.В

 

АНОТАЦІЯ

 

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

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

 

АННОТАЦИЯ

 

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

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

 

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.

 

 

ЗМІСТ

Вступ………………………………………………………………………...……………6

1 Математичні аспекти методу найменших квадратів ……...………….……..…......7

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

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

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

2.1 Розробка функціональної структури  програми…………………………....14

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

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

3.1 Розробка програми за методом найменших квадратів …...…...……….…18

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

3.3 Розробка програми  в Math Cad……………………………………………..21

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

Висновки……………………………………………………………..……….………....24

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

Додаток А. Блок-схема апроксимації за методом найменших квадратів

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

 

 

 

 

 

Вступ

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

Потрібно вказати, що ж саме являє  собою апроксимація: Апроксимація - в обчислювальній математиці спосіб полегшення розв’язання задач.

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

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

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

 

1. Математичні аспекти методу найменших квадратів

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

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

Поняття "найкращим чином" означає розв’язання задачі по заданому критерію. Найбільш відомим критерієм для задач апроксимації є критерій середньоквадратичних відхилень (СКВ), який являє собою мінімізацію суми квадратів відхилень експериментальних даних від аналітичної функції і визначається на заданій множині точок як

,

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

певного вигляду, наприклад: 

степеневим  поліномом  

 ,   (1.1)

   тригонометричним поліномом

,     (1.2)

   ортогональним поліномом

,    (1.3)

   сплайн-функцією та інш.

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

,     (1.4)

такий, щоб сума квадратів  відхилень полінома від заданої системи експериментальних точок була би мінімальною. Така задача зводиться до визначення коефіцієнтів поліному . Метод, що дозволяє розв’язати її називається методом найменших квадратів (МНК). Критерій середньо квадратичного відхилення (СКО) в даному випадку має вигляд:

 .    (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 <n. Ступінь m може змінюватися в межах

Якщо m = 1, то ми апроксимуємо табличну функцію прямою лінією. Така задача називається лінійної регресією. 
 Якщо m = 2, то ми апроксимуємо табличну функцію квадратичної параболою. Така задача називається квадратичною апроксимацією. 
 Якщо m = 3, то ми апроксимуємо табличну функцію кубічною параболою. Така задача називається кубічної апроксимацією.

Уточнимо метод найменших квадратів: для табличної функції, отриманої в результаті експерименту, побудувати апроксимуючої многочлен (1.9) ступеня m, для якого сума квадратів відхилень за всіма вузловим точкам мінімальна, тобто

(1.10)

(1.10

Змінимо вигляд многочлена Pm. Поставимо на останнє місце складові, які містять xm. На передостаннє - складові, які містять xm-1 і т.д. У результаті отримаємо:

,  (1.11)

або

При цьому змінимо індекси коефіцієнтів многочлена. Тоді умова (1.8) буде мати вигляд:

де

xi і yi-координати вузлових точок таблиці,

a_j, - невідомі коефіцієнти многочлена (1.11).

Необхідною умовою існування мінімуму функції S є рівність нулю її приватних похідних по кожній aj.

У результаті отримали систему лінійних рівнянь. Розкриваючи дужки і переносячи вільні члени в правій частині рівнянь, отримаємо в нормальній формі систему лінійних рівнянь:

(1.12)

де: a_m -невідомі системи лінійних рівнянь (1.12),

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

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

Порядок системи дорівнює m +1. 
 При ручному рахунку коефіцієнти ck і вільні члени dj зручно визначати, користуючись таблицею 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