EMBED Equation.3 АПРОКСИМАЦІЯ ФУНКЦІЙ
Поняття про наближення функцій
Нехай величина "y" є функцією аргумента "х", тобто будь?якому значенню "х" з області визначення поставлено у відповідність значення "у".
На практиці досить часто бувають випадки, коли неможливо записати зв'язок між "х" та "у" у вигляді деякої залежності у = f(x). Най-більш поширеним випадком, коли вид зв'язку між параметрами х та у невідомий, є задання цього зв'язку у вигляді таблиці {xi, yi}. Це означає, що дискретній множині значень аргумента {xi} поставлена у відповідність множина значень функції {yi} (і= EMBED Equation.3 ). Цими значеннями можуть бути, наприклад, експериментальні дані. На практиці можуть бути потрібні значення величини у і в інших точках, відмінних від вузлів xi. Однак одержати ці значення можна тільки експериментальним шляхом, що не завжди зручно і вигідно.
З точки зору економії часу та засобів доцільно було б використати наявні табличні дані для наближеного обчислення шуканого параметра "у" при будь?якому значенні (з деякої області, звичайно) визначального параметра "х", оскільки точний зв'язок у = f(x) невідомий.
Цій меті служить задача про наближення (апроксимацію) функцій:
– дану функцію f(x) потрібно наближено замінити (апроксимувати) деякою функцією ?(х) так, щоб відхилення (в певному розумінні) ?(х) від f(x) в заданій області було найменшим. При цьому функція ?(х) називається апроксимуючою.
Наприклад, в тому випадку, коли функція f(x) задається у вигляді таблиці значень, задача апроксимації полягає в наступному: за табличними даними підібрати таку аналітичну залежність ?(х), яка мала б просту структуру, згладжувала б особливості заданої експериментальної таблиці і найкращим чином відбивала б загальний хід зміни f(x) в середньому. Тобто основна мета апроксимації – одержати швидкий (економний) алгоритм обчислення значень f(x) для значень x, що не містяться в таблиці даних. Основне питання апроксимації – як вибрати ?(х) і як оцінити відхилення ?(х) від f(x) .
На практиці досить часто ?(х) вибирається з класу алгебраїчних поліномів (многочленів)
?(х)=a0 + a1x + a2x2 +…+ amxm (1)
Якщо початкова функція задана таблично, тобто на множині окремих точок, то апроксимація називається точковою. Якщо ж початкова функція задана на неперервній множині точок (наприклад, на відрізку [a; b]), то апроксимація називається інтегральною (неперервною).
Одним з основних типів точкової апроксимації є інтерполяція. Вона полягає в наступному: для даної функції у = f(x) будуємо функцію ?(х), яка в заданих точках хі (і = EMBED Equation.3 ) приймає ті ж значення, що і функція f(x), тобто
?(хі) = f(xi),
а в решті точок відрізку [a; b] з області визначення f(x), наближено представляє f(x) з деякою похибкою. Точки xі називають вузлами інтерполяції, а ?(х) – інтерполюючою функцією. Найчастіше інтерполюючу функцію ?(х) виражають через алгебраїчний многочлен степені m.
?(x)
f(х)
х
у



Інтерполяція в цьому випадку називається алгебраїчною. Якщо використовується один многочлен ?(х) = Pn(x) для інтерполяції функції f(х) на всьому інтервалі зміни аргумента х, тобто коли m = n (m – максимальний степінь інтерполяційного многочлена), то це – глобальна інтерполяція.
Інтерполяційні многочлени можуть будуватися окремо для різних частин інтервалу зміни х. В цьому випадку маємо кускову (локальну) інтерполяцію. Як правило, інтерполяційні многочлени використовують для апроксимації функцій у проміжних точках між крайніми вузлами інтерполяції, тобто х0 < х < хn. Однак іноді вони використовуються і для наближеного обчислення функції зовні інтервалу (х < х0, x > хn). Це наближення називається екстраполяцією.
Таким чином, при інтерполюванні основною умовою є проходження графіка інтерполяційного многочлена через дані значення функції у вузлах інтерполяції. Однак виконання цієї умови в деяких випадках є недоцільним. Наприклад, при великому числі вузлів інтерполяцї одержуємо високу степінь полінома у випадку глобальної інтерполяції (це пов’язано з рядом неприємностей – осциляція функції). Крім того, табличні дані можуть містити в собі похибки (якщо ці дані одержані шляхом вимірювань). Отже, інтерполюючий многочлен теж повторював би ці похибки. Вихід із цього становища може бути знайдений вибором такого многочлена, графік якого близько проходить від даних точок.


Поняття “близько” уточнюється при розгляді окремих видів наближення.
Середньо-квадратичне наближення. Степінь полінома m при цьому, як правило, значно менша від n. На практиці не вище 5,6. Мірою відхилення многочлена ?(х) від заданої функції f(х) на множині точок (xi, yi) (і = EMBED Equation.3 ) є величина S, яка дорівнює сумі квадратів різниць між значеннями многочлена та функції в даних точках
EMBED Equation.3
При побудові апроксимуючого многочлена потрібно підібрати коефіцієнти а0, а1, … , аm так, щоб величина S була мінімальна. В цьому полягає ідея методу найменших квадратів.
Рівномірне наближення. В багатьох випадках, особливо при обробці експериментальних даних, середньоквадратичне наближення зручне, оскільки воно згладжує деякі неточності функції f(х) і дає достатньо правильне уявлення про неї. Однак, іноді ставиться більш жорстка умова і вимагається, щоб у всіх точках деякого відрізку [a, b] модуль відхилення многочлена ?(х) від f(х) був менший від деякого ?
|f(x) – ?(х)| < ?, EMBED Equation.3
В цьому випадку маємо рівномірну апроксимацію. Тепер введемо такі поняття. Абсолютним відхиленням ? многочлена ?(х) від функції f(х) на відрізку [a, b] називається максимальне значення абсолютної різниці між ними на даному відрізку:
? = max | f(х) – ?(х)| , EMBED Equation.3
За аналогією можна ввести середньоквадратичне відхилення
EMBED Equation.3 .
?
?
y
x
f(х)
?(х)
?
?
y
x
f(х)
?(х)
На малюнку показано відмінність цих двох видів наближень.
рівномірне середньоквадратичне




