Skip to content

Instantly share code, notes, and snippets.

@maccesch
Created May 27, 2011 12:27
Show Gist options
  • Save maccesch/995144 to your computer and use it in GitHub Desktop.
Save maccesch/995144 to your computer and use it in GitHub Desktop.
Lagrange Polynomial Interpolation. Example: http://jsfiddle.net/maccesch/jgU3Y/
/**
* At least two points are needed to interpolate something.
* @class Lagrange polynomial interpolation.
* The computed interpolation polynomial will be reffered to as L(x).
* @example
* var l = new Lagrange(0, 0, 1, 1);
* var index = l.addPoint(0.5, 0.8);
* console.log(l.valueOf(0.1));
*
* l.changePoint(index, 0.5, 0.1);
* console.log(l.valueOf(0.1));
*/
var Lagrange = function(x1, y1, x2, y2) {
this.xs = [x1, x2];
this.ys = [y1, y2];
this.ws = [];
this._updateWeights();
}
/**
* Adds a new point to the polynomial. L(x) = y
* @return {Number} The index of the added point. Used for changing the point. See changePoint.
*/
Lagrange.prototype.addPoint = function(x, y) {
this.xs.push(x);
this.ys.push(y);
this._updateWeights();
return this.xs.length-1;
}
/**
* Changes a previously added point.
*/
Lagrange.prototype.changePoint = function(index, x, y) {
this.xs[index] = x;
this.ys[index] = y;
this._updateWeights();
}
/**
* Recalculate barycentric weights.
*/
Lagrange.prototype._updateWeights = function() {
var k = this.xs.length;
var w;
for (var j = 0; j < k; ++j) {
w = 1;
for (var i = 0; i < k; ++i) {
if (i != j) {
w *= this.xs[j] - this.xs[i];
}
}
this.ws[j] = 1/w;
}
}
/**
* Calculate L(x)
*/
Lagrange.prototype.valueOf = function(x) {
var a = 0;
var b = 0;
var c = 0;
for (var j = 0; j < this.xs.length; ++j) {
if (x != this.xs[j]) {
a = this.ws[j] / (x - this.xs[j]);
b += a * this.ys[j];
c += a;
} else {
return this.ys[j];
}
}
return b / c;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment