neville interpolation

neville.cc

// neville interpolation based on code by Behzad Torkian 
// - rlyeh, public domain

/*
There is a distinction between interpolation and curve fitting.In interpolation we construct
a curve through the data points.In doing so, we make the implicit assumption that the data
points are accurate and distinct. Curve fitting is applied to data that contain scatter(noise),
usually due to measurement errors. Here we want to find a smooth curve that approximates the data
in some sense. Thus the curve does not have to hit the data points. This difference between
interpolation and curve fitting is illustrated in Fig. 3.1.

y
|                     ..p..    *    [p] data points
|       .p.         ..  *  ..       [.] interpolated points
|     ...  ...   *...        .p.    [*] curve fitting 
|   ...    *  ..p..
| .. * 
|p_____________________________ x

// see also:
// 1. linear interpolation
// 2. polynomial interpolation
//    2.1 newton interpolation
//    2.2 neville interpolation
//    2.3 spline interpolation
// 3. least squares interpolation
//    3.1 least squares straight line approximation
//    3.2 least squares polynomial approximation
*/

#include <vector>

struct point {
    double x, y;
};

double neville_interpolation( std::vector<point> pt, const double t ) {
    const int n = pt.size();
    double total;
    for( int j = 1; j < n; j++ ) {
        for( int i = n-1; i >= j; i-- ) {
            pt[ i ].y = ( (t - pt[i-j].x )* pt[i].y - ( t - pt[i].x ) * pt[i-1].y ) / ( pt[i].x - pt[i-j].x );
        }
    }
    total = pt[n-1].y;  
    return ( total );
}

#include <iostream>

int main() {
    std::vector<point> points { {1,1},{2,4},{3,9},{4,4},{5,1} };
    std::cout << neville_interpolation( points, 1.5 ) << std::endl;
    std::cout << neville_interpolation( points, 2.5 ) << std::endl;
    std::cout << neville_interpolation( points, 3.5 ) << std::endl;
    std::cout << neville_interpolation( points, 4.5 ) << std::endl;
}