OBSOLETE: inverse distance weighting interpolation/fitting

Inverse distance weighting is a scattered data interpolation algorithm. There exists several variations of the algorithms, different both in conceptual and implementation aspects. ALGLIB package contains local version of inverse distance weighting algorithm, which generates C1-continuous interpolant and have O(N·logN) construction complexity and O(logN) interpolation complexity.

IMPORTANT: this algorithm is considered obsolete and was superseded by improved RBF models. Although it is still supported because of backward compatibility, we recommend you to use ALGLIB implementation of RBFs for scattered interpolation/fitting.

Contents

    1 Inverse distance weighting: Shepard's method
    2 Modified Shepard's method: scattered data interpolation
    3 Modified Shepard's method: scattered data fitting
    4 Tuning: Nw and Nq
    5 Tuning: nodal functions
    6 Downloads section

Inverse distance weighting: Shepard's method

Consider the simplest form of inverse distance weighting interpolation before proceeding to a more complex algorithm implemented in the ALGLIB. Let x are points in D dimensional space, let y are function values at x. Then Shepard interpolant have following form:

Such algorithm have both benefits and drawbacks. Its benefits are:

However, it has a number of important drawbacks:

For these reasons original Shepard's method is rarely used in practice.

Modified Shepard's method: scattered data interpolation

ALGLIB package contains more advanced version of inverse distance weighting interpolation algorithm - modified Shepard's method, first proposed by Robert J. Renka ('Multivariate Interpolation of Large Sets of Scattered Data', 1988). Modified interpolant have following form:

Modified Shepard's method differs from original algorithm in the following aspects:

Main benefits of modified algorithm are:

However, several drawbacks may be noted too:

However, these drawbacks did not outweigh the benefits of modified Shepard's algorithm, so we can recommend it as a standard tool for multidimensional interpolation (either scattered or regular).

Modified Shepard's method: scattered data fitting

Modified Shepard's method can be slightly modified to fit noisy data. The only modification is just calculation of Q(x). First, constraint Q(x)=y is removed; thus f(x) ≠ y. Second, an equal weight is assigned to all points used to fit Q(x).

Note #1
(1), (2) and (3) are left unchanged. All modifications are related to calculation of A, b and c from (3).

This algorithm should be applied only to noisy tasks. In absence of noise it have no benefits over interpolation algorithm.

Tuning: Nw and Nq

N and N parameters control number of nodes used during nodal functions construction (N parameter) and interpolation (N parameter):

Situation is somewhat different with fitting tasks. Meaning of N is still the same, but N now have two meanings: it controls both algorithm locality and noise suppression. N noisy points are combined to get noise-free picture, so the larger level of noise is, the larger N is needed.

Tuning: nodal functions

User can choose between four types of nodal functions:

As for fitting problems, user can choose between only two types of nodal functions: linear and quadratic. Quadratic nodal function is still best choice - as long as you have enough data to fight with the noise. If noise level is too high, or data are too sparse, linear nodal function may be better option.

This article is licensed for personal use only.

Download ALGLIB for C++ / C# / ...

ALGLIB Project offers you two editions of ALGLIB:

ALGLIB Free Edition:
delivered for free
offers full set of numerical functionality
extensive algorithmic optimizations
no low level optimizations
non-commercial license

ALGLIB Commercial Edition:
flexible pricing
offers full set of numerical functionality
extensive algorithmic optimizations
high performance (SMP, SIMD)
commercial license with support plan

Links to download sections for Free and Commercial editions can be found below:

ALGLIB 3.12.0 for C++

C++ library.
Delivered with sources.
Monolithic design.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for C#

C# library with native kernels.
Delivered with sources.
VB.NET and IronPython wrappers.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for Delphi

Delphi wrapper around C core.
Delivered as precompiled binary.
Compatible with FreePascal.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for CPython

CPython wrapper around C core.
Delivered as precompiled binary.
Editions:   FREE   COMMERCIAL