Переваги та недоліки сплайн-інтерполяції, види та характеристики

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

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

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

Типи сплайнів:

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

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

3. Сплайн Катмулла-Рома - це сплайн Ерміта, похідні якого визначаються за формулою:

Як і сплайн Ерміта, сплайн Катмулла-Рома має безперервну першу похідну і розривну другу. Сплайн Катмулла-Рома локальний - значення сплайна залежать тільки від значень функції в чотирьох сусідніх точках (двох зліва, двох праворуч). Можна використовувати два типи граничних умов:

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

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

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

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

· Якщо значення першої (або другої) похідної на кордоні невідомо, то можна задати так звані природні граничні умови S'' (A) = 0, S'' (B) = 0, і отримати природний сплайн. Похибка інтерполяції природним сплайном становить O (h 2). Максимум похибки спостерігається в околицях граничних вузлів, у внутрішніх вузлах точність інтерполяції значно вище.

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

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

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

5. Сплайн Акіми - це особливий вид сплайна, стійкий до викидів. Недоліком кубічних сплайнів є те, що вони схильні осцилювати в околицях точки, що істотно відрізняється від своїх сусідів. На графіку наведено набір точок, що містить один викид. Зеленим кольором позначено кубічний сплайн з природними граничними умовами. На відрізках інтерполяції, що межують з викидом, сплайн помітно відхиляється від інтерпольованої функції - позначається вплив викиду. Червоним кольором позначено сплайн Акімов. Можна бачити, що, на відміну від кубічного сплайна, сплайн Акіми в меншій мірі схильний до впливу викидів - на відрізках, що межують з викидом, практично відсутні ознаки осциляції. Важливою властивістю сплайна Акіми є його локальність - значення функції на відрізку [x_i , x_i+1 ] залежать тільки від f_i-2 , f_i-1 , f_i , f_i+1 , f_i+2 , f_i+3 . Другою властивістю, яке слід брати до уваги, є нелінійність інтерполяції сплайнами Акіми - результат інтерполяції суми двох функцій не дорівнює сумі інтерполяційних схем, побудованих на основі окремих функцій. Для побудови сплайна Акіми потрібно не менше 5 точок. У внутрішній області (тобто між x₂ і x_N-3 при нумерації точок від 0 до N-1) похибка інтерполяції має порядок O(h ²).

2.2 Інтерполяція функції, заданої таблицею значень кубічними сплайнами (Реалізація Java)

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

public class Splayn {
public SplineTuple[] splines; // Сплайн

// Побудова сплайна
// x - вузли сітки, повинні бути впорядковані за зростанням, кратні вузли заборонені
// y - значення функції в вузлах сітки
// n - кількість вузлів сітки
public void BuildSpline(double[] x, double[] y, int n) {
// Ініціалізація масиву сплайнів
splines = new SplineTuple[n];
for(int i=0;i<n;i++){
splines[i] = new SplineTuple();
}

for (int i = 0; i < n; ++i) {
splines[i].x = x[i];
splines[i].a = y[i];
}
splines[0].c = splines[n - 1].c = 0.0;

/ / Рішення СЛАР щодо коефіцієнтів сплайнів c [i] методом прогонки для трехдіагональной матриць
// Обчислення прогонних коефіцієнтів - прямий хід методу прогонки
double[] alpha = new double[n - 1];
double[] beta = new double[n - 1];
alpha[0] = beta[0] = 0.0;
for (int i = 1; i < n - 1; ++i) {
double h_i = x[i] - x[i - 1], h_i1 = x[i + 1] - x[i];
double A = h_i;
double C = 2.0 * (h_i + h_i1);
double B = h_i1;
double F = 6.0 * ((y[i + 1] - y[i]) / h_i1 - (y[i] - y[i - 1]) / h_i);
double z = (A * alpha[i - 1] + C);
alpha[i] = -B / z;
beta[i] = (F - A * beta[i - 1]) / z;
}

// Знаходження рішення - зворотний хід методу прогонки
for (int i = n - 2; i > 0; --i)
splines[i].c = alpha[i] * splines[i + 1].c + beta[i];
// Звільнення пам'яті, займаної прогоночние коефіцієнтами
beta = null;
alpha = null;
// За відомим коефіцієнтам c [i] знаходимо значення b [i] і d [i]
for (int i = n - 1; i > 0; --i) {
double h_i = x[i] - x[i - 1];
splines[i].d = (splines[i].c - splines[i - 1].c) / h_i;
splines[i].b = h_i * (2.0 * splines[i].c + splines[i - 1].c) / 6.0 + (y[i] - y[i - 1]) / h_i;
}
}
// Обчислення значення інтерпольованої функції в довільній точці
public double f(double x) {
SplineTuple s;
int n= splines.length;
//BuildSpline(myx,y,n);
if (x <= splines[0].x) // Якщо x менше точки сітки x [0] - користуємося першим елементом масиву

s = splines[1];
else if (x >= splines[n - 1].x) // Якщо x більше точки сітки x [n - 1] - користуємося останнім елементом масиву
s = splines[n - 1];
else // Інакше x лежить між граничними точками сітки - виробляємо бінарний пошук потрібного елемемту масиву
{
int i = 0, j = n - 1;
while (i + 1 < j) {
int k = i + (j - i) / 2;
if (x <= splines[k].x)
j = k;
else
i = k;
}
s = splines[j];
}
double dx = (x - s.x);
// Обчислюємо значення сплайна в заданій точці за схемою Горнера (в принципі, "розумний" компілятор застосував би схему Горнера сам, але ж не всі такі розумні, як здаються)

return s.a + (s.b + (s.c / 2.0 + s.d * dx / 6.0) * dx) * dx;
}
}
public class SplineTuple {
public double a, b, c, d, x;

 

 

}