拉格朗日插值算法及牛顿插值算法的C++实现

拉格朗日插值法

声明：本算法源自此博客：http://blog.csdn.net/xiaowei_cqu/article/details/8584966

本算法实现了批数据处理的插值实现，为上面网址博客提及的算法改良版（注：上面所述网址博客算法只能实现单个数据的插值，无法实现批数据插值）。

算法代码：

#include <iostream> #include <string> #include <vector> using namespace std; void Lagrange(int N, int N1, vector<double>&X, vector<double>&Y, vector<double>&xp, vector<double> &result); int main() { char a = 'n'; do{ cout << "请输入所需插值点N的值：" << endl; int N; int N1; cin >> N; vector<double>X(N, 0); vector<double>Y(N, 0); cout << "请输入"<<N<<"个插值点对应的值X[i]：" << endl; for (int a = 0; a<N; a++) { cin >> X[a]; if (a >= N) break; } cout << "请输入" << N << "个插值点对应的函数值Y[i]：" << endl; for (int a = 0; a<N; a++) { cin >> Y[a]; if (a >= N) break; } cout << "请输入所求xp次数N1的值：" << endl; cin >> N1; vector<double>xp(N1, 0); vector<double> result(N1, 0); cout << "请输入" << N1 << "个所求向量xp[i]的值：" << endl; for (int a = 0; a<N1; a++) { cin >> xp[a]; if (a >= N1) break; } Lagrange(N, N1, X, Y, xp, result); for (int a = 0; a < N1; a++) { cout << result[a] << endl; } cout << "是否要继续？(y/n)："; cin >> a; } while (a == 'y'); return 0; } void Lagrange(int N, int N1,vector<double>&X, vector<double>&Y, vector<double>&xp, vector<double> &result) { double temp1=0; for (int h = 0; h < N1; h++) { for (int i = 0; i < N; i++) { double temp = Y[i]; for (int j = 0; j < N; j++) { if (i != j) { temp = temp*(xp[h] - X[j]); temp = temp/(X[i] - X[j]); } } temp1 += temp; } result[h] = temp1; temp1 = 0 ; } }

牛顿插值法：

其公式：

算法流程：

算法代码：

#include<iostream> #include<string> #include<vector> using namespace std; double ChaShang(int n, vector<double>&X, vector<double>&Y); void Newton(int n1, vector<double>& xp, vector<double>&X, vector<double>&Y, vector<double> &result); int main() { char a = 'n'; do {int n,n1; cout << "请输入插值点的个数" << endl; cin >> n; vector<double>X(n, 0); vector<double>Y(n, 0); cout << "请输入插值点X[i]的值" << endl; for (int i = 0; i<n; i++) { cin >> X[i] ; } cout << "请输入插值点Y[i]的值" << endl; for (int i = 0; i<n; i++) { cin >> Y[i]; } cout << "请输入所求点的个数" << endl; cin >> n1; vector<double> xp(n1, 0); vector<double> result(n1, 0); cout << "请输入所求插值点xp[i]的值：" << endl; for (int i = 0; i<n1; i++) { cin >> xp[i]; } Newton(n1,xp, X, Y,result); cout << "输出所求插值点的函数值：" << endl; for (int h = 0; h < n1; h++) { cout<< result[h]<<endl; } cout << "是否要继续？(y/n)："; cin >> a; } while (a == 'y'); return 0; } double ChaShang(int n, vector<double>&X, vector<double>&Y) { double f = 0; double temp = 0; for (int i = 0; i<n + 1; i++) { temp = Y[i]; for (int j = 0; j<n + 1; j++) if (i != j) temp /= (X[i] - X[j]); f += temp; } return f; } void Newton(int n1, vector<double>& xp, vector<double>&X, vector<double> &Y, vector<double> &result) { double temp1 = 0; for (int h = 0; h < n1; h++) { for (int i = 0; i < X.size(); i++) { double temp = 1; double f = ChaShang(i, X, Y); for (int j = 0; j < i; j++) { temp = temp*(xp[h] - X[j]); } temp1 += f*temp; } result[h] = temp1; temp1 = 0; } }

实验结果：

给定数据值：

所求插值点及结果：

总结：本算法实现的结果与引用博客的算法结果完全一致。