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

這應該足以讓你開始。