第一章 误差
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.