Існує також поняття найкращого наближення функції f(х) многочленом ?(х) фіксованої степені m. В цьому випадку коефіцієнти многочлена а0, а1, … , аm слід вибирати так, щоб на заданому відрізку [a, b] значення абсолютного відхилення ? було мінімальне. Многолен ?(х) при цьому називається многочленом найкращого рівномірного наближення.
Інтерполяція
Під апроксимацією розуміють операцію знаходження невідомих чисельних значень якоїсь величини за відомими її значеннями і чисельними значеннями інших величин, які пов’язані з розглядуваною.
Інтерполяція - частковий випадок апроксимації. Нехай в точках х0, х1, х2, … , хn відомі значення f(x0), f(x1), f(x2)… f(xn) деякої функції f(x). Потрібно відновити функцію f(x) при інших значеннях х ? хі (і = 0, 1, 2, … , n). У цьому випадку будують достатньо просту для обчислення функцію ?(х), яка в заданих точках х0, х1, х2, … , хn приймає значення f(x0), f(x1), f(x2), …, f(xn), а в решті точках відрізку [a, b] (область визначення f(x) ), наближено представляє f(x) з деякою точністю. Задача побудови ?(х) називається задачею інтерполювання. Найчастіше інтерполюючу функцію ?(х) виражають через алгебраїчний многочлен деякої степені n.
Якщо аргумент х знаходиться зовні відрізку [a, b], то поставлена задача називається екстраполюванням (екстраполяція).
Інтерполяція в цьому випадку називається алгебраїчною. Алгебраїчне інтерполювання функції y = f(x) на відрізку [a, b] полягає в наближеній заміні цієї функції на даному відрізку многочленом Рn(х) степені n, тобто
f(x) ? Рn(х), (1)
причому в точках х0, х1, х2, … , хn, f(xі) = Рn(хі), (і= EMBED Equation.3 ).
Відмітимо, що двох різних інтерполяційних многочленів одної й тої ж степені n існувати не може. Якщо вважати протилежне, приходимо до висновку, що різниця двох таких многочленів, що є многочленом степені не вище n, має n + 1 корінь, а отже тотожно дорівнює нулю.
Інтерполяційний поліном Лагранжа
Поставимо задачу: знайти многочлен степені Рn(x) степені n, котрий в n + 1 даних точках х0, х1, х2, … , хn (ці точки називаються вузлами інтерполяції) приймає дані значення у0, у1, … , уn.
EMBED Equation.3
EMBED Equation.3
Для побудови Рn(х) спочатку розглянемо допоміжні (іноді їх називають фундаментальні) многочлени Qnk(х), тобто многочлени n-ї степені відносно х, котрі задовільняють таким умовам:
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
при , (к= EMBED Equation.3 ).
Ця властивість означає, що, наприклад, многочлен Qn0(x) приймає в точці х0 значення, рівне одиниці, а в решті вузлів – нуль; многочлен Qn1(x) в вузлі х1 приймає значення 1, а в решті – нуль і т. д. В загальному випадку многочлен Qnі(x) в вузлі хі приймає значення 1, а в решті вузлів 0. Тоді шуканий многочлен:
Рn(x) = y0Qn0(x) + y1Qn1(x) + y2Qn2(x) + … + ynQnn(x) (2).
Оскільки х0, х1, х2, … , хк-1, хк+1, … , хn – нулі многочлена Qnk(x), то
Qnk(x) = ck(x – x0)(x – x1)(x – x2) … (x – xk-1)(x – xk+1) … (x – xn)
(це просто інша форма запису полінома степені n).
Визначаючи ск з умови Qnk(xк) = 1, одержимо вираз для ск (замість х підставляємо хк)
EMBED Equation.3 (2)
Тоді явний вираз для допоміжних многочленів
EMBED Equation.3 (3)
Формула (2) з врахуванням (3) приймає вигляд :
EMBED Equation.3 (4)
Многочлен, що визначається за формулою (4) називається інтерполяційним многочленом Лагранжа, а допоміжні многочлени (3) – коефіцієнтами Лагранжа.
Введемо позначення
EMBED Equation.3
Розглянемо похідну в точці хк
EMBED Equation.3
Звідси
EMBED Equation.3
EMBED Equation.3
Розглянемо інтерполяційну формулу Лагранжа для випадку рівновіддалених вузлів інтерполяції, тобто х1 – х0 = х2 – х1 =…= xn – xn-1 = h. Зробимо заміну x = ht + x0, тоді
t0 = 0; t1 = 1; t2 = 2; … tn = n
x – xk = h(t – k), ?(x)=nn+1?*(t)
?*(t) = t(t – 1)(t – 2) … (t – n)
?'(xk) = (–1)n-kk!(n – k)!hn
f(x) = f(ht + x0) ? t(t – 1)(t – 2) … (t – n)* EMBED Equation.3
Приклад.
Знайти інтерполяційний многочлен Лагранжа для функції, заданої таблицею
При n=3, формула (4) приймає вигляд
EMBED Equation.3
Підставляючи значення хк та ук (к= EMBED Equation.3 ).
EMBED Equation.3
P3(x)=x3+3x2-2x+2

Інтерполяційний поліном Ньютона
Інтерполяційна формула Лагранжа має два суттєвих недоліки:
формула громіздка- кожен доданок є многочленом n-го степеня;
якщо з якоїсь причини додаються вузли інтерполювання (наприклад, якщо отримана інтерполяційна формула неточна), то всі обчислення необхідно повторювати знову – ні один із доданків формули Лагранжа не зберігається.
Розглянем форму запису інтерполяційного полінома Рn(х), яка допускає уточнення результатів інтерполяції послідовним додаванням нових вузлів. При цьому будем використовувати таке поняття як розділені різниці функцій.
Нехай маємо функцію f(x) і не обов"язково рівновіддалені вузли інтерполяції хі (і=0, 1, 2, … , n).
Розділеними різницями 1-го порядку називають величини, які мають зміст, наприклад, середніх швидкостей зміни функції:
EMBED Equation.3 (5)
Розділені різниці другого порядку визначаються співвідношеннями
EMBED Equation.3 (6)
Аналогічно, розділена різниця k?го порядку визначається через розділені різниці (k?1) порядку за рекурентною формулою:
EMBED Equation.3 (7)
Тепер перейдемо безпосередньо до самого інтерполяційного полінома Ньютона.
Маєм, наприклад, один вузол інтерполяції х0.
Виходячи із визначення розділеної різниці 1?го порядку f(x; x0) маємо:
EMBED Equation.3
EMBED Equation.3
Для розділених різниць другого порядку (два вузли ? х0, х1)
EMBED Equation.3
Підставляючи це значення у формулу для f(x)
EMBED Equation.3
Повторюючи цей процес, отримаємо (для n+1 вузлів інтерполяції):
EMBED Equation.3 (8)
Оскільки Рn(x) ? інтерполяційний поліном для функції f(x), то його значення у вузлах інтерполяції співпадають із значеннями функції f(x) (а, значить, і співпадають і розділені різниці)
Рn(xі) = f(xі) = уі, (і= EMBED Equation.3 ),
оскільки залишковий член в цих вузлах
EMBED Equation.3
(х приймає значення х0, х1, … , хn, тому один із співмножників завжди рівний 0, через те залишковий член у вузлах інтерполяції дорівнює нулю).
Тому замість (8) можна записати
EMBED Equation.3 (9)
Це і є інтерполяційний поліном Ньютона з розділеними різницями.
Для того, щоб пересвідчитись, що інтерполяційний поліном приймає значення уі в вузлах інтерполяції хі, візьмемо два вузли х0 та х1
n = 2 f(x) = y0 + (x ? x0)f( x0 ; x1) + (x ? x0)(x ? x1)f(x; x0; x1)
При x = x1
f(x1) = y0 + (x1 ? x0)(f(x1) ? f(x0))/(x1 ? x0) = у0 + f(x1) – f(x0);
f(x1) = f(x1)
Якщо маєм чотири вузли інтерполяції (n=3), то поліном Ньютона має вигляд:
Pn(x) = y0 + (x ? x0)f(x0; x1) + (x ? x0)(x?x1)f(x0; x1; x2) +
+ (x ? x0)(x ? x1)(x ? x2)f(x0; x1; x2; x3)
Якщо ж маєм вже шість вузлів, тобто n=5, то йде просте нарощу-вання формули:
Pn(x) = y0 + (x ? x0)f(x0; x1) + (x ? x0)(x ? x1)f(x0; x1; x2) +
+ (x ? x0)(x ? x1)(x ? x2)f(x0; x1; x2; x3) +
+ (x ? x0)(x ? x1)(x ? x2)(х ? х3)f(x0; x1; x2; x3; x4) +
+ (x ? x0)(x ? x1)(x ? x2)(х ? х3)(х ? х4)f(x0; x1; x2; x3; x4; x5).
Приклад.
Знайти інтерполяційний поліном Ньютона:
х ?3 ?1 1 2
у 8 6 4 18 При n = 3 інтерполяційний поліном Ньютона буде мати вигляд:
Pn(x) = y0 + (x ? x0)f(x0; x1) + (x ? x0)(x ? x1)f(x0; x1; x2) +
+ (x ? x0)(x ? x1)(x ? x2)f(x0; x1; x2; x3)
Р3(х) = 8 + (х + 3)(?1) + (х + 3)(х + 1)*0 + (х + 3)(х + 1)(х ? 1)*1=
= 8 ? х ? 3 + (х + 3)(х2 ? 1) = 5 ? х + х3 + 3х2 ? х ? 3 =
= х3 + 3х2 ? 2х + 2
Перш ніж приступати до заповнення таблиці, розпишемо розділені різниці
Розділені різниці 1?го порядку
EMBED Equation.3
Розділені різниці 2?го порядку
EMBED Equation.3
EMBED Equation.3
Розділені різниці 3?го порядку
EMBED Equation.3
При написанні програми будемо користуватися наступним алгоритмом: позначимо через k – порядок розділених різниць ( EMBED Equation.3 – межі зміни k, де n – порядок (найвищий) інтерполюючого полінома), а через і – число розділених різниць ( EMBED Equation.3 – межі зміни і) для даного порядку k.
k=1 EMBED Equation.3 збереглося
EMBED Equation.3
k=2 EMBED Equation.3
k=3 EMBED Equation.3
EMBED Equation.3 – кількість штрихів – це порядок
k = 1 до n
Для і = 0 до n ввести значення хі, уі
Для k = 1 до n
Для і = n до k з кроком –1
уі = (уі – уі–1)/( хі – хі–1)
Тоді відповідно збережуться у0, у1?, у2??, у3???

