Оптимальна апроксимація сплайнами. Апроксимація з невідомими горизонтальними вузлами

• Tutorial

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


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

Основні визначення

Зауважимо, що для побудови сплайну потрібно спочатку задати сітку з горизонтальних вузлів. Розташуємо їх таким чином, щоб усередині інтервалу (a, b) стояло g вузлів, а по краях – k+1: і .

Кожен сплайн у точці може бути представлений у базовій формі:

Апроксимація із заданими горизонтальними вузлами

Тоді все завдання та всі попередні формули зводяться до вирішення простої системи лінійних рівнянь:

Згладжування

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

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

Розв'язання задачі одновимірної мінімізації

Коефіцієнти a i та b i можуть бути знайдені з рівнянь

Ідея полягає в тому, щоб розставити три крапки α 0< α 1 < α 2 таким образом, чтобы по значениям ошибок, достигаемых в этих точках, можно было построить простую аппроксимирующую функцию и вернуть её минимум. Притом значение ошибки в α 1 должно быть меньше, чем значение ошибки в α 0 и α 2 .

Знаходимо початкове наближення α 1 із умови S"(α 1)=0, де S(α) - функція виду

Якщо ми прорахувалися з початковим наближенням, то ми зменшуємо крок α 1 доти, доки він доставляє більше значенняпомилки, ніж α0. Вибір виходить із умови , де Q(α) - парабола, що інтерполює функцію помилки : , і .
Якщо k > 0, то ми знайшли значення α 1 , таке, що при його виборі значення помилки буде менше, ніж при виборі α 0 і α 2 і ми повертаємо його як грубе наближення α*.

Якщо ж наше початкове наближення було вірним, ми намагаємося знайти крок α 2 , такий що . Він буде знайдений між α 1 і α max , так як α max - точка сингулярності для штрафної функції.

Коли знайдено всі три значення α 0 , α 1 і α 2 ми представляємо функцію помилки у вигляді суми двох функцій, що наближають різницю квадратів і функцію штрафу. Функція Q(α) - парабола, чиї коефіцієнти може бути знайдено, оскільки ми знаємо її значення трьох точках. Функція R(α) йде на нескінченність при α, що прагне α max . Коефіцієнти b i також можуть бути знайдені із системи з трьох рівнянь. В результаті ми приходимо до рівняння, яке може бути приведено до квадратного і легко вирішене:

Теги:

• сплайни
• оптимізація
• python3

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

Розглянемо побудову кубічного сплайну. Нехай нам дано дві сусідні точки, через які проведемо кубічний поліном, але у полінома ? 4 коефіцієнти, отже потрібно ще два додаткові умовичи точки. Для цього прихопимо ще дві сусідні точки. Чим плавніший ми хочемо бачити лінію, тим складніше пройти точно через точки. Якщо формулі x = q 3 , досить плавності 3.

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

Розглянемо. Нехай t | параметр, по якому пробігаємо від точки P i до точки P i +1 . При t = 0 ми знаходимося в точці P i , при t = 1 в точці P i +1 . Якщо 0< t < 1, то мы находимся между P i и P i+1 .

Ця лінія в кожній точці має систему:

y(t) = ((b 3 t + b 2)t + b 1)t + b 0 для 0<= t <= 1 a 3 = (-x i-1 + 3x i - 3x i+1 + x i+2)/6

A 2 = (x i-1 - 2x i + x i+1)/2

A 1 = (-x i-1 + x i+1)/2

A 0 = (x i-1 + 4x i + x i+1)/6

Точки b 3 - b 0 розписують так само, але замість x підставляють. Між P i та P i+1 точки а та b не змінюються. Якщо після останньої точки вказати першу точку, система замкне контур.

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

Наслідки

Згладжування B-сплайнами

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

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

Можна будувати досить гладкі криві та поверхні з використанням поліномів. Припустимо, що хочемо побудувати поверхню як графіка функції z = z(x, y). Лінія y = const на цій поверхні буде представлена ​​лінією z = z(x), вона проходитиме через послідовність точок (x 0 , z 0), ..., (x i , z i), ..., (x n , z n) з x 0< ... < x i < ... < x n . Наша цель — провести через эти точки составную кривую f(x), имеющую следующие свойства:

• на кожному підінтервалі x i-1<= x <= x i , i = 1, 2, ..., n функция f(x) является кубическим полиномом;
• її перші та другі похідні безперервні у вузлах.

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

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

Перше обмеження можна усунути за допомогою B-сплайну. Загальна форма отриманої у разі кривої показано на .

На цьому малюнку сплайн продовжений від його кінцевих точок x i-4 x i прямими лініями, що йдуть вздовж осі x. В результаті виходить кубічний сплайн на будь-якій кількості відрізків, але він не дорівнює нулю лише на чотирьох із них. Така функція називається B-сплайн (або фундаментальним сплайн) четвертого порядку (або третього ступеня). Про нього говорять, що він має мінімальний носій (носій – це кількість відрізків, на яких сплайн відмінний від нуля).

