ОБРОБКА ТАБЛИЧНИХ ДАНИХ

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

 

2.1 Інтерполяція

 

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

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

Якість зору, %
Тривалість щодобового перебування за комп’ютером, годин	0,7	1,1	1,4	1,9	2,2	3,4	4,1

Приклад задачі інтерполяції – встановити, якою буде якість зору, якщо підліток щодобово сидітиме за комп’ютером 2 години, 1,5 годин, 3 години тощо?

 

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

Приклад задачі екстраполяції – встановити, якою буде якість зору, якщо підліток щодобово сидітиме за комп’ютером 4,3 години, 4,5 години, 0,5 години тощо?

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

2.2 Концепція інтерполяції

 

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

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

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

· вибір інтерполяційної функції ;

· оцінка похибки інтерполяції ;

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

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

 

Малюнок 2.1 - Ілюстрація інтерполяції.

 

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

 

(2.1)

 

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

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

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

Спочатку розглянемо деякі види шматкової інтерполяції, а саме: лінійну, квадратичну і сплайн-інтерполяцію.

 

2.3 Лінійна і квадратична інтерполяції

 

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

Для і-го інтервалу можна написати рівняння прямої, що проходить через точки та у вигляді:

.

Звідси

(2.2)

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

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

Тут невідомими є вони знаходяться з умови проходження многочлена через три точки

. (2.3)

Інтерполяція для будь-якої точки х з інтервалу проводитьсяпо трьох найближчихдо неї вузлах.

 

Приклад: Знайти наближене значення функції при х=0,32, якщо відома таблиця її значень:

 

х	0.15	0.30	0.4	0.55
у	2.17	3.63	5.07	7.78

 

а) При лінійній інтерполяції х=0.32 знаходиться між вузлами0.3 і 0.4. В цьому випадку

При маємо:

.

б) При квадратичній інтерполяції складемо систему рівняньдля найближчих до точки х=0.32 вузлів:

відповідно

Маємо систему рівнянь:

Розв’язуючи цю систему, знаходимо:

Тоді шукане значення в точці х=0.32 буде:

.

 

 

 

2.5 Глобальна інтерполяція. Многочлен Лагранжа.

Нехай відомі значення функції в точках . Для інтерполяції функції в довільній точці х, що належить відрізку , необхіднопобудуватиінтерполяційний поліном n-го порядку, який в методі Лагранжа має вигляд:

(2.14)

де

 

Якщо розкрити добутки всіх дужок в чисельнику (в знаменнику всі дужки є числами), то отримаємо поліном n-го порядку від х, тобто в чисельнику n співмножників першого порядку. Наступний поліном Лагранжа не що інше, як звичайний поліном n-го порядку, але записаний в іншій формі. Підставляючи l(x) у вираз для L(x), отримаємо

(2.15)

Неважко помітити, що у вузлах інтерполяції:

Оцінити похибку інтерполяції в точці (друга проблема інтерполяції) можна по формулі:

(2.16)

де - максимальне значення -ої похідної початкової функції f(x) на відрізку .

Отже, щоб оцінити погрішність, треба знати , що не завжди можливо.

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

 

2.6 Глобальна інтерполяція. Многочлен Ньютона

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

Тоді , де .

Метод використовує поняття скінчених різниць:

- різниці 1-го порядку

- різниці 2-го порядку

- різниці 3-го порядку

 

Для визначення різниці k – го порядку потрібне знання всіх точок від до :

(2.17)

Можна помітити, що за наявності n+1 точок (0,1,2,.., n), скінчену різницю 1- го порядку можна обчислити тільки для перших n точок (0,1,2,....,n –1), скінчену різницю n – го порядку – тільки для нульової точки, а k– го порядку - тільки для перших n - k+1 точок, тобто треба знати k точок попереду. Інтерполяційниймногочлен Ньютона записується таким чином:

(2.18)

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

Часто замість х вводять безрозмірну величину q, що показує, скільки міститься кроків від до заданої точки .Ця величина визначається таким чином:

.

Тоді

