拉格朗日插值是一种数据拟合的方法。对于$n+1$组点对$(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})$，其拟合结果为

$$P(x)=\sum_{i=0}^n(\prod_{j=0,j \neq i}^n \frac{x-x_j}{x_i-x_j})y_i,$$

将其用幂形式表示为

$$P(x)=\sum_{i=0}^n c_ix^i.$$

求解下面的线性方程组

$$\begin{pmatrix} x_0^n & x_0^{n-1} & \cdots & x_0 & 1\\ x_1^n & x_1^{n-1} & \cdots & x_1 & 1\\ \cdots & \cdots & \cdots & \cdots & 1\\ x_n^n & x_n^{n-1} & \cdots & x_n & 1\\ \end{pmatrix} \begin{pmatrix} c_n\\ c_{n-1}\\ \cdots\\ c_0\\ \end{pmatrix} = \begin{pmatrix} y_0\\ y_1\\ \cdots\\ y_n\\ \end{pmatrix}$$

可以得到$P(x)$的各项系数。

V = vander(x);
c = V\y(:);

实际操作中，拉格朗日插值不是一个好的拟合方法，当拟合函数次数超过三次时，区间末端拟合效果一般很差。 可以使用多项式拟合，如果数据和多项式差别过大，应考虑其他的插值方法，如三次样条插值。

原函数：$f(x) = \frac{1}{1+x^2}$