Created
January 18, 2021 22:40
-
-
Save Eleobert/8e3d070190c9862d2442a2f5db517bd9 to your computer and use it in GitHub Desktop.
Interpolation using Neville's Algorithm in C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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