多项式插值定理

🔎 [16：46]

定理：若$x_i$两两不同，则对任意给定的$y_i$，存在唯一的次数至多是$n$次的多项式$p_n$，使得$p_n(x)=y_i,i=0,\cdots,x^n$。

✅ 唯一的多项式p的意思是唯一的一组系数$a_0, \cdots, a_n$

证明：在幂基$(1,x,\cdots,x^n)$下待定多项式$p$的形式为：
$$ p(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n $$
定理不限于幂基，下面证时过程只是以幂基为例
由插值条件$p(x_i)=y_i,i=0,\cdots,n$得到如下方程组:

👆 如果基函数选取不一样,方程组的系数矩阵不同

系数矩阵为Vandermonde矩阵，其行列式非零，因此方程组有唯一解。

✅ 如果不使用幂基而是别的基函数，也能得到上述方程组并解出唯一解，只是矩阵的内容不同。
要求解的系数是$a_1,a_2, \cdots, a_n$,此处系数a是未知数，而不是通常理解的$x$, $x$ 代表输入，因此是已知量。

技巧1：构造插值问题的通用解

🔎 [17：44] ✅ 上一页方法中的问题：每次x或y变化都要构造一个公式来解。本页的目的是，只变y而x不变时不需要构造矩阵和解方程。

给定 $n+1$个点 {$(x_0,y_0),\cdots,(x_n,y_n)$}, 寻找一组次数为$n$的多项式基函数$l_i$使得

$$ l_i(x_j) = \begin{cases} 1, & \text{ if } i=j \\ 0, & \text{ if } i\neq j \end{cases} $$

那么，插值问题的解为:
$$ P(x)=y_{0} l_{0}(x)+y_{1} l_{1}(x)+\cdots+y_{n} l_{n}(x)=\sum_{i=0}^{n} y_{i} l_{i}(x) $$

✅ 这样做的好处是，即使y变化，也不用重新解方程组。$l_i(x)$可以通过上述方程组提前解出来，以$y$为系数对$l_i(x)$做线性组合，就可以得到$P(x)$
多项式$l_i(x)$被称为拉格朗日多项式，即拉格朗日插值问题的通用解。
该方法称为拉格朗日插值。
给定$n+1$个点，通过上面的方法解方程组，可以解出$l_i(x)$系数，从而得到拟合函数。
但 $n+1$ 个点有任何一点改变，都要重新"构造方程组→解系数→得拟合函数"。
该技巧对以上过程做简化。在 $n+1$ 个定点的$x$不变而只有$y$的变化的情况下，无须解方程而快速得到拟合函数。
具体步骤为：
2.先求拟合函数 $l_i(x)$. 用上一页的方法。
构造用于拟合$l_i(x)$的数据点。其中$x_i$为原给定的$n+1$个时,$x_i$,$y_i$为公式(1)中的$l_i(x_j)$，这样给每个$l_i(x)$构造了$n+1$个用于拟合点。例如:
$n+1$个点{$(x_0,1),(x_1,0)\dots ,(x_n,0)$}导拟合函数$l_0(x)$
这样就得到了$n+1$个函数$l_i(x)$
在拟合$l_i(x)$的过程中只用到了原给定数据点的$x$而没有用 $y$。因此，只要x不变，$l_i(x)$函数就一直适用。
要拟合的函数$P(x)$就成了$l_i(x)$的线性组合，$y_i$是系数。

💡 我的思考：
根据 $Aa=y$ 解出$a$,得到拟合函数$f(x)= A(x)\cdot a$
现在，先算出 $A{a}' = E,根据Ey=y可知：A{a}'y=Aa$.
因此得到拟合函数$f(x)=A(x)a=A(x){a}' y$.
结论：把计算的过程或目标分解，分析每一部分计算的依赖项。根据依赖项决定是否能提前算好。

怎么计算多项式$l_i(x)$?

$n$阶多项式,且有以下$n$个根

$$ x_0,x_1,x_2,\cdots,x_{i-1} ,x_{i+1} ,\cdots,x_n $$

故可表示为

$$ l_i(x) \\
=C_{i}\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{i-1}\right)\left(x-x_{i+1}\right) \ldots\left(x-x_{n}\right) \\ =C_{i} \prod_{j \neq i}\left(x-x_{j}\right) $$

由$l_i(x_i)=1$可得
$$ 1=c_{i} \prod_{j \neq i}\left(x_{i}-x_{j}\right) \Rightarrow c_{i}=\frac{1}{\prod_{j \neq i}\left(x_{i}-x_{j}\right)} $$

最终多项式基函数为
$$ l_{i}(x)=\frac{\prod_{j \neq i}\left(x-x_{j}\right)}{\prod_{j \neq i}\left(x_{i}-x_{j}\right)} $$

多项式$l_i(x)$被称为拉格朗日多项式

技巧2：更方便的求解表达

Newton插值：具有相同“导数”（差商）的多项式构造（$n$阶Taylor展开）

定义：
一阶差商：

$$ f\left[x_{0}, x_{1}\right]=\frac{f\left(x_{1}\right)-f\left(x_{0}\right)}{x_{1}-x_{0}}
$$

$k$阶差商:

设{$x_0,x_1,\cdots,x_k$}互不相同,$f(x)$关于{$x_0,x_1,\cdots,x_k$}的$k$阶差商为:

$$ f\left[x_{0}, x_{1}, \cdots, x_{k}\right]=\frac{f\left[x_{1}, \cdots, x_{k}\right]-f\left[x_{0}, x_{1}, \cdots, x_{k-1}\right]}{x_{k}-x_{0}}
$$

所以Newton插值多项式表示为： $$ N_{n}(x)=f\left(x_{0}\right)+f\left[x_{0}, x_{1}\right]\left(x-x_{0}\right)+\cdots+f\left[x_{0}, x_{1}, \cdots, x_{n}\right]\left(x-x_{0}\right) \cdots\left(x-x_{n-1}\right) $$