Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

Кафедра ЛОТ

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

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

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

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

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.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	x_i⁰	x_i¹	x_i²	...	x_i^2m	x_i⁰ y_i	x_i¹ y_i	...	x_i^m
0	1
1	1
2	1
...	...
N	1
	c₀	c₁	c₂	...	c_2m	d₀	d₁	...	d_m

Змінимо індексацію в системі (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.13). Визначаємо коефіцієнти c_k,j і вільні члени d_k. Так як система (1.13) симетрична відносно головної діагоналі, то достатньо визначити лише наддиагональні элементи системи.
Розв’язуємо систему (1.13) методом Гаусса. Знаходим коэфіцієнти aj многочлена (1.14).
Будуємо апроксимуючий многочлен (1.14) и знаходимо його значення в кожній вузловій точці P_i = P_m(x_i).
Знаходимо відхилення кожної вузлової точки .
Знаходимо суму квадратів відхилень по всім вузловим точкам .
Знаходимо остаточну дисперсію .

Для побудови апроксимуючого многочлена (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 – Система рівнянь

a₀n +	a₁Σ x_i +	a₂Σ x_i² +	... +	a_kΣ x_i^k =	Σ y_i
a₀Σ x_i +	a₁Σ x_i² +	a₂Σ x_i³ +	... +	a_kΣ x_i^k+1 =	Σ x_iy_i
...
a₀Σ x_i^k +	a₁Σ x_i^k+1 +	a₂Σ x_i^k+2 +	... +	a_kΣ x_i^2k =	Σ x_i^ky_i

де скрізь під символом Σ мається на увазі підсумовування по 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 – таблиця значень хі, уі

x₀	y₀
x₁	y₁
x₂	y₂
...
x_N	y_N

Наприклад:

Таблиця 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 с.

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

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

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

ДОДАТОК А.

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

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

Додаток Б

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

#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;

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