WikiDer > Полигармонический сплайн

Polyharmonic spline

Полигармонические сплайны используются для аппроксимация функции и данные интерполяция. Они очень полезны для интерполяции и подгонки разрозненных данных во многих измерениях. Особые случаи включают шлицы тонкой пластины[1][2] и естественные кубические шлицы в одном измерении.[3]

Определение

Полигармонический сплайн - это линейная комбинация полигармонических радиальные базисные функции (RBFs) обозначается плюс полиномиальный член:

 

 

 

 

(1)

куда

Полигармонические базисные функции
  • ( обозначает транспонирование матрицы, что означает вектор-столбец) является вещественным вектором независимые переменные,
  • находятся векторы того же размера, что и (часто называемые центрами), которые кривая или поверхность должна интерполировать,
  • являются веса RBFs,
  • являются веса полинома.

Многочлен с коэффициентами повышает точность подгонки полигармонических сглаживающих сплайнов, а также улучшает экстраполяцию вдали от центров См. Рисунок ниже для сравнения шлицев с полиномиальным членом и без полиномиального члена.

Полигармонические RBF имеют вид:

Другие значения показателя степени бесполезны (например, ), потому что решение проблемы интерполяции может не существовать. Чтобы избежать проблем при (поскольку ) полигармонические RBF с натуральным логарифмом могут быть реализованы как:

Веса и определены так, что функция интерполирует данные баллы (за ) и выполняет условия ортогональности

В совокупности эти ограничения эквивалентны симметричной линейной системе уравнений

 

 

 

 

(2)

куда

Чтобы эта система уравнений имела единственное решение, должен быть в полном звании. является полным рангом для очень мягких условий во входных данных. Например, в двух измерениях три центра, образующие невырожденный треугольник, гарантируют, что имеет полный ранг, а в трех измерениях четыре центра, образующие невырожденный тетраэдр, гарантируют, что B имеет полный ранг. Как поясняется позже, линейное преобразование, являющееся результатом ограничения области линейного преобразования к пустое пространство из положительно определен. Это означает, что если полного ранга, система уравнений (2) всегда имеет уникальное решение, и его можно решить с помощью Разложение Холецкого после подходящего преобразования. Вычисленные веса позволяют оценить сплайн для любых используя уравнение (1). Многие практические детали реализации и использования полигармонических сплайнов объясняются в Фасхауэре.[4] В Иске[5] полигармонические сплайны рассматриваются как частные случаи других методов множественного разрешения при моделировании рассеянных данных.

Причина названия "полигармоническая"

Полигармоническое уравнение - это уравнение в частных производных формы для любого натурального числа , куда это Оператор Лапласа. Например, бигармоническое уравнение является и уравнение тригармонии . Все полигармонические радиальные базисные функции являются решениями полигармонического уравнения (или, точнее, модифицированного полигармонического уравнения с Дельта-функция Дирака справа, а не 0). Например, радиальная базисная функция тонкой пластины является решением модифицированного 2-мерного бигармонического уравнения.[6] Применяя двумерный оператор Лапласа () к радиальной базисной функции тонкой пластины либо вручную, либо с помощью система компьютерной алгебры показывает, что . Применение оператора Лапласа к (это ) дает 0. Но 0 не совсем правильно. Чтобы увидеть это, замените с (куда некоторое небольшое число, стремящееся к 0). Оператор Лапласа применяется к дает . За правая часть этого уравнения стремится к бесконечности при приближается к 0. Для любого другого , правая часть стремится к 0 при приближается к 0. Это означает, что правая часть является дельта-функцией Дирака. Система компьютерной алгебры покажет, что

Таким образом, радиальная базисная функция тонкой пластины является решением уравнения .

Применяя трехмерный лапласиан () к бигармоническому RBF дает и применяя 3D оператор к тригармоническому RBF дает . Сдача и вычисления снова указывает на то, что правая часть PDE для бигармонических и тригармонических RBF являются дельта-функциями Дирака. С

точные PDE, удовлетворяющие бигармоническим и тригармоническим RBF, равны и .

Полигармонические сглаживающие сплайны

Полигармонические сплайны минимизировать

 

 

 

 

(3)

куда какая-то коробка в содержащая окрестность всех центров, - некоторая положительная константа, а вектор всех частные производные порядка Например, в 2D и и в 3D . В 2D превращая интеграл в упрощенный тонкая пластина энергетический функционал.

Чтобы показать, что полигармонические сплайны минимизируют уравнение (3), аппроксимирующий член должен быть преобразован в интеграл, используя определение дельта-функции Дирака:

Итак, уравнение (3) можно записать как функционал

