Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
1 | $ hexo new "My New Post" |
More info: Writing
1 | $ hexo server |
More info: Server
1 | $ hexo generate |
More info: Generating
1 | $ hexo deploy |
More info: Deployment
最近完成了一些审稿任务，有了一些审稿心得，大致总结一下，作为以后审稿和论文写作的参考。
审阅一篇论文，主要从以下几个方面进行评价
（未完待续…）
使用多项式逼近函数在数值分析中属于基本问题，这是因为多项式具有良好的性质，其函数值的计算只要通过有限次加减乘除即可完成，且导数和原函数仍是多项式。多项式在函数逼近中的地位可以由Weierstrass逼近定理体现，其证明过程参见Weierstrass逼近定理证明。
【Weierstrass逼近定理】对于$f(x) \in C[a,b]$，有
这一定理说明，定义在闭区间上的连续函数可以使用多项式来逼近，并且逼近的效果可以充分好。
用多项式逼近一般函数的方法可以分为两种：多项式插值和多项式逼近。
一个多项式插值问题的一般性描述如下：
对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为
需要在区间$[a,b]$上求一个多项式$P(x)$，使得
在这一描述中，$x_0,x_1,…,x_n$称为插值节点，$f(x)$称为被插函数，$P(x)$称为插值多项式，$P(x_i)=y_i$称为插值条件。对于这一描述，需要解决两个问题：满足这一描述的多项式是否存在？如果多项式存在，是否唯一？下述定理解决了存在性和唯一性的问题，其证明过程参见插值多项式的存在性和唯一性证明。
【定理】当$n+1$个插值节点$x_0,x_1,…,x_n$互不相同时，一定存在唯一的次数不超过$n$的多项式$P(x)$满足条件$P(x_i)=y_i$.
该定理给出了通过解线性代数方程组得到多项式$P(x)$的系数的方法，但是计算量较大，该计算问题一般也是病态的，所以并不适合求解插值多项式$P(x)$。下面介绍求解插值多项式的更有效的方法。
记所有次数不超过$n$的实系数多项式组成的线性空间为$\mathbb{P}_n$，那么多项式插值问题实际上就是寻找元素$P(x)$，使其满足$P(x_i)=y_i$。
为寻找满足$P(x_i)=y_i$的多项式$P(x)\in \mathbb{P}_n$，自然地希望构造一组$\mathbb{P}_n$的基函数$\{l_i(x)\}_{i=0}^n$，满足
容易构造出$l_i(x)$的表达式为
这样，由$\{l_i(x)\}$构造的多项式$P(x)$称为$n$次Lagrange插值多项式$L_n(x)$，有
使用$L_n(x)$逼近$f(x)$的截断误差定义为$R_n(x)=f(x)-L_n(x)$，称为余项。
下面不加证明地分别给出关于余项与收敛性的定理。
【定理】对于被插函数$f(x) \in C^{(n+1)}[a,b]$和互不相同的插值节点$x_0,x_1,…,x_n$，有
【定理】对于复函数$f(z)$，如果存在$r_0 > \frac{3}{2}(b-a)$，使得$f(z)$在$B_{r_0}(\frac{a+b}{2})$内解析，则$L_n(x)$在$[a,b]$内一致收敛于$f(x)$，其中$B_{r_0}(\frac{a+b}{2})$指在复平面上圆心在$\frac{a+b}{2}$且半径为$r_0$的圆
对于Lagrange插值方法来说，已知$n$次插值多项式$L_{n+1}$，如果想要再增加一个插值节点$x_{n+1}$，就需要重新计算$\{l_i(x)\}$，效率较低。为了解决这一问题，自然地想到差分的方法，即构造一组新的$\mathbb{P}_n$的基函数，能够通过差分的方式由低阶基函数向高阶基函数构造。这样，在增加新的插值节点时，只需要多构造一个更高阶的基函数即可，不需要重新计算所有基函数。根据这一思路，递归地构造$n$阶差商$f[x_0,x_1,…,x_n]$。
$0$阶差商：$f[x_i] = f(x_i), i=0,1,…,n$
$k$阶差商：
这样递归定义的差商具有如下性质（不加证明给出）
【性质1】$f(x)$在节点$x_0,x_1,…,x_n$上的$n$阶差商的解析式为
【性质2】差商的值与节点的排列顺序无关，不妨设$\{i_0,i_1,…,i_n\}$是$\{0,1,…,n\}$的任意排列，则
【性质3】如果$f(x)$存在$n$阶导数，则
注意到，一组差商$\{f[x_0],f[x_0,x_1],…,f[x_0,x_1,…,x_n]\}$是$\mathbb{P}_n$的一组基，由此构造的多项式$P(x)$称为$n$次Newton插值多项式$N_n(x)$，有
根据【性质3】，不难发现
这与下述Lagrange插值余项的形式很相似
可以发现，当增加一个插值节点$x_{n+1}$，插值多项式从$N_n(x)$变为$N_{n+1}(x)$时，增加的部分与$n$阶Lagrange插值多项式$L_n(x)$对应的余项同阶（都为$n+1$阶），是对原有逼近结果的一种”修正“，这就是Newton插值包含的”差分“含义。因此，Newton可以通过逐渐添加插值节点的方式，逐渐增加更高阶的部分，从而逐渐逼近函数$f(x)$。
Newton插值多项式的余项为
由于插值多项式的唯一性，Newton插值多项式的余项与Lagrange插值多项式的余项实际上是同一余项的不同表现形式，而前者在$f(x)$的导数不存在时仍有意义，适用范围更广。
从Lagrange插值和Newton插值的余项分析中可以发现，采用更高阶的插值方法，得到的插值多项式$P(x)$的余项越小，也就更加逼近函数$f(x)$。但是，虽然$P(x)$在很多个点上严格等于$f(x)$，但整体的逼近效果不一定好。记
作为表示插值节点疏密程度的参数。注意到$h\rightarrow 0$意味着$n\rightarrow \infty$，而$n\rightarrow \infty$不一定有$h\rightarrow 0$。这样，我们采用等距插值节点
时，$h\rightarrow 0$与$n\rightarrow\infty$等价，此时Lagrange插值得到的插值多项式记为$L_h(x)$。根据函数逼近理论，不加证明地认为：即使$f(x)$无穷次可微，也不能得出
这种现象称为Runge现象。这说明高次的插值多项式的数值稳定性很差，计算的舍入误差会被高阶多项式迅速放大，最终对计算结果产生灾难性的影响。
既然不能使用高次的插值多项式逼近函数，可以将原先的区间$[a,b]$分割成$n$个子区间$[x_i,x_{i+1}]$，在每个子区间内函数的变化程度可能相较于原区间更小，因此可以分段对每个子区间使用低次的插值多项式逼近函数。
分段线性插值问题的确切描述如下：
对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为
需要在区间$[a,b]$上求一个分段线性插值函数$\phi_h(x)$，使得
【条件1】$\phi_h(x) \in C[a,b]$
【条件2】在每个子区间$x_i,x_{i+1}$上$\phi_h(x) \in \mathbb{P}_1$
【条件3】$\phi_h(x_i)=y_i,i=0,1,…,n$
不妨记满足【条件2】的所有函数构成的线性空间为$\Phi_h$，为了构造分段线性插值函数$\phi_h(x)$，一个自然的想法是首先构造$\Phi_h$的一组基函数$\{l_i(x)\}_{i=0}^n$，再通过【条件3】对基函数配置系数，最终得到$\phi_h(x)$。
在每个子区间内，由于$\phi_h(x) \in \mathbb{P}_1$，则应该有$l_i(x)\in \mathbb{P}_1$。于是，可以使用Lagrange插值的思想构造基函数如下
因此，分段线性插值函数$\phi_h(x)$可以写为
这样构造出的插值函数$\phi_h(x)$，【条件1】由【条件3】中隐含的“相邻区间的共同端点的函数值相同”满足，【条件2】由求得的$\mathbb{P}_1$的基函数满足，【条件3】由基函数的系数满足。
下面不加证明地给出分段线性插值的余项分析
【定理】设被插函数$f(x) \in C^2[a,b]$，则
其中$M=\max_{x\in[a,b]}|f^{\prime\prime}(x)|$.
此定理说明，对于二阶连续的被插函数$f(x)$，分段线性插值函数$\phi_h(x)$一致收敛到被插函数$f(x)$。
分段线性插值函数具有一个明显的缺点，即不够光滑，因此可以在插值数据中添加被插函数在插值节点上的导数值，这样的插值问题称为Hermite插值。特别地，对于分段三次Hermite插值，其插值函数不仅本身连续，一阶导数也连续，比分段线性插值函数更加光滑。
作为示例，下面仅讨论分段三次Hermite插值，其具体描述如下
对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值和导数值为
需要在区间$[a,b]$上求一个分段三次Hermite插值函数$H_h(x)$，使得
【条件1】$H_h(x) \in C^1[a,b]$
【条件2】在每个子区间$x_i,x_{i+1}$上$H_h(x) \in \mathbb{P}_3$
【条件3】$H_h(x_i)=y_i,H_h^{\prime}(x_i)=m_i,i=0,1,…,n$
同样使用Lagrange插值的思想构造满足【条件2】的一组基函数$\{h_i,\hat{h}_i\}_{i=0}^n$如下，其基本思路见两点三次Hermite插值的求解过程
因此，分段三次Hermite插值函数$H_h(x)$可以写为
这样构造出的插值函数$H_h(x)$，【条件1】中的“函数连续”和“一阶导数连续”分别由【条件3】中隐含的“相邻区间的共同端点的函数值相同”和“相邻区间的共同端点的一阶导数值相同”满足，【条件2】由求得的$\mathbb{P}_3$的基函数满足，【条件3】由基函数的系数满足。
下面不加证明地给出分段三次Hermite插值的余项分析
【定理】设被插函数$f(x) \in C^4[a,b]$，则
其中$M=\max_{x\in[a,b]}|f^{(4)}(x)|$.
此定理说明，分段三次Hermite插值函数$H_h(x)$的截断误差的量级为$O(h^4)$。
$k$次样条插值问题的描述为：
对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为
需要在区间$[a,b]$上求一个分段线性插值函数$S_k(x)$，使得
【条件1】$S_k(x) \in C^{k-1}[a,b]$
【条件2】在每个子区间$[x_i,x_{i+1}],i=0,1,…,n-1$上$S_k(x) \in \mathbb{P}_k$
【条件3】$S_k(x_i)=y_i,i=0,1,…,n$
值得注意的是，分段线性插值就是一次样条插值。而三次样条插值函数与Hermite插值函数同为分段三次多项式插值函数，不仅在每个插值节点的一阶导数连续，在每个插值节点的二阶导数也连续，比Hermite插值函数更加光滑。
作为示例，下面仅讨论三次样条插值函数$S_3(x)$。
为寻找同时满足【条件1】、【条件2】和【条件3】的插值函数$S_3(x)$，首先联想到条件更弱的分段三次Hermite插值。根据分段三次Hermite插值的分析，一定存在插值函数$S_3(x) \in C^1[a,b]$满足【条件2】和【条件3】，即一定存在满足【条件2】和【条件3】，且一阶导数存在的插值函数。
不妨设$S_3^{\prime}(x_i)=m_i$，其中$m_i$是未知数。这样，可以利用分段三次Hermite插值的基函数将$S_3(x)$表示为
自此，【条件2】和【条件3】已由基函数与其系数满足，而【条件1】则需要通过定下作为未知数的$m_i$来满足。也就是说，需要找到一组$m_i$，以$y_i$和$m_i$作为参数，利用分段三次Hermite插值得到的$S_3(x) \in C^2[a,b]$。
可以求出$S_3(x)$在每个子区间中的二阶导数表达式，记$\Delta x_i = x_{i+1} - x_i$，则有
于是可以得到
要使$S_3(x) \in C^2[a,b]$，只要
由于一组$m_i$共有$n+1$个未知数，而上述方程共有$n-1$个，因此还需要在$x_0$和$x_n$处各增加两个边界条件。这样的边界条件有很多种，而常用的边界条件共有下列三种
上诉三种边界条件任取其一，就能够与之前的方程组一起求解$m_i$。值得注意的是，加入边界条件的方程组的系数矩阵是三对角方程组或其变形，可以使用追赶法快速求解。
在求解得到一组$m_i$后，就可以利用分段三次Hermite插值的方法得到满足【条件1】、【条件2】和【条件3】的插值函数$S_3(x)$。
下面不加证明地给出三次样条插值的余项分析
【定理】设被插函数$f(x) \in C^4[a,b]$，则
其中$C_k$为常数.
多项式逼近与多项式插值不同，并非寻求某一函数与原函数在某些点上严格相等，而是寻求在某一范数的意义下，与原函数误差最小的某一函数，其一般性描述如下：
对于定义在区间$[a,b]$中的一般函数$f(x)$及某一范数$||\cdot ||$，寻找$P_0(x) \in \mathbb{P}_n$，使得
常用的范数有
当范数取为$L^{\infty}$范数时，多项式逼近问题称为最佳一致逼近问题。
对于最佳一致逼近问题，首先要解决存在性和唯一性的问题。设$f(x)\in C[a,b]$，令
为$P(x)$与$f(x)$的偏差，令
为$\mathbb{P}_n$对$f(x)$的最小偏差或最佳逼近。显然有$E_n \geq E_{n+1} \geq \cdots$，并且由Weierstrass定理保证$\lim_{n\rightarrow\infty}E_n=0$。
最佳一致逼近问题需要关心的存在性与一致性的问题是：是否存在$P_0 \in \mathbb{P}_n$，使得$\Delta(P_0)=E_n$；如果存在，称$P_0$为$f(x)$在$\mathbb{P}_n$中的最佳一致逼近多项式，那么这样的$P_0$是否唯一？
【Borel存在定理】对$\forall f(x) \in C[a,b]$，$\exists P_0 \in \mathbb{P}_n$，使得
由Weierstrass逼近定理，有
最小二乘问题是一类
三对角方程组是指系数形如
的方程组。当系数矩阵是严格对角占优矩阵时，即满足
时，可以使用追赶法求解方程组，计算量很小。
追赶法的核心算法是矩阵分析中常用的LU分解，对于给定方程组$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$，其系数矩阵为三对角矩阵，可以利用LU分解得到如下形式
其中
因此有下述等式
现已知$a_i,b_i,c_i$，由$\gamma_i = a_i$可求得$\gamma_i$。观察到，由$\alpha_i \beta_i = c_i$有，若知$\alpha_i$可求得$\beta_i$，由$\alpha_i + \gamma_i \beta_{i-1} = b_i$有，若知$\beta_i$可求得$\alpha_{i+1}$。而由$\alpha_1 = b_1$可求得$\alpha_1$，从而可以依次求出$\alpha_i$和$\beta_i$。
要想求解$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$，只需要求解$\boldsymbol{L}\boldsymbol{y}=\boldsymbol{d}$和$\boldsymbol{U}\boldsymbol{x}=\boldsymbol{y}$。
对于$\boldsymbol{L}\boldsymbol{y}=\boldsymbol{d}$，有
从而有下述等式
可以依次求出$y_1,y_2,…,y_n$。
对于$\boldsymbol{U}\boldsymbol{x}=\boldsymbol{y}$，有
从而有下述等式
可以依次求出$x_n,x_{n-1},…,x_1$。
这样，就求出了方程组$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$的解。这样的，先依次正向求出$y_1,y_2,…,y_n$（追），再依次逆向求出$x_n,x_{n-1},…,x_1$（赶）的方法称为追赶法。
两点三次Hermite插值是指：已知被插函数$f(x)$在区间$[x_0,x_1]$的两个端点的函数值和导数值为
需要寻找一个三次多项式$H_3(x)$满足
记区间$[x_0,x_1]$上三次多项式空间为$\mathbb{P}_3$，首先求其一组基函数$\{\alpha_0,\alpha_1,\beta_0,\beta_1\}$在$[x_0,x_1]$上的表达式，使之满足
显然基函数一定都是三次多项式。
由$\alpha_0(x_1)=0$和$\alpha_0^{\prime}(x_1)=0$，有$(x-x_1)^2 \mid \alpha_0(x)$，则$\alpha_0(x)=(ax+b)(x-x_1)^2$。
由$\alpha_0(x_0)=1$，有$(ax_0+b)(x_0-x_1)^2=1$；由$\alpha_0^{\prime}(x_0)=0$，有$a(x_0-x_1)+2(ax+b)=0$。
于是，$a=-\frac{2}{(x_0-x_1)^3},b=\frac{3x_0-x_1}{(x_0-x_1)^3}$，经调整后得
同理有
由$\beta_0(x_1)=0$和$\beta_0^{\prime}(x_1)=0$，有$(x-x_1)^2 \mid \beta_0(x)$；由$\beta_0(x_0) = 0$，有$(x-x_0) \mid \beta_0(x)$，因此有$\beta_0(x)=c(x-x_0)(x-x_1)^2$。
由$\beta_0^{\prime}(x_0)=1$，有$c=\frac{1}{(x_0-x_1)^2}$，于是有
同理有
因此
一个插值逼近问题的一般性描述如下：
对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为
需要在区间$[a,b]$上求一个多项式$P(x)$，使得
下述定理解决了插值多项式$P(x)$的存在性和唯一性。
【定理】当$n+1$个插值节点$x_0,x_1,…,x_n$互不相同时，一定存在唯一的次数不超过$n$的多项式$P(x)$满足条件$P(x_i)=y_i$.
不妨设
由条件$P(x_i)=y_i$可以得到关于$a_n,a_{n-1},…,a_0$的线性代数方程组
其系数矩阵
是一个$n+1$阶的Vandermonde矩阵。由于$x_0,x_1,…,x_n$互不相同，Vandermonde矩阵$X$是非奇异矩阵。由Cramer法则，由于关于$a_n,a_{n-1},…,a_0$的线性代数方程组的系数矩阵$X$是非奇异矩阵，因此该线性代数方程组存在唯一解，即
Q.E.D.
当我们使用vscode登录远程服务器时，总会遇到一个问题，python程序难以像Pycharm那样方便地进行调试，只能使用print大法查看中间变量值。但其实vscode已经提供了调试python程序的方法，那就是launch.json文件。
打开vscode，在上方菜单栏中选择“运行 - 添加配置”，就能够打开launch.json文件，设置调试参数，如下方格式所示。version代表json文件的版本号，不需要理会；configurations代表具体的调试配置项。
1 | { |
下面来看看具体的调试配置项如何编写。
1 | # 运行程序时使用的命令行 |
1 | // 对应的配置项 |
还需要注意的是，在调试环境下，所有的文件名和文件夹名都需要使用完整的绝对路径，否则将会报错：文件/文件夹未找到/无法打开。
当需要运行分布式程序时，可能会使用到形如下述命令行。
1 | python -m torch.distributed.launch --nproc_per_node 8 train.py |
这时需要将program项更换为torch/distributed/launch.py的绝对路径，不需要python项，如下。
1 | { |
Weierstrass逼近定理：闭区间上的连续函数可被多项式逼近，使用数学语言叙述如下。
对于在闭区间$[a,b]$上连续的$f(x)$，有
其中$||f(x) - P(x)||_{\infty} = \max_{a \leq x \leq b}{|f(x) - P(x)|}$
显然，“$f(x)$可被多项式逼近”与“存在多项式序列一致收敛到$f(x)$”互为充分必要条件，后者叙述如下。
这里补充一致收敛的定义：
下面对Weierstrass逼近定理进行证明。
【引理1】如果函数$f_j(x)(j=1,…,J)$在$[a,b]$上可被多项式逼近，且$c_j\in \mathbb{R}(j=1,…,J)$，则$\sum_{j=1}^{J}{c_jf_j(x)}$在$[a,b]$上可被多项式逼近.
由于$f_j(x)(j=1,…,J)$在$[a,b]$上可被多项式逼近，则有
因此对于$\sum_{j=1}^{J}{c_jf_j(x)}$，存在多项式$\sum_{j=1}^{J}{c_jP_j(x)}$，有
Q.E.D.
【引理2】如果函数序列$\{f_n(x)\}$满足$\forall n$，$f_n(x)$在$[a,b]$上可被多项式逼近，并且$f_n(x) \rightrightarrows f(x)$，则$f(x)$在$[a,b]$上可被多项式逼近.
由于$f_n(x) \rightrightarrows f(x)$，则有
由于$\forall n$，$f_n(x)$在$[a,b]$上可被多项式逼近，因此$\forall n$，对于上述的$\varepsilon$，有
因此，结合上述两者，有
Q.E.D.
【引理3】$\forall c \in \mathbb{R}, \exists \{P_n(x)\}, s.t.P_n(x)\rightrightarrows|x-c|$，收敛半径为任意闭区间.
首先需要承认如下两个事实。
事实1：$(1+t)^{\alpha}$通过泰勒公式得到的幂级数展开式为$\sum_{n=0}^{\infty}{\begin{pmatrix}\alpha \\ n\end{pmatrix}t^n}$，其收敛半径为$[-1,1]$
事实2：$f(x)$的幂级数展开式的部分和序列$\{S_n(x)\}$在收敛半径内一致收敛到$f(x)$
基于事实1，可以有如下推导
基于事实2，如果令$\sum_{n=0}^{\infty}{\begin{pmatrix}\frac{1}{2} \\ n\end{pmatrix}(x^2-1)^n}$的部分序列和的序列为$\{S_n(x)\}$，那么应当有$S_n(x)\rightrightarrows |x|$。
根据【引理2】，由于$\{S_n(x)\}$是多项式序列，因此$|x|$在$[-1,1]$上可被多项式逼近，即
考虑从$\{S_n(x)\}$中挑选出新的序列$\{Q_n(x)\}$，使得序列$\{Q_n(x)\}$能够满足
这就是说，依次将$\varepsilon$设置为$\frac{1}{1},\frac{1}{4},\frac{1}{9},\frac{1}{16},…$，分别找到能够满足这些$\varepsilon$的$S_n(x)$，组成新的序列$\{Q_n(x)\}$。
由此，构造$P_n(x) = nQ_n(\frac{x-c}{n})$，则有
因此，只要使$\frac{x-c}{n} \in [-1,1]$，即$x \in [c-n,c+n]$这一段区间能够覆盖特定区间$[A,B]$，即$n > \max\{c-A,B-c\}$，就能够保证在任意闭区间$[A,B]$上，有
Q.E.D.
【引理4】$H(x)=\max\{x,0\}$在任意闭区间上可被多项式逼近.
根据【引理2】和【引理3】，$|x|$在任意闭区间上可被多项式逼近。
根据【引理1】，$H(x)=\frac{x+|x|}{2}$在任意闭区间上可被多项式逼近。
Q.E.D.
【引理5】如果$g(x)$在$[a,b]$上连续且分段线性，则$g(x)$可以表示为$g(x)=g(a)+\sum_{i=1}^{n}{c_iH(x-x_{i-1})}$，其中$x \in [a,b], c_i \in \mathbb{R}, i=1,2,…,n$
对于$g(x) \in C[a,b]$，如果存在$[a,b]$的分割$\Delta:a=x_0 < x_1 < … < x_n=b$，使得$g(x)$在$[x_{i-1}, x_{i}],i=1,2,…,n$均为线性函数，称$g(x)$在$[a,b]$上分段线性。
显然。
Q.E.D.
【引理6】对于$f(x) \in C[a,b]$，存在分段线性函数序列$\{P_n(x)\}$使得$P_n(x) \rightrightarrows f(x)$.
这一引理的一个充分条件是
其中$\omega_i = \max_{x_{i-1} < x < x_i}{f(x)} - min_{x_{i-1} < x < x_i}{f(x)}$，$\Delta x_i = x_i - x_{i-1}$。
这一充分条件在数学分析学科的定积分理论中是显然的，但为了保证博客的完整性，这里给出一个简要的证明。
根据Cantor定理（一致连续性定理），$f(x)$在$[a,b]$上连续，则在$[a,b]$上一致连续，即
不妨设$M_i = \max_{x_{i-1}\leq x\leq x_i}f(x) = f(x_{i}^{\prime}), m_i = \min_{x_{i-1}\leq x\leq x_i}f(x)=f(x_{i}^{\prime\prime})$，于是$\forall \varepsilon > 0, \exists \delta > 0, \forall \Delta:a=x_0 < x_1 < … < x_n = b$满足$\lambda(\Delta) < \delta$，则$\forall x_i^{\prime},x_i^{\prime\prime} \in [x_{i-1},x_i]$，有$|x_i^{\prime}-x_i^{\prime\prime}|<\varepsilon$，从而$M_i - m_i < \varepsilon$。其中$\lambda(\Delta)=\max_{1\leq i\leq n}(x_i - x_{i-1})$。
观察到$\omega_i = M_i - m_i$，于是有
Q.E.D.
【Weierstrass逼近定理】闭区间上的连续函数$f(x)$可被多项式逼近.
根据【引理6】，可以找到$[a,b]$上的一列分段线性函数$\{g_m(x)\}$，使得$g_m(x) \rightrightarrows f(x)$。
根据【引理5】，对于分段线性函数$g_m(x)$，存在$[a,b]$的分割$\Delta_m:a=x_0^{(m)} < x_1^{(m)} < … < x_n^{(m)}=b$，使得
根据【引理4】，$H(x-x_{i-1}^{(m)})$在$[a,b]$上可被多项式逼近。
根据【引理1】，$g_m(x)$因此在$[a,b]$上也可被多项式逼近。
根据【引理2】，$f(x)$在$[a,b]$上可被多项式逼近。
Q.E.D.
数值分析是一门偏工程的数学分支学科，其基本思想是“近似”，就是说当原问题无法精确求解或者精确求解代价太高时，可以使用近似的方法在低开销的情况下获得尽可能精确的解。这样的解称之为数值解，得到这样的解的方法称之为数值解法。
一般来说，一个好的数值解法应当符合如下评价标准：
简而言之，好的数值解法应当既“快”又“准”，而在具体的应用场景下对于二者的要求标准不同，需要加以权衡。
算法大致可以分为两类：一类是直接法，指在没有误差的情况下可以在有限步内得到精确解的算法；另一类是迭代法，指采取逐次逼近的方法来逼近问题的精确解，而任意有限步内都得不到精确解的算法。
对于直接法来说，运算量是衡量算法快慢的标志，而算法的计算复杂性则能够很好地估计算法的运算量。
对于迭代法来说，除了要估计每一次迭代的运算量，还要估计迭代多少次才能将数值解逼近到足够的精度内，这就需要对其收敛速度进行分析。假设某一迭代法产生的序列$\{x_k\}$收敛于$x$，且存在某个正数$r \in [1,\infty)$，使得
存在，则称算法是$r$阶收敛的。
特别地，如果$lim_{k\rightarrow\infty}\frac{||x_k-x||}{||x_{k-1}-x||}=0$，称为超线性收敛，如果$r>1$，则$r$阶收敛一定是超线性收敛。
在使用算法得到数值解后，需要评估其与精确解之间的差值有多少，要回答这一问题，需要进行敏度分析与误差分析。
敏度分析研究的是计算问题的固有属性对数值解精确度的影响，简单来说就是原始数据的微小变化会引起计算问题的数值解的多大变化。理想情况下，应当找到关系$g(\cdot)$，使得$f(x+\delta x) - f(x) = g(\delta x)$，然而找到这样的$g(\cdot)$是很困难的，通常的做法是：对于一个特定的$x$，在$\frac{|\delta x|}{|x|}$很小的情况下，找到一个尽可能小的正数$c(x)$使得
这样$c(x)$的大小就在一定程度上反映了微小扰动在$x$点处对$f(\cdot)$的影响程度，$c(x)$称为$f(\cdot )$在$x$点处的条件数；可以看出，当$f(\cdot )$在$x$点处可微时，$c(x) \approx \frac{|f^{\prime}(x)||x|}{|f(x)|}$。当$c(x)$很大时，称$f(\cdot )$在$x$点处是病态的；当$c(x)$较小时，称$f(\cdot )$在$x$点处是良态的。需要注意的是，计算问题$f(\cdot )$是否病态是计算问题$f(\cdot )$的固有属性，与算法无关。
误差分析研究的是计算方法对数值解精确度的影响，具体来说，计算方法引起的数值解误差来源于以下四个方面。
对于这些误差，可以使用前向误差分析和后向误差分析两种误差分析方法进行处理。前向误差分析是指对于数值解$\hat{y}$和精确解$y$，估计误差$\delta y = \hat{y} - y$的过程；后向误差分析是指对于数值解$\hat{y}$，认为$\hat{y} = f(x + \delta x)$，估计$\delta x$如$|\delta x| \leq |x|\varepsilon$的过程。
这样，通过对计算问题进行敏度分析以及对计算方法进行误差分析，可以对计算结果的精度进行如下估计。
由此可见，只有使用数值稳定的计算方法（$\varepsilon$较小）来求解良态的计算问题（$c(x)$较小），才能得到可靠的计算结果。
书接上文，昨天写完爬虫简易教程（一）后，室友连夜完成了他的种子爬虫1号。然而，在爬取的过程中，他发现有些网页链接并没有显式地写在网页中，我进一步确认后发现，网页链接是通过与后端数据库交互来获取，这样的动态页面就不能通过requests库来获取到所有需要的内容。为了解决这个问题，助力室友完成他的种子爬虫2号，这篇文章将介绍自动化测试工具selenium库，通过模拟浏览器的点击等操作实现链接的跳转，从而爬取到需要的内容。
这里仅介绍Chrome浏览器的配置方法，selenium库还支持包括Firefox浏览器、IE浏览器、Edge浏览器等主流浏览器，配置方法类似，不再赘述。
可以直接前往官网进行下载。
首先在Chrome浏览器的地址栏中输入chrome://version，查看Chrome浏览器的版本号，我的版本号是107.0.5304.88。
然后打开驱动器列表，找到适配浏览器版本号的最新的驱动器版本，我这里选择了107.0.5304.62版本。
将下载好的文件解压，得到chromedriver.exe文件，并将其放在与当前虚拟环境的Python解释器使用的python.exe文件相同的路径下。下面以Pycharm为例演示。
将鼠标悬浮在Pycharm窗口右下角解释器的位置。
可以显示解释器的路径，将chromedriver.exe文件放在同一路径下即可。
selenium库将浏览器自动化脚本进行封装，使其能够操纵浏览器实现启动、关闭、更改窗口大小、截屏、点击、悬浮、滚动等操作，就好像真的是用户在操作一样。
想要简单地使用selenium库实现网页爬取，可以参考以下代码。
1 | from selenium import webdriver |
如果想要获取并保存网页内容，可以使用如下代码。
1 | content = browser.page_source |
需要注意的是，一个Chrome()实例可以对应多个网页窗口的句柄，而对实例的任何操作都视为对实例中当前窗口的操作，正如一个浏览器中可以包含多个窗口，在浏览器中点击就视为在当前窗口点击。由于selenium有这样的特性，在实际运用时，不仅可以获取到网页窗口的内容，还可以与窗口甚至浏览器本身产生交互，从而达到更加灵活的效果。
在使用requests库时，只需要打开窗口就可以爬取内容，这也导致requests库只能用来爬取静态页面的内容。Selenium库相较于requests库的最大优势就在于能够模拟浏览器，与窗口中的各个元素交互，从而能够爬取到动态页面的内容。例如，当某些内容需要登录后才能查看时，就可以使用Selenium库模拟登录操作，”欺骗“服务器返回需要的内容。从理论上来说，Selenium库能够模拟真人对于浏览窗口的所有操作。
1 | #-> 获取页面基本属性 |
更多的Selenium模拟键盘、鼠标、触摸笔、滚轮的操作参见官方文档。
定位元素可以直接使用以下代码，css语法和xpath语法详见爬虫简易教程（一），Selenium定位元素的语法糖详见官方文档。
1 | element = browser.find_element(By.CSS_SELECTOR, 'element') |
与元素交互有五种基本命令，下面给出简单的介绍，更详细的介绍参见官方文档。
1 | #-> 点击操作（适用于任何元素） |
有时在定位元素时或与元素交互时会失败，这是由于存在iframe窗口。在这种情况下，需要先搜索并定位到iframe结点，切换到iframe窗口，再定位并与元素交互。
1 | iframe_node = browser.find_element(By.CSS_SELECTOR, 'iframe') |
如果想要切换出iframe窗口，可以使用以下代码。
1 | browser.switch_to.parent_frame() # 切换回上一级窗口 |
对于静态页面，在页面加载完成后，所有的页面元素就都可以定位；但是对于动态页面，由于存在懒加载等机制，需要定位的元素或是需要滚动到页面底部、或是需要等待一段时间才能够定位。因此，如果在打开一个页面后立即定位某元素，很有可能定位失败，需要设置等待时间使元素能够加载出来。
设置等待时间的方法一般有两种：显式等待和隐式等待。显式等待指的是无论如何都要等待一段时间，在这段时间之后再进行定位操作，隐式等待则设定一个超时阈值，在超时之前轮询元素，在超时之前找到元素或者达到超时阈值都会结束定位元素的操作。下面是示例代码。
1 | # 显式等待，在需要等待的位置插入 |
1 | #-> 打开指定网页 |
使用上述代码编写的selenium自动化脚本在运行时模拟浏览器打开和关闭各种窗口，如果在运行时不希望显示这些窗口，可以使用selenium的无界面模式。一般来说，在调试时使用有界面模式，在运行正常后转为无界面模式。
1 | # 创建无界面模式的选项 |
与requests库一样，Selenium库同样可以携带cookie信息访问服务器。
以www.baidu.com为例，F12、Network、刷新、点击www.baidu.com、Cookies，能够得到下述界面。
可以看到浏览器中cookie的表现形式，这里我们暂时只需要name和value。
同样地，使用爬虫简易教程（一）提到的方法提取cookie，能够得到下述界面。
可以发现两者是相互对应的。
Selenium库使用cookie的语法基于上述name和value，示例语法如下。
1 | # 添加cookie |