(2.19)

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

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

В цьому випадку

(2.20)

 

Похибку інтерполяції, як і для многочлена Лагранжа, можна оцінити так:

. (2.21)

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

, , ,…, .

Тоді для отримання наближеного значення достатньо мати декілька (або навіть одну) додаткових точок , з використанням яких легко знайти максимальне значення скінченої різниці (n+1) – го порядку:

(2.22)

Аналогічно можна знайти похибку і в методі Лагранжа при рівномірному кроці.

 

Приклад. Задана таблиця , необхідно знайти у(2.05). Використовуємо для інтерполяції тільки три перші точки, а решту – для оцінок похибки.

Отже, n+1=3, n=2

 

х	у	Δy	Δ²y	Δ³y
2,0	0,0540	-0,0100	0,0015	-0,0002
2,1	0.0440	-0,0085	0,0013
2,2	0.0355	-0,0072	0,0013	-0,0003
2,3	0.0283	-0,0057	0,0010	-0,0001
2,4	0.0224	-0,0049
2,5	0.0175	-0,0049
2,6	0.0136

 

Скористаємося першою інтерполяційною формулою Ньютона:

Оцінимо похибку знайденого значення у. З таблиці знаходимо, що М3=0,001,

тоді

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

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

 

 

 

2.7 Апроксимація

У процесі обробки емпіричних даних необхідно враховувати помилки цих даних. Ці помилки умовно можна розділити на 3 групи за їх походженням і величиною: систематичні, випадкові, грубі.

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

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

Грубі помилки явно спотворюють результат вимірювання, вони надмірно великі і, як правило, зникають при повторенні досвіду.

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

Побудова апроксимуючої залежності за експериментальними даними складається з 2-х етапів:

- підбір загального виду апроксимуючої залежності;

- визначення найкращих значень параметрів цієї залежності.

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

Після визначення формули у вигляді

(2.23)

необхідно знайти такі параметри , при яких формула дала б добре наближення до виміряних даних, не обов'язково проходячи через ці точки.

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

(2.24)

При цьому вимагається, щоб

. (2.25)

В цьому випадку говорять, що функція рівномірно апроксимує функцію на відрізку .

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

 

а) б)

Малюнок 2.2-рівномірне а), і середньоквадратичне б) наближення

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

(2.26)

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

 

2.8. Побудова апроксимуючої залежності

Існує декілька методів розв’язування задачі побудови апроксимуючої залежності.

Найпростіший з них – метод вибраних точок. Він складається з наступних етапів:

- отримані експериментальні точки наносять на координатну площину;

- проводиться найпростіша плавна лінія, що максимально близько примикає до експериментальних точок;

- вибираються на цій лінії точки і записуються їх координати (число точок дорівнює числу коефіцієнтів вибраної апроксимуючої функції);

- складається для цих точок система рівнянь і визначаються з неї коефіцієнти функції.

 

Метод середніх. Він полягає в тому, що параметри залежності (2.23) визначаються з умови рівності нулю суми відхилень (2.24) у всіх точках _:

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

Наприклад

Розв’язуючи цю систему рівнянь, знаходимо невідомі коефіцієнти.

 

Метод найменших квадратів (МНК). Запишемо суму квадратів відхилень (2.26) для всіх точок :

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

 

 

Розв’язуючи цю систему рівнянь з невідомими , знаходимо ці параметри апроксимуючої функції.

Приклад 1. У ролі апроксимуючої функції на практиці часто використовується многочлен

.

Тоді

Звідки, після узяття частинних похідних, отримуємо систему лінійних рівнянь

Групуючи коефіцієнт при невідомих , отримаємо

 

Цю систему можна записати компактніше:

 

Приклад 2. Вивести емпіричну формулу для наведеної нижче табличної залежності f(х), використовуючи метод найменших квадратів МНК.

 

х	0,75	1,50	2,25	3,00	3,75
у	2,50	1,20	1,12	2,25	4,28

Побудуємо емпіричний точковий графік.

