2022-09-22-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}\) 。