基本概念
如果$|x-x_A|leqslant 0.5 imes 10^{k-n}$，k为指数，则称xA为x的n位有效数字近似值。
准确性：误差分析，输入数据误差，舍入误差和截断误差。
稳定性：条件数分析，输出误差除以输入误差，包括问题本身（病态）和算法过程的稳定性。
收敛性：范数分析，向量范数，矩阵范数，柯西不等式。
数据插值
Lagrange, 直接利用多项式空间的基函数$l_i(x_j)=delta_{ij}=prod_{j=0,j eq 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}inom{t}{k}Delta^kf_0$。
Peano余项泛函：可以确切给出余项公式。
Hermite：给定各个节点的值与导数，同样可以利用基函数（包括导函数）来处理。
分段插值：为了避免高次插值的Runge现象，采用分段低次插值来取得一致收敛的插值函数。
三次样条：在区间上连续可导的三次多项式，满足边界条件，例如等于给定导数值。利用边界条件形成三对角方程组，从而解得各个区间上的样条参数
B-样条：一组基函数，满足$B_i^m(t)=0, tin(-infty,x_i]igcup [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))$
函数逼近
函数逼近：对于$fin X$，求$pin M$，使得f, P之差在某种量度下最小。通常X=C[a, b]，M为便于计算的函数集合。常用量度有极大范数、平方范数两种，分别称为极大逼近和平方逼近。为了计算便利，可以引入带权的量度函数。以权函数非零定义域覆盖逼近函数的程度，可以区分为全域逼近和局域逼近。
$min_{pin M}int_a^b ho( au )left | f-p ight |_2d au$。这里$left | f ight |_2=sqrt{int_a^b ho(x)[f(x)]^2dx}$
函数插值：插值是一种简单的函数逼近。一般情况下，只知道若干f(ti)，M一般为多项式，而权函数$ ho(t)$为$delta(t_i - t_j)$，其逼近量度一般应为零。对于分段插值而言，其逼近函数在不同分段上具有不同的表达式，因而也有不同的权函数。此时一般对pi(t)有连续性要求。特别地，当M为正交多项式，称为正交逼近。
$min_{pin M}int_a^bdelta_i(t_i- au_i)left | f-p ight |_2d au$
函数微分逼近：对于这种问题，被逼近函数以微分形式给出，是用数值方法求解微分方程的基本原理。当权函数$ ho(t)$为$delta(t_i - t_j)$的时候，为有限差分法。
$min_{pin M}int_a^b ho( au )left | f^{(n)}-p^{(n)} ight |_2d au$
正交多项式：$(f,g)=int_a^b ho(x)f(x)g(x)dx=0$，在区间[-1,1]上，例如：
- Legendre多项式：$ ho(x)=1$
- Chebyshev多项式：$T_n(x)=cos(n arccos x)$，$ ho(x)=frac{1}{sqrt{1-x^2}}$
- Laguerre多项式：$ ho(x)=e^{-x}$
- Hermite多项式：$ ho(x)=e^{-x^2}$
多项式序列有递推关系：$varphi_{n+1}(x)=(alpha_nx+eta_n)varphi_{n}(x)+gamma_{n-1}varphi_{n-1}(x)$
最佳平方逼近：$left |f-s^* ight |_2=inf_{sinPhi}left |f-s ight |_2$。f在正交函数空间$Phi$中的最佳平方逼近函数为：$s_n^*(x)=sum_{j=0}^na_j^*phi_j(x)$
最佳平方逼近问题离散化之后，称为最小二乘问题：$arg min_{sinPhi}sum_{j=0}^m ho(x_j)[f(x_j)-s(x_j)]^2$
最佳一致逼近：$left |f-s^* ight |_{infty}=inf_{sinPhi}left |f-s ight |_{infty}$。$s_n^*$是$fin 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)$给定权函数为$ ho$的正交多项式序列$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_kint_a^b ho(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}sumfrac{f(x)}{g(x)}$
非线性方程组的数值解
方程$F(x)=0$，改造成迭代格式$x=Phi(x)$,求不动点：$x^*=Phi(x^*)$
Brouwer不动点定理：设$Phi:Dsubset R^n o R^n,Phi$在有界闭集$D_0subset D$上连续，且$Phi(X)subset X$，则$Phi$在$D_0$中必存在不动点。
p阶收敛：$lim_{k o infty}frac{left | x^{k+1}-x^k ight |}{left | x^k-x^* ight |^p}=C$
Lipschitz条件：$left | Phi(x)-Phi(x^*) ight |leqslant Lleft | x-x^* ight |$
牛顿法：$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 o 0}x_n=x(t_n)$
- 绝对稳定性：用算法求解$y'=lambda y Rightarrow y_{n+1}=E(lambda h)y_n$。如果$left | E(lambda h) ight |<1$，称算法绝对稳定。
参考文献
- 关冶、陆金甫，数值分析基础，高等教育出版社，1994