|
Интерполяция сплайнами третьего порядка - это быстрый, эффективный и устойчивый способ интерполяции функций. Наравне с рациональной интерполяцией, сплайн-интерполяция является одной из альтернатив полиномиальной интерполяции.
В основе сплайн-интерполяции лежит следующий принцип. Интервал интерполяции разбивается на небольшие отрезки, на каждом из которых функция задается полиномом третьей степени. Коэффициенты полинома подбираются таким образом, чтобы выполнялись определенные условия (какие именно, зависит от способа интерполяции). Общие для всех типов сплайнов третьего порядка требования - непрерывность функции и, разумеется, прохождение через предписанные ей точки. Дополнительными требованиями могут быть линейность функции между узлами, непрерывность высших производных и т.д.
Основными достоинствами сплайн-интерполяции являются её устойчивость и малая трудоемкость. Системы линейных уравнений, которые требуется решать для построения сплайнов, очень хорошо обусловлены, что позволяет получать коэффициенты полиномов с высокой точностью. В результате даже про очень больших N вычислительная схема не теряет устойчивость. Построение таблицы коэффициентов сплайна требует O(N) операций, а вычисление значения сплайна в заданной точке - всего лишь O(log(N)).
Линейный сплайн - это сплайн, составленный из полиномов первой степени, т.е. из отрезков прямых линий. Точность интерполяции линейными сплайнами невысока, также следует отметить, что они не обеспечивают непрерывности даже первых производных. Однако в некоторых случаях кусочно-линейная аппроксимация функции может оказаться предпочтительнее, чем аппроксимация более высокого порядка. Например, линейный сплайн сохраняет монотонность переданного в него набора точек.
Сплайн Эрмита - это сплайн третьего порядка, производная которого принимает в узлах сплайна заданные значения. В каждом узле сплайна Эрмита задано не только значение функции, но и значение её первой производной. Сплайн Эрмита имеет непрерывную первую производную, но вторая производная у него разрывна. Точность интерполяции значительно лучше, чем у линейного сплайна.
Все сплайны, рассмотренные на этой странице, являются кубическими сплайнами - в том смысле, что они являются кусочно-кубическими функциями. Однако, когда говорят "кубический сплайн", то обычно имеют в виду конкретный вид кубического сплайна, который получается, если потребовать непрерывности первой и второй производных. Кубический сплайн задается значениями функции в узлах и значениями производных на границе отрезка интерполяции (либо первых, либо вторых производных).
Если известно точное значение первой производной на обеих границах, то такой сплайн называют фундаментальным. Погрешность интерполяции таким сплайном равна O(h 4). Если значение первой (или второй) производной на границе неизвестно, то можно задать т.н. естественные граничные условия S''(A)=0, S''(B)=0, и получить естественный сплайн. Погрешность интерполяции естественным сплайном составляет O(h 2). Максимум погрешности наблюдается в окрестностях граничных узлов, во внутренних узлах точность интерполяции значительно выше. Ещё одним видом граничного условия, которое можно использовать, если неизвестны граничные производные функции, является условие типа "сплайн, завершающийся параболой". В этом случае граничный отрезок сплайна представляется полиномом второй степени вместо третьей (для внутренних отрезков по-прежнему используются полиномы третьей степени). В ряде случаев это обеспечивает большую точность, чем естественные граничные условия. Наконец, можно сочетать различные типы граничных условий на разных границах. Обычно так имеет смысл делать, если у нас есть только часть информации о поведении функции на границе (например, производная на левой границе - и никакой информации о производной на правой границе).
Сплайн Акимы - это особый вид сплайна, устойчивый к выбросам. Недостатком кубических сплайнов является то, что они склонны осциллировать в окрестностях точки, существенно отличающейся от своих соседей. На графике приведен набор точек, содержащий один выброс. Зеленым цветом обозначен кубический сплайн с естественными граничными условиями. На отрезках интерполяции, граничащих с выбросом, сплайн заметно отклоняется от интерполируемой функции - сказывается влияние выброса. Красным цветом обозначен сплайн Акимы. Можно видеть, что, в отличие от кубического сплайна, сплайн Акимы в меньшей мере подвержен влиянию выбросов - на отрезках, граничащих с выбросом, практически отсутствуют признаки осцилляции.
Важным свойством сплайна Акимы является его локальность - значения функции на отрезке [xi , xi+1 ] зависят только от fi-2 , fi-1 , fi , fi+1 , fi+2 , fi+3 . Вторым свойством, которое следует принимать во внимание, является нелинейность интерполяции сплайнами Акимы - результат интерполяции суммы двух функций не равен сумме интерполяционных схем, построенных на основе отдельных функций. Для построения сплайна Акимы требуется не менее 5 точек. Во внутренней области (т.е. между x2 и xN-3 при нумерации точек от 0 до N-1) погрешность интерполяции имеет порядок O(h 2).
Работа с кубическими сплайнами в ALGLIB осуществляется в два этапа:
Для решения задачи интерполяции, т.е. построения сплайна, который проходит через все предписанные точки, можно использовать следующие подпрограммы:
Регрессионный сплайн - это сплайн, построенный на основе сокращенного набора из M узлов, использующийся для аппроксимации набора из N точек (N может быть существенно больше M). Результат такой аппроксимации сильно зависит от используемого набора узлов. В пакете ALGLIB используется простая, но эффективная стратегия выбора узлов: интервал, на котором располагаются данные, разбивается на M-1 равный отрезок, полученная сетка используется для построения базисных функций. Регрессионные сплайны позволяют осуществлять аппроксимацию без ограничений, либо с ограничениями на функцию и её производные.
Замечание #1
Следует учитывать, что избыточные ограничения могут оказаться несовместимы. Более подробно этот вопрос рассмотрен в комментариях к подпрограммам Spline1DFitCubicWC и Spline1DFitHermiteWC.
Для построения регрессионного сплайна можно использовать следующие подпрограммы:
Для вычисления значения сплайна в заданной точке служат подпрограммы Spline1DCalc (вычисление значения сплайна) и Spline1DDiff (вычисление значения сплайна, первой и второй производных). Подпрограмма Spline1DIntegrate позволяет проинтегрировать сплайн. Подпрограммы Spline1DLinTransX и Spline1DLinTransY служат для линейной замены аргумента и линейного преобразования сплайна в целом.
Прочие операции включают в себя копирование (подпрограмма Spline1DCopy), сериализацию/десериализацию (подпрограммы Spline1DSerialize/Spline1DUnserialize), доступ к таблице коэффициентов (подпрограмма Spline1DUnpack).
| C++ | spline1d.h | |
| C# | spline1d.cs | |
| MPFR | spline1d.h | |
| Delphi | spline1d.pas | |
| FreePascal | spline1d.pas | |
| VBA | spline1d.bas |
This article is intended for personal use only.
Исходный код на C#
Исходный код на C++
Исходный код на C++, использующий библиотеки MPFR/GMP.
Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.
Исходный код на Free Pascal.
Исходный код на Delphi.
Исходный код на VBA.
|
ALGLIB project, 1999-2010 |