Візуальний аналіз побудови дозволяє обрати на роль апроксимуючої функції квадратичну параболу

.

Тобто m=2, n=4.

Система рівнянь для визначення коефіцієнтів :

 

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

	0,75	2,5	0,5625	0,421875	0,31640625	1,875	1,40625
	1,5	1,2	2,25	3,375	5,0625	1,8	2,7
	2,25	1,12	5,0625	11,390625	25,62890625	2,52	5,67
		2,25				6,75	20,25
	3,75	4,28	14,0625	52,734375	197,7539063	16,05	60,1875
Сума	11,25	11,35	30,9375	94,921875	309,7617188	28,995	90,21375

Коефіцієнти обчислюються по формулах

, , ,

, , ,

, , ,

, , .

Отримуємо наступну систему рівнянь:

З якої знаходимо

Маємо апроксимуючу функцію:

Зауваження:

1. З формул обчислення коефіцієнтів видно, що всі коефіцієнти однакові при к+l=const.

2. Розв’язки системи нормальних рівнянь дуже чутливі до коефіцієнтів цієї системи, тому вони (розв’язки) можуть істотно змінюватися при навіть незначних змінах цих коефіцієнтів. Тому бажано не округлювати розраховані коефіцієнти .

 

 

3. РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ (СЛАР)

 

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

 

3.1 Концепція методів

Методи розв’язування СЛАР звичайно розділені на дві великі групи: точні (або прямі) і наближені ітераційні.

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

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

З прямих методів найбільш поширені методи Гауса, Крамера і LU-перетворення, набагато рідше використовується метод оберненої матриці. Метод Крамера (з використанням визначників) вимагає дуже великих обчислень вже при розв’язуванні системи 5 рівнянь, тому використовується тільки в учбовій літературі.

З ітераційних методів використовуються в основному методи простої ітерації і метод Гаусса-Зейделя.

3.2 Метод Гаусса (метод послідовного виключення змінних)

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

Нагадаємо, що матрична форма СЛАР порядку

має вид:

.

Тут

- матриця системи рівнянь,

- вектор-стовпчик правих частин рівнянь системи.

- вектор-стовпчик невідомих розв’язків системи.

 

Запишемо рівняння в наступному вигляді, позначивши через , тоді:

(3.1)

Розділимо перше рівняння на , і запишемо його:

 

де

Помножимо це рівняння на , і складемо його з другим рівнянням. Коефіцієнти отриманого другого рівняння

.

 

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

i=2, 3..., n j= 2..., n+1

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

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

На наступному кроці виключимо з розгляду перше рівняння і застосуємо аналогічну процедуру до рівнянь від другого до n-го. Запишемо формули для обчислення нових значень коефіцієнтів, за винятком тих, які стають рівними 0 при j=2, і тобто для j=3,4.,n+1.

i=3, 4..., n;

j= 3, 4..., n+1.

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

;

(3.2)

k=1, 2..., n; i=k+1..., n;

j=k+1..., n+1.

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

(3.3)

..

.

Це повністю відповідає послідовному виключенню змінних з системи рівнянь (прямий хід методу Гаусса).

Для визначення невідомих необхідно провести зворотну підстановку (зворотний хід методу Гаусса). В загальному вигляді зворотну підстановку можна записати так:

i=n-1, n-2..., 1. (3.4)

Тут верхні індекси опущені.

Прямий хід методу Гаусса вимагає виконання ~ , де під операцією розуміється комбінація множення і віднімання, а n – порядок матриці.

Зворотна підстановка (зворотний хід методу Гаусса) вимагає ~ операцій.

Приклад розв’язування СЛАР методом Гаусса

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

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

Початкова матриця I крок: k=1; j=2, 3, 4; i=2, 3, 4

при к=0

II крок: k=2; j=3, 4; i=3, 4 III крок: k=3; j=4; i =4

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

Розв’язуємо цю систему зворотним ходом:

х3=3;

х2=-37/13 + 21/13 ^. х3=2;

х1=3/2- 5/2 х2+3/2^. х3= 1.