lagrangePoly function

List<double> lagrangePoly(List<({double x, double y})> table)

Returns interpolating polynomial coefficients using Lagrange's formula.

The returned list can be evaluated with horner.

Implementation

List<double> lagrangePoly(List<({double x, double y})> table) {
  final n = table.length;
  final sum = List<double>.filled(n, 0);
  final prod = List<double>.filled(n, 0);
  final last = n - 1;
  for (var i = 0; i < n; i++) {
    final xi = table[i].x;
    final yi = table[i].y;
    prod[last] = 1;
    var den = 1.0;
    var idx = last;
    for (var j = 0; j < n; j++) {
      if (i != j) {
        final xj = table[j].x;
        prod[idx - 1] = prod[idx] * -xj;
        for (var k = idx; k < last; k++) {
          prod[k] -= prod[k + 1] * xj;
        }
        idx--;
        den *= (xi - xj);
      }
    }
    for (var j = 0; j < n; j++) {
      sum[j] += yi * prod[j] / den;
    }
  }
  return sum;
}