куда это мультииндекс пробегает все частные производные порядка за Чтобы применить Уравнение Эйлера-Лагранжа для одной функции нескольких переменных и производных более высокого порядка величины

и

необходимы. Подставление этих величин в уравнение E-L показывает, что

 

 

 

 

(4)

Слабое решение из (4) удовлетворяет

 

 

 

 

(5)

для всех гладких тестовых функций которые исчезают за пределами Слабое решение уравнения (4) по-прежнему будет минимизировать (3), избавившись от дельта-функции путем интеграции.[7]

Позволять - полигармонический сплайн, как определено уравнением (1). Следующие расчеты покажут, что удовлетворяет (5). Применяя оператор к уравнению (1) дает

куда и Так (5) эквивалентно

 

 

 

 

(6)

Единственно возможное решение (6) для всех тестовых функций является

 

 

 

 

(7)

(что подразумевает интерполяцию, если ). Объединяя определение в уравнении (1) с уравнением (7) приводит к почти той же линейной системе, что и уравнение (2) за исключением того, что матрица заменяется на куда это единичная матрица. Например, для трехмерных тригармонических RBFs, заменяется на

Объяснение дополнительных ограничений

В (2) нижняя половина системы уравнений () дается без объяснения причин. Для объяснения сначала требуется получить упрощенную форму когда все из

Во-первых, потребуйте, чтобы Это гарантирует, что все производные порядка и выше исчезают в бесконечности. Например, пусть и и быть тригармоническим RBF. потом (учитывая как отображение из к ). Для данного центра

На линии для произвольной точки и единичный вектор

Разделив числитель и знаменатель этого на показывает, что количество, не зависящее от центра Итак, в данной строке

Недостаточно требовать, чтобы потому что в дальнейшем это необходимо для исчезнуть на бесконечности, где и мультииндексы такие, что Для тригармонии (куда и веса и центры ) всегда является суммой полиномов 5-й степени от и делится на квадратный корень из общего многочлена степени 8. Рассмотрим поведение этих терминов в строке в качестве приближается к бесконечности. Числитель представляет собой многочлен 5-й степени от Разделив числитель и знаменатель на оставляет в числителе члены степени 4 и 5 и функцию только в знаменателе. Срок 5 степени, разделенный на это продукт пяти координаты и В ) ограничение заставляет это исчезать везде на линии. Срок 4 степени, разделенный на является либо произведением четырех координаты и координата или произведение четырех координаты и единый или же координировать. В ограничение приводит к тому, что член первого типа исчезает везде на линии. Дополнительные ограничения заставит исчезнуть второй тип члена.

Теперь определите внутренний продукт двух функций. определяется как линейная комбинация полигармонических RBFs с и в качестве

Интеграция по частям показывает, что

 

 

 

 

(8)

Например, пусть и потом

 

 

 

 

(9)

Интегрирование первого члена этого по частям один раз дает

поскольку исчезает на бесконечности. Снова интеграция по частям приводит к

Таким образом, интегрируя по частям дважды для каждого члена (9) дает

С (8) показывает, что

Так что если и

 

 

 

 

(10)

Теперь происхождение ограничений можно объяснить. Здесь является обобщением определенное выше, чтобы по возможности включать мономы до степени Другими словами,

куда вектор-столбец любой степени мономы координат Верхняя половина (2) эквивалентно Итак, чтобы получить сглаживающий сплайн, нужно минимизировать скалярное поле определяется

Уравнения

и

(куда обозначает строку из ) эквивалентны двум системам линейных уравнений и С обратима, первая система эквивалентна Итак, первая система подразумевает, что вторая система эквивалентна Как и в предыдущем вычислении коэффициента сглаживающего сплайна, верхняя половина (2) становится

Этот вывод системы уравнений полигармонического сглаживающего сплайна не предполагал ограничений, необходимых для гарантии того, что Но ограничения, необходимые для этого, и являются подмножеством что верно для критической точки из Так верно для формируется из решения системы уравнений полигармонического сглаживающего сплайна. Поскольку интеграл положителен для всех линейное преобразование, возникающее в результате ограничения области линейного преобразования к такой, что должно быть положительно определенным. Этот факт позволяет преобразовать систему полигармонических сглаживающих сплайновых уравнений в симметричную положительно определенную систему уравнений, которую можно решить вдвое быстрее с помощью разложения Холецкого.[6]

Примеры

На следующем рисунке показана интерполяция через четыре точки (отмеченные «кружками») с использованием различных типов полигармонических сплайнов. «Кривизна» интерполированных кривых растет с порядком сплайна, и экстраполяция на левой границе (x <0) разумна. На рисунке также представлены радиальные базисные функции phi = exp (-r2), что также дает хорошую интерполяцию. Наконец, на рисунке есть также неполигармонический сплайн phi = r2 чтобы продемонстрировать, что эта радиальная базисная функция не может проходить через заранее определенные точки (линейное уравнение не имеет решения и решается методом наименьших квадратов).

