C中的算法使用拉格朗日插值计算多项式的系数

Question

我一直坚持这一段时间了。我正在用C编写一个算法，用拉格朗日插值法提取多项式的系数。

我的代码部分的工作，例如，如果我们做的第一个例子这里http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_1然后代码可以打印出第2个系数（0和4.834848）

同样有例如3这篇文章中，将打印2个系数6和-11。

我需要能够准确地获得任何一组点的所有系数。请告知代码所需的更改。

在此先感谢！

已更新为最新的代码，7:57 PM，GMT于8月5日。现在9个系数正在工作，看起来很丑。将调查明天n度的迭代过程！

#include<ncursesw/ncurses.h> 
#include<math.h> 
#include <stdio.h> 
#include <string.h> 
#include <errno.h> 
#include <stdlib.h> 
#define MAX 200 
float coeff[MAX], coefftwo[MAX], coeffthree[MAX], coefffour[MAX]; 
int count; 
void main() 
{ 
int n,i,j ; 
char ch; 
float x[MAX],y[MAX],fp2, coeff1, coeff2; 
printf("\n\nn = "); 
scanf("%i", &count); 

    for(i=0; i < count; i++) 
    { 
     printf("\n\n The value of x%i= ", i); 
     scanf("%f",&x[i]); 
     printf("\n The value of f(x%i)= ", i); 
     scanf("%f",&y[i]); 
    } 
    for(i=0;i<count;i++) 
    { 
     coeff1 = 1.0; 
     coeff2 = 0.0; 
     coeff3 = 0.0; 
     coeff4 = 0.0; 
     coeff5 = 0.0; 
     coeff6 = 0.0; 
     coeff7 = 0.0; 
     coeff8 = 0.0; 
     coeff9 = 0.0; 
     for(j=0; j<count; j++) 
     { 
      if(i!=j) { 
       coeff1 = coeff1 * (array[i]-array[j]); 
       coeff2 -= array[j]; 
       for (int k=j; k < count; k++) { 
       if ((j!=k) && (k!=i)) { 
       coeff3 += array[j] * array[k]; 
        for(int l=k; l < count; l++) { 
        if ((l!=j) && (l!=k) && (l!=i))  { 
    coeff4 -= array[j] * array[k] * array[l]; 

    for (int m = l; m < count; m++) { 
     if ((m!=l) && (m!=k) && (m!=j) && (m!=i)) {     coeff5 += array[j] * array[k] * array[l] * array[m]; 
      for (int n = m; n < count; n++) { 
      if ((n!=m) && (n!=l) && (n!=k) && (n!=j) && (n!=i)) { 
      coeff6 -= array[j] * array[k] * array[l] * array[m] * array[n]; 
      for (int o = n; o < count; o++) { 
      if ((o!=n) && (o!=m) && (o!=l) && (o!=k) && (o!=j) && (o!=i)) { 
      coeff7 += array[j] * array[k] * array[l] * array[m] * array[n] * array[o]; 
      for (int p = o; p < count; p++) { 
      if ((p!=o) && (p!=n) && (p!=m) && (p!=l) && (p!=k) && (p!=j) && (p!=i)) { 
      coeff8 -= array[j] * array[k] * array[l] *array[m] *array[n] * array[o] * array[p]; 
      for (int q = p; q < count; q++) { 
      if ((q!=p) && (q!=o) && (q!=n) && (q!=m) && (q!=l) && (q!=k) && (q!=j) && (q!=i)) { 
      coeff9 += array[j] * array[k] * array[l] * array[m] * array[n] * array[o] * array[p] * array[q]; 
      } 
      } 
      } 
      } 
      } 
      } 
      } 
      } 
        }    
     } 
        } 
       } 
      } 
     }  
    } 
}  
     coeff[i] = y[i]/coeff1; 
     coefftwo[i] = y[i] * coeff2/coeff1; 
     coeffthree[i] = y[i] * coeff3/coeff1; 
     coefffour[i] = y[i] * coeff4/coeff1; 
     coefffive[i] = y[i] * coeff5/coeff1; 
     coeffsix[i] = y[i] * coeff6/coeff1; 
     coeffseven[i] = y[i] * coeff7/coeff1; 
     coeffeight[i] = y[i] * coeff8/coeff1; 
     coeffnine[i] = y[i] * coeff9/coeff1; 
    } 
float coefficientone = 0.0; 
float coefficienttwo = 0.0; 
float coefficientthree = 0.0; 
float coefficientfour = 0.0; 
float coefficientfive = 0.0; 
float coefficientsix = 0.0; 
float coefficientseven = 0.0; 
float coefficienteight = 0.0; 
float coefficientnine = 0.0; 
for (int i = 0; i< count; i++){ 
     coefficientone = coefficientone + coeff[i]; 
     coefficienttwo = coefficienttwo + coefftwo[i]; 
     coefficientthree = coefficientthree + coeffthree[i]; 
     coefficientfour = coefficientfour + coefffour[i]; 
     coefficientfive = coefficientfive + coefffive[i]; 
     coefficientsix = coefficientsix + coeffsix[i]; 
     coefficientseven = coefficientseven + coeffseven[i]; 
     coefficienteight = coefficienteight + coeffeight[i]; 
     coefficientnine = coefficientnine + coeffnine[i]; 
} 
printf("coefficient 1 = %f\n", coefficientone); 
printf("coefficient 2 = %f\n", coefficienttwo); 
printf("coefficient 3 = %f\n", coefficientthree); 
printf("coefficient 4 = %f\n", coefficientfour); 
printf("coefficient 5 = %f\n", coefficientfive); 
printf("coefficient 6 = %f\n", coefficientsix); 
printf("coefficient 7 = %f\n", coefficientseven); 
printf("coefficient 8 = %f\n", coefficienteight); 
printf("coefficient 9 = %f\n", coefficientnine); 

}

Answer 1

你的代数是完全错误的，而实际上是通过选择不当的变量名是隐藏的。

当你计算我^个基础多项式的贡献（别提y现在）什么变量表示X项的系数？这是coeff3。而且你没有正确计算它。

举一个更简单的例子。假设你想要求出（x + a）（x + b）（x + c）（x + d）。第一项是x ，简单。接下来是（a + b + c + d）x ，不算太坏。接下来是（ab + ac + ad + bc + bd + cd）x ，现在很明显，单个循环将无法完成这项工作。 在尝试更复杂的问题之前，花时间确保您可以编写正确处理简单问题的代码。你需要像这样：

for(unsigned int j=0 ; j<count ; ++j) 
{ 
    ... 
    coeff2 -= x[j]; 
    for(unsigned int k=j ; k<count ; ++k) 
    { 
    if(j!=k && k!=i) 
     coeff3 += x[j] * x[k]; 
    ... 
    } 
} 

这应该足以让你开始。