2022-09-22-「Note」Lagrange

妙

插值

插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。

因为两点确定一条直线，三点确定一条抛物线，所以说 $k + 1$ 个点可以确定 一个 $k$ 次的多项式，这个确定的方式可以暴力的高斯消元直接 $k^3$ 确定每一项的系数，但是显然是不优秀的，现在引入拉格朗日插值。

拉格朗日插值

这个方法比较粗暴，具体而言，就是对于这已知的 $k$ 个点，每个点求出一个子函数记为 $f_i$ 要求是要让这个函数在 $x = x_i$ 时为 $1$ ，在 $x \not = x_i$ 时取到 $0$ ，那么 $f(x) = \sum_{i = 1}^{n} y_i f_i(x)$ 。

现在的目标是要构造出这 $n$ 个子函数，可以得到 $f_i(x) = \prod_{j \not = i} \frac{x - x_j}{x_i - x_j}$ 。