多项式插值定理

🔎 [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)$