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

Метод аппроксимации функций и интерполяции данных

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

Определение

Полигармонический сплайн представляет собой линейную комбинацию полигармонических радиальных базисных функций (РБФ), обозначаемую как плюс полиномиальный член: ${\displaystyle \varphi }$

где

Полигармонические базисные функции

• ${\displaystyle \mathbf {x} =[x_{1}\ x_{2}\ \cdots \ x_{d}]^{\textrm {T}}}$( обозначает транспонированную матрицу, т.е. вектор-столбец) — действительный вектор независимых переменных, ${\displaystyle {\textrm {T}}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle d}$
• ${\displaystyle \mathbf {c} _{i}=[c_{i,1}\ c_{i,2}\ \cdots \ c_{i,d}]^{\textrm {T}}}$являются векторами того же размера (часто называемыми центрами), которые кривая или поверхность должна интерполировать, ${\displaystyle N}$ ${\displaystyle \mathbf {x} }$
• ${\displaystyle \mathbf {w} =[w_{1}\ w_{2}\ \cdots \ w_{N}]^{\textrm {T}}}$являются весами РБФ, ${\displaystyle N}$
• ${\displaystyle \mathbf {v} =[v_{1}\ v_{2}\ \cdots \ v_{d+1}]^{\textrm {T}}}$— веса полинома. ${\displaystyle d+1}$

Полином с коэффициентами улучшает точность подгонки для полигармонических сглаживающих сплайнов, а также улучшает экстраполяцию от центров. На рисунке ниже приведено сравнение сплайнов с полиномиальным членом и без полиномиального члена. ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {c} _{i}.}$

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

${\displaystyle {\begin{aligned}\varphi (r)&={\begin{cases}r^{k}&{\text{with }}k=1,3,5,\ldots ,\\r^{k}\ln(r)&{\text{with }}k=2,4,6,\ldots \end{cases}}\\[5mm]r&=|\mathbf {x} -\mathbf {c} _{i}|={\sqrt {(\mathbf {x} -\mathbf {c} _{i})^{\mathrm {T} }\,(\mathbf {x} -\mathbf {c} _{i})}}.\end{aligned}}}$

Другие значения показателя степени не являются полезными (например, ), поскольку решение проблемы интерполяции может не существовать. Чтобы избежать проблем при (поскольку ), полигармонические РБФ с натуральным логарифмом могут быть реализованы как: ${\displaystyle k}$ ${\displaystyle \varphi (r)=r^{2}}$ ${\displaystyle r=0}$ ${\displaystyle \log(0)=-\infty }$

${\displaystyle \varphi (r)={\begin{cases}r^{k-1}\ln(r^{r})&{\text{for }}r<1,\quad {\text{(this works because }}0^{0}{\text{ is defined)}}\\r^{k}\ln(r)&{\text{for }}r\geq 1.\end{cases}}}$

или, проще говоря, добавление расширения непрерывности в ${\displaystyle r=0}$

${\displaystyle \varphi (r)={\begin{cases}0&{\text{for }}r<\epsilon ,\quad {\text{(for some very small value of }}\epsilon {\text{, e.g. if using floating point numbers in double precisions, }}\epsilon =10^{-200}{\text{)}}\\r^{k}\ln(r)&{\text{for }}r\geq \epsilon .\end{cases}}}$

Веса и определяются таким образом, чтобы функция интерполировала заданные точки (для ) и удовлетворяла условиям ортогональности ${\displaystyle w_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle N}$ ${\displaystyle (\mathbf {c} _{i},f_{i})}$ ${\displaystyle i=1,2,\ldots ,N}$ ${\displaystyle d+1}$

${\displaystyle \sum _{i=1}^{N}w_{i}=0,\;\;\sum _{i=1}^{N}w_{i}\mathbf {c} _{i}=\mathbf {0} .}$

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

где

${\displaystyle A_{i,j}=\varphi (|\mathbf {c} _{i}-\mathbf {c} _{j}|),\quad B={\begin{bmatrix}1&1&\cdots &1\\\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{N}\end{bmatrix}}^{\textrm {T}},\quad \mathbf {f} =[f_{1},f_{2},\ldots ,f_{N}]^{\textrm {T}}.}$

