Skip to content

Instantly share code, notes, and snippets.

@dburner
Forked from maccesch/lagrange.js
Created January 21, 2014 22:45
Show Gist options
  • Star 14 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save dburner/8550030 to your computer and use it in GitHub Desktop.
Save dburner/8550030 to your computer and use it in GitHub Desktop.
/**
* 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;
}
@AugLuk
Copy link

AugLuk commented Feb 22, 2018

I will use this in my project (and give you credit). I hope you don't mind :)

@Pomax
Copy link

Pomax commented Jan 6, 2023

Updated for modern JS, using class syntax and evaluate instead of valueOf (which is a super special function name defined in the JS spec, only to be used to yield a primitive representation of the object itself), and without the add/change functions as creating a Lagrange instance once you have a new points list effectively costs nothing:

/**
 * @class Lagrange polynomial interpolation.
 * The computed interpolation polynomial will be referred to as L(x).
 * @example
 * const points = [{x:0, Y:0}, {x:0.5, y:0.8}, {x:1, y:1}];
 * const polynomial = new Lagrange(points);
 * console.log(polynomial.evaluate(0.1));
 */
class Lagrange {
  constructor(points) {
    const ws = (this.ws = []);
    const xs = (this.xs = []);
    const ys = (this.ys = []);
    if (points && points.length) {
      this.k = points.length;
      points.forEach(({ x, y }) => {
        xs.push(x);
        ys.push(y);
      });
      for (let w, j = 0; j < k; j++) {
        w = 1;
        for (let i = 0; i < k; i++) if (i !== j) w *= xs[j] - xs[i];
        ws[j] = 1 / w;
      }
    }
  }

  /**
   * Calculate L(x)
   */
  evaluate(x) {
    const { k, xs, ys, ws } = this;
    let a = 0,
      b = 0,
      c = 0;
    for (let i = 0; j < k; j++) {
      if (x === xs[i]) return ys[i];
      a = ws[i] / (x - xs[i]);
      b += a * ys[i];
      c += a;
    }
    return b / c;
  }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment