《数值分析》总结

数值分析

第一章 误差

• 绝对误差 $e^{*} = x^{*} - x$
• 相对误差 $e^{*}_{r} = \frac{e^{*}}{x}$，常取 $e^{*}_{r} = \frac{e^{*}}{x^{*}}$
• 误差限/绝对误差限 $\epsilon^{*} \ge e^{*}$，绝对误差的上限
• 相对误差限 $\epsilon^{*}_{r} \ge e^{*}_{r} \to \frac{e^{*}}{}$，相对误差的上限
• 误差的四个类型
  
  • 数学模型和实际问题的误差： 模型误差
  • 测量物理量(e.g. 长度，温度)时的误差： 观测误差
  • 计算方法的误差：截断误差
  • 计算结果在计算机中因字长限制保存时出现的误差：舍入误差
• 一个计算方法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的。 $\to~$条件数
  
  • 误差的四则运算
• 加减法：$\epsilon(x_{1}^{*} \pm x_{2}^{*}) = \epsilon(x_{1}^{*}) \pm \epsilon(x_{2}^{*})$
• 乘法：$\epsilon(x_{1}^{*} \times x_{2}^{*}) = | x_1^{*} \times \epsilon(x_{2}^{*}) + |x_2^{*}| \times \epsilon(x_{1}^{*})$
• 除法：${\epsilon({x_{1}^{*} \over x_{2}^{*}}}) = {{|x_1^{*}| \times \epsilon(x_{2}^{*}) + |x_2^{*}| \times \epsilon(x_{1}^{*})}\over{|x_{2}^{*}|^2}}$

第二章 插值法

• [一般的]多项式插值：$P(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$
• 牛顿插值：$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) + \dots$
• 拉格朗日插值：$L(x) = {(x-x_1)(x-x_2)\dots\over(x_0-x_1)(x_0-x_2)\dots}f(x_0) + {(x-x_0)(x-x_2)(x-x_3)\dots\over (x_1-x_0)(x_1-x_2)(x_1-x_3)\dots}f(x_1) + \dots$ $$L(x) = \sum_{i=1}^{n}{(x-x_0)(x-x_1)\dots(x-x_{i-1})(x-x_{i+1})\dots(x-x_{n})\over(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_{n})}f(x_i)$$
• [牛顿插值法]均差表构造

第三章 函数逼近

• 权函数

  $$\int_{a}^{b}\rho(x)g(x)\mathrm{d}x$$

• 函数内积

  $$(f(x), g(x)) = \int_{a}^{b}\rho(x)f(x)g(x)\mathrm{d}x$$
  • 两函数内积为0，则称它们在$[a,b]$上带权$\rho(x)$正交

• 正交函数族：函数族$\phi_{0}(x), \phi_{1}(x),...$满足

  $$(\phi_{j}, \phi_{k}) = \int_{a}^{b}\rho(x)\phi_{j}(x)\phi_k(x)\mathrm{d}x = 0(j\ne k) | A_k > 0(j = k)$$

• 勒让德多项式

  $$P_0(x) = 1, P_n(x) = {1\over 2^nn!}{\mathrm{d}^n\over \mathrm{d}x^n}(x^2-1)^n$$

第四章 数值积分方法

• 代数精度：如果某个求积公式对次数不超过m的多项式均能准确成立，但对m+1次不准确成立，则称其具有m次代数精度

• 梯形公式：$\int_{a}^{b}f(x)\mathrm{d}x = \frac{b-a}{2}[f(a)+f(b)]$

• 矩形公式：$\int_{a}^{b}f(x)\mathrm{d}x = {b-a}[f(\frac{a+b}{2})]$

• 牛顿-科斯特公式

  • $n$次的牛顿-科斯特公式至少具有$n$次代数精度;
  • 当$n$为偶数时，则至少具有$n+1$次代数精度。
  • 二阶为辛普森公式，系数：$\frac{b-a}{6}\to1\to4\to1$
  • 四阶系数：$\frac{b-a}{90}\to7\to32\to12\to32\to7$

• 辛普森公式：$S=\frac{b-a}{6}[f(a) + 4f(\frac{a+b}{2}) + f(b)]$

  • 余项：$R[f] = -\frac{b-a}{180}(\frac{b-a}{2})^4f^{(4)}(\eta)$

• 复合求积公式(令$h=b-a$)

  • 复合梯形：$T_n=\frac{h}{2}[f(a)+2\sum_{k=1}^{n-1}f(x_k)+f(b)]$，误差为$O(h^2)$
  • 复合辛普森：$S_n=\frac{h}{6}[f(a)+4\sum_{k=0}^{n-1}f(x_{k+\frac{1}{2}})+2\sum_{k=1}^{n-1}f(x_k)+f(b)]$，误差阶$O(h^4)$

• 高斯求积公式

• 高斯-勒让德公式