Интерполяция с помощью различных полигармонических сплайнов, которые должны проходить через 4 предопределенные точки, отмеченные кружком (интерполяция с phi = r2 бесполезен, так как система линейных уравнений интерполяционной задачи не имеет решения; решается методом наименьших квадратов, но не проходит центров)

На следующем рисунке показана та же интерполяция, что и на первом рисунке, за исключением того, что точки, которые должны быть интерполированы, масштабируются с коэффициентом 100 (и случай phi = r2 больше не входит). Поскольку phi = (scale * r)k = (масштабk)*рk, коэффициент (масштабk) можно извлечь из матрицы А системы линейных уравнений и, следовательно, масштабирование не влияет на решение. Это отличается для логарифмической формы сплайна, хотя масштабирование не оказывает большого влияния. Этот анализ отражен на рисунке, где интерполяция не показывает больших различий. Обратите внимание, что для других радиальных базисных функций, таких как phi = exp (-k * r2) с k = 1 интерполяция больше нецелесообразна и необходимо адаптировать k.

Та же интерполяция, что и на первом рисунке, но точки для интерполяции масштабируются на 100

На следующем рисунке показана та же интерполяция, что и на первом рисунке, за исключением того, что полиномиальный член функции не принимается во внимание (и случай phi = r2 больше не входит). Как видно из рисунка, экстраполяция для x <0 уже не такая «естественная», как на первом рисунке для некоторых базисных функций. Это означает, что полиномиальный член полезен при экстраполяции.

Та же интерполяция, что и на первом рисунке, но без полиномиального члена

Обсуждение

Основное преимущество полигармонической сплайн-интерполяции состоит в том, что обычно очень хорошие результаты интерполяции получаются для разрозненных данных без выполнения какой-либо «настройки», поэтому возможна автоматическая интерполяция. Это не относится к другим радиальным базисным функциям. Например, функция Гаусса нужно настроить, чтобы выбирается в соответствии с базовой сеткой независимых переменных. Если эта сетка неоднородна, правильный выбор добиться хорошего результата интерполяции сложно или невозможно.

Основные недостатки:

  • Чтобы определить веса, необходимо решить плотную линейную систему уравнений. Решение плотной линейной системы становится непрактичным, если размер большой, так как требуется память а количество необходимых операций равно
  • Оценка вычисленной полигармонической сплайн-функции на точки данных требует операции. Во многих приложениях (например, обработка изображений), намного больше, чем и если оба числа большие, это непрактично.

Недавно были разработаны способы преодоления вышеупомянутых трудностей. Например, Beatson et al.[8] представить метод интерполяции полигармонических сплайнов в одной точке в трех измерениях в операции вместо операции.

Смотрите также

Рекомендации

  1. ^ Р.Л. Хардер, Р.Н. Десмаре: Интерполяция с использованием сплайнов поверхности. Журнал самолетов, 1972, выпуск 2, стр. 189-191.
  2. ^ Ж. Дюшон: Сплайны, минимизирующие инвариантные относительно вращения полунормы в пространствах Соболева. Конструктивная теория функций нескольких переменных, W. Schempp and K. Zeller (ред.), Springer, Berlin, pp.85-100.
  3. ^ Вендланд, Хольгер (2005). Аппроксимация разрозненных данных. Издательство Кембриджского университета. п.9. ISBN 0521843359.
  4. ^ Г.Ф. Фассауэр Г.Ф .: Бессеточные методы аппроксимации с помощью MATLAB. World Scientific Publishing Company, 2007, ISPN-10: 9812706348
  5. ^ А. Иске: Методы множественного разрешения в моделировании рассеянных данных, Конспект лекций по вычислительным наукам и технике, 2004, т. 37, ISBN 3-540-20479-2, Springer-Verlag, Гейдельберг.
  6. ^ а б Пауэлл, М. Дж. Д. (1993). «Некоторые алгоритмы интерполяции сплайнов тонких пластин к функциям двух переменных» (PDF). Технический отчет кафедры прикладной математики и теоретической физики Кембриджского университета. Получено 7 января, 2016.
  7. ^ Эванс, Лоуренс (1998). Уравнения с частными производными. Провиденс: Американское математическое общество. стр.450-452. ISBN 0-8218-0772-2.
  8. ^ Р.К. Битсон, M.J.D. Пауэлл, А. Загар: Быстрая оценка полигармонических сплайнов в трех измерениях. IMA Journal of Numerical Analysis, 2007, 27, стр. 427-450.