第一章 误差
1. 误差的分类
- 模型误差：数学模型本身包含的误差；
- 观测误差：观测结果带来的误差；
- 数据误差：数据可能由先前的计算等途径得到，从而导致的误差；
- 截断误差（方法误差）：模型的准确解和用数值方法求得的解之差；
- 舍入误差：计算过程中只能取有限位数字进行运算而引来的误差.
2. 近似计算中需要注意的一些现象
- 要避免两个相近的数相减；
- 两个相差很大的数进行运算时，要防止小的那个数被“吃掉”；
- 要注意计算步骤的简化，减少运算次数；
- 要避免做被除数的绝对值远远大于除数绝对值的除法；
- 要选用数值稳定的计算公式.
第二章 插值法与数值微分
1. 线性插值
线性插值就是用直线近似地代替函数 $f(x)$ 。用两个点( $ x_0 $ , $ y_0 $ )和( $ x_1 $ , $ y_1 $ )通过两点式来构建直线方程 $ \phi_1(x) $ ，得到的 $ \phi_1(x)$ 就是插值函数：
$$ \phi_1(x)=y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x-x_0}{x_1-x_0}
$$
记 $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$ ，即：
$$ \phi_1(x)=y_0l_0(x)+y_1l_1(x)
$$
这种形式的插值函数称为 Lagrange 插值。
Newton 插值
把直线用点斜式表示，有：
$$ \phi_1(x)=y_0+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)
$$
函数 $f(x)$ 在 $ x_i $ ， $ x_j$ 的一阶均方差的定义是：
$$ f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}
$$
利用均方差的对称性，可以将点斜式表示为：
$$ \phi_1(x)=y_0+(x-x_0)f[x_0,x_1]
$$
这种形式的插值叫做 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)$ ，其中三个插值基函数分别为：
$$ l_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}
$$
$$ l_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}
$$
$$ l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}
$$
二次 Newton 插值
二次牛顿插值多项式为：
$$ \phi_2(x)=f(x_0)+(x-x_0)f[x_0,x1]+(x-x_0)(x-x_1)f[x_0,x_1,x_2]\=f(x_0)+(x-x_0)\frac{f(x_0)-f(x_1)}{x_0-x_1}+(x-x_0)(x-x_1)\frac{f[x_0-x_1]-f[x_1-x_2]}{x_0-x_2}
$$
3. n 次插值
n 次 Lagrange 插值
n 次拉格朗日插值多项式为：
$$ \phi_n(x)=\sum_{i=0}^ny_il_i(x)
$$
其中插值基函数 $l_i(x)$ 为：
$$ l_i(x)=\frac{(x-x_0)...(x-x_{i-1})(x-x_{i+1})...(x-x_n)}{(x_i-x_0)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)},;i=0,1,2,...,n
$$
$l_i(x)$ 还有另一种形式：
$$ l_i(x)=\sum_{i=0}^n\frac{\omega_n(x)}{(x-x_i)\omega_n^{'}(x_i)}
$$
其中，
$$ \omega_n(x)=(x-x_0)(x-x_1)...(x-x_n)\ \omega_n^{'}(x_i)=(x_i-x0)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)
$$
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 阶均差，它的表达式为：
$$ f[x_0,x_1,...,x_n]=\frac{f[x_0,x_1,...,x_{n-1}]-f[x_1,x_2,...,x_n]}{x_0-x_n}
$$
利用均差表，可以写出 n 次牛顿插值多项式：
n 次牛顿插值多项式中的所含均差都是均差表中对角线上的项。
$$ \phi_n(x)=f(x_0)+(x-x_0)f[x_0,x_1]+(x-x_0)(x-x_1)f[x_0,x_1,x_2]+...+\(x-x_0)(x-x_1)...(x-x_{n-1})f[x_0,x_1,...,x_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)]$
由上述条件可知：
$$ h_i(x_j)= \begin{cases} 1 ,& i=j \ 0 ,&i\neq{j};(j=0,1,2,...,n) \end{cases}
$$
$$ h'_i(x_j)=0,;j=0,1,2,...,n
$$
$$ H'_i(x_j)= \begin{cases} 1, & i=j \ 0, & i\neq{j};(j=0,1,2,...,n) \end{cases}
$$
$$ H_i(x_j)=0,;j=0,1,2,...,n
$$
第三章 数据拟合法
1. 正交多项式
Legendre 多项式
$$ P_n(x)=\frac{1}{2^{n}n!}\frac{d^n}{dx^n}(x^2-1)^n,;n=0,1,2,\cdots
$$
Laguerre 多项式
$$ L_n(x)=e^x\frac{d^n}{dx^n}(x^ne^{-x}),;n=0,1,2,\cdots
$$
Chebyshev 多项式
$$ T_n(x)=cos(n;arccosx)\ =\frac{1}{2}[(x+\sqrt{x^2-1})^n+(x-\sqrt{x^2-1})^n],;\lvert{x}\rvert\leq1
$$
第五章 数值积分
1. 梯形求积公式
梯形求积公式就是过 $(a, f(a))$ 和 $(b, f(b))$ 两点做直线 $P_1(x)$ ，用 $P_1(x)$ 来代替 $f(x)$ ：
$$ \int_{a}^{b}f(x)dx\approx{\int_{a}^{b}P_1(x)dx}={\frac{b-a}{2}[f(a)+f(b)]}
$$
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)$ :
$$ \int_{a}^{b}f(x)dx\approx{\int_{a}^{b}P_2(x)dx}={\frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]}
$$
3. Newton-Cotes 公式
把区间 $[a,b]$ 作 n 等分，分点为：
$$ x_i=a+ih,;i=0,1,2,...,n,;h=\frac{a+b}{n}
$$
过这 n+1 个节点，构造一个 n 次多项式：
$$ P_n(x)=\sum_{i=0}^n\frac{\omega(x)}{(x-x_i)\omega'(x_i)}f(x_i)
$$
其中 $\omega(x)=(x-x_0)(x-x_1)...(x-x_n)$ ，用 $P_n(x)$ 代替被积函数 $f(x)$ ，有：
$$ \int_a^bf(x)dx\approx\int_a^bP_n(x)dx=\sum_{i=0}^nA_if(x_i)=(b-a)\sum_{i=0}^nc_i^{(n)}f(x_i)
$$
其中 $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 公式的代数精度
对一个一般求积公式
$$ \int_a^bf(x)dx\approx\sum_{k=0}^nA_kf(x_k)
$$
若 $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}]$ 使用梯形求积公式，有：
$$ I=\int_a^bf(x)dx=\sum_{k=0}^n\int_{x_k}^{x_{k+1}}f(x)dx\\approx\sum_{k=0}^n\frac{x_{k+1}-x_k}{2}[f(x_k)+f(x_{k+1})]\=\frac{h}{2}[f(a)+f(b)+2\sum_{k=1}^{n-1}f(a+kh)]
$$
记复化梯形公式 $T_n$ 为：
$$ T_n=\frac{h}{2}[f(a)+f(b)+2\sum_{k=1}^{n-1}f(a+kh)]
$$
5. 复化抛物线公式
由于抛物线求积公式用到了区间的中点，所以在构造复化抛物线公式时必须将区间 $[a,b]$ 进行 2n 等分，在每个小区间 $[x_{2k-2},x_{2k}]$ 上使用抛物线求积公式：
$$ \int_{x_{2k-2}}^{x_{2k}}f(x)dx\approx\sum_{k=1}^n\frac{2h}{6}[f(x_{2k-2})+4f(x_{2k-1})+f(x_{2k})],;h=\frac{b-a}{2n}
$$
于是有：
$$ I=\int_a^bf(x)dx=\sum_{k=1}^n\int_{x_{2k-2}}^{x_{2k}}f(x)dx\\approx\sum_{k=1}^n\frac{h}{3}[f(x_{2k-2})+4f(x_{2k-1})+f(x_{2k})]\=\frac{h}{3}[f(a)+f(b)+4\sum_{k=1}^nf(x_{2k-1})+2\sum_{k=1}^{n-1}f(x_{2k})]
$$
记复化抛物线公式 $S_n$ 为：
$$ S_n=\frac{h}{3}[f(a)+f(b)+4\sum_{k=1}^nf(x_{2k-1})+2\sum_{k=1}^{n-1}f(x_{2k})]
$$
第六章 解线性代数方程组的直接法
1. LU 分解法
当矩阵 A 的前 n-1 个顺序主子式都不为零时，矩阵 A 可以唯一地分解为两个三角矩阵的乘积：
$$ A=LU
$$
其中 L 是单位下三角矩阵， U 是上三角矩阵。
如何求 LU 分解矩阵：
- 利用初等行变换将矩阵 A 化为上三角矩阵 U；
- 有下三角可逆矩阵 P，使得 PA=U，从而有 LU 分解： $A=P^{-1}U;(L=P^{-1})$ .
原方程 $Ax=b$ 等价于 $LUx=b$ ，令 $Ux=y$ ，有
$$ Ly=b
$$
从 $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)$ ，则称
$$ \rho(A)=max\lvert{\lambda_i}\rvert;(1\leq{i}\leq{n})
$$
为矩阵 A 的谱半径.
5. 条件数
条件数
数 $\parallel{A}\parallel\cdot\parallel{A^{-1}}\parallel$ 称为矩阵 $A$ 的条件数，记为 $Cond(A)$ 。
当线性方程组的系数矩阵 $A$ 的条件数 $ Cond(A)$ 很大时，说明在系数矩阵或右端项产生微小变化时会引起解的巨大变化，则称此方程组是“病态”方程组，否则称方程组为“良态”方程组。
条件数和范数有关，可以在条件数上加下标，对应的范数也应加相同的下标：
$$ Cond(A){\infty}=\parallel{A}\parallel{\infty}\cdot\parallel{A^{-1}}\parallel_{\infty} \ Cond(A){2}=\parallel{A}\parallel{2}\cdot\parallel{A^{-1}}\parallel_{2}=\sqrt{\lambda_1/\lambda_n} \
$$
其中， $\lambda_1$ ， $\lambda_n$ 是矩阵 $A^TA$ 的最大和最小特征值，故 $Cond(A)_2$ 又称谱条件数。
条件数的性质
- $Cond(A)\geq{1}$ .
- 单位矩阵、置换矩阵和正交矩阵的谱条件数都为 1.
- 对任意非零实数 $\alpha$ ，有 $Cond(\alpha{A})=Cond(A)$ .
第八章 解线性方程组的迭代法
1. Jacobi 迭代
设有方程组
$$ \begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1 \ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n=b_2 \ ............ \ a_{n1}x_1+a_{n2}x_2+...+a_{nn}x_n=b_n \end{cases}
$$
用矩阵表示为
$$ Ax=b
$$
假设 $a_{ii\neq{0}}$ ，令
$$ \begin{cases} b_{ij}=-a_{ij}/a_{ii},;i\neq{j} \ g_i=bi/a_{ii},;i=1,2,...,n \end{cases}
$$
方程组可改写成
$$ \begin{cases} x_1=\qquad\qquad{b_{12}x_2+b_{13}x_3+...+b_{1n}x_n}+g_1 \ x_2=b_{21}x_1\qquad\qquad+{b_{23}x_3+...+b_{2n}x_n}+g_2 \ ............ \ x_n=b_{n1}x_1+{b_{n2}x_2+b_{n3}x_3+...+b_{n,n-1}x_{n-1}}+g_n \ \end{cases}
$$
若令
$$ B=\begin{bmatrix} 0 & b_{12} & b_{13} & \cdots & b_{1n} \ b_{21} & 0 & b_{23} & \cdots & b_{2n} \ \vdots & \vdots & \vdots & & \vdots \ b_{n1} & b_{n2} & b_{n3} & \cdots & 0 \end{bmatrix}
$$
$$ D=\begin{bmatrix} a_{11} & & & \ & a_{22} & & \ & & \ddots & \ & & & a_{nn} \ \end{bmatrix}, ; g=\begin{pmatrix} g_1 \ g_2 \ \vdots \ g_3 \end{pmatrix}
$$
则
$$ B=D^{-1}(D-A)=I-D^{-1}A,;g=D^{-1}b
$$
方程可用矩阵表示为
$$ x=Bx+g
$$
选取初始向量 $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)}$ ，依此类推，可得到迭代格式
$$ \begin{cases} x_1^{(k+1)}=\qquad\qquad{b_{12}x_2^{(k)}+b_{13}x_3^{(k)}+...+b_{1n}x_n^{(k)}}+g_1 \ x_2^{(k+1)}=b_{21}x_1^{(k)}\qquad\qquad+{b_{23}x_3^{(k)}+...+b_{2n}x_n^{(k)}}+g_2 \ ............ \ x_n^{(k+1)}=b_{n1}x_1^{(k)}+{b_{n2}x_2^{(k)}+b_{n3}x_3^{(k)}+...+b_{n,n-1}x_{n-1}^{(k)}}+g_n \ \end{cases}
$$
即
$$ x^{(k+1)}=Bx^{(k)}+g,;k=0,1,2,\cdots
$$
通过上式的计算，可得到向量序列 $\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}$ 代入迭代公式进行计算.
其迭代过程为：
$$ \begin{cases} x_1^{(k+1)}=\qquad\qquad{b_{12}x_2^{(k)}+b_{13}x_3^{(k)}+...+b_{1n}x_n^{(k)}}+g_1 \ x_2^{(k+1)}=b_{21}x_1^{(k+1)}\qquad\qquad+{b_{23}x_3^{(k)}+...+b_{2n}x_n^{(k)}}+g_2 \ ............ \ x_n^{(k+1)}=b_{n1}x_1^{(k+1)}+{b_{n2}x_2^{(k+1)}+b_{n3}x_3^{(k+1)}+...+b_{n,n-1}x_{n-1}^{(k+1)}}+g_n \ \end{cases}
$$
令
$$ L=\begin{bmatrix} 0 & & & & \ b_{21} & 0 & & & \ b_{31} & b_{32} & 0 & & \ \vdots & \vdots & & \ddots & \ b_{n1} & b_{n2} & \cdots & & 0 \ \end{bmatrix},; U=\begin{bmatrix} 0 & b_{12} & b_{13} & \cdots & b_{1n} \ & 0 & b_{23} & \cdots & b_{2n} \ & & 0 & & \vdots \ & & & \ddots & b_{n-1,n} \ & & & & 0 \ \end{bmatrix};
$$
迭代过程用矩阵表示为
$$ x^{(k+1)}=Lx^{(k+1)}+Ux^{(k)}+g,;k=0,1,2,\cdots
$$
因 $(I-L)$ 存在，所以上述迭代格式可表示为
$$ x^{(k+1)}=(I-L)^{-1}Ux^{(k)}+(I-L)^{-1}g
$$
称 $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$ 按行严格对角占优或按列严格对角占优，即满足条件
$$ \begin{vmatrix}a_{ii}\end{vmatrix}>\sum_{j=1,i\neq{j}}^n\begin{vmatrix}a_{ij}\end{vmatrix},;i=1,2,\cdots,n
$$
或
$$ \begin{vmatrix}a_{ii}\end{vmatrix}>\sum_{i=1,i\neq{j}}^n\begin{vmatrix}a_{ij}\end{vmatrix},;j=1,2,\cdots,n
$$
则 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$ 后，把它改写成等价形式：
$$ x=\phi(x)
$$
再作迭代
$$ x_{n+1}=\phi(x_n)
$$
简单迭代法敛散性判别
- 若 $\lvert{\phi'(x)}\rvert<1$ ，则简单迭代法收敛.
- 若 $\phi'(\xi)=\cdots=\phi^{(p-1)}(\xi)=0,\phi^{(p)}(\xi)\not=0,$ ，则迭代在 $\xi$ 处 p 阶收敛.
4. 牛顿法
$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}
$$
5. 弦截法
$$ x_{n+1}=x_n-\frac{f(x_n)}{f(x_n)-f(x_{n-1})}(x_n-x_{n-1})
$$
第十一章 常微分方程初值问题的数值解法
1. Euler 方法（显示欧拉法）
$$ \begin{cases} y_{n+1}=y_n+hf(x_n,y_n)\qquad n=0,1,2,\cdots,N-1 \ y(x_0)=y_0 \ y'=f(x,y) \end{cases}
$$
2. 向后 Euler 方法（隐式欧拉法）
$$ \begin{cases} y_{n+1}=y_n+hf(x_{n+1},y_{n+1})\qquad n=0,1,2,\cdots \ y(x_0)=y_0 \ y'=f(x,y) \end{cases}
$$
3. 改进 Euler 方法
$$ \begin{cases} y_{n+1}=y_n+\frac{h}{2}[f(x_{n},y_{n})+f(x_{n+1},y_n+hf(x_n,y_n))]\quad n=0,1,2,\cdots \ y(x_0)=y_0 \ y'=f(x,y) \end{cases}
$$
4. 梯形公式
$$ \begin{cases} y_{n+1}^{(0)}=y_n+hf(x_n,y_n) \ y_{n+1}^{(k+1)}=y_n+\frac{h}{2}[f(x_{n},y_{n})+f(x_{n+1},y_{n+1}^{(k)})]\quad k=0,1,2,\cdots \ y'=f(x,y) \end{cases}
$$
注意：
- 使用改进 Euler 方法进行迭代时，需要解隐式方程.
- 若题中不给出迭代步长 $h$，则 $h=0.1$.