Основні підходи до апроксимації та інтерполяції даних

ВСТУП

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

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

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

Досягнення зазначеної мети передбачає вирішенню наступних завдань.

· написання алгоритму,

· його запрограмування,

· проведення інтерполяції за даними Рівненської атомної електростанції.

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

ОСНОВНІ ПІДХОДИ ДО АПРОКСИМАЦІЇ ТА ІНТЕРПОЛЯЦІЇ ДАНИХ

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

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

Тобто, інтерполяція — це спосіб, за допомогою якого за таблицею, що містить деякі числові дані, можна знайти проміжні результати, яких нема безпосередньо в таблиці. Наприклад, визначення функції f(x) для аргументів x, які знаходяться між значеннями x₀,…, x_i,…,x_n, за відомими значеннями f(x_i). Якщо x лежить зовні інтервалу [ x₀, x_n ], аналогічна процедура називається екстраполяцією. Найпростішою є лінійна інтерполяція, при якій приріст функції вважають пропорційним приросту аргументу.

Можна дати наступне визначення інтерполяції:

Нехай маємо n значень xі, кожному з який відповідає своє значення y_i. Потрібно знайти таку функцію F, що:

F(x_i) = y_i, i = 1,…, n

При цьому:

x_i називають вузлами інтерполяції,

пари (x_i, y_i) називають точками даних чи базовими точками,

різницю між «сусідніми» значеннями x_i-x_i-1 — кроком,

функцію F (x) — функцією, що інтерполює чи інтерполянтом.

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

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

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

До методів рівномірної сітки відносяться: інтерполяційний поліном Ньютона, сплайн інтерполяція та інші.

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

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

Цей многочлен називають першим інтерполяційним многочленом Ньютона.

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

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

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

Прикладами таких формул можуть служити наступні:

- інтерполяційні формули Гауса;

- інтерполяційна формула Стірлінга;
- інтерполяціонная формула Бесселя;

Метод сплайнів, або сплайн-інтерполяція, ґрунтується на використанні для інтерполяції в околах даного вузла кускових поліноміальних функцій, які мають назву «функції сплайнів». Термін «сплайн» походить від англійського spline, що означає гнучку лінійку, за допомогою якої креслярі проводили через задані точки плавні криві. Для двовимірного випадку (на площині) функція сплайна, що математично еквівалентна гнучкій лінійці, є кубічним поліномом (поліномом третього ступеня), який є безперервною функцією і має безперервні першу і другу похідні. Для тривимірного випадку, коли замість лінії має бути інтерпольована поверхня, використовуються бікубічні сплайни — полігони третього ступеня двох координат простору. Сплайн-інтерполяція належить до точних методів інтерполяції, при яких інтерпольована лінія (двовимірний випадок) або поверхня (тривимірний випадок) у точках вимірювань збігається із виміряними значеннями.

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

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

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

До метотодів, що краще працюють на нерівномірній сітці можна віднести: лінійна інтерполяція, крайгінг інтерполяція, метод найменшої кривизни, також використовуються радіальні базисні функції(Radial Basis Function), метод “найближчого сусіда”, інтерполяційний поліном Лагранжа,існує також інтерполяція оберненої середньозваженої відстані, метод Шепарда та інші.

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

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

Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для n + 1 пар чисел (x₀, y₀), (x₁, y₁)…(x_n, y_n), де всі x_i різні, існує єдиний многочлен L(x) степеня не більшого від n, для якого L(x_i) =y_i. Цей многочлен називається інтерполяційною формулою Лагранжа і має такі властивості: при заданій сукупності вузлових точок будова многочлена можлива тільки єдиним способом. Многочлен Лагранжа може бути побудовано при будь-якому розташуванні вузлів інтерполяції (включаючи і нерівномірне).

У найпростішому випадку n = 1 - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки.

Кригінг (інколи — крайгінг) — загальна назва локально-стохастичних методів просторової інтерполяції (на честь південно-африканського гірничого інженера Д.Дж. Кріге — D.G. Krige).

Кригінг інтерполяція є більш точною, але вона набагато складніша. Крайгінг менше робить «пухирців», і виявляється більш точною при інтерполяції карт висот.

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

Ще існує інтерполяція методом найменшої кривизни. Грубо кажучи, її суть полягає в тому, що треба побудувати яку-небудь поверхню на рівномірній сітці, відповідно виміряним даними, а потім цю поверхню багаторазово згладити, постійно підправляючи її, щоб вона не суперечила виміряним даними. Ця інтерполяція виявляється менш точною, ніж крайгінг, але зате одержувана поверхня сама гладка, і містить менше за все «пухирців». Метод найменшою кривизни широко використовується в науках про Землю, він розраховує саму гладку можливу поверхню з найменшими спотвореннями вихідних даних, тому не є найточнішим інтерполятором.

Радіальні базисні функції(Radial Basis Function)- група різноманітних методів інтерполяції даних. Ступінь згладженість поверхні визначається вживаними коефіцієнтами.

Метод “найближчого сусіда” є методом просторової інтерполяції, розроблений Робіном Сібсоном. Природний метод сусід використовує зміну розбиття Вороного для обчислення ваги. Цей метод використовується, коли вихідні дані вже задані по рівномірної сітці, або у випадках, де дані – з незначними втратами величин. Метод ефективний для заповнення "дірок" у даних.

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

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

У 1968-му році був вперше опублікований метод Шепарда. Це та ж сама середньозважена інтерполяція, тільки зважуються в ній не значення в точках, а опорні функції. На відміну від методу оберненої середньозваженої відстані метод Shepard використовує квадрати відстані. Дана особливість визначає його використання для візуалізації геофізичних (Гравітаційних, магнітних, електричних) полів, інтенсивність яких зазвичай зменшується пропорційно квадрату відстані від джерела. Метод Shepard може працювати як точний інтерполятор або як інтерполятор згладжування. Працездатність в просторі будь-якої розмірності. Алгоритм успішно працює навіть на сітках із співпадаючими вузлами.

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