Skip to content

Instantly share code, notes, and snippets.

@maccesch

maccesch/lagrange.js

Created May 27, 2011 12:27
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save maccesch/995144 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save maccesch/995144 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. maccesch revised this gist May 27, 2011. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion lagrange.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,7 @@
    /**
    * At least two points are needed to interpolate something.
    * @class Lagrange polynomial interpolation. The computed interpolation polynomial will be reffered to as L(x).
    * @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);
  2. maccesch created this gist May 27, 2011.
    77 changes: 77 additions & 0 deletions lagrange.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,77 @@
    /**
    * 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;
    }