如何使用拉格朗日插值计算多项式的系数

Question

我需要使用 Lagrange interpolation polynomial 计算多项式的系数，作为我的家庭作业，我决定在 Javascript 中执行此操作。

这是拉格朗日多项式 (L(x)) 的定义

拉格朗日基多项式定义如下

计算特定 X 的 y 值（W(x) 函数）很简单，但我需要计算多项式的系数（[a0, a1, …, an] 的数组）我需要对 n<=10 执行此操作，但它拥有任意 n 会很好，然后我可以将该函数放入 horner 函数并绘制该多项式。

我有计算第一个方程式中分母的函数

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;
      }
   }
   return result;
}

和使用 horner 方法返回 y 的函数（我也有使用画布的绘图函数）

 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;
   };
}

任何人都知道这样做的算法，或者知道如何计算这些系数

原文由 jcubic 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

好吧，你可以用天真的方法来做。用系数数组表示多项式，数组

[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_k 对所有 k != i 。这样就给出了 L i的系数，然后你只需将它们与 y i相乘（你可以通过将 coefficients 初始化为 y_i/denominator(i,points) 如果你将 y 值作为参数传递）和最后将所有系数加在一起。

 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];
}

反而。不过还是没有好结果。

Update2： 最终错字修复，以下工作：

 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;
}

原文由 Daniel Fischer 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

此代码将确定以常数项开头的系数。

 var xPoints=[2,4,3,6,7,10]; //example coordinates
var yPoints=[2,5,-2,0,2,8];
var coefficients=[];
for (var m=0; m<xPoints.length; m++) coefficients[m]=0;
    for (var m=0; m<xPoints.length; m++) {
        var newCoefficients=[];
        for (var nc=0; nc<xPoints.length; nc++) newCoefficients[nc]=0;
        if (m>0) {
            newCoefficients[0]=-xPoints[0]/(xPoints[m]-xPoints[0]);
            newCoefficients[1]=1/(xPoints[m]-xPoints[0]);
    } else {
        newCoefficients[0]=-xPoints[1]/(xPoints[m]-xPoints[1]);
        newCoefficients[1]=1/(xPoints[m]-xPoints[1]);
    }
    var startIndex=1;
    if (m==0) startIndex=2;
    for (var n=startIndex; n<xPoints.length; n++) {
        if (m==n) continue;
        for (var nc=xPoints.length-1; nc>=1; nc--) {
            newCoefficients[nc]=newCoefficients[nc]*(-xPoints[n]/(xPoints[m]-xPoints[n]))+newCoefficients[nc-1]/(xPoints[m]-xPoints[n]);
        }
        newCoefficients[0]=newCoefficients[0]*(-xPoints[n]/(xPoints[m]-xPoints[n]));
    }
    for (var nc=0; nc<xPoints.length; nc++) coefficients[nc]+=yPoints[m]*newCoefficients[nc];
}

原文由 Kevin Bertman 发布，翻译遵循 CC BY-SA 4.0 许可协议