Skip to content

Instantly share code, notes, and snippets.

@Eleobert
Created January 18, 2021 22:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Eleobert/8e3d070190c9862d2442a2f5db517bd9 to your computer and use it in GitHub Desktop.
Save Eleobert/8e3d070190c9862d2442a2f5db517bd9 to your computer and use it in GitHub Desktop.
Interpolation using Neville's Algorithm in C++
class poly
{
const std::vector<double> xs;
const std::vector<double> ys;
std::vector<double> data;
auto& qs(int i, int j){return data[i * xs.size() + j];}
public:
poly(const std::vector<double> xs, const std::vector<double> ys): xs(xs), ys(ys), data(xs.size() * xs.size())
{
assert(xs.size() == ys.size());
//std::copy(ys.begin(), ys.end(), data.begin());
for(int i = 0; i < xs.size(); i++)
{
qs(i, 0) = ys[i];
}
}
double neville(size_t i, size_t j, double x);
double operator()(double x);
};
double poly::neville(size_t i, size_t j, double x)
{
for(int i = 1; i < std::ssize(xs); i++)
{
for(int j = i; j < std::ssize(xs); j++)
{
qs(j, i) = ((x - xs[j-i]) * qs(j,i-1) - (x - xs[j]) * qs(j-1,i-1)) / (xs[j] - xs[j-i]);
}
}
return qs(xs.size() - 1, xs.size() - 1);
}
double poly::operator()(double x)
{
return neville(0, xs.size() - 1, x);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment