Интерполяция сплайнами

Интерполяция  сплайнами

Интерполяция  сплайнами третьего порядка - это  быстрый, эффективный и устойчивый способ интерполяции функций. Наравне  с рациональной интерполяцией, сплайн-интерполяция является одной из альтернатив полиномиальной интерполяции.

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

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

Типы сплайнов

Линейный сплайн

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

Сплайн Эрмита

Сплайн Эрмита - это сплайн третьего порядка, производная  которого принимает в узлах сплайна  заданные значения. В каждом узле сплайна Эрмита задано не только значение функции, но и значение её первой производной. Сплайн Эрмита имеет непрерывную первую производную, но вторая производная у него разрывна. Точность интерполяции значительно лучше, чем у линейного сплайна.

Сплайн Катмулла-Рома

Сплайн Катмулла-Рома - это сплайн Эрмита, производные  которого определяются по формуле:

Как и сплайн Эрмита, сплайн Катмулла-Рома имеет непрерывную  первую производную и разрывную  вторую. Сплайн Катмулла-Рома локален - значения сплайна зависят только от значений функции в четырех соседних точках (двух слева, двух справа). Можно использовать два типа граничных условий:

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

Кубический сплайн

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

• Если известно точное значение первой производной на обеих границах, то такой сплайн называют фундаментальным. Погрешность интерполяции таким сплайном равна O(h ⁴).
• Если значение первой (или второй) производной на границе неизвестно, то можно задать т.н. естественные граничные условия S''(A)=0, S''(B)=0, и получить естественный сплайн. Погрешность интерполяции естественным сплайном составляет O(h ²). Максимум погрешности наблюдается в окрестностях граничных узлов, во внутренних узлах точность интерполяции значительно выше.
• Ещё одним видом граничного условия, которое можно использовать, если неизвестны граничные производные функции, является условие типа "сплайн, завершающийся параболой". В этом случае граничный отрезок сплайна представляется полиномом второй степени вместо третьей (для внутренних отрезков по-прежнему используются полиномы третьей степени). В ряде случаев это обеспечивает большую точность, чем естественные граничные условия.
• Можно указать периодические граничные условие (этот вид граничных условий используется при моделировании периодических функций).

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

Сплайн Акимы

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

Важным свойством сплайна Акимы является его локальность - значения функции на отрезке [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 ²).