Для того чтобы эта система уравнений имела единственное решение, должен быть полного ранга. является полным рангом для очень мягких условий на входные данные. Например, в двух измерениях три центра, образующие невырожденный треугольник, гарантируют, что является полным рангом, а в трех измерениях четыре центра, образующие невырожденный тетраэдр, гарантируют, что B является полным рангом. Как объясняется далее, линейное преобразование, полученное в результате ограничения области линейного преобразования нулевым пространством , является положительно определенным. Это означает, что если является полным рангом, система уравнений ( 2 ) всегда имеет единственное решение, и ее можно решить с помощью линейного решателя, специализированного для симметричных матриц. Вычисленные веса позволяют оценить сплайн для любого с использованием уравнения ( 1 ). Многие практические детали реализации и использования полигармонических сплайнов объясняются в Fasshauer. ^[4] В Iske ^[5] полигармонические сплайны рассматриваются как особые случаи других методов с несколькими разрешениями в моделировании разбросанных данных. ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\textstyle B^{\textrm {T}}}$ ${\displaystyle B}$ ${\displaystyle \mathbf {x} \in \mathbb {R} ^{d}}$

Обсуждение

Главное преимущество полигармонической сплайн-интерполяции заключается в том, что обычно очень хорошие результаты интерполяции получаются для разбросанных данных без выполнения какой-либо «настройки», поэтому автоматическая интерполяция осуществима. Это не относится к другим радиальным базисным функциям. Например, гауссова функция должна быть настроена, поэтому она выбирается в соответствии с базовой сеткой независимых переменных. Если эта сетка неравномерна, правильный выбор для достижения хорошего результата интерполяции затруднен или невозможен. ${\displaystyle e^{-k\cdot r^{2}}}$ ${\displaystyle k}$ ${\displaystyle k}$

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

• Для определения весов необходимо решить плотную линейную систему уравнений. Решение плотной линейной системы становится непрактичным, если размерность велика, поскольку требуемая память составляет и количество требуемых операций составляет ${\displaystyle N}$ ${\displaystyle O(N^{2})}$ ${\displaystyle O(N^{3}).}$
• Оценка вычисленной полигармонической сплайн-функции в точках данных требует операций. Во многих приложениях (примером является обработка изображений) намного больше, чем и если оба числа велики, это непрактично. ${\displaystyle M}$ ${\displaystyle O(MN)}$ ${\displaystyle M}$ ${\displaystyle N,}$

Быстрые методы построения и оценки

Один из простых подходов к ускорению построения и оценки модели заключается в использовании подмножества ближайших узлов интерполяции для построения локальной модели каждый раз, когда мы оцениваем сплайн. В результате общее время, необходимое для построения и оценки модели в точках, изменяется с до . Это может дать лучшие временные показатели, если намного меньше . Такой подход пропагандируется некоторыми библиотеками программного обеспечения, наиболее заметной из которых является scipy.interpolate.RBFInterpolator. Главным недостатком является то, что он вносит небольшие разрывы в сплайн и требует настройки под конкретную задачу: правильный выбор количества соседей, . Недавно были разработаны методы, позволяющие преодолеть вышеупомянутые трудности, не жертвуя основными преимуществами полигармонических сплайнов. ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle O(N^{3}+MN)}$ ${\displaystyle O(k^{3}*M)}$ ${\displaystyle k}$ ${\displaystyle N}$ ${\displaystyle k}$

Во-первых, был предложен ряд методов быстрой оценки: ${\displaystyle O(\log N)}$

• Битсон и др. ^[6] представляют метод интерполяции полигармонических сплайнов, являющихся базисной функцией в одной точке в 3-мерном пространстве или менее. ${\displaystyle r^{2k-1}}$
• Черри и др. ^[7] представляют метод интерполяции полигармонических сплайнов с использованием в качестве базовой функции в одной точке в 4 измерениях или менее. ${\displaystyle r^{2k}\log r}$

