概述

拉格朗日插值法常用于通过点值获得满足这些点值的多项式，是一种由点值到多项式的转换方式。下面介绍其原理及应用。

过程

对于某个k次多项式函数，已知给定k+1个取值点，分别为 (x_0, y_0), \ldots, (x_k, y_k) 。
假设这些点的x值都不同，那么对于每个点我们写出它的拉格朗日基本多项式（插值基函数），为
\ell_j(x) = \prod_{i=0, i \neq j}^k \frac{x-x_i}{x_j-x_i}
再利用这些多项式构成拉格朗日插值多项式，为
L(x) = \sum_{j=0}^k y_j \ell_j(x)
我们容易观察到，拉格朗日基本多项式的特点是只有当x值为x_j时取值为1，其他点值的x值的取值都为0。

例子

假如我们需要求出某个二次多项式函数f，我们知道了三个点值(1, 1)、(2, 4)和(3, 9)，下面构造它们的拉格朗日基本多项式
\begin{aligned} \ell_0(x) &= \frac{(x-2)(x-3)}{2} \\ \ell_1(x) &= -(x-1)(x-3) \\ \ell_2(x) &= \frac{(x-1)(x-2)}{2} \end{aligned}
加起来，得到了
f(x) = x^2

算法

点值求多项式：O(n^2)
多项式求值：O(n^2)