5
10
y
x
5
10
y
x
5
10
y
x
5
10
y
x
5
10
y
x
5
y
x
Інтерполяція функції у = |x – 5| з допомогою полінома Ньютона на 6-10 точках.
Підбір емпирічних формул
1. Характер експериментальних дослідних даних
При інтерполюванні функцій використовується відома умова ?(хі) = = f(xi) – рівність значень інтерполяційного многочлена та даної функції у вузлах інтерполяції. Якщо f(xi) містить похибку, то апроксимуючий многочлен ?(хі) цю похибку повторить.
При обробці експериментальних даних, одержаних в результаті спостережень або вимірювань, потрібно мати на увазі похибки цих даних. Ці похибки можуть бути зумовлені недосконалістю вимірювального приладу, суб’єктивними причинами, різноманітними випадковими факторами.
Похибки експериментальних даних (ЕД) можна умовно розбити на 3 групи:
систематичні;
випадкові;
грубі.
Систематичні – дають, як правило, відхилення в одну сторону від істинного значення вимірювальної величини. Вони можуть бути сталими або закономірно змінюватись при повторі експерименту і їх причина та характеристики відомі. Систематичні похибки можуть бути викликані умовами експерименту (вологістю, температурою середовища і т. п.), дефектом вимірювального приладу, його поганим регулюванням (наприклад зміщення нуля) і т. п. Такі похибки усуваються наладкою апаратури або внесенням відповідних поправок.
Випадкові похибки – визначаються великим числом факторів, які не можуть бути усунуті або достатньо точно враховані при вимірюваннях або обробці результатів. Вони носять випадковий (несистематичний) характер, дають відхилення від середнього значення величини в різні сторони. Вони не можуть бути усунуті в експерименті. З точки зору теорії ймовірності математичне сподівання випадкової похибки дорівнює нулю.
Статистична обробка експериментальних даних дозволяє знайти значення випадкової похибки і довести її до деякого прийнятного рівня шляхом повторювання вимірювань.
Грубі похибки (помилки) явно спотворюють результат вимірювання. Вони надмірно великі і як правило зникають при повторі досліду. Вимірювання з такими похибками відкидаються і не враховується при остаточній обробці результатів вимірювань.
Таким чином, в ЕД завжди є випадкові похибки. Вони можуть бути зменшені шляхом багатократних повторних вимірювань. Однак для цього потрібні значні матеріальні та часові ресурси. Значно дешевше і швидше уточнені дані можна отримати шляхом спеціальної математичної обробки наявних результатів вимірювань (наприклад, статистична обробка дає значення розподілу похибок вимірювань, найбільш ймовірний діапазон зміни шуканої величини (довірчий інтервал) та інші параметри).
Ми розглянемо тільки визначення зв’язку між вхідними параметрами х та шуканою величиною у на підставі результатів вимірювань
2. Емпіричні формули
Маємо таблицю значень:
х1 х2 … хn
у1 у2 … уn
Необхідно знайти наближену залежність у = f(x), значення якої при х = хі (і= EMBED Equation.3 ), мало відрізняються від дослідних даних уі. Наближена функціональна залежність у = f(x), яка одержана на основі експериментальних даних, називається емпіричною формулою.
Одним із способів одержання емпіричних формул є метод найменших квадратів (МНК). Будем вважати, що тип емпіричної формули відомий (це, наприклад, пряма, парабола, многочлен чи інше) і її можна зобразити у вигляді
у = ?(х, а0, а1, … , аm), (1)
де ? - відома функція;
а0, а1, … , аm – невідомі сталі параметри.
Задача полягає в тому, щоб визначити такі значення цих параметрів, при яких емпірична формула дає достатньо добре наближення таблично заданої функції.
Ідея МНК полягає в наступному. Запишемо суму квадратів відхилень для всіх точок хі (і= EMBED Equation.3 )
EMBED Equation.3 (2)
Параметри а0, а1, … , аm емпіричної формули (1) будем шукати з умови min функції S = S(а0, а1, … , аm). Оскільки тут параметри а0, а1, … , аm виступають в ролі незалежних змінних функції S, то її min знайдемо, прирівнюючи до нуля частинні похідні за цими змінними
EMBED Equation.3 EMBED Equation.3 … EMBED Equation.3 (3)
Розглянем випадок, коли за емпіричну функцію вибирають многочлен
?(х)= а0 + а1х + а2х2 + … + аmхm (4)
Тоді формула визначення суми квадратів відхилень S зобразиться так
EMBED Equation.3 (5)
Тоді система рівнянь для визначення а0, а1, … , аm з врахуванням (3) набере вигляду
EMBED Equation.3 (6)
Збираючи коефіцієнти при невідомих а0, а1, … , аm, одержимо наступну систему рівнянь (2 перед знаком суми опускаєм ? сталий множник, який не змінює коренів системи):
EMBED Equation.3 (7)
Систему (7) можна записати в більш компактному вигляді:
с0а0 + с1а1 + с2а2 + … + сmam = d0 ,
c1a0 + c2a1 + c3a2 + … + cm+1am = d1 , (8)
– – – – – – – – – – – – – – – – – – – – – – – – – –
cma0 + cm+1a1 + cm+2a2 + … + c2mam = dm ,
де EMBED Equation.3 , j = 0, 1, 2, … , 2m (9)
EMBED Equation.3 , k = 0, 1, 2, … , m (10)
Поліном (4) степені m < n, де n ? число пар хі, уі забезпечує апроксимацію таблично заданої функції уі(хі) з мінімальною середньоквадратичною похибкою:
EMBED Equation.3 EMBED Equation.3 (11)
Якщо m = n, то має місце звичайна інтерполяція, тобто
EMBED Equation.3
Зауваження щодо побудови програми .
Система (8) ? це система лінійних алгебраїчних рівнянь відносно невідомих а0, а1, … , аm. Коефіцієнти при невідомих одержуються за формулами (9) та (10). Для обчислення і зберігання коефіцієнтів сj потрібен масив із (2m+1) чисел, а для dk ? масив із (m + 1) чисел, де m ? степінь полінома, яка задається на початку роботи програми.
Потрібно ввести в циклі (і= EMBED Equation.3 ) пари значень хі, уі, потім сформувати коефіцієнти при невідомих сj та вільні члени dk .
Одержану таким чином систему лінійних алгебраїчних рівнянь розв'язати методом Гауса (з частковим вибором головного елемента), одержуючи значення параметрів а0, а1, … , аm апроксимуючого полінома ?(х).
На практиці використовується поліноміальна апроксимація за МНК з автоматичним вибором степені полінома. Алгоритм наступний: задається початкове значення m, потім шукається коефіцієнти полінома а0, а1, … , аm , за формулою (11) обчислюється середньоквадратична похибка і порівнюється із заданою Е1. Якщо Е > заданої, степінь m збільшується на 1 і все повторюється. Обчислення припиняється при Е < E1.