5.1 离散问题
定义给定一组点\(\{x_i,y_i\}\quad(i=0,1,\cdots,n)\)
并且\(x_0<x_1<\cdots<x_n\)，若函数\(f(x)\)使得
\(\qquad f(x_i)=y_i\quad (i=0,1,\cdots,n)\)
成立，则\(y=f(x)\)就是这一组数据点的一个插值函数，求\(y=f(x)\)的过程称为函数插值。
函数插值不是唯一的。
其他处理离散点的方式允许存在误差，因此没有必要要求函数一定要准确地通过给定的数据点。
5.2 一般插值问题
5.2.1 对插值函数的要求
- 插值函数应该有比被插值函数具有更简单的形式；
- 插值函数应当继承被插值函数的某些特性，包括但不限于单调性、凹凸性、周期性；
- 简单程度
- 性态方面的接近程度
5.2.2 多项式插值
1）多项式插值的定义
定义给定一组点\(\{x_i,y_i\}\quad(i=0,1,\cdots,n)\)，且
\(\qquad \qquad x_0<x_1<\cdots<x_n\)
求次数不超过n的多项式\(p_n(x)\)使得
\(\qquad \qquad p_n(x_i)=y_i,\quad i=0,1\cdots,n\)
成立，其中\(x_i\)称为插值节点，\(p_n(x)\)称为n次插值多项式。
5.2.3 单项式基底下的多项式插值
设n次插值多项式为\(p_n(x)=t_0+t_1x+t_2x^2+\cdots+t_nx^n\)
根据插值条件，得到
\(\qquad \qquad p_n(x)=t_0+t_1x_i+t_2x_i^2+\cdots+t_nx_i^2,\quad i=0,1,\cdots,n\)
即
\(\qquad \begin{bmatrix}1&x_i&\cdots&x_i^n\end{bmatrix}\begin{bmatrix}t_0\\t_1\\\vdots\\t_n\end{bmatrix}=\begin{bmatrix}y_0\\y_1\\\vdots\\y_n\end{bmatrix}\)
上述关系就是一个关于\(t_0,t_1,\cdots,t_n\)的线性方程组：
\(\qquad \begin{bmatrix}1&x_0&\cdots&x_0^n\\1&x_1&\cdots&x_1^n\\\vdots&\vdots&\ddots&\vdots\\1&x_n&\cdots&x_n^n\end{bmatrix}\begin{bmatrix}t_0\\t_1\\\vdots\\t_n\end{bmatrix}=\begin{bmatrix}y_0\\y_1\\\vdots\\y_n\end{bmatrix}\)
用矩阵符号记之为\(At=y\)，其中A称为插值矩阵。
矩阵A是Vandermonde矩阵，当\(x_i\)互不相同时，A可逆。
但通常不会这么做：①工作量大 ②A通常是一个病态矩阵
5.2.4 一般基底下的插值多项式
假设有一组\(P_n\)的基底：\(\quad\varphi_{0}(x),\varphi_1(x),\cdots,\varphi_{n}(x)\in P_n\)
任意次数不超过n的多项式可写成：\(\qquad P_{n}(x)=t_0\varphi_{0}(x)+t_1\varphi_{1}(x)+\cdots+t_n\varphi_{n}(x)\)
写成矩阵形式\(At=y\)
\(\qquad\begin{bmatrix}\varphi_0(x_0)&\varphi_1(x_0)&\cdots&\varphi_{n}(x_0)\\\varphi_0(x_1)&\varphi_1(x_1)&\cdots&\varphi_{n}(x_1)\\\vdots&\vdots&\ddots&\vdots\\\varphi_0(x_n)&\varphi_1(x_n)&\cdots&\varphi_{n}(x_n)\end{bmatrix}\begin{bmatrix}t_0\\t_1\\\vdots\\t_n\end{bmatrix}=\begin{bmatrix}y_0\\y_1\\\vdots\\y_n\end{bmatrix}\)
A称为一般插值矩阵。
什么情况下，\(At=y\)能够被快速求解？显然，当\(A=I\)时，系统求解起来最为方便。
当插值矩阵是单位阵时，对应的就是Lagrange插值多项式。
5.3 常用插值公式和算法
5.3.1 Lagrange型插值多项式
当矩阵A是单位阵时，对角线上元素为1，其他元素为0，得到
\(\qquad \varphi_j(x_i)=\delta_{ij}=\cases{1,\qquad i=j,i=0:n,\\0,\qquad i\ne j}\)
若可以求出这样的\(\varphi_j(x)\)它们就称为Lagrange插值基，并记为\(l_j(x)\)，它们又称基本插值多项式。
由于要求插值矩阵是单位阵，那么
\(l_j(x_i)=0\qquad(i\ne j),\quad l_j(x_j)=1\)
\(l_j(x)=\alpha_j(x-x_0)\cdots(x-x_{j-1})(x-x_{j+1})\cdots(x-x_n)\)
由上式知，\(\alpha_j=\frac{1}{\prod\limits_{i=0,i\ne j}^{n}(x_j-x_i)}\)，则\(l_j(x)=\frac{\prod\limits_{i=0,i\ne j}^{n}(x-x_i)}{\prod\limits_{i=0,i\ne j}^{n}(x_j-x_i)}\)
\(p_n(x)=y_0l_0(x)+y_1l_1(x)+\cdots+y_nl_n(x)=\sum\limits_{j=0}^{n}y_jl_j(x)=\sum\limits_{j=0}^{n}y_j\frac{\prod\limits_{i=0,i\ne j}^{n}(x-x_i)}{\prod\limits_{i=0,i\ne j}^{n}(x_j-x_i)}\)，称\(p_n(x)\)为n次Lagrange插值多项式。
5.3.2 插值误差余项
设\(f(x)\)在包含\(n+1\)个互异节点\(x_0,x_1,\cdots,x_n\)的区间\([a,b]\)上具有n阶连续倒是，且在\((a,b)\)内存在\(n+1\)阶导数，则对于任意的\(x\in[a,b]\)，有\(R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}W_{n+1}(x)\)，其中\(\xi\in(a,b),W_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)\)
5.3.4 差商与Newton插值
设0阶差商为\(f[x_i]=f(x_i)\)，则1阶差商定义为\(f[x_i,x_j]=\frac{f[x_j]-f[x_i]}{x_j-x_i}\)，2阶差商定义为\(f[x_i,x_j,x_k]=\frac{f[x_j,x_k]-f[x_i,x_j]}{x_k-x_i}\)，k阶差商定义为\(f[x_0,x_1,\cdots,x_k]=\frac{f[x_1,\cdots,x_k]-f[x_0,\cdots,x_{k-1}]}{x_k-x_0}\)
对比上节我们发现\(\alpha_k=f[x_0,x_1,\cdots,x_k]\)，即插值多项式为\(p_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots\\+f[x_0,x_1,\cdots,x_n](x-x_0)\cdots(x-x_{n-1})\)
这种类型的插值多项式称为n次Newton型插值多项式。相当于把\(1,x-x_0,(x-x_0)(x-x_1),\cdots,(x-x_0)(x-x_1)\cdots(x-x_{n-1})\)作为多项式空间\(P_n\)的一组基。
1）Newton型插值多项式的计算流程
给定数据点\((x_0,y_0)\quad (x_1,y_1)\quad\cdots\quad(x_n,y_n)\)
列差商表
| k | \(x_k\) | 0阶 | 1阶 | 2阶 | 3阶 |
|---|---|---|---|---|---|
| 0 | \(x_0\) | \(f[x_0]\) | \(f[x_0,f_1]\) | \(f[x_0,x_1,x_2]\) | \(f[x_0,x_1,x_2,x_3]\) |
| 1 | \(x_1\) | \(f[x_1]\) | \(f[x_1,x_2]\) | \(f[x_1,x_2,x_3]\) | |
| 2 | \(x_2\) | \(f[x_2]\) | \(f[x_2,x_3]\) | ||
| 3 | \(x_3\) | \(f[x_3]\) |
根据第一行结果，得到插值多项式为\(N_3(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)\\+f[x_0,x_1,x_2,x_3](x-x_0)(x-x_1)(x-x_2)\)
2）差商的性质
性质2 差商具有对称性 \(f[x_0,x_1,x_2,x_3]=f[x_3,x_0,x_1,x_2]\)
性质3 差商同高阶导数具有如下关系 \(f[x_0,x_1,\cdots,x_k]=\frac{f^{(k)}(\eta)}{k!}\quad \eta\in(\min\limits_{0\le i\le k}\{x_i\},\max\limits_{0\le i\le k}\{x_i\})\)
性质4 上性质的推论 \(f[x_0,x_1,\cdots,x_k,x]=\frac{f^{(k+1)}(\xi)}{(k+1)!}\quad \xi\in(\min\{x_0,x_1,\cdots,x_i,x\},\max\{x_0,x_1,\cdots,x_i,x\})\)
可以证明Newton误差余项可以写成\(R_k(x)=f(x)-N(x)=f[x_0,x_1,\cdots,x_k,x]W_{k+1}(x)\)
差分及等距节点Newton插值多项式
上节讨论的是节点任意分布的Newton插值多项式。但在实际使用时又是碰到等距节点的情况，即节点为\(x_i=a+ih \quad (i=0,1,\cdots,n)\)这里h称为步长，此时插值多项式可以进一步简化，同时可以避免做除法运算。
定义：已知函数\(f(x)\)在等距节点\(x_i\)上的函数值为\(f(x_i)=f_i(i=0,1,\cdots,n)\)，称\(f_{i+1}-f_i\)在\(x_i\)处以h为步长的1阶差分，记作\(\Delta f_i\)，即\(\Delta f_i=f_{i+1}-f_i\)，类似的，称\(\Delta^kf_i=\Delta^{k-1}f_{i-1}-\Delta^{k-1}f_i\)为\(f(x)\)在\(x_i\)处以h为步长的k阶向前差分，简称k阶差分。
和差商的计算一样，可构造差分表
| k | \(x_k\) | \(f_k\) | \(\Delta f_k\) | \(\Delta^2f_k\) | \(\Delta^3f_k\) | \(\Delta^4f_k\) |
|---|---|---|---|---|---|---|
| 0 | \(x_0\) | \(f_0\) | \(\Delta f_0\) | \(\Delta^2f_0\) | \(\Delta^3f_0\) | \(\Delta^4f_0\) |
| 1 | \(x_1\) | \(f_1\) | \(\Delta f_1\) | \(\Delta^2f_1\) | \(\Delta^3f_1\) | |
| 2 | \(x_2\) | \(f_2\) | \(\Delta f_2\) | \(\Delta^2f_2\) | ||
| 3 | \(x_3\) | \(f_3\) | \(\Delta f_3\) | |||
| 4 | \(x_4\) | \(f_4\) |
应用数学归纳法可以证明差分和差商有如下关系：\(f[x_i,x_{i+1},\cdots,x_{i+k}]=\frac{\Delta^kf_i}{k!h^k}\)
令\(x=x_0+th\)，则\(\prod\limits_{j=0}^{k-1}(x-x_j)=\prod\limits_{j=0}^{k-1}[(x_0+th)-(x_0+jh)]=h^k\prod\limits_{j=0}^{k-1}(t-j)\)
代入到Newton插值多项式\(N_n(x)=\sum\limits_{k=0}^{n}f[x_0,x_1,\cdots,x_k]\prod\limits_{j=0}^{k-1}(x-x_j)\)
得到\(N_n(x_0+th)=\sum\limits_{k=0}^{n}\frac{\Delta^kf_0}{k!}\prod\limits_{j=0}^{k-1}(t-j)\)
其中\(t=\frac{x-x_0}{h}\)，称为n次Newton前插公式。
5.3.8 一种带导数的插值
带导数插值问题的一种处理手段就是，先用函数值数据构造一个低次多项式，然后找到二者的联系，最后再用倒数条件确定一些未知的系数，需要指出的是，并非任意一个带导数插值问题都有解或唯一解，要具体问题具体分析。
5.3.9 Hermite插值
给定区间\([a,b]\)中n+1个互异节点\(x_i\quad(i=0,1,\cdots,n)\)上的函数值以及直到\(m_i\)阶的导数值\(f(x_i),f'(x_i),\cdots,f^{(m_i)}(x_i)\)，令\(m=\sum\limits_{i=0}^{n}(m_i+1)-1\)。若存在次数不超过m的多项式\(H_m(x)\)，使得每个\(x_i\quad(i=0,1,\cdots,n)\)处\(H_m(x_i)=f(x_i),H'_{m}(x_i)=f'(x_i),\cdots,H_{m}^{m_i}(x_i)=f^{(m_i)}(x_i)\)
则称\(H_m(x)\)为\(f(x)\)的m次Hermite插值多项式。
Hermite插值又称为重节点上的插值。
当被插值函数\(f(x)\)在节点\(x_i\)处具有\(m_i\)阶连续导数时，Hermite插值多项式\(H_m(x)\)存在且唯一。
当\(f(x)\in C^{(m+1)}[a,b]\)时，Hermite插值的误差余项为\(f(x)-H_m(x)=\frac{f^{(m+1)}(\xi)}{(m+1)!}\prod\limits_{i=0}^{n}(x-x_i)^{m_i+1},\quad \xi\in(a,b)\)
2）Newton型Hermite插值多项式
重节点上的差商可以这样计算：\(f[x_0,x_0]=f'(x_0)\)
更多节点时：\(f[\underbrace{x_0,\cdots,x_0}_{k+1}]=\frac{f^{(k)}(x_0)}{k!}\)
有了重节点上的差商，Hermite插值多项式：\(H_m(x)=f[x_0]+f[x_0,x_0](x-x_0)+\cdots+f[x_0,\cdots,x_0](x-x_0)^{m_0}+\\f[x_0,\cdots,x_0,x_1](x-x_0)^{m+1}+\\f[x_0,\cdots,x_0,x_1,x_1](x-x_0)^{m_0+1}(x-x_1)+\cdots\)
5.4.2 分段线性插值
2）分段线性插值简介
最简单的分段插值是分段线性插值，所谓分段线性插值，简而言之就是用折现直接把数据点连接起来，然后就形成一个分段函数。
理论分析
| \(x\) | \(x_0\) | \(x_1\) | \(\cdots\) | \(x_{n-1}\) | \(x_n\) |
|---|---|---|---|---|---|
| \(f(x)\) | \(f(x_0)\) | \(f(x_1)\) | \(\cdots\) | \(f(x_{n-1})\) | \(f(x_n)\) |
记\(h_i=x_{i-1}-x_i\quad,h=\max\limits_{0\le i\le n-1}\{h_i\}\)在\([x_i,x_{i+1}]\)上进行线性插值，得到\(L_{1,i}(x)=f(x_i)+f[x_i,x_{i+1}](x-x_i)\)根据误差余项公式，子区间上的插值误差余项为\(f(x)-L_{1,i}(x)=\frac{1}{2}f''(\xi)(x-x_i)(x-x_{i+1})\quad,\xi_i\in(x_i,x_{i+1})\)
因此小区间上的误差估计为\(\max\limits_{x_i\le x\le x_{i+1}}|f(x)-L_{1,i}(x)|\le\frac{h^2_i}{8}\max\limits_{x_i\le x\le x_{i+1}}|f''(x)|\)
令\(\widetilde{L}_1(x)=\cases{L_{1,0}(x),\qquad x\in[x_0,x_1)\\L_{1,1}(x),\qquad x\in[x_1,x_2)\\\cdots\\L_{1,n-2}(x),\quad x\in[x_{n-2},x_{n-1})\\L_{1,n-1}(x),\quad x\in[x_{n-1},x_n)}\)就得到了分段线性插值函数\(\widetilde{L_1}(x)\)，它的误差(整体误差)为
\(\begin{aligned}\max\limits_{a\le x\le b}|f(x)-\widetilde{L}_1(x)|&=\max\limits_{0\le i\le n-1}\max\limits_{x_i\le x\le x_{i+1}}|f(x)-\widetilde{L}_{1,i}(x)|\\&\le\max\limits_{0\le i\le n-1}\frac{h^2_i}{8}\max\limits_{x_i\le x\le x_{i+1}}|f''(x)|\\&\le\frac{h^2}{8}\max\limits_{a\le x\le b}|f''(x)|\end{aligned}\)
3）分段线性插值多项式的总结
优点：能消除高次插值的过分振荡和不收敛现象。
缺点：在插值函数的光滑性方面有所欠缺。
5.4.4 样条插值与三次样条插值
3）三次样条函数的高效计算
关键点：假设\(M_j=S''(x_j)\)，称之为力矩。
对小区间\([x_j,x_{j+1}]\)来说，\(M_j,M_{j+1}\)足够表示出样条函数的2阶导数，并且同下一个区间\([x_{j+1},x_{j+2}]\)共用同一个力矩\(M_{j+1}\)
根据Lagrange插值，在小区间\([x_j,x_{j+1}]\)上，有\(S''(x)=M_j\frac{x_{j+1}-x}{h_j}+M_{j+1}\frac{x-x_j}{h_j},\qquad x\in[x_j,x_{j+1}]\)
积分有\(S'(x)=-M_j\frac{(x_{j+1}-x)^2}{2h_j}+M_{j+1}\frac{(x-x_j)^2}{2h_j}+A_j\)，其中\(A_j\)是待定的常数
再次积分得到样条函数为\(S(x)=M_j\frac{(x_{j+1}-x)^3}{6h_j}+M_{j+1}\frac{(x-x_{j})^3}{6h_j}+A_jx+B_j\)
通过\(S(x_j)=y_j,S(x_{j+1})=y_{j+1}\)，求解\(A_j,B_j\)，发现是关于\(M_j\)的表达式。
再根据\(S'(x_j-0)=S'(x_j+0)\)列写\(M_{j-1},M_j,M_{j+1}\)
接着对\(S'(x_j-0)=S'(x_j+0)\)化简出等式的系数设为参数，而后会得到一个严格对角占优的三对角系统，即
\(\cases{2M_0+M_1=d_0\\\mu_jM_{j-1}+2M_j+\lambda_jM_{j+1}=d_j,\qquad j=1,2,\cdots,n-1,\\M_{n-1}+2M_n=d_n}\)
定义参数：
\(\cases{h_j=x_{j+1}-x_j,\qquad\qquad\qquad j=0:n-1,\\\lambda_0=1,\\d_0=\frac{6}{h_0}(\frac{y_1-y_0}{h_0})-y_0',\\\lambda_j=\frac{h_j}{h_{j-1}+h_j},\qquad\qquad\qquad\quad j=1:n-1,\\\mu_j=1-\lambda_j=\frac{h_{j-1}}{h_{j-1}+h_j},\qquad\quad\quad j=1:n-1,\\d_j=\frac{6}{h_{j-1}+h_j}(\frac{y_{j+1}-y_j}{h_j}-\frac{y_j-y_{j-1}}{h_{j-1}}),\quad j=1:n-1,\\\mu_n=1,\\d_n=\frac{6}{h_{n-1}}(y_n'-\frac{y_n-y_{n-1}}{h_{n-1}}).}\)
5.5 函数逼近
5.5.1 函数逼近简介
1）范数与距离
设X是一个线性空间，假设有函数\(||·||:X\rightarrow R\)，它满足：
①\(||x||\ge0,||x||=0\Leftrightarrow x=0\)
②\(||\alpha x||=\alpha\cdot||x||,\alpha\in R\)
③\(||x+y||\le||x||+||y||\)
则称\(||·||\)是X上的范数，定义了范数的线性空间被称为线性赋范空间。其中常用范数为
\(||f||_1=\int_a^b|f(x)|\mbox{d}x,\quad||f||_\infty=\max\limits_{a\le x\le b}|f(x)|,\quad||f||_2=\sqrt{\int_a^b[f(x)]^2\mbox{d}x}\)
2）最佳逼近定义
设X是一个线性赋范空间，\(M\subset X,f\in X\)，若M中的元素\(\varphi\)满足：\(||f-\varphi||\le||f-\psi||, \forall\psi\in M\)，则称\(\varphi\)为f在M中的最佳逼近元。
选择无穷范数时，得到最佳一致逼近；
选择2-范数时，得到最佳平方逼近。
5.5.2 最佳一致逼近简介
1）最佳一致逼近多项式
对函数来说，无穷范数度量的就是最大误差，即\(||f-g||_\infty=\max\limits_{a\le x\le b}|f(x)-g(x)|\)两个函数在某区间上的“最大”差别很小，二者的“整体”差别就很小，这也是一致的含义。所谓最佳一致逼近，就是求最大误差最小的逼近函数。
定义5.8，设\(f\in C[a,b]\)，若\(\exists p_n\in P_n\)，使得对\(\forall q_n\in P_n\)，有
\(||f-p_n||_\infty\le||f-q_n||_\infty\)，
则称\(p_n(x)\)是f(x)的n次最佳一致逼近多项式。
定理5.8 设\(f\in C[a,b]\)，则它的n次最佳一致逼近多项式存在且唯一。
定义5.9，设\(g\in C[a,b]\)，如果\(\exists x_k\in[a,b]\)使得
\(|g(x_k)|=||g||_\infty\)，则称\(x_k\)为g(x)在[a,b]上的偏差点。
5.5.3 最佳平方逼近
1）为什么要研究最佳平方逼近
最佳一致逼近考虑的是整个区间上绝对误差的最大值，最佳一致逼近反而不能很好地反映真实情况。
2）内积与范数
设X是一个线性空间，对\(\forall x,y\in X\)，都有唯一的师叔与之对应，我们记该实数为\((x,y)\)，若它满足：
①\(\forall x,y\in X\)，有\((x,y)=(y,x)\)； ②\(\forall x,y\in X,\lambda\in R\)，有\((\lambda x,y)=\lambda(x,y)\)；
③\(\forall x,y,z\in X\)，有\((x+y,z)=(x,z)+(y,x)\)；④\(\forall x\in X\)，有\((x,x)\ge 0\)且\((x,x)=0\Leftrightarrow x=0\)
则X称为内积空间，又称Hilbert空间。二元运算\((·,·)\)称为内积运算，简称内积，它是一个具有对称性的双线性函数。
常用的内积有两个：①\(R^n:(x,y)=\sum\limits_{i=1}^{n}x_iy_i\)；②\(C[a,b]:(f,g)=\int_a^bf(x)g(x)\mbox{d}x\)
4）离散情形的最佳平方逼近
\(\begin{bmatrix}(\varphi_0,\varphi_0)&\cdots&(\varphi_0,\varphi_m)\\(\varphi_1,\varphi_0)&\cdots&(\varphi_1,\varphi_m)\\\vdots&\ddots&\vdots\\(\varphi_m,\varphi_0)&\cdots&(\varphi_m,\varphi_m)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_m\end{bmatrix}=\begin{bmatrix}(y,\varphi_0)\\(y,\varphi_1)\\\vdots\\(y,\varphi_m)\end{bmatrix}\)
5）超定方程组的最小二乘解
超定方程组的正规方程组为：\(A^TAx=A^Tb\)
6）连续情形的最佳平方逼近
\(\begin{bmatrix}(\varphi_0,\varphi_0)&\cdots&(\varphi_0,\varphi_m)\\(\varphi_1,\varphi_0)&\cdots&(\varphi_1,\varphi_m)\\\vdots&\ddots&\vdots\\(\varphi_m,\varphi_0)&\cdots&(\varphi_m,\varphi_m)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_m\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_m)\end{bmatrix}\)
其中\((\varphi_i,\varphi_j)=\int_a^b\varphi_i(x)\varphi_j(x)\mbox{d}x,\quad(f,\varphi_i)=\int_a^bf(x)\varphi_i(x)\mbox{d}x\)
若基函数\(\varphi_i(x)=x^i(i=0,1,\cdots,m)\)，那么\(p(x)\)称为\(f(x)\)在区间\([a,b]\)上的m次最佳平方逼近多项式。
标签：le,frac,逼近,插值,varphi,cdots,第五章,bmatrix From： https://www.cnblogs.com/tseyublog/p/16938946.html