第一章 误差
1. 误差的分类
- 模型误差：数学模型本身包含的误差；
- 观测误差：观测结果带来的误差；
- 数据误差：数据可能由先前的计算等途径得到，从而导致的误差；
- 截断误差（方法误差）：模型的准确解和用数值方法求得的解之差；
- 舍入误差：计算过程中只能取有限位数字进行运算而引来的误差。
2. 近似计算中需要注意的一些现象
- 要避免两个相近的数相减；
- 两个相差很大的数进行运算时，要防止小的那个数被“吃掉”；
- 要注意计算步骤的简化，减少运算次数；
- 要避免做被除数的绝对值远远大于除数绝对值的除法；
- 要选用数值稳定的计算公式。
第二章 插值法与数值微分
1. 线性插值
线性插值就是用直线近似地代替函数 f(x) 。用两个点( x_0 , y_0 )和( x_1 , y_1 )通过两点式来构建直线方程 \phi_1(x) ，得到的 \phi_1(x) 就是插值函数：
记 l_0(x) = \frac{x-x_1}{x_0-x_1} ， l_1(x) = \frac{x-x_0}{x_1-x_0} ，并把 l_0(x) 叫做 x_0 的一次插值基函数， l_1(x) 叫做 x_1 的一次插值基函数.
Lagrange 插值
插值函数 \phi_1(x) 是两个插值基函数 l_0(x) 和 l_1(x) 的线性组合，其组合系数就是对应点的函数值 y_0 和 y_1 ，即：
这种形式的插值函数称为 Lagrange 插值。
Newton 插值
把直线用点斜式表示，有：
函数 f(x) 在 x_i ， x_j 的一阶均方差的定义是：
利用均方差的对称性，可以将点斜式表示为：
这种形式的插值叫做 Newton 插值。
2. 二次插值
过三个点 ( x_0 , y_0 )，( x_1 , y_1 ) 和 ( x_2 , y_2 ) 来构造 y=f(x) 的插值函数，就是二次插值（该插值函数的次数不高于二次）。
二次 Lagrange 插值
二次拉格朗日插值多项式为 \phi_2(x)=y_0l_0(x)+y_1l_1(x)+y_2l_2(x) ，其中三个插值基函数分别为：
二次 Newton 插值
二次牛顿插值多项式为：
3. n 次插值
n 次 Lagrange 插值
n 次拉格朗日插值多项式为：
其中插值基函数 l_i(x) 为：
l_i(x) 还有另一种形式：
其中，
n 次 Newton 插值
n 次牛顿插值多项式需要先构造均差表（差商表）：
| x | y | f[x_i,x_j] | f[x_i,x_j,x_k] | ... | f[x_0,x_1,...,x_n] |
|---|---|---|---|---|---|
| x_0 | \underline{y_0} | ||||
| x_1 | y_1 | \underline{f[x_0,x_1]} | |||
| x_2 | y_2 | f[x_1,x_2] | \underline{f[x_0,x_1,x_2]} | ||
| x_3 | y_3 | f[x_2,x_3] | f[x_1,x_2,x_3] | ... | |
| ... | ... | ... | ... | ... | |
| x_n | y_n | f[x_{n-1},x_n] | f[x_{n-2},x_{n-1},x_n] | ... | \underline{f[x_0,x_1,...,x_n]} |
其中 f[x_0,x_1,...,x_n] 是 n 阶均差，它的表达式为：
利用均差表，可以写出 n 次牛顿插值多项式：
n 次牛顿插值多项式中的所含均差都是均差表中对角线上的项。
4. Hermite 插值
若给定 n+1 个结点和相应的函数值与微商值，可以构造 2n+1 次的 Hermite 插值多项式 H(x) ：
- H(x) 是不超过 2n+1 次的插值多项式；
- H(x_i)=y_i ， H'(x)=y'_i\;(i=0,1,2,...,n) .
H(x)=\sum_{i=0}^{n}[y_ih_i(x)+y'_iH_i(x)]
由上述条件可知：
第三章 数据拟合法
1. 正交多项式
Legendre 多项式
Laguerre 多项式
Chebyshev 多项式
第五章 数值积分
1. 梯形求积公式
梯形求积公式就是过 (a, f(a)) 和 (b, f(b)) 两点做直线 P_1(x) ，用 P_1(x) 来代替 f(x) ：
2. 抛物线求积公式（Simpson 公式）
将 [a,b] 区间二等分，过点 (a, f(a)) ， (\frac{a+b}{2},f(\frac{a+b}{2})) 和 (b,f(b)) 三点做抛物线 P_2(x) ，用 P_2(x) 来代替 f(x) :
3. Newton-Cotes 公式
把区间 [a,b] 作 n 等分，分点为：
过这 n+1 个节点，构造一个 n 次多项式：
其中 \omega(x)=(x-x_0)(x-x_1)...(x-x_n) ，用 P_n(x) 代替被积函数 f(x) ，有：
其中 c_i^{(n)} 是不依赖于函数 f(x) 和区间 [a,b] 的常数，叫做 Newton-Cotes 系数，它的值如下表所示：
期末考试只要求掌握到 n=4 的情况即可。
| n | c_0^{(n)} | c_1^{(n)} | c_2^{(n)} | c_3^{(n)} | c_4^{(n)} |
|---|---|---|---|---|---|
| 1 | \frac{1}{2} | \frac{1}{2} | |||
| 2 | \frac{1}{6} | \frac{4}{6} | \frac{1}{6} | ||
| 3 | \frac{1}{8} | \frac{3}{8} | \frac{3}{8} | \frac{1}{8} | |
| 4 | \frac{7}{90} | \frac{16}{45} | \frac{2}{15} | \frac{16}{45} | \frac{7}{90} |
Newton-Cotes 公式的代数精度
对一个一般求积公式
若 f(x) 为一个次数不高于 m 次的代数多项式时，上式等号成立，但当 f(x) 为 m+1 次多项式时，上式不能精确成立，说明该求积公式具有 m 次代数精度。
- 若 f(x) 是 n 次多项式，则 f^{(n+1)}\equiv0 ，所以 f(x)=P_n(x) ，Newton-Cotes 公式代数精度至少为 n.
- 当 n 为偶数时，Newton-Cotes 公式的代数精度可达到 n+1.
4. 复化梯形公式
将区间 [a,b] 作 n 等分，节点 x_k=a+kh\;(k=0,1,2,...,n,\;h=\frac{b-a}{n}) .对每个小区间 [x_k,x_{k+1}] 使用梯形求积公式，有：
记复化梯形公式 T_n 为：
5. 复化抛物线公式
由于抛物线求积公式用到了区间的中点，所以在构造复化抛物线公式时必须将区间 [a,b] 进行 2n 等分，在每个小区间 [x_{2k-2},x_{2k}] 上使用抛物线求积公式：
于是有：
记复化抛物线公式 S_n 为：
第六章 解线性代数方程组的直接法
1. LU 分解法
当矩阵 A 的前 n-1 个顺序主子式都不为零时，矩阵 A 可以唯一地分解为两个三角矩阵的乘积：
其中 L 是单位下三角矩阵， U 是上三角矩阵。
如何求 LU 分解矩阵：
- 利用初等行变换将矩阵 A 化为上三角矩阵 U；
- 有下三角可逆矩阵 P，使得 PA=U，从而有 LU 分解： A=P^{-1}U\;(L=P^{-1}) .
原方程 Ax=b 等价于 LUx=b ，令 Ux=y ，有
从 Ly=b 中解出 y ，再将 y 代入 Ux=y 解出 x 即可。
2. 向量范数
向量范数
任一向量 x\in{R^n} ，对应一个非负实数 \parallel{x}\parallel ，具有下面三个性质：
- 正定性：对所有的 x\in{R^n} 有 {\parallel{x}\parallel}\;\geq0 ，而且 {\parallel{x}\parallel}\;=0 当且仅当 x=0 .
- 齐次性：对所有的 x\in{R^n} 和 \alpha\in{R} ，有 {\parallel{\alpha{x}}\parallel}\;=\lvert\alpha\rvert\;\cdot{\parallel{x}\parallel} .
- 三角不等式：对所有的 x，y\in{R^n} ，有： {\parallel{x+y}\parallel}\;\leq\;{\parallel{x}\parallel}+{\parallel{y}\parallel} .
则称 \parallel{x}\parallel 为向量 x 的范数.
常见向量范数
常见的向量范数有：
- 1 范数： {\parallel{x}\parallel}_1=\sum_{i=1}^{n}\lvert{x_i}\rvert
- 2 范数： {\parallel{x}\parallel}_2=(\sum_{i=1}^{n}x_i^2)^{\frac{1}{2}}
- \infty 范数： {\parallel{x}\parallel}_{\infty}=max(\lvert{x_1}\rvert,\lvert{x_2}\rvert,...,\lvert{x_n}\rvert)
- p 范数： {\parallel{x}\parallel}_p=(\sum_{i=1}^n\lvert{x_i}\rvert^p)^{\frac{1}{p}},\;p\geq1
3. 矩阵范数
矩阵范数
设 A 是一个 n \times n 的实矩阵，按一定规则对应一个非负实数 \parallel{A}\parallel ，称为矩阵 A 的范数，必须满足以下四个性质：
- 正定性：对所有的 A\in{R^{n\times{n}}} 有 \parallel{A}\parallel\;\geq{0} ，而且 \parallel{A}\parallel=0 当且仅当 A=0 .
- 齐次性：对所有的 A\in{R^{n\times{n}}} 和 \alpha\in{R} 有 \parallel{\alpha{A}}\parallel=\lvert{\alpha}\rvert\cdot\lvert{A}\rvert .
- 三角不等式：对所有的 A,B\in{R^{n\times{n}}} 有 \parallel{A+B}\parallel\;\leq\;\parallel{A}\parallel+\parallel{B}\parallel .
- 相容性：对所有的 A,B\in{R^{n\times{n}}} 有 \parallel{AB}\parallel\;\leq\;\parallel{A}\parallel\cdot\parallel{B}\parallel .
常见矩阵范数
常见的矩阵范数有：
- 1 范数（列和范数）： \parallel{A}\parallel_1=max\sum_{i=1}^n\lvert{a_{ij}}\rvert\;(1\leq{j}\leq{n})
- 2 范数： \parallel{A}\parallel_2=\sqrt{\lambda_1} ， \lambda_1 为矩阵 A^TA 的最大特征值
- \infty 范数（行和范数）： \parallel{A}\parallel_{\infty}=max\sum_{j=1}^n\lvert{a_{ij}}\rvert\;(1\leq{i}\leq{n})
- F 范数： \parallel{A}\parallel_F=(\sum_{i,j=1}^n\lvert{a_{ij}^2}\rvert)^{\frac{1}{2}}
4. 谱半径
设 n \times n 阶矩阵 A 的特征值为 \lambda_i\;(i=1,2,...,n) ，则称
为矩阵 A 的谱半径.
5. 条件数
条件数
数 \parallel{A}\parallel\cdot\parallel{A^{-1}}\parallel 称为矩阵 A 的条件数，记为 Cond(A) 。
当线性方程组的系数矩阵 A 的条件数 Cond(A) 很大时，说明在系数矩阵或右端项产生微小变化时会引起解的巨大变化，则称此方程组是“病态”方程组，否则称方程组为“良态”方程组。
条件数和范数有关，可以在条件数上加下标，对应的范数也应加相同的下标：
其中， \lambda_1 ， \lambda_n 是矩阵 A^TA 的最大和最小特征值，故 Cond(A)_2 又称谱条件数。
条件数的性质
- Cond(A)\geq{1} .
- 单位矩阵、置换矩阵和正交矩阵的谱条件数都为 1.
- 对任意非零实数 \alpha ，有 Cond(\alpha{A})=Cond(A) .
第八章 解线性方程组的迭代法
1. Jacobi 迭代
设有方程组
用矩阵表示为
假设 a_{ii\neq{0}} ，令
方程组可改写成
若令
则
方程可用矩阵表示为
选取初始向量 x^{(0)}=(x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)})^{T} ，代入 x^{(1)}=Bx^{(0)}+g 得到一个新向量 x^{(1)}=(x_1^{(1)},x_2^{(1)},\cdots,x_n^{(1)})^{T} ，再将 x^{(1)} 代入 x^{(2)}=Bx^{(1)}+g ，可以得到 x^{(2)} ，依此类推，可得到迭代格式
即
通过上式的计算，可得到向量序列 \lbrace{x^{(k)}}\rbrace ，当 k\rightarrow+\infty 时，若序列 \lbrace{x^{(k)}}\rbrace 收敛到 x^* ， x^* 就是方程组的解。 以上计算过程过程称为 Jacobi 迭代法，矩阵 B 为 jacobi 迭代法的迭代矩阵。
2. Gauss-Seidel 迭代
Gauss-Seidel 迭代法和 Jacobi 迭代法相似，但不同点是：在计算 x_{i}^{(k+1)} 时，Jacobi 迭代法用 (x_1^{(k)},x_2^{(k)},...,x_n^{(k)})^T 代入迭代公式，而 Gauss-Seidel 迭代法会利用之前已经计算出的结果，用 (x_1^{(k+1)},x_2^{(k+1)},...,x_{i-1}^{(k+1)},x_{i+1}^{(k)},...,x_n^{(k)})^{T} 代入迭代公式进行计算。
其迭代过程为：
令
迭代过程用矩阵表示为
因 (I-L) 存在，所以上述迭代格式可表示为
称 B_1=(I-L)^{-1}U 为 Gauss-Seidel 迭代法的迭代矩阵.
注意：
交换方程和未知数的次序都会影响 Gauss-Seidel 迭代法的计算结果，但这种交换对 Jacobi 迭代法没有影响。
3. 迭代法的收敛性判别
定理 1
Jacobi 迭代法和 Gauss-Seidel 迭代法收敛的充分必要条件是迭代矩阵的谱半径小于 1.
定理 2
若迭代矩阵 M 的范数 \parallel{M}\parallel<1 ，则 Jacobi 迭代和 Gauss-Seidel 迭代一定收敛，但这只是迭代收敛的充分条件（因为 \rho(M)\leq{\parallel{M}\parallel} ）.
定理 3
若方程组 Ax=b 的系数矩阵 A 按行严格对角占优或按列严格对角占优，即满足条件
或
则 Jacobi 迭代法和 Gauss-Seidel 迭代法都收敛。
定理 4
若方程组 Ax=b 的系数矩阵 A 为对称正定矩阵，则 Gauss-Seidel 迭代法收敛。
注意：
通常判断 Jacobi 或 Gauss-Seidel 迭代法是否收敛，先看方程组的系数矩阵 A 是否按行严格对角占优或按列严格对角占优，若严格对角占优，则收敛；否则，继续判断对应迭代矩阵的谱半径是否小于 1，小于 1 则收敛，否则不收敛。
第十章 非线性方程组及非线性方程组解法
1. 二分法
- 找出 f(x)=0 的根所在区间 (a,b) ，并计算出端点的函数值 f(a),f(b) .
- 计算 f(x) 在区间中点的值 f(\frac{a+b}{2}) .
- 若 f(\frac{a+b}{2})\approx0 ，则停止迭代。 否则，若 f(\frac{a+b}{2}) 与 f(a) 异号，则根位于 (a,\frac{a+b}{2}) 中，用 \frac{a+b}{2} 代替 b ； 若 f(\frac{a+b}{2}) 与 f(b) 异号，则根位于 (\frac{a+b}{2},b) 中，用 \frac{a+b}{2} 代替 a .
- 重复上述过程中的第二步和第三步，直到区间缩小到容许误差范围之内。
2. 等步长扫描法
设 h 是给定的步长，方程 f(x)=0 的有根区间为 [a,b] ，一般初始时 h 取 0.1，取 x_0=a,x_1=a+h ，若 f(x_0)f(x_1)<0 表明扫描成功；否则令 x_0=x_1,x_1=x_0+h ，继续上述方法，直到成功。 若 x_1>b 表明扫描失败，将 h 缩小（一般 h 按照 10 的倍数进行缩小，从 0.1 到 0.01 再到 0.001 等等），重新开始扫描。
3. 简单迭代法
若给定方程 f(x)=0 后，把它改写成等价形式：
再作迭代
简单迭代法敛散性判别
- 若 \lvert{\phi'(x)}\rvert<1 ，则简单迭代法收敛。
- 若 \phi'(\xi)=\cdots=\phi^{(p-1)}(\xi)=0,\phi^{(p)}(\xi)\not=0, ，则迭代在 \xi 处 p 阶收敛。
4. 牛顿法
5. 弦截法
第十一章 常微分方程初值问题的数值解法
1. Euler 方法（显示欧拉法）
2. 向后 Euler 方法（隐式欧拉法）
3. 改进 Euler 方法
4. 梯形公式
注意：
- 使用改进 Euler 方法进行迭代时，需要解隐式方程。
- 若题中不给出迭代步长 h，则 h=0.1.
