好吧，你可以用天真的方式来做。通过其系数的数组表示多项式，数组
[a_0,a_1,...,a_n]
对应a_0 + a_1*X + ... + a_n*X^n。我不擅长 JavaScript，所以伪代码必须这样做：
interpolation_polynomial(i,points)
coefficients = [1/denominator(i,points)]
for k = 0 to points.length-1
if k == i
next k
new_coefficients = [0,0,...,0] // length k+2 if k < i, k+1 if k > i
if k < i
m = k
else
m = k-1
for j = m downto 0
new_coefficients[j+1] += coefficients[j]
new_coefficients[j] -= points[k]*coefficients[j]
coefficients = new_coefficients
return coefficients
从常数多项式开始，1/((x_1-x_0)* ... *(x_i-x_{i-1})*(x_i-x_{i+1})*...*(x_i-x_n))然后乘以X - x_kfor all k != i。这样就给出了 L i的系数，然后你只需将它们与 y i相乘（如果你将 y 值作为参数传递，你可以通过初始化coefficients来做到这一点y_i/denominator(i,points)），最后将所有系数相加。
polynomial = [0,0,...,0] // points.length entries
for i = 0 to points.length-1
coefficients = interpolation_polynomial(i,points)
for k = 0 to points.length-1
polynomial[k] += y[i]*coefficients[k]
计算每个L i是O(n²)，所以总计算量是O(n³)。
更新：在您的 jsFiddle 中，除了我所做的起始索引（现在已更正）错误之外，您在多项式乘法循环中还有一个错误，它应该是
for (var j= (k < i) ? (k+1) : k; j--;) {
new_coefficients[j+1] += coefficients[j];
new_coefficients[j] -= points[k].x*coefficients[j];
}
由于您在测试时递减j，因此需要从高一开始。
这还不能产生正确的插值，但至少比以前更明智。
此外，在您的horner功能中，
function horner(array, x_scale, y_scale) {
function recur(x, i, array) {
if (i == 0) {
return x*array[0];
} else {
return array[i] + x*recur(x, --i, array);
}
}
return function(x) {
return recur(x*x_scale, array.length-1, array)*y_scale;
};
}
您将最高系数乘以 两次x，它应该是
if (i == 0) {
return array[0];
}
反而。不过还是没有好结果。
更新 2：最终的错字修复，以下工作：
function horner(array, x_scale, y_scale) {
function recur(x, i, array) {
if (i == 0) {
return array[0];
} else {
return array[i] + x*recur(x, --i, array);
}
}
return function(x) {
return recur(x*x_scale, array.length-1, array)*y_scale;
};
}
// initialize array
function zeros(n) {
var array = new Array(n);
for (var i=n; i--;) {
array[i] = 0;
}
return array;
}
function denominator(i, points) {
var result = 1;
var x_i = points[i].x;
for (var j=points.length; j--;) {
if (i != j) {
result *= x_i - points[j].x;
}
}
console.log(result);
return result;
}
// calculate coefficients for Li polynomial
function interpolation_polynomial(i, points) {
var coefficients = zeros(points.length);
// alert("Denominator " + i + ": " + denominator(i,points));
coefficients[0] = 1/denominator(i,points);
console.log(coefficients[0]);
//new Array(points.length);
/*for (var s=points.length; s--;) {
coefficients[s] = 1/denominator(i,points);
}*/
var new_coefficients;
for (var k = 0; k<points.length; k++) {
if (k == i) {
continue;
}
new_coefficients = zeros(points.length);
for (var j= (k < i) ? k+1 : k; j--;) {
new_coefficients[j+1] += coefficients[j];
new_coefficients[j] -= points[k].x*coefficients[j];
}
coefficients = new_coefficients;
}
console.log(coefficients);
return coefficients;
}
// calculate coefficients of polynomial
function Lagrange(points) {
var polynomial = zeros(points.length);
var coefficients;
for (var i=0; i<points.length; ++i) {
coefficients = interpolation_polynomial(i, points);
//console.log(coefficients);
for (var k=0; k<points.length; ++k) {
// console.log(points[k].y*coefficients[k]);
polynomial[k] += points[i].y*coefficients[k];
}
}
return polynomial;
}