Во-вторых, ускоренное построение модели путем применения итеративного решателя к предварительно обусловленной ACBF линейной системе было предложено Брауном и др. ^[8]. Этот подход сокращает время выполнения с до и далее до при сочетании с ускоренными методами оценки. ${\displaystyle O(N^{3})}$ ${\displaystyle O(N^{2})}$ ${\displaystyle O(N\log N)}$

Описанные выше подходы часто используются коммерческими библиотеками анализа геопространственных данных и некоторыми реализациями с открытым исходным кодом (например, ALGLIB ). Иногда методы доменной декомпозиции используются для улучшения асимптотического поведения, снижая требования к памяти с до , что делает полигармонические сплайны подходящими для наборов данных с более чем 1.000.000 точек. ${\displaystyle O(N^{2})}$ ${\displaystyle O(N)}$

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

Полигармоническое уравнение — это уравнение в частных производных вида для любого натурального числа , где — оператор Лапласа . Например, бигармоническое уравнение — это , а тригармоническое уравнение — это . Все полигармонические радиальные базисные функции являются решениями полигармонического уравнения (или, точнее, модифицированного полигармонического уравнения с дельта-функцией Дирака в правой части вместо 0). Например, радиальная базисная функция тонкой пластины является решением модифицированного 2-мерного бигармонического уравнения. ^[9] Применение 2D-оператора Лапласа ( ) к радиальной базисной функции тонкой пластины вручную или с помощью системы компьютерной алгебры показывает, что . Применение оператора Лапласа к (это ) дает 0. Но 0 не совсем верно. Чтобы увидеть это, замените на (где — некоторое малое число, стремящееся к 0). Оператор Лапласа, примененный к, дает . Для правая часть этого уравнения стремится к бесконечности, когда стремится к 0. Для любого другого правая часть стремится к 0, когда стремится к 0. Это указывает на то, что правая часть является дельта-функцией Дирака. Система компьютерной алгебры покажет, что ${\displaystyle \Delta ^{m}f=0}$ ${\displaystyle m}$ ${\displaystyle \Delta }$ ${\displaystyle \Delta ^{2}f=0}$ ${\displaystyle \Delta ^{3}f=0}$ ${\displaystyle \Delta =\partial _{xx}+\partial _{yy}}$ ${\textstyle f_{\text{tp}}(x,y)=(x^{2}+y^{2})\log {\sqrt {x^{2}+y^{2}}}}$ ${\displaystyle \Delta f_{\text{tp}}=4+4\log r}$ ${\displaystyle \Delta f_{\text{tp}}}$ ${\displaystyle \Delta ^{2}f_{\text{tp}}}$ ${\displaystyle r^{2}=x^{2}+y^{2}}$ ${\displaystyle \rho ^{2}=x^{2}+y^{2}+h^{2}}$ ${\displaystyle h}$ ${\displaystyle 4\log \rho }$ ${\displaystyle \Delta ^{2}f_{\text{tp}}=8h^{2}/\rho ^{4}}$ ${\displaystyle (x,y)=(0,0),}$ ${\displaystyle h}$ ${\displaystyle (x,y)}$ ${\displaystyle h}$

${\displaystyle \lim _{h\to 0}\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }8h^{2}/(x^{2}+y^{2}+h^{2})^{2}\,dx\,dy=8\pi .}$

Таким образом, радиальная базисная функция тонкой пластины является решением уравнения . ${\displaystyle \Delta ^{2}f_{\text{tp}}=8\pi \delta (x,y)}$

Применение трехмерного лапласиана ( ) к бигармоническому RBF дает и применение трехмерного оператора к тригармоническому RBF дает . Повторное вычисление показывает, что правая часть PDE для бигармонического и тригармонического RBF является дельта-функцией Дирака. Поскольку ${\displaystyle \Delta =\partial _{xx}+\partial _{yy}+\partial _{zz}}$ ${\textstyle f_{\text{bi}}(x,y,z)={\sqrt {x^{2}+y^{2}+z^{2}}}}$ ${\displaystyle \Delta f_{\text{bi}}=2/r}$ ${\displaystyle \Delta ^{2}}$ ${\displaystyle f_{\text{tri}}(x,y,z)=(x^{2}+y^{2}+z^{2})^{3/2}}$ ${\displaystyle \Delta ^{2}f_{\text{tri}}=24/r}$ ${\displaystyle \rho ^{2}=x^{2}+y^{2}+z^{2}+h^{2}}$ ${\displaystyle \Delta (1/\rho )=-3h^{2}/\rho ^{5}}$