Зауважимо, що кубічний B-сплайн повністю визначається безліччю вузлів, на яких він визначений, і лише однією заданою величиною z. У загальному вигляді B-сплайн M mi (x) порядку m (чи ступеня m - 1) цьому безлічі вузлів скрізь дорівнює нулю, крім m послідовних відрізків x i-m< x < x i . Опять-таки M mi (x) определяется множеством узлов и одной величиной z. Принято исключать последнюю степень свободы и фиксировать амплитуду B-сплайна некоторым стандартным образом.

Часто зручно для обчислень використовувати нормалізований B-сплайн N mi (x), пов'язаний з M mi (x) співвідношенням N mi (x) = (xi - xi-m) M mi (x).

Будь-який сплайн порядку m на множині вузлів x 0 , x 1 , ..., x n може бути виражений у вигляді лінійної комбінації B-сплайнів, визначених на тій же множині вузлів, розширеному (m - 1) додатковими вузлами на кожному з кінців інтервалу, які можна вибрати довільно: x-m+1, x-m+2, ..., x-1 і x n+1, ..., x n+m-1. Можна побудувати m + n – 1 послідовних B-сплайнів на розширеній множині вузлів, кожен з яких відмінний від нуля на m послідовних відрізках. Тому можна записати:
j(x) = S c i * M mi (x),
де j (x) будь-який сплайн ступеня (m - 1) на початковій множині вузлів і M mi (x) є B-сплайн на розширеній множині вузлів, відмінний від нуля при x i-m< x < x i ; c i суть числовые коэффициенты; суммирование ведется по i = 1, ..., m + n - 1.

Якщо є безліч векторів r 0 , r 1 , ..., r n , можна використовувати їх: r(u) = S r i * N 4, i+1 (u) (підсумовування ведеться по i = 0, ..., n). Оскільки є (n + 1) векторних коефіцієнтів, то необхідний набір (n + 1) B-сплайнів. Остання формула для 0<= u <= n - 2 является уравнением кривой, образованной кубическими B-сплайнами.

Властивості

Деякі найпростіші властивості випливають із тотожності S N 4, i+1 = 1, 0<= u <= n - 2, i = 0..n. При u = 0 следует: r(0) = N 42 (0)(r 1 - r 0). Из этого следует, что если r 0 , r 1 , .., r n — вершины некоторой замкнутой ломанной, то кривая, построенная на основе B-сплайна, начинается в r 0 и ее касательная в этой точке имеет направление (r 1 - r 0). Аналогичное утверждение верно и для другого конца. Главное преимущество этого сплайна заключается в том, что изменение одной из вершин влечет за собой изменение только четырех отрезков кривой. Далее, мы также можем построить кривую, аппроксимирующую ломанную с любым желаемым числом сторон. Отрезок сплайна всегда лежит в выпуклой оболочке:

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

Є ще 2 корисні факти:

• крива проходить поблизу середньої точки кожної сторони, за винятком 1-ої та останньої точками;
• при k = 2, ..., n - 2 крива проходить через точки: 1/6r k-1 + 2/3r k + 1/6r k+1 = 2/3r k + 1/3(1/2(r k-1 + r k+1))

Ці точки, як показано на , лежать на 1/3 відстані від r k на прямій, що з'єднує r k з серединою відрізка між r k-1 і r k+1 .

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

Сущ., кіл у синонімів: 1 функція (49) Словник синонімів ASIS. В.М. Тришин. 2013 … Словник синонімів

Сплайн-функція- кусково гладка функція, що використовується для вирівнювання часових рядів. Застосування С. ф. замість звичайних функцій тренду ефективно, коли всередині періоду, що аналізується, змінюється тенденція, напрямок ряду. С. ф. допомагає… … Економіко-математичний словник

сплайн- (Spline) Математична крива, що плавно з'єднує окремі точки. Застосовується для зображення контурів знаків [межа зображення знака]. також криві Безьє [метод опису вітерських кривих] … Шрифтова термінологія

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

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

Інтерполіювання за допомогою сплайнів, тобто побудова інтерполяційного сплайну (і. с.), що приймає в заданих точках (xi)задані значення (f(xi)), i=0, 1, . . ., n. Зазвичай в. с. задовольняють додатковим умовам кінцевих точках. Так, … … Математична енциклопедія

Функція визначена на відрізку, що збігається на часткових відрізках [х i, xi + 1], утворених сіткою а = x0 Математична енциклопедія

сплайн- а, ч. Одна з елементарних функцій, включена до сучасного числового аналізу … Український тлумачний словник

сплайн-апроксимація- Іменник жіночого роду …

сплайн-інтерполяція- Іменник жіночого роду … Орфографічний словарь української мови

Книги

• Сплайн-сплески та їх реалізації, Бурова І.Г.. У цій книзі основна увага приділяється сплайн-сплесковим розкладанням першого та другого порядку. Розглянуто прийоми розкладання потоків у ермітовому випадку з використанням потоку значень.