第五章 消元

第六章 迭代法

• $A = D - L - U$
  
  • $A~$为原系数矩阵
  • $D~$为$~A~$的对角线元素构成的矩阵(diagonal?)
  • $L~$为$~A~$的下三角矩阵(lower?)
  • $U~$为$~A~$的上三角矩阵(upper?)
• 雅克比迭代，迭代矩阵$~B = D^{-1}(L+U)$
• 高斯-赛德尔迭代，迭代矩阵$~G = (D - L)^{-1}U$
• 迭代收敛充要条件: 迭代矩阵谱半径$~\rho(B) < 1$
• 迭代收敛充分条件: 迭代矩的某个范数$~||B||< 1$

第七章 非线性方程的数值解法

• 不动点存在且唯一的条件：
  
  • $C[a,b]\to a\le \varphi(x)\le b$
  • $\exists L < 1, |\varphi(x)-\varphi(y)|\le L|x-y|$
• 局部收敛：$\varphi(x)$在$x^*$的某个邻连续，并且$|\varphi'(x^*)|<1$
• 若$\frac{x_{k+1}}{x_k^p}\to C, C\ne 0$，则称迭代过程是$p$阶收敛的。
  
  • $p=1~$称为线性收敛
  • $p>1~$称为超线性收敛
  • $p=2~$称为平方收敛
  • 若$\varphi'(x^*)=\varphi''(x^*)=\dots=\varphi^{(n-1)}(x^*)=0,\varphi^{(n)}(x^*)\ne 0$，则该迭代过程在$x^*$附近是$p$阶收敛的
  • 迭代法误差估计：若有不动点$x^*$，则误差估计为$|x_k-x^*|\le \frac{L^k}{1-L}|x_1-x_0|$
• 二分法
  
  • 当求出有根区间为$(a,b)$时，误差为$\frac{|b-a|}{2}$
• 牛顿法
  
  • $\varphi(x)=x - \frac{f(x)}{f'(x)}$, 是平方收敛的
  • 简化牛顿法：$\varphi(x)=x-\frac{f(x)}{f'(x_0)}$，线性收敛。
  • 牛顿下山法：$\varphi(x) = x - \lambda \frac{f(x_k)}{f'(x_k)}$，$\lambda$称为下山因子，初始取$\lambda=1$，逐次减半直到满足$|f(x_{k+1})|<|f(x_k)|$
• 弦截法
  
  • $\varphi(x) = x - \frac{f(x)}{\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}}$，用差商代替牛顿法中的导数。超线性收敛($p = \frac{1+\sqrt5}{2}\approx 1.618$)

第九章 常微分方程处置问题数值解法

• 欧拉法：$y_{n+1} = y_n + h * f(x_n, y_n)$
  
  • 隐式欧拉法：$y_{n+1} = y_n + hf(x_{n+1}, y_{n+1})$
• 改进欧拉法
  
  • 预测：$y'_{n+1} = y_n + h * f(x_n, y_n)$
  • 校正：$y_{n+1} = y_n + \frac{h}{2}*[f(x_n, y_n) + f(x_{n+1}, y'_{n+1})]$
• R-K法
  
  • 二阶中点：$y_{n+1} = y_n + h * (f(x_n, y_n) + f(x_n + \frac{h}{2}, y_n + \frac{h}{2}f(x_n, y_n))$
  • 二阶休恩：$y_{n+1} = y_n + \frac{h}{4}(K_1 + 3K_2)$
    
    • $K_1 = f(x_n, y_n)$
    • $K_2 = f(x_n + \frac{2}{3}h, y_n + \frac{2}{3}hK_1)$
  • 三阶：$y_{n+1} = y_n + \frac{h}{6}(K_1 + 4K_2 + K_3)$
    
    • $K_1 = f(x_n, y_n)$
    • $K_2 = f(x_n + \frac{h}{2}, y_n + \frac{h}{2}K_1)$
    • $K_3 = f(x_n + h, y_n - hK_1 + 2hK_2)$
  • 四阶：$y_{n+1} = y_n + \frac{h}{6}(K_1 + 2K_2 + 2K_3 + K_4)$
    
    • $K_1 = f(x_n, y_n)$
    • $K_2 = f(x_n + \frac{h}{2}, y_n + \frac{h}{2}K_1)$
    • $K_3 = f(x_n + \frac{h}{2}, y_n + \frac{h}{2}K_2)$
    • $K_4 = f(x_n + h, y_n + hK_3)$
• 绝对稳定域：判断某方法在什么区间稳定
  
  • 模型方程：$y' = \lambda y$
  • 用单步法求解该方程，得$~y_{n+1} = E(h\lambda)y_n$，如欧拉法可得到$y_{n+1} = (1 + h\lambda)y_n$
  • 然后令$~|E(h\lambda)| < 1$，解出$~h$