${\displaystyle \lim _{h\to 0}\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }-3h^{2}/(x^{2}+y^{2}+z^{2}+h^{2})^{5/2}\,dx\,dy\,dz=-4\pi ,}$

Точные уравнения в частных производных, которым удовлетворяют бигармонические и тригармонические РБФ, равны и . ${\displaystyle \Delta ^{2}f_{\text{bi}}=-8\pi \delta (x,y,z)}$ ${\displaystyle \Delta ^{3}f_{\text{tri}}=-96\pi \delta (x,y,z)}$

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

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

где — некоторый ящик в, содержащий окрестность всех центров, — некоторая положительная константа, а — вектор всех частных производных порядка Например, в 2D и и в 3D . В 2D интеграл представляет собой упрощенный функционал энергии тонкой пластины . ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \lambda }$ ${\displaystyle \nabla ^{m}f}$ ${\displaystyle m}$ ${\displaystyle f.}$ ${\displaystyle \nabla ^{1}f=(f_{x}\ f_{y})}$ ${\displaystyle \nabla ^{2}f=(f_{xx}\ f_{xy}\ f_{yx}\ f_{yy})}$ ${\displaystyle \nabla ^{2}f=(f_{xx}\ f_{xy}\ f_{xz}\ f_{yx}\ f_{yy}\ f_{yz}\ f_{zx}\ f_{zy}\ f_{zz})}$ ${\displaystyle |\nabla ^{2}f|^{2}=f_{xx}^{2}+2f_{xy}^{2}+f_{yy}^{2},}$

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

${\displaystyle \sum _{i=1}^{N}(f(\mathbf {c} _{i})-f_{i})^{2}=\int _{\mathcal {B}}\sum _{i=1}^{N}(f(\mathbf {x} )-f_{i})^{2}\delta (\mathbf {x} -\mathbf {c} _{i})\,d\mathbf {x} .}$

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

${\displaystyle J[f]=\int _{\mathcal {B}}F(\mathbf {x} ,f,\partial ^{\alpha _{1}}f,\partial ^{\alpha _{2}}f,\ldots ,\partial ^{\alpha _{n}}f)\,d\mathbf {x} =\int _{\mathcal {B}}\left[\sum _{i=1}^{N}(f(\mathbf {x} )-f_{i})^{2}\delta (\mathbf {x} -\mathbf {c} _{i})+\lambda |\nabla ^{m}f|^{2}\right]\,d\mathbf {x} .}$

где — мультииндекс , который пробегает все частные производные порядка Для того чтобы применить уравнение Эйлера–Лагранжа для одной функции нескольких переменных и производных более высокого порядка, величины ${\displaystyle \alpha _{i}}$ ${\displaystyle m}$ ${\displaystyle \mathbb {R} ^{d}.}$

${\displaystyle {\partial F \over \partial f}=2\sum _{i=1}^{N}(f(\mathbf {x} )-f_{i})\delta (\mathbf {x} -x_{i})}$

и

${\displaystyle \sum _{i=1}^{n}\partial ^{\alpha _{i}}{\partial F \over \partial (\partial ^{\alpha _{i}}f)}=2\lambda \Delta ^{m}f}$

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

Слабое решение ( 4 ) удовлетворяет ${\displaystyle f(\mathbf {x} )}$

для всех гладких тестовых функций , которые исчезают вне слабого решения уравнения ( 4 ), все равно будет минимизировать ( 3 ), избавляясь при этом от дельта-функции посредством интегрирования. ^[10] ${\displaystyle g}$ ${\displaystyle {\mathcal {B}}.}$

Пусть будет полигармоническим сплайном, как определено уравнением ( 1 ). Следующие вычисления покажут, что удовлетворяет ( 5 ). Применение оператора к уравнению ( 1 ) дает ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \Delta ^{m}}$

${\displaystyle \Delta ^{m}f=\sum _{i=1}^{M}w_{i}C_{m,d}\delta (\mathbf {x} -\mathbf {c} _{i})}$

где и Так ( 5 ) эквивалентно ${\displaystyle C_{2,2}=8\pi ,}$ ${\displaystyle C_{2,3}=-8\pi ,}$ ${\displaystyle C_{3,3}=-96\pi .}$

Единственное возможное решение ( 6 ) для всех тестовых функций — это ${\displaystyle g}$

(что подразумевает интерполяцию, если ). Объединение определения в уравнении ( 1 ) с уравнением ( 7 ) приводит к почти той же линейной системе, что и уравнение ( 2 ), за исключением того, что матрица заменяется на , где — единичная матрица. Например, для трехмерных тригармонических RBF заменяется на ${\displaystyle \lambda =0}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A+(-1)^{m}C_{m,d}\lambda I}$ ${\displaystyle I}$ ${\displaystyle N\times N}$ ${\displaystyle A}$ ${\displaystyle A+96\pi \lambda I.}$

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

В ( 2 ) нижняя половина системы уравнений ( ) дана без объяснения. Объяснение сначала требует вывода упрощенной формы, когда все ${\displaystyle B^{\textrm {T}}\mathbf {w} =0}$ ${\textstyle \int _{\mathcal {B}}|\nabla ^{m}f|^{2}\,d\mathbf {x} }$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \mathbb {R} ^{d}.}$

Во-первых, потребуем, чтобы Это гарантирует, что все производные порядка и выше исчезают на бесконечности. Например, пусть и и будут тригармоническими RBF. Тогда (рассматривая как отображение из в ). Для заданного центра ${\textstyle \sum _{i=1}^{N}w_{i}=0.}$ ${\displaystyle m}$ ${\textstyle f(\mathbf {x} )=\sum _{i=1}^{N}w_{i}\varphi (|\mathbf {x} -\mathbf {c} _{i}|)}$ ${\displaystyle m=3}$ ${\displaystyle d=3}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi _{zzy}=3y(x^{2}+y^{2})/(x^{2}+y^{2}+z^{2})^{3/2}}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbf {P} =(P_{1},P_{2},P_{3}),}$

${\displaystyle \varphi _{zzy}(\mathbf {x} -\mathbf {P} )={\frac {3(y-P_{2})((y-P_{2})^{2}+(x-P_{1})^{2})}{((x-P_{1})^{2}+(y-P_{2})^{2}+(z-P_{3})^{2})^{3/2}}}.}$

На прямой для произвольной точки и единичного вектора ${\displaystyle \mathbf {x} =\mathbf {a} +t\mathbf {b} }$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {b} ,}$

${\displaystyle \varphi _{zzy}(\mathbf {x} -\mathbf {P} )={\frac {3(a_{2}+b_{2}t-P_{2})((a_{2}+b_{2}t-P_{2})^{2}+(a_{1}+b_{1}t-P_{1})^{2})}{((a_{1}+b_{1}t-P_{1})^{2}+(a_{2}+b_{2}t-P_{2})^{2}+(a_{3}+b_{3}t-P_{3})^{2})^{3/2}}}.}$

Разделив числитель и знаменатель этого числа на , мы получаем величину, не зависящую от центра , поэтому на данной прямой ${\displaystyle t^{3}}$ ${\textstyle \lim _{t\to \infty }\varphi _{zyy}(\mathbf {x} -\mathbf {P} )=3b_{2}(b_{2}^{2}+b_{1}^{2})/(b_{1}^{2}+b_{2}^{2}+b_{3}^{2})^{3/2},}$ ${\displaystyle \mathbf {P} .}$

${\displaystyle \lim _{t\to \infty }f_{zyy}(\mathbf {x} )=\lim _{t\to \infty }\sum _{i=1}^{N}w_{i}\varphi _{zyy}(\mathbf {x} -\mathbf {c} _{i})=\left(\sum _{i=1}^{N}w_{i}\right)3b_{2}(b_{2}^{2}+b_{1}^{2})/(b_{1}^{2}+b_{2}^{2}+b_{3}^{2})^{3/2}=0.}$

Недостаточно требовать этого, поскольку в дальнейшем необходимо, чтобы для исчезало на бесконечности, где и являются мультииндексами такими, что Для тригармонического (где и являются весами и центрами ) всегда является суммой всех полиномов степени 5 по и делится на квадратный корень из общего полинома степени 8. Рассмотрим поведение этих членов на прямой по мере приближения к бесконечности. Числитель является полиномом степени 5 по Разделив числитель и знаменатель на, в числителе остаются члены степени 4 и 5, а в знаменателе — функция . Член степени 5, деленный на , является произведением пяти координат и Ограничение (и ) обращает его в нуль всюду на прямой. Член степени 4, деленный на , является либо произведением четырех координат и координаты, либо произведением четырех координат и одной или координаты. Ограничение заставляет первый тип членов исчезать всюду на прямой. Дополнительные ограничения заставят второй тип членов исчезать. ${\textstyle \sum _{i=1}^{N}w_{i}=0,}$ ${\displaystyle f_{\alpha }g_{\beta }}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle |\alpha |+|\beta |=2m-1.}$ ${\displaystyle \varphi ,}$ ${\displaystyle w_{i}u_{j}\varphi _{\alpha }(\mathbf {x} -\mathbf {c} _{i})\varphi _{\beta }(\mathbf {x} -\mathbf {d} _{j})}$ ${\displaystyle u_{j}}$ ${\displaystyle \mathbf {d} _{j}}$ ${\displaystyle g}$ ${\displaystyle x,}$ ${\displaystyle y,}$ ${\displaystyle z}$ ${\displaystyle \mathbf {x} =\mathbf {a} +t\mathbf {b} }$ ${\displaystyle t}$ ${\displaystyle t.}$ ${\displaystyle t^{4}}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle t^{4}}$ ${\displaystyle b}$ ${\displaystyle t.}$ ${\textstyle \sum w=0}$ ${\textstyle \sum u=0}$ ${\displaystyle t^{4}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c_{i}}$ ${\displaystyle d_{j}}$ ${\textstyle \sum w=0}$ ${\textstyle \sum _{i=1}^{N}w_{i}\mathbf {c} _{i}=0}$

Теперь определим скалярное произведение двух функций, определенных как линейная комбинация полигармонических РБФ с и как ${\displaystyle f,g:\mathbb {R} ^{d}\to \mathbb {R} }$ ${\displaystyle \varphi _{m,d}}$ ${\textstyle \sum w=0}$ ${\textstyle \sum w\mathbf {c} =0}$

${\displaystyle \langle f,g\rangle =\int _{\mathbb {R} ^{d}}(\nabla ^{m}f)\cdot (\nabla ^{m}g)\,d\mathbf {x} .}$

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

Например, пусть и Тогда ${\displaystyle m=2}$ ${\displaystyle d=2.}$

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

${\displaystyle \int _{-\infty }^{\infty }\int _{-\infty }^{\infty }f_{xx}g_{xx}\,dx\,dy=\int _{-\infty }^{\infty }f_{x}g_{xx}{\big |}_{-\infty }^{\infty }\,dy-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }f_{x}g_{xxx}\,dx\,dy=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }f_{x}g_{xxx}\,dx\,dy}$

поскольку исчезает на бесконечности. Интегрирование по частям снова приводит к ${\displaystyle f_{x}g_{xx}}$ ${\textstyle \int _{-\infty }^{\infty }\int _{-\infty }^{\infty }fg_{xxxx}\,dx\,dy.}$

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

${\displaystyle \langle f,g\rangle =\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }f(g_{xxxx}+2g_{xxyy}+g_{yyyy})\,dx\,dy=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }f(\Delta ^{2}g)\,dx\,dy.}$

Поскольку ( 8 ) показывает, что ${\textstyle (\Delta ^{m}f)(\mathbf {x} )=\sum _{i=1}^{N}w_{i}C_{m,d}\delta (\mathbf {x-\mathbf {c} _{i}} ),}$

