数值分析基础

准确性：误差分析，输入数据误差，舍入误差和截断误差。

稳定性：条件数分析，输出误差除以输入误差，包括问题本身（病态）和算法过程的稳定性。

收敛性：范数分析，向量范数，矩阵范数，柯西不等式。

Lagrange, 直接利用多项式空间的基函数$l_i(x_j)=\delta_{ij}=\prod_{j=0,j\neq i}^{n}\frac{x-x_j}{x_i-x_j}=\frac{\omega_{n+1}(x)}{(x-x_i)\omega_{n+1}'(x_i)}$构造公式$L_n(x)=\sum_{i=0}^nf_il_i(x)$，具有微分型余项$R(x)=f(x)-L_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\omega_{n+1}(x)$。

Newton：利用均差$f[x_0,...,x_k]=\frac{f[x_0,...,x_{k-1}]-f[x_0,...,x_{k-1}]}{x_i-x_k}$构造增量公式$L_n(x)=f[x_0]+...+f[x_0,...,x_k]\omega_k(x)$，具有均差型余项，并且对于等距节点还可以利用差分使公式简化$L_n(x_0+th)=\sum_{k=0}^{n}\binom{t}{k}\Delta^kf_0$。

Peano余项泛函：可以确切给出余项公式。

Hermite：给定各个节点的值与导数，同样可以利用基函数（包括导函数）来处理。

分段插值：为了避免高次插值的Runge现象，采用分段低次插值来取得一致收敛的插值函数。

三次样条：在区间上连续可导的三次多项式，满足边界条件，例如等于给定导数值。利用边界条件形成三对角方程组，从而解得各个区间上的样条参数

B-样条：一组基函数，满足$B_i^m(t)=0, t\in(-\infty,x_i]\bigcup [x_{i+m+1},\infty)\;\int_{x_i}^{x_{i+m+1}}B_i^m(t)dt=1$具有递推关系：$B_i^m(t)=\frac{m+1}{m}(\frac{t-x_i}{x_{i+m+1}-x_i}B_i^{m-1}(t)+\frac{x_{i+m+1}-t}{x_{i+m+1}-x_i}B_{i+1}^{m-1}(t))$

函数逼*：对于$f\in X$，求$p\in M$，使得f, P之差在某种量度下最小。通常X=C[a, b]，M为便于计算的函数集合。常用量度有极大范数、*方范数两种，分别称为极大逼*和*方逼*。为了计算便利，可以引入带权的量度函数。以权函数非零定义域覆盖逼*函数的程度，可以区分为全域逼*和局域逼*。

$\min_{p\in M}\int_a^b\rho(\tau )\left \| f-p \right \|_2d\tau$。这里$\left \| f\right \|_2=\sqrt{\int_a^b\rho(x)[f(x)]^2dx}$

函数插值：插值是一种简单的函数逼*。一般情况下，只知道若干f(t_i)，M一般为多项式，而权函数$\rho(t)$为$\delta(t_i - t_j)$，其逼*量度一般应为零。对于分段插值而言，其逼*函数在不同分段上具有不同的表达式，因而也有不同的权函数。此时一般对p_i(t)有连续性要求。特别地，当M为正交多项式，称为正交逼*。

$\min_{p\in M}\int_a^b\delta_i(t_i-\tau_i)\left \| f-p \right \|_2d\tau$

函数微分逼*：对于这种问题，被逼*函数以微分形式给出，是用数值方法求解微分方程的基本原理。当权函数$\rho(t)$为$\delta(t_i - t_j)$的时候，为有限差分法。

$\min_{p\in M}\int_a^b\rho(\tau )\left \| f^{(n)}-p^{(n)}\right \|_2d\tau$

正交多项式：$(f,g)=\int_a^b\rho(x)f(x)g(x)dx=0$，在区间[-1,1]上，例如：

• Legendre多项式：$\rho(x)=1$
• Chebyshev多项式：$T_n(x)=cos(n arccos x)$，$\rho(x)=\frac{1}{\sqrt{1-x^2}}$
• Laguerre多项式：$\rho(x)=e^{-x}$
• Hermite多项式：$\rho(x)=e^{-x^2}$

多项式序列有递推关系：$\varphi_{n+1}(x)=(\alpha_nx+\beta_n)\varphi_{n}(x)+\gamma_{n-1}\varphi_{n-1}(x)$

最佳*方逼*：$\left \|f-s^* \right \|_2=\inf_{s\in\Phi}\left \|f-s \right \|_2$。f在正交函数空间$\Phi$中的最佳*方逼*函数为：$s_n^*(x)=\sum_{j=0}^na_j^*\phi_j(x)$

最佳*方逼*问题离散化之后，称为最小二乘问题：$\arg \min_{s\in\Phi}\sum_{j=0}^m\rho(x_j)[f(x_j)-s(x_j)]^2$

最佳一致逼*：$\left \|f-s^* \right \|_{\infty}=\inf_{s\in\Phi}\left \|f-s \right \|_{\infty}$。$s_n^*$是$f\in C[a,b]$的最佳一致逼*的充要条件（Chebyshev定理）是[a,b]上至少有n+2个正负偏差点。

Chebyshev节约化：对于多项式$p_n(x)=a_nx^n+q(x)$这里q(x)为次数小于n的多项式，那么最佳一致逼*：$p_{n-1}^*(x)=p_n(x)-a_n2^{1-n}T_n(x)$

Newton-Cotes积分：先插值，再求积分。n=1为梯形公式，n=2为Simpson公式。

Gauss积分：通过选择采样点，提高积分公式的精度。$f(x)=\sum_{k=1}^{n}f(x_k)l_k(x)+f[x_1,...,x_n,x]\omega(x)$给定权函数为$\rho$的正交多项式序列$g_j\;f[x_1,...,x_n,x]=\sum_{k=0}^{n-1}c_kg_k(x)\Rightarrow R_n[f]=\sum_{k=0}^{n-1}c_k\int_a^b\rho(x)\omega(x)g_k(x)dx$在$g_k$的零点采样，精度可到2n-1。

Romberg积分公式也称为逐次分半加速法，是一个递推模式（Richardson外推）。以梯形法$T_n$为例，$S=\frac{4}{3}T_{2n}-\frac{1}{3}T_n$可以提高到Simpson方法的精度。

蒙特卡洛积分：对于概率密度f(x)求积分

• 频率法：生成满足密度f(x)的变量x，统计是否落入给定区间[a,b]。
• 期望法：生成满足密度g(x)的变量x，计算*均值$\frac{1}{N}\sum\frac{f(x)}{g(x)}$

非线性方程组的数值解

方程$F(x)=0$，改造成迭代格式$x=\Phi(x)$,求不动点：$x^*=\Phi(x^*)$

Brouwer不动点定理：设$\Phi:D\subset R^n\to R^n,\Phi$在有界闭集$D_0\subset D$上连续，且$\Phi(X)\subset X$，则$\Phi$在$D_0$中必存在不动点。

p阶收敛：$\lim_{k\to \infty}\frac{\left \| x^{k+1}-x^k \right \|}{\left \| x^k-x^* \right \|^p}=C$

Lipschitz条件：$\left \| \Phi(x)-\Phi(x^*) \right \|\leqslant L\left \| x-x^* \right \|$

牛顿法：$\Phi(x)=x-(F'(x))^{-1}F(x)$，对F'(x)采用*似方法，则称为拟牛顿法。

初值问题

$f(t,x,\dot{x})=0, f(t_0,x_0,\dot{x}_0)=0$。通过对时间t离散化，用数值微分代替$\dot{x}$，转换成非线性方程组。

• 欧拉方法：$\dot{x}=\frac{x_{i+1}-x_i}{\Delta t_{i+1}}$
• 线性两步方法：$\dot{x}=\frac{1}{2}(\frac{x_{i+1}-x_i}{\Delta t_{i+1}}+\frac{x_i-x_{i-1}}{\Delta t_i})$
• 梯形方法：$\dot{x}=\frac{1}{2}(\frac{x_{i+1}-x_i}{\Delta t_{i+1}}+\dot{x}_i)$

算法性能

• 局部截断误差：泰勒展开之后，减去泰勒级数，得到的几阶无穷小。
• 收敛性：$\lim_{\Delta t\to 0}x_n=x(t_n)$
• 绝对稳定性：用算法求解$y'=\lambda y \Rightarrow y_{n+1}=E(\lambda h)y_n$。如果$\left | E(\lambda h) \right |<1$，称算法绝对稳定。

参考文献

• 关冶、陆金甫，数值分析基础，高等教育出版社，1994