Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Интерполяция/аппроксимация по обратному средневзвешенному расстоянию

Inverse distance weighting - это способ многомерной интерполяции на нерегулярной сетке. Существует много вариаций метода, отличающихся как концептуальными, так и техническими аспектами. В пакете ALGLIB реализован локальный вариант метода, генерирующий C1-непрерывные интерполянты и обладающий умеренной трудоемкостью (O(N·logN) - время построения модели, O(logN) - время интерполяции).

Содержание

    1 Простейший алгоритм
    2 Модифицированный метод Шепарда: интерполяция на неравномерной сетке
    3 Модифицированный метод Шепарда: аппроксимация на неравномерной сетке
    4 Настройка алгоритма: выбор Nw и Nq
    5 Настройка алгоритма: выбор узловых функций
    6 Manual entries

Простейший алгоритм

Рассмотрим простейший вариант IDW-алгоритма, перед тем, как перейти к более сложному алгоритму, входящему в состав ALGLIB. Пусть x - это набор точек в пространстве размерности D, а y - значения функции в этих точках. Тогда IDW-интерполянт имеет вид:

В такой формулировке алгоритм обладает как достоинствами, так и недостатками. Достоинствами являются:

Однако недостатки алгоритма очень серьезны:

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

Модифицированный метод Шепарда: интерполяция на неравномерной сетке

В пакете ALGLIB реализована более утонченная версия алгоритма, являющаяся незначительной модификацией модифицированного метода Шепарда, предложенного Robert J. Renka ('Multivariate Interpolation of Large Sets of Scattered Data', 1988). Модифицированный интерполянт имеет вид:

Модифицированный метод Шепарда отличается от оригинального алгоритма тем, что:

Основными достоинствами модифицированного алгоритма являются:

Можно отметить следующие недостатки алгоритма:

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

Модифицированный метод Шепарда: аппроксимация на неравномерной сетке

Алгоритм естественным образом модифицируется для работы с зашумленными данными: достаточно лишь незначительно модифицировать задачу МНК, решением которой является узловая функция Q(x). Во-первых, исчезает ограничение Q(x)=y. Во-вторых, весовые коэффициенты, использующиеся для вычисления Q(x), полагаются равными 1. Таким образом, функция Q(x) в некотором смысле усредняет соседние с xi точки.

Замечание #1
Сами формулы (1), (2) и (3) остаются прежними. Все изменения относятся лишь к тому, как вычисляются коэффициенты A, b и c в формуле (3).

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

Настройка алгоритма: выбор Nw и Nq

Параметры N и N отвечают за количество узлов, использующихся на стадии интерполяции (параметр N) и на стадии построения узловых функций (параметр N):

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

Настройка алгоритма: выбор узловых функций

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

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

Manual entries

C++ idwint subpackage   
C# idwint subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.