МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ

Системи цифрової обробки сигналів

методичні вказівки до лабораторних робіт

з курсу «Системи цифрової обробки сигналів» для студентів спеціальності 7………

всіх форм навчання

Затверджено на засіданні кафедри спеціалізованих комп’ютерних систем, протокол № від

та Методичною радою ЧДТУ,

протокол № від

Черкаси 20__

Укладачі:

Відповідальний редактор______________________

Рецензент __________________________________

Методичні вказівки до виконання лабораторних з курсу „Системи цифрової обробки сигналів” для студентів спеціальності ………… всіх форм навчання. / Укл.: Черкаси: ЧДТУ, 20__ – …. с.

ВИМОГИ ДО ЗВІТІВ

Звіт з лабораторної роботи повинен містити:

• Титульна сторінка з темою лабораторної роботи

• Тема

• Мета

• Теоретичні відомості

• Виконання роботи

• Результати

• Висновки

Приклад оформлення титульної сторінки:

Лабораторна робота №1 інтерполяція та апроксимація даних

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

Програмне забезпечення: NUMERI

Теоретичні відомості

Апроксимація даних:

Нехай величина y є функцією аргументу x. Це значить, що будь-якому значенню x з області визначення поставлено у відповідність значення y. Разом з тим на практиці часто невідомий дійсний зв’язок між y та x, тобто неможливо записати цей зв’язок у вигляді y=f(x). В деяких випадках навіть при невідомій залежності y=f(x) він настільки громіздкий(наприклад, містить важко обчислювані вирази, складні інтеграли і т.д.), що його використання у практичних розрахунках утруднено.

Найбільш розповсюдженим та практично важливим випадком, коли вигляд зв’язку між параметрами x та y невідомий, є задання цього зв’язку у вигляді деякої таблиці {x_i y_i}. Це значить, що дискретній множині значень аргументу {x_i} відповідає множина значень функції {y_i} (i=0,1…n). Ці значення - або результати розрахунків, або експериментальні дані. На практиці нам можуть знадобитися значення величини y також і в інших точках, що відрізняються від вузлів x_i. Однак отримати ці значення можні лише шляхом дуже важких розрахунків або проведенням дорогих експериментів.

Таким чином, з точки зору економії часу та засобів ми приходимо до необхідності використання існуючих табличних даних для наближеного обчислення шуканого параметра y при будь-якому значенні(з деякої області), що визначає параметр x, оскільки точний зв’язок y=f(x) невідомий.

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

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

g(x)=a₀+a₁x+a₂x²+…+a_mx^m (1.1)

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

Якщо наближення будується на заданій множині точок {xi}, то апроксимація називається точковою. До неї відносяться інтерполювання, середньоквадратичне наближення таі інше. При побудові наближення на неперервній множині точок(наприклад, на проміжку [a,b] апроксимація називається неперервною або інтегральною).

Точкова апроксимація:

Одним з основних типів точкової апроксимації є інтерполювання. Воно полягає у наступному: для даної функції y=f(x) будуємо багаточлен (1.1), що приймає в заданих точках x_i ті самі значення y_i, що і функція f(x), тобто g(x_i)=y_i, i=0,1,…n.

При цьому припускається, що серед значень x_i немає однакових, тобто x_ix_k при цьому ik. Точки x_i називаються вузлами інтерполяції, а багаточлен g(x) - інтерполяційним багаточленом.

Р ис. 1.1

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

Максимальний ступінь інтерполяційного багаточлена m=n; в цьому випадку говорять про глобальну інтерполяцію.

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

Одним з таких видів є середньоквадратичне наближення функції за допомогою багаточлена (1.1). При цьому m  n; випадок m = n відповідає інтерполяції. На практиці стараються підібрати апроксимуючий багаточлен якомога меншого

ступеня(як правило, m=1, 2, 3).

Мірою відхилення багаточлена g(x) від заданої функції f(x) на множині точок (x_i,y_i) (i=0,1,…,n) при середньоквадратичному наближенні є величина S, що дорівнює сумі квадратів різниці між значеннями багаточлена і функції в даних точках:

Для побудови апроксимуючого багаточлена необхідно підібрати коефіцієнти a₀, a₁,…,a_m так, щоб величина S була найменшою. В цьому і полягає метод найменших квадратів.

Інтерполяція, екстраполяція. Постановка задачі:

Припустимо, що задано різних точок площини:

(1.2)

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

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

Рис.1.2

Потрібно розрізняти два випадки:

1. Інтерполяцію — відтворення проміжних значень функції на проміжку за рядом відомих її значень;

2. Екстраполяцію — коли значення , що не увійшло у дослідження, лежить поза проміжком .

Очевидно, інтерполяція більш надійна, ніж екстраполяція.

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

(1.3)

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

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

можливого ступеня, що задовольняє умовам:

Інтерполяційний багаточлен Лагранжа для довільних вузлів:

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

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

і отже, також і на добуток цих різниць, тобто його ступінь не може бути нижче .

В такому випадку багаточлен повинен мати вигляд:

(1.4)

Рис.1.3

З умови знаходимо значення const:

,

таким чином знаходимо

(1.5)

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

то вираз для багаточлена, що приймає при відповідних значеннях абсцис численні значення, що виписані в одному із рядків, буде аналогічний розглянутому, тобто

(1.6)

Загальне рішення є суперпозицією(сумою) часних рішень (1.6)

(1.7)

Це і є інтерполяційний багаточлен Лагранжа. За наборами вихідних пар (1.2) формула (1.7) дозволяє достатньо просто скласти «зовнішній вигляд» багаточлена.

Використовуючи позначення

,(1.8)

формулі Лагранжа можна придати більш стиснутий вигляд. Продиференціюємо по

при маємо:

.(1.9)

Формула Лагранжа з урахуванням (1.8) и (1.9) приймає вигляд:

або

(1.10)

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

Інтерполяційний багаточлен Лагранжа для рівновіддалених вузлів:

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

де

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

Позначимо , де . Звідки:

..................................................

Тобто в загальному випадку:

(1.11)

Використовуючи (1.11) та прийняте позначення отримаємо:

(1.12)

Враховуючи, що знайдемо:

(1.13)

Помітимо, що в (1.13) рівно рядків( -ий рядок відсутній); причому чисельні значення перших рядків додатні, а інші — від’ємні. Використовуючи (1.13), отримаємо:

тобто

(1.14)

З урахуванням (1.12) та (1.14) формула Лагранжа для рівновіддалених вузлів приймає вигляд:

(1.15)

Інтерполяційний багаточлен Ньютона для рівновіддалених вузлів

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

Кінцеві різниці:

Назвемо кінцевими різницями різниці між значеннями функції в сусідніх вузлах інтерполяції:

де

Отримані кінцеві різниці будемо називати різницями першого порядку. З різниць першого порядку отримаємо різниці другого порядку:

де

Повторюючи процедуру, отримаємо кінцеві різниці третього порядку:

Для кінцевих різниць -го порядку:

В результаті отримаємо таблицю кінцевих різниць:

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

Інтерполяційна формула Ньютона

Поліном -ого ступеня(що має коренів)

перепишемо у вигляді

де — вузли інтерполяції.

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

1) Вважаючи знайдемо

2) Вважаючи знайдемо

звідки

3) Вважаючи знайдемо

звідки і т.д.

k-1) В загальному випадку і

звідки

Підставивши обчислювальні значення у вираз для багаточлена , отримаємо

(1.16)

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