${\displaystyle {\begin{aligned}\langle f,f\rangle &=(-1)^{m}\int _{\mathbb {R} ^{d}}f(\mathbf {x} )\sum _{i=1}^{N}w_{i}(-1)^{m}C_{m,d}\delta (\mathbf {x-\mathbf {c} _{i}} )\,d\mathbf {x} =(-1)^{m}C_{m,d}\sum _{i=1}^{N}w_{i}f(\mathbf {c} _{i})\\&=(-1)^{m}C_{m,d}\sum _{i=1}^{N}\sum _{j=1}^{N}w_{i}w_{j}\varphi (\mathbf {c} _{i}-\mathbf {c} _{j})=(-1)^{m}C_{m,d}\mathbf {w} ^{\textrm {T}}A\mathbf {w} .\end{aligned}}}$

Так что если и ${\textstyle \sum w=0}$ ${\textstyle \sum w\mathbf {c} =0,}$

Теперь можно объяснить происхождение ограничений . Вот обобщение определенного выше, чтобы, возможно, включить мономы вплоть до степени Другими словами, где — вектор-столбец всех мономов степени координат Верхняя половина ( 2 ) эквивалентна Итак , чтобы получить сглаживающий сплайн, следует минимизировать скалярное поле, определяемое как ${\displaystyle B^{\textrm {T}}\mathbf {w} =0}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle m-1.}$ $${\displaystyle B={\begin{bmatrix}1&1&\dots &1\\\mathbf {c} _{1}&\mathbf {c} _{2}&\dots &\mathbf {c} _{N}\\\vdots &\vdots &\dots &\vdots \\\mathbf {c} _{1}^{m-1}&\mathbf {c} _{2}^{m-1}&\dots &\mathbf {c} _{N}^{m-1}\end{bmatrix}}^{\textrm {T}}}$$ ${\displaystyle \mathbf {c} _{i}^{j}}$ ${\displaystyle j}$ ${\displaystyle \mathbf {c} _{i}.}$ ${\displaystyle A\mathbf {w} +B\mathbf {v} -\mathbf {f} =0.}$ ${\displaystyle F:\mathbb {R} ^{N+d+1}\rightarrow \mathbb {R} }$

${\displaystyle F(\mathbf {w} ,\mathbf {v} )=|A\mathbf {w} +B\mathbf {v} -\mathbf {f} |^{2}+\lambda C\mathbf {w} ^{\textrm {T}}A\mathbf {w} .}$

Уравнения

${\displaystyle {\frac {\partial F}{\partial w_{i}}}=2A_{i*}(A\mathbf {w} +B\mathbf {v} -\mathbf {f} )+2\lambda CA_{i*}\mathbf {w} =0\quad {\textrm {for}}\ i=1,2,\ldots ,N}$

и

${\displaystyle {\frac {\partial F}{\partial v_{i}}}=2B_{i*}^{\textrm {T}}(A\mathbf {w} +B\mathbf {v} -\mathbf {f} )=0\quad {\textrm {for}}\ i=1,2,\ldots ,d+1}$

(где обозначает строку ) эквивалентны двум системам линейных уравнений и Поскольку обратимо, первая система эквивалентна. Таким образом, первая система подразумевает, что вторая система эквивалентна. Так же, как и в предыдущем выводе коэффициента сглаживающего сплайна, верхняя половина ( 2 ) становится ${\displaystyle A_{i*}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle A(A\mathbf {w} +B\mathbf {v} -\mathbf {f} +\lambda C\mathbf {w} )=0}$ ${\displaystyle B^{\textrm {T}}(A\mathbf {w} +B\mathbf {v} -\mathbf {f} )=0.}$ ${\displaystyle A}$ ${\displaystyle A\mathbf {w} +B\mathbf {v} -\mathbf {f} +\lambda C\mathbf {w} =0.}$ ${\displaystyle B^{\textrm {T}}\mathbf {w} =0.}$ ${\displaystyle (A+\lambda CI)\mathbf {w} +B\mathbf {v} =\mathbf {f} .}$

