数值分析期末公式总结

数值分析期末公式总结

第一章 误差

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_0y_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_iH'(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.

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://cangmang.xyz/articles/1642848277745