计算方法:插值与数值逼近
多项式插值
多项式插值要做的就是,找一个多项式 \(y(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n\) 来近似任意函数 \(f(x)\)。
为了让插值尽量精确，我们让 \(y(x)\) 经过所有的 \(x_i\)（插值节点）。这样就得到：
\[ \left\{\begin{aligned} a_0+a_1x_0+a_2x_0^2+\cdots+a_nx_0^n&=f(x_0)\\ a_0+a_1x_1+a_2x_1^2+\cdots+a_nx_1^n&=f(x_1)\\ &\vdots \\ a_0+a_1x_n+a_2x_n^2+\cdots+a_nx_n^n&=f(x_n)\\ \end{aligned}\right. \]
显然这个方程组的解是唯一的，即：多项式插值具有唯一性。Lagrange 插值、Newton 插值等只是得到这个方程组的解的不同方式，最终得到的结果是一样的。
Lagrange 插值
计算
\[ L(x)=\sum_{j=0}^nf(x_j)l_j(x) \]
其中
\[ \begin{aligned} l_j(x)&=\frac{(x-x_0)(x-x_1)\cdots(x-x_{j-1})(x-x_{j+1})\cdots(x-x_n)}{(x_j-x_0)(x_j-x_1)\cdots(x_j-x_{j-1})(x_j-x_{j+1})\cdots(x_j-x_n)} \\ &= \prod_{i=0, i\neq j}^n\frac{x-x_i}{x_j-x_i} \end{aligned} \]
事实上，\(l_j(x)\) 的本质就是 \[\left\{\begin{aligned} &0, x\neq x_j\\ &1, x=x_j \end{aligned}\right.\] 类似布尔函数.
被插函数可以表示为 \(f(x)=L(x)+E(x)\)，其中 \(E(x)\) 即为误差（又叫「插值余项」）。
误差 / 余项
\[ E(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}p_{n+1}(x), p_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n) \]
其中 \(\xi\in(a, b)\)。
容易得到误差上限 \(|E(x)|\leqslant\frac{\max\limits_{a<x<b} f^{(n+1)}(x)}{(n+1)!}p_{n+1}(x)\)。事实上，因为多项式插值是唯一的，所有多项式插值的误差和上限都是这个东西。
Newton 插值
计算
将 \(n\) 次插值多项式写成如下的形式：
\[ y(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)(x-x_1)\cdots(x-x_{n+1}) \]
其中：
\[ \begin{aligned} a_0 &= f(x_0)\\ a_1 &= \frac{f(x_1)-f(x_0)}{x_1-x_0} \\ a_2 &= \frac{\frac{f(x_2)-f(x_0)}{x_2-x_0}-\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_1} \\ &\cdots \end{aligned} \]
为了便于表示，引入差商的定义。
差商
\[ \begin{aligned} f[x_0 x_1] &= \frac{f(x_1)-f(x_0)}{x_1-x_0} \\ f[x_0x_1x_2] &= \frac{f[x_0x_2]-f[x_0x_1]}{x_2-x_1} \\ f[x_0x_1x_2x_3] &= \frac{f[x_0x_1x_3]-f[x_0x_1x_2]}{x_3-x_2} \\ &\cdots \\ f[x_0x_1\cdots x_k] &= \frac{f[x_0x_1\cdots x_{k-2}x_k]-f[x_0x_1\cdots x_{k-2}x_{k-1}]}{x_k-x_{k-1}} \end{aligned} \]
从上到下依次称「一阶差商」「二阶差商」……「\(k\) 阶差商」。可以证明，\(a_k=f[x_0x_1\cdots x_k], k=0, 1, 2, \cdots, n\)。
用差商表示的 Newton 插值多项式：
\[ N_n(x)=f(x_0)+f[x_0x_1](x-x_0)+f[x_0x_1x_2](x-x_0)(x-x_1)+\cdots+f[x_0x_1\cdots x_n](x-x_0)\cdots(x-x_{n-1}) \]
误差 / 余项
\[ E(x)=f[x_0x_1\cdots x_nx](x-x_0)(x-x_1)\cdots(x-x_n) \]
由于多项式插值的唯一性，这个式子的值和 Lagrange 插值的余项是相等的，由此可以得到差商和导数的关系：
\[ f[x_0x_1\cdots x_j]=\frac{f^{(j)}(\xi_j)}{j!} \]
其中 \(\xi_j\in(x_0, x_j)\)。
差分与等距节点的插值
差分
- \(k\) 阶向前差分：\(\Delta^kf(x)=\Delta^{k-1}f(x+h)-\Delta^{k-1}f(x)\)；
- 0 阶向前差分：\(\Delta^0f(x)=f(x)\)；
- \(k\) 阶向后差分：\(\nabla^kf(x)=\nabla^{k-1}f(x)-\nabla^{k-1}f(x-h)\)；
- 0 阶向后差分：\(\nabla^0f(x)=f(x)\)；
- \(k\) 阶中心差分：\(\delta^kf(x)=\delta^{k-1}f(x+\frac{h}{2})-\delta^{k-1}f(x-\frac{h}{2})\)；
- 0 阶中心差分：\(\delta^0f(x)=f(x)\)。
向前差分与差商的关系：\(f[x_0x_1\cdots x_k]=\frac{\Delta^kf_0}{k!h^k}=\frac{\nabla^kf_k}{k!h^k}\)。
Newton 向前插值公式
用差分代替 Newton 插值公式中的差商：
\[ \begin{aligned} N_n(x) = \Delta^0f_0&+\frac{\Delta^1f_0}{h}(x-x_0)+\frac{\Delta^2f_0}{2!h^2}(x-x_1)(x-x_0)+\cdots \\ &+\frac{\Delta^nf_0}{n!h^n}(x-x_{n-1})(x-x_{n-2})\cdots(x-x_0) \end{aligned} \]
用 \(x_0+th\) 代替 \(x\)：
\[ \begin{aligned} N_n(x_0+th) &= \Delta^0f_0+ \Delta^1f_0t+\Delta^2f_0\frac{t(t-1)}{2!} +\cdots+\Delta^nf_0\frac{t(t-1)\cdots(t-(n-1))}{n!} \\ &= \sum_{j=0}^n\Delta^jf_0\frac{t(t-1)(t-2)\cdots(t-(j-1))}{j!} \\ &= \sum_{j=0}^n\Delta^jf_0\mathrm{C}_t^j \end{aligned} \]
（组合数公式：\(\mathrm{C}_n^m=\frac{n!}{m!(n-m)!}=\frac{n(n-1)(n-2)\cdots(n-(m-1))}{m!}\)。广义的组合数中 \(n\) 可以是负数、小数）
Newton 向后插值公式
起始点选 \(x_n\)，使用向后的差分，可以推出下面的 Newton 向后插值公式。
\[ \begin{aligned} N_n(x_n+th) &=\sum_{j=0}^{n}\nabla^jf_n\frac{t(t+1)\cdots(t+j-2)(t+j-1)}{j!} \\ &=\sum_{j=0}^n\nabla^jf_n\mathrm{C}_{t+j-1}^{j} \end{aligned} \]
函数的最佳平方逼近
问题描述
先来看连续情况.给定函数 \(f(x)\in C[a,b], x\in[a, b];\phi_0,\phi_1,\cdots,\phi_n\)是\(C[a,b]\)上n+1个线性无关函数，找一个 \(\phi^*(x)\in\Phi(x)=\mathrm{span}\{\phi_0(x), \phi_1(x), \cdots, \phi_n(x)\}\)，使得
\[ \int\limits_a^b\rho(x)(f(x)-\phi^*(x))^2\mathrm{d}x=\min_{\phi(x)\in\Phi(x)}\int\limits_a^b\rho(x)(f(x)-\phi(x))^2\mathrm{d}x \]
即左侧的积分式取得最小值。式中 \(\rho(x)\) 是权函数，满足：
- \(\rho(x)\geqslant 0, \forall x\in[a, b]\)；
- \(\int_a^b\rho(x)x^k\mathrm{d}x\) 存在，\(\forall k=0, 1, 2, \cdots\)；
- 对任何非负函数 \(f(x)\)，若 \(\int_a^bf(x)\rho(x)\mathrm{d}x=0\)，则 \(f(x)\equiv0\)。
求解
记 \(\phi^*(x)=a_0\phi_0(x)+a_1\phi_1(x)+\cdots+a_n\phi_n(x)\)。
记 \(||f-\phi^*||_2^2=F(a_0, a_1, \cdots, a_n)=\int_a^b\rho(x)(f(x)-\phi^*(x))^2\mathrm{d}x\)。令 \(\frac{\partial F}{\partial a_j}=0\)，有
\[ \begin{aligned} \int\limits_a^b\rho(x)f(x)\phi_j(x)\mathrm{d}x = a_0\int\limits_a^b\rho(x)\phi_0(x)\phi_j(x)\mathrm{d}x&+a_1\int\limits_a^b\rho(x)\phi_1(x)\phi_j(x)\mathrm{d}x+\cdots \\ &+ a_n\int\limits_a^b\rho(x)\phi_n(x)\phi_j(x)\mathrm{d}x \end{aligned} \]
记 \((f, g)\) 为 \(\int_a^b\rho(x)f(x)g(x)\mathrm{d}x\)。令 \(F\) 的所有偏导为零，得到下面的线性方程组：
\[ \left[\begin{matrix} (\phi_0,\phi_0) & (\phi_1, \phi_0) & \cdots & (\phi_n, \phi_0) \\ (\phi_0,\phi_1) & (\phi_1, \phi_1) & \cdots & (\phi_n, \phi_1) \\ \vdots & \vdots & \ddots & \vdots \\ (\phi_0,\phi_n) & (\phi_1, \phi_n) & \cdots & (\phi_n, \phi_n) \\ \end{matrix}\right] \left[\begin{matrix} a_0 \\ a_1 \\\vdots\\a_n \end{matrix}\right]= \left[\begin{matrix} (f, \phi_0)\\ (f, \phi_1)\\ \vdots \\ (f, \phi_n) \\ \end{matrix}\right] \]
求解这个方程组，即可得到最佳平方逼近时的系数。
误差
记 \(f-\phi^*(x)=\delta\)，记 \(||\delta||_2^2\) 为「平方误差」，记它的平方根 \(||\delta||_2\) 为「均方误差」。
\[ \begin{aligned} ||\delta||_2^2&=||f-\phi^*||_2^2=(f, f)-(\phi^*, f)\\ &=||f||_2^2-\sum_{j=0}^na_j^*(\phi_j, f) \end{aligned} \]
正交函数与正交多项式
对 \(f(x),g(x)\in C[a, b]\)，记 \((f,g)=\int_a^b\rho(x)f(x)g(x)\mathrm{d}x\)，若 \((f,g)=0\)，称 \(f(x)\)、\(g(x)\) 在 \([a,b]\) 上带权 \(\rho(x)\) 正交，记作 \(f\bot g\)。
如果函数序列 \(\{\phi_j\}_0^{+\infty}\) 在 \([a, b]\) 上两两带权 \(\rho(x)\) 正交，称 \(\{\phi_j\}\) 为 \([a, b]\) 上带权 \(\rho(x)\) 的正交函数族。
例如：\(1, \sin x, \cos x, \sin 2x, \cos 2x, \cdots\) 是在 \([-\pi,\pi]\) 上带权 \(\rho(x)\equiv1\) 的正交函数族，因为
\[ \begin{aligned} (1, 1)&=\int\limits_{-\pi}^{\pi}\mathrm{d}x=2\pi\\ (\sin nx, \sin mx)&=\int\limits_{-\pi}^\pi\sin nx\sin mx\mathrm{d}x=\left\{\begin{aligned}&\pi,m=n\\&0, m\neq n\end{aligned}\right. \\ (\cos nx, \cos mx)&=\int\limits_{-\pi}^\pi\cos nx\cos mx\mathrm{d}x=\left\{\begin{aligned}&\pi,m=n\\&0, m\neq n\end{aligned}\right. \\ (\cos nx, \sin mx)&=\int\limits_{-\pi}^\pi\cos nx\sin mx\mathrm{d}x=0 \\ \end{aligned} \]
如果 \(\phi_n(x)\) 为首项系数非零的 \(n\) 次多项式，称 \(\{\phi_j\}\) 为正交多项式族。
使用正交多项式族作为 \(\Phi(x)\) 进行最佳平方逼近，这样得到的左侧矩阵是对角阵。
曲线拟合（最小二乘法）
曲线拟合即是离散情况的最佳平方逼近问题。给定已知 \((m+1)\) 个数据点的离散函数 \(f(x), x\in[a, b]\)，找一个 \(\phi^*(x)\in\Phi(x)=\mathrm{span}\{\phi_0(x), \phi_1(x), \cdots, \phi_n(x)\}\)，使得
\[ ||f-\phi^*||_2^2=F(a_0, a_1,\cdots, a_n)=\min_{\phi\in\Phi}\sum_{j=0}^m\rho(x_j)(f(x_j)-\phi(x_j))^2 \]
定义离散情况的内积
\[ (f,g)=\sum_{i=0}^m\rho(x_i)f(x_i)g(x_i) \]
使用与前文相同的解法，可以解出系数 \(a_i,i=0, 1, \cdots, n\)。
同样可以定义离散情况下的平方误差
\[ ||\delta||_2^2=||f-\phi^*||_2^2=\sum_{i=0}^m\rho(x_i)(f_i-\phi(x_i))^2 \]
以及均方误差
\[ ||\delta||_2=\sqrt{||\delta||_2^2}=\sqrt{\sum_{i=0}^m\rho(x_i)(f_i-\phi(x_i))^2} \]
特别注意，在曲线拟合这里的「均方误差」没有「均」，即不用将根号里的东西乘以 \(\frac{1}{m}\)。