多项式

在平面坐标上，$n+1$个横坐标轴互异的点确定唯一的至多$n$次多项式。

Weierstrass 逼近定理：$[a,b]$上的连续函数都能被多项式一致逼近。

多项式拟合

对于一个函数$f(x)$，选取$n$个点，用这$n$个点确定的唯一的$n-1$次多项式近似$f(x)$

• 拟合的过程实际就是逐渐取点的过程，拟合程度不好，就逐渐取多一点

• 取点的方式有讲究：

  取等距结点（Equispace）时，就很容易出现龙格现象。

  切比雪夫分点（Chebyshev）是很好的选择。

  ***龙格现象：***多项式拟合中，拟合点所在的区间内拟合还可以，但出了这个区间，拟合函数就十分发散

范德蒙矩阵解析

对于一组点$\{ (x_0,y_0), \cdots, (x_n,y_n) \}$，确定一个$n$次多项式$P_n(x)=a_0+a_1x+\cdots+a_nx^n$，带入点集，得到矩阵表示，即范德蒙矩阵 Vandermonde matrix：（中间部分）

$$\begin{bmatrix} y_0\\ y_1\\ \vdots\\ y_n \end{bmatrix} = \begin{bmatrix} 1&x_0&x_0^2&\cdots&x_0^n\\ 1&x_1&x_1^2&\cdots&x_1^n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^n \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_n \end{bmatrix}$$

$$P_n(x) = \begin{bmatrix} x^0,x^1,\cdots,x^n \end{bmatrix} \begin{bmatrix} a_0,a_1,\cdots,a_n \end{bmatrix}^\text T$$

带入点集，用矩阵除法即可得到系数矩阵$[a_0,a_1,\cdots,a_n]^\text T$，但精度低。

拉格朗日插值

拉格朗日插值把多项式转换为$n+1$组拉格朗日基函数的和，即

$$P_n(x)=\sum \limits_{i=0}^{n} y_i*l_i(x)\\$$

其中$l_i(x)$是对第$i$个点$(x_i,y_i)$构造的拉格朗日基函数（也是$n$次多项式），有$x \in \{ x_0,\cdots,x_n\}$，

$$l_i(x)= \begin{cases} 1,\ &x=x_i\\ 0,\ &x\ne x_i \end{cases} \\ \\ \Rightarrow \sum \limits_{i=0}^n l_i(x) = \begin{cases} 1,\ &x \in \{ x_0,\cdots,x_n \} \\ \text{UNKOWN} &x \notin \{ x_0,\cdots,x_n \} \end{cases}$$

问题简化为确定$l_i(x)$，有：

$$l_i(x) = c_i \prod \limits_{j=0,j\ne i}^n (x-x_j)\\ l_i(x_i) = 1 \Rightarrow c_i = \frac 1{\prod \limits_{j=0,j\ne i}^n (x_i-x_j)}\\ \begin{align} \therefore l_i(x) &= \frac {\prod \limits_{j=0,j\ne i}^n (x-x_j)}{\prod \limits_{j=0,j\ne i}^n (x_i-x_j)}\\ &= \prod \limits_{j=0,j\ne i}^n \frac {x-x_j}{x_i-x_j} \end{align} \\ \\ \Rightarrow P_n(x)=\sum \limits_{i=0}^{n} \left( y_i\prod \limits_{j=0,j\ne i}^n \frac {x-x_j}{x_i-x_j} \right)$$

对于拉格朗日插值函数$P_n(x)$，有：

• 对点集外的点，每次计算插值需要$O(n^2)$次加法和乘法
• 加入新点时，需要重新构造插值函数
• 多是理论意义，效率低，抛砖引玉的老祖宗

质心公式

优化拉格朗日插值：

$$l(x)=\prod \limits_{j=0}^n(x-x_j)\\ \omega_i = \frac {1}{\prod \limits_{j=0,j\ne i}^n (x_i-x_j)}\\ \Rightarrow\ l_i(x) = \omega_i \cdot \frac {l(x)}{x-x_i}\\ \begin{align} \Rightarrow\ P_n(x) &= \sum \limits_{i=0}^{n} y_i*l_i(x)\\ &= l(x)\sum \limits_{i=0}^n {\frac{\omega_i}{x-x_i}y_i} \end{align}$$

插值函数除以拉格朗日基函数的和，仍会经过点集，以此作对插值函数作优化，得到质心公式：

$$\begin{align} P_n(x) &= \frac{l(x)\sum \limits_{i=0}^n {\frac{\omega_i}{x-x_i}y_i}}{\sum\limits_{i=0}^n l_i(x)}\\ &= \frac{l(x)\sum \limits_{i=0}^n {\frac{\omega_i}{x-x_i}y_i}}{\sum\limits_{i=0}^n \omega_i \cdot \frac {l(x)}{x-x_i}}\\ &= \frac{\sum \limits_{i=0}^n {\frac{\omega_i}{x-x_i}y_i}}{\sum\limits_{i=0}^n \frac {\omega_i}{x-x_i}} \end{align}$$

对于一个点集，对应的各点权重集$\{ \omega_0,\omega_1,\cdots,\omega_n \}$是唯一的，只需要计算一次。质心公式插值：

• 对点集外的点，每次计算插值需要$O(n)$次加法
• 加入新点时，计算量都显著减少
• 对于分式中无定义的点，取极限或补充定义可以解决
• 拟合结果相对更稳定

误差估计

原函数$f(x)$，拟合函数$P_n(x)$，误差为$f(x)-P_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}l(x)$。