拉格朗日插值法

简介

拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数

对于n+1个点，对应于它们的次数都不超过n的拉格朗日多项式只有一个

定义

对某个多项式函数，已知有给定的n+1个取值点
::: align-center
(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)

:::
其中x_j对应着自变量的位置，而y_j对应着函数在这个位置的取值

假设任意两个不同的x_j都不相同，那么应用拉格朗日插值公式得到的拉格朗日插值多项式为
::: align-center
p_n(x)=\sum_{k=0}^ny_kL_k(x)

:::
其中，每个L_j(x)为拉格朗日基本多项式（或称为插值基函数）
::: align-center
L_k(x)=\prod_{j=0,j\ne k}^n\frac{x-x_j}{x_k-x_j}

:::
拉格朗日基本多项式L_j(x)的特点是在x_j上的取值为1，在其他的点x_j,i\ne j上的取值为0

拉格朗日插值多项式的存在和唯一性由多项式插值定理保证
定理（多项式插值定理） 给定任意两两不同的n+1个点(x_0,y_0),(x_1,y_1)\cdots(x_n)，即满足i\ne j时x_i\ne x_j，则经过这n+1个点的阶数小于等于n的多项式有且只有一个

下面证明对于拉格朗日插值法多项式插值定理是适用的：
先证明存在性，对于每个拉格朗日基本多项式都有
::: align-center
L_j(x_k)=\delta_{jk}:=\left\{\begin{matrix}1 & j=k\\0& j\ne k\end{matrix}\right .

:::
可以看到每个拉格朗日基本多项式都相当于一个克罗内克Delta函数，则由Delta函数的筛选性
::: align-center
p(x_k)=\sum_{i=0}^ny_iL_i(x_k)=y_k

:::
存在性得证

再证唯一性，假设还有另一n阶的拉格朗日插值多项式q(x)，构造
::: align-center
P(x)=p(x)-q(x)

:::
则对于i=0,1\cdots,n都有P(x_i)=p(x_i)-q(x_i)=y_i-y_i=0，由零点定理知有n+1个零点的n阶多项式仅可能是0，故p(x)=q(x)，唯一性得证

复杂度分析：插值

考虑给定n+1个点，求解拉格朗日多项式
::: align-center
p_n(x)=\sum_{k=0}^ny_kL_k(x)

:::
其中
::: align-center
L_k(x)=\prod_{j=0,j\ne k}^n\frac{x-x_j}{x_k-x_j}

:::

• 内层L_j(x)：n次运算
• 外层求和：n+1次运算
• 总计：\mathcal{O}(n^2)

但若我们考虑提前计算
::: align-center
w_k=\prod_{j=0,j\ne k}^n(x_k-x_j)

:::

在实际求解时内层操作变为
::: align-center
L_k(x)=\left\{\begin{matrix}\frac{w(x)}{(x-x_k)w_k}& x\ne x_k\\1&x=x_k\end{matrix}\right .

:::
其中
::: align-center
w(x)=(x-x_0)(x-x_1)\cdots(x-x_k)\cdots(x-x_n)

:::
此时求解时的复杂度变为

• 提前求解w_k：\mathcal{O}(n)
• 展开w(x)：\mathcal{O}(n)
• 重构L_k(x)：\mathcal{O}(1)
• 总计：\mathcal{O}(n)+\mathcal{O}(n)=\mathcal{O}(n)

复杂度分析：一阶导数

考虑上述拉格朗日插值多项式的一阶导数,在不考虑优化的情况下
::: align-center
p'_n(x)=\sum_{k=0}^ny_kL'_k(x)

:::
其中
::: align-center
L'_k(x)=\frac{1}{w_k}\frac{d}{dx}\prod_{j=0,j\ne k}^n(x-x_j)=\frac{1}{w_k}\sum_{i=0,i\ne k}^n\prod_{j=0,j\ne i,k}(x-x_j)

:::
分析其复杂度，在提前计算w_k的情况下计算L'_k(x)的复杂度为\mathcal{O}(n^2)，计算p'_n(x)的复杂度为\mathcal{O}(n^3)

现在考虑进行优化：
先考虑x=x_k时，此时
::: align-center
L_k'(x_k)=\frac{1}{w_k}\sum_{i=0,i\ne k}^n\frac{w_k}{x_k-x_i}=\sum_{i=0,i\ne k}^n\frac{1}{x_k-x_i}

:::
倒数和\sum_{i=0,i\ne k}^n\frac{1}{x_k-x_i}可以预计算，花费\mathcal{O}(n)
此时复杂度：

1. 预计算倒数和获得L'_k(x_k)：\mathcal{O}(n)
2. 计算p_n'(x_k)：\mathcal{O}(n)
3. 总计：\mathcal{O}(n)+\mathcal{O}(n)=\mathcal{O}(n)

再考虑x\ne x_k时，此时
::: align-center
L_k'(x)=\frac{d}{dx}\frac{w(x)}{(x-x_k)w_k}=\frac{1}{w_k}\frac{w'(x)(x-x_k)-w(x)}{(x-x_k)^2}

:::
考虑复用w(x)计算w'(x)
::: align-center
w'(x)=\sum_{i=0}^n\frac{w(x)}{x-x_i}

:::
其复杂度为\mathcal{O}(n)，考虑到w'(x)对于每个L_k'(x)都是相同的，所以完全可以将其提前计算而不需要再每个L_k'(x)的计算过程中都重新计算一遍，故考虑：

1. 提前计算w'(x)：\mathcal{O}(n)（构造w'(x)所用的w(x)也可以提前计算）
2. 计算p_n'(x)：

• 每个L'_k(x)：现在复杂度变为\mathcal{O}(1)
• 总计：\mathcal{O}(n)

3. 总计：\mathcal{O}(n)+\mathcal{O}(n)=\mathcal{O}(n)