### Lagrange与Newton插值——计算机专业数值分析实验
#### 实验目的
本实验旨在让学生掌握两种常用的插值方法——Lagrange插值法和Newton插值法，并能够通过编程实现这两种方法。具体目标包括：
1. **理解并掌握**Lagrange插值法和Newton插值法的基本理论和计算过程。
2. **编程实现**两种插值法，并能够通过输入不同的节点值和待求值，计算出相应的函数值。
3. **提高编程能力**，使编写的程序具有一定的通用性和灵活性。
#### 实验设备与环境
- 安装有C、C++或MATLAB等编程语言环境的计算机。
#### 实验原理
##### 插值的基本原理
插值是指通过一组已知的数据点（节点），寻找一个适当的函数，使得该函数能够准确地经过这些数据点，并可以用来估计其他未知点的函数值。插值问题的核心在于构建一个函数\( y = f(x) \)，使得对于每一个节点\((x_i, y_i)\)，都有\( f(x_i) = y_i \)。
##### Lagrange插值
Lagrange插值是一种基于多项式的插值方法，它通过构造一个多项式函数，使其通过所有给定的数据点。Lagrange插值多项式的一般形式为：
\[ L(x) = \sum_{i=0}^{n} y_i l_i(x) \]
其中，\( l_i(x) \)是基函数，定义为：
\[ l_i(x) = \prod_{j=0,j\neq i}^{n} \frac{x - x_j}{x_i - x_j} \]
##### Newton插值
Newton插值也是一种多项式插值方法，但与Lagrange插值不同的是，Newton插值使用了分段多项式来逼近函数。Newton插值多项式的一般形式为：
\[ N(x) = [y_0] + [y_0,y_1](x-x_0) + [y_0,y_1,y_2](x-x_0)(x-x_1) + \cdots + [y_0,\ldots,y_n](x-x_0)\cdots(x-x_{n-1}) \]
其中，\([y_0,\ldots,y_k]\)表示\(k\)阶差商，可以通过递推公式计算得到：
\[ [y_0,\ldots,y_{k+1}] = \frac{[y_1,\ldots,y_{k+1}] - [y_0,\ldots,y_k]}{x_{k+1}-x_0} \]
初始条件为：
\[ [y_i] = y_i \]
#### 实验内容及步骤
实验分为两个部分：
1. **Lagrange插值**
- 已知三个点\((11, 0.190809), (12, 0.207912), (13, 0.224951)\)，计算\(sin(11°30′)\)。
- 编写程序实现Lagrange插值法，并验证结果。
2. **Newton插值**
- 已知四个点\((0.40, 0.41075), (0.55, 0.57815), (0.65, 0.69675), (0.80, 0.88811)\)，计算当\(x=0.596\)时的函数值。
- 编写程序实现Newton插值法，并验证结果。
#### 实验结果
实验结果展示了如何编写Lagrange插值和Newton插值的程序，并给出了相应的输出结果。下面是一段示例代码：
```cpp
#include<iostream>
using namespace std;
double Lanrange(double *x, double *y, double k, int n); // Lagrange插值
double Diff(double *x, double *y, int n); // 计算n-1阶差商
double Newton(double *x, double *y, double k, int n); // Newton插值
int main(void)
{
/* 实验数据 */
double x1[3] = {11, 12, 13};
double y1[3] = {0.190809, 0.207912, 0.224951};
cout << "Lanrange插值:sin(11°30′)=" << Lanrange(x1, y1, 11.5, 3) << endl;
cout << "Newton插值:sin(11°30′)=" << Newton(x1, y1, 11.5, 3) << endl;
cout << endl;
double x2[4] = {0.40, 0.55, 0.65, 0.80};
double y2[4] = {0.41075, 0.57815, 0.69675, 0.88811};
cout << "Lanrange插值:x=0.596时的函数值=" << Lanrange(x2, y2, 0.596, 4) << endl;
cout << "Newton插值:x=0.596时的函数值=" << Newton(x2, y2, 0.596, 4) << endl;
return 0;
}
```
以上实验内容和步骤详细介绍了如何实现Lagrange插值和Newton插值，并通过具体的示例数据进行了验证。通过这个实验，学生不仅能够深入理解这两种插值方法的原理，还能够提高自己的编程能力。
