科学计算期末复习

科学计算

1.

误差、稳定性、精度、条件数、适定的概念。误差的传递、如何防止相对误差过快增长。

向前误差：比较 $f(x)$ 值
向后误差：比较 $x$ 值；
条件数：

$$\frac{|(f(\hat x)-f(x))/f(x)|}{|(\hat x-x)/x|}=\frac{|\Delta y/y|}{|\Delta x/x|}\doteq\left|\frac{xf'(x)}{f(x)}\right|$$

2.

向量和矩阵的各类范数、矩阵各类范数的估计及物理意义。线性方程组的条件数及其意义、建立线性方程组时防止条件数过大的基本要求。（选主元）的LU分解算法及复杂度。对称矩阵的Cholesky分解的算法及复杂度。带状矩阵的LU分解。

$n$ 维向量的 $p$ - 范数：

$$\|x\|_p=\left(\sum_{i=1}^{n}|x_i|^p\right)^{1/p}$$ $1$ - 范数： $$\|x\|_1=\sum_{i=1}^{n}|x_i|$$ $2$ - 范数： $$\|x\|_2=\sqrt{\sum_{i=1}^{n}x_i^2}$$ $\infty$ - 范数： $$\|x\|_\infty=\max_{1\leqslant i<n}|x_i|$$
$m\times n$ 矩阵 $A$ 的范数（诱导范数、从属范数）： $$\|A\|=\max_{x\neq 0}\frac{\|Ax\|}{\|x\|}$$ $$\|A\|_1=\max_{j}\sum_{i=1}^m |a_{ij}|$$ $$\|A\|_2=\sqrt{\lambda_1},\ \ \ \lambda_1为A^TA的最大特征值$$ $$\|A\|_\infty=\max_{i}\sum_{j=1}^n |a_{ij}|$$
条件数（当 $A$ 奇异时，条件数为 $\infty$）：$\mathrm{cond}(A)=\|A\|\cdot\|A^{-1}\|$
LU分解、高斯分解：下三角*上三角
Cholesky 分解：对角线开根号

3.

线性最小二乘法的物理意义和应用。线性最小二乘问题的各种求解方法及算法复杂度和条件数。正交矩阵的性质、广义逆。QR分解的算法、复杂度及应用。Householder变换和Givens变换的算法复杂度和应用范围。

最小二乘法： $\min_x\sum_{i=1}^m(y_i-f(t_i,x))^2$
其中 $f(t,x)=x_1\phi_1(t)+x_2\phi_2(t)+\cdots+x_n\phi_n(t)$
广义逆：$A^+=(A^TA)^{-1}A^T$
条件数：$\mathrm{cond}(A)=\|A\|_2\cdot\|A^+\|_2$

4.

特征值问题的条件数。幂法和反幂法的算法和应用。应用降阶（deflation）方法求解多个特征值。QR迭代的算法原理及复杂度、Hessenberg（三对角）矩阵的QR迭代算法。Krylov子空间、Arnoldi和Lanczos迭代求Hessenberg（三对角）矩阵。

5.

非线性方程组求解的条件数。二分法、不动点法、牛顿法、割线法的算法、收敛性和应用。方程组的Broyden’s方法。

牛顿法：

$$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$$ $$解J_f(x_k)s_k=-f(x_k)$$ 割线法： $$x_{k+1}=x_k-\frac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1})}$$

6.

优化问题的条件数、水平集。约束最优问题的Lagrange乘子法。一维优化问题的黄金分割法、牛顿法。最速
下降法、牛顿法的算法及缺陷，BFGS方法、共轭梯度法。

7． 插值的求解、Runge现象。Hermite插值。三次样条插值。B样条。
8． 数值积分的阶。几类基本的积分公式。高斯积分公式及其原理。奇异积分的处理。各阶导数的各种数值差分方法。
9． 常微分方程的稳定性和算法稳定性概念。显式和隐式格式、向前和向后Euler格式、Runge-Kutta格式、算法的精度和稳定区域。
10. 常微分方程边值问题的打靶法、有限差分方法、Galerkin方法、有限元方法。弱解形式。
11. 发展型偏微分方程的有限差分方法、精度和稳定性、CFL条件。椭圆形方 程的有限元方法。
12. FFT的算法和应用。
13. Markov过程。Metropolis方法。