Этот вывод системы уравнений полигармонического сглаживающего сплайна не предполагал ограничений, необходимых для гарантии того, что Но ограничения, необходимые для гарантии этого, и являются подмножеством , которое верно для критической точки Поэтому верно для сформированного из решения системы уравнений полигармонического сглаживающего сплайна. Поскольку интеграл положителен для всех линейных преобразований, полученных из ограничения области линейного преобразования до такого, что должно быть положительно определенным. Этот факт позволяет преобразовать систему уравнений полигармонического сглаживающего сплайна в симметричную положительно определенную систему уравнений, которая может быть решена в два раза быстрее с помощью разложения Холецкого. ^[9] ${\textstyle \int _{{\mathcal {\mathbb {R} }}^{d}}|\nabla ^{m}f|^{2}\,d\mathbf {x} =Cw^{\textrm {T}}Aw.}$ ${\textstyle \sum w=0}$ ${\textstyle \sum w\mathbf {c} =0,}$ ${\displaystyle B^{\textrm {T}}w=0}$ ${\displaystyle w}$ ${\displaystyle F.}$ ${\textstyle \int _{{\mathcal {\mathbb {R} }}^{d}}|\nabla ^{m}f|^{2}\,d\mathbf {x} =Cw^{\textrm {T}}Aw}$ ${\displaystyle f}$ ${\displaystyle w\neq 0,}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle B^{T}w=0}$

Примеры

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

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

Следующий рисунок показывает ту же интерполяцию, что и на первом рисунке, с единственным исключением, что точки, которые должны быть интерполированы, масштабируются с коэффициентом 100 (и случай phi = r ² больше не включен). Поскольку φ = (масштаб · r ) ^k = (масштаб ^k ) · r ^k , фактор (масштаб ^k ) может быть извлечен из матрицы A системы линейных уравнений, и поэтому решение не зависит от масштабирования. Это отличается для логарифмической формы сплайна, хотя масштабирование не оказывает большого влияния. Этот анализ отражен на рисунке, где интерполяция показывает не так много различий. Обратите внимание, что для других радиальных базисных функций, таких как φ = exp(− kr ² ) с k  = 1, интерполяция больше не является разумной, и необходимо адаптировать  k .

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

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

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

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

• Обратное взвешивание расстояний
• Радиальная базисная функция
• Поверхность подразделения (новая альтернатива поверхностям на основе сплайнов)
• Сплайн

Ссылки

1. RL Harder и RN Desmarais: Интерполяция с использованием поверхностных сплайнов. Journal of Aircraft, 1972, выпуск 2, стр. 189−191
2. J. Duchon: Сплайны, минимизирующие инвариантные относительно вращения полунормы в пространствах Соболева. Конструктивная теория функций нескольких переменных, W. Schempp и K. Zeller (редакторы), Springer, Берлин, стр. 85−100
3. Вендланд, Хольгер (2005). Аппроксимация рассеянных данных . Издательство Кембриджского университета. п. 9. ISBN 0521843359.
4. GF Fasshauer GF: Методы аппроксимации без сеток с MATLAB. World Scientific Publishing Company, 2007, ISPN-10: 9812706348
5. А. Иске: Методы многомасштабного моделирования в разрозненных данных, Конспект лекций по вычислительной науке и технике, 2004, т. 37, ISBN 3-540-20479-2 , Springer-Verlag, Гейдельберг. 
6. RK Beatson, MJD Powell и AM Tan: Быстрая оценка полигармонических сплайнов в трех измерениях. Журнал численного анализа IMA, 2007, 27, стр. 427–450.
7. JB Cherrie; RK Beatson; DL Ragozin (2000), Быстрая оценка радиальных базисных функций: методы для четырехмерных полигармонических сплайнов
8. Дамиан Браун; Ливан Линг; Эдвард Канса; Джереми Левсли (2000), О методах приближенного кардинального предобуславливания для решения уравнений в частных производных с радиальными базисными функциями
9. Powell, MJD (1993). "Некоторые алгоритмы интерполяции сплайнов тонкой пластины для функций двух переменных" (PDF) . Cambridge University Dept. Of Applied Mathematics and Theoretical Physics Technical Report . Архивировано из оригинала (PDF) 2016-01-25 . Получено 7 января 2016 г.
10. Эванс, Лоуренс (1998). Уравнения с частными производными . Провиденс: Американское математическое общество. С. 450−452. ISBN 0-8218-0772-2.

Внешние ссылки

Компьютерный код

• Полигармонический сплайн, интерактивный пример с исходным кодом Matlab/Octave