数值分析期末公式总结

第一章误差

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.