Краткий обзор алгоритмов интерполяции

В современных программных продуктах реализовано множество методов интерполяции — рассмотрим известные алгоритмы, чтобы лучше в них разобраться.

Решить задачу интерполяции — означает найти значение наблюдаемой величины в неизмеренной точке Х на основе имеющихся данных:

Методы интерполяции можно разделить на два типа:

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

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

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

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

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

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

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

В отличии от метода ОВР, с помощью РБФ можно рассчитывать значения выше максимальных и ниже минимальных известных значений, что позволяет создавать слабо меняющиеся поверхности: например, поверхность высот.

Интерполяция является частью геостатистики. Геостатистика — это раздел статистики, который занимается анализом и прогнозом значений, связанных с пространственными и пространственно-временными явлениями.

Геостатистический метод применяется в различных сферах, позволяя моделировать распределение объектов, явлений и процессов в пространстве — начиная с оценки нефтегазового потенциала и заканчивая анализом загрязнения окружающей среды в рамках поиска взаимосвязи между заболеванием и определенными факторами.

Таким геостатистическим методом интерполяции является кригинг — многоэтапный процесс, который позволяет наиболее достоверно отобразить моделируемую поверхность при условии наличия пространственной корреляции. При кригинге решается две задачи: определение пространственной структуры данных и создание прогноза.

Случайная величина — значение, которое может принимать результат случайного события.

Математическое ожидание — среднее значение случайной величины, ожидаемое значение при многократном повторении эксперимента.

Дисперсия — мера разброса значений случайной величины относительно ее математического ожидания.

Вариограмма — график, который показывает, как распределена дисперсия значений некоторой случайной величины в зависимости от расстояния между соответствующими наблюдаемыми точками.

Ковариация — мера зависимости двух случайных величин; демонстрирует степень линейной зависимости этих величин друг от друга.

Вариограммы позволяют пользователям подобрать к данным модель пространственной зависимости. Для описания поведения вариограммы используются следующие характеристики:

Диапазон (sill) — это расстояние, на котором вариограмма достигает своего насыщения и перестает изменяться. Если вариограмма насыщается быстро, это говорит о том, что значения случайной величины в этой области примерно одинаковы. Если вариограмма насыщается медленно, то значения случайной величины в этой области значительно меняются.

Порог (range) — расстояние, на котором вариограмма начинает увеличиваться быстрее. Он позволяет определить, на каком расстоянии объекты перестают влиять друг на друга.

Эффект самородка (nugget) — это особенность вариограммы, которая проявляется как "пик" на графике на малых расстояниях между точками измерения. Происхождение эффекта связано с тем, что при малых расстояниях между объектами значение аналогичных объектов может оказаться очень близко друг к другу, что приводит к тому, что показания вариограммы на этом участке резко увеличиваются.

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

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

Как уже описывалось ранее, методы интерполяции призваны рассчитать значения в тех местах, где измерения отсутствуют, что очень удобно, например, для построения цифровых моделей рельефа. При помощи методов интерполяции можно также создавать тематические карты: например, прогнозные карты радиационного заражения или же карты распространения загрязняющих веществ.