Computational Methods

第 1 章绪论

1.2 计算方法的误差

1.2.2 误差与有效数字

绝对误差
$\epsilon(x)=x^*-x$
其中精确值为 $x$ , 近似值为 $x^*$
有效数字
定义: 若近似值 $x^*$ 的绝对误差限是某一位上的半个单位, 且该位直到 $x^*$ 的第一位的非零数字一共有 $n$ 位, 则称近似值 $x^*$ 有 $n$ 位有效数字
若是通过四舍五入的原则确定近似值, 则可以直接肉眼观察有效数字位数
如果将 $x$ 的近似值 $x^*$ 表示为
$x^{*}=\pm x.a_{1}a_{2}\dots a_{n} \times 10^{m}$ $(a_{1} \ne 0)$
若 $|x^{*} - x| \le \frac{1}{2} \times 10^{m-l}, 1\le l \le n$
则可得出 $x^{*}$ 的有效数字位数为 $l$

1.2.4 数值运算的误差估计

$\eta(x^{*})$ 表示 $x^{*}$ 的误差限

$\eta(x^{*}\pm y^{*})=\eta(x^{*})+\eta(y^{*})$
$\eta(x^{*}y^{*})=|x^{*}|\eta(y^{*})+|y^{*}|\eta(x^{*})$
$\eta\left( \frac{x^{*}}{y^{*}} \right)=\frac{|x^{*}|\eta(y^{*})+|y^{*}|\eta(x^{*})}{|y^{*}|^{2}}$

第 2 章非线性方程的数值解法

2.2 迭代法及其收敛性

2.2.2 不动点的存在性与收敛性

[定理 2.3] 设迭代函数 $\phi(x)$ 在 $[a,b]$ 上具有连续的一阶导数, 且
(1) 当 $x \in [a,b]$ 时, $a\le \phi(x) \le b$ ;
(2) 存在正数 $L<1$ , 对任意 $x \in [a,b]$ , 有 $|\phi^{\prime}(x)|\le L < 1$ 成立, 则 $x=\phi(x)$ 在 $[a,b]$ 上有唯一解 $x^{*}$ , 且对任意初始近似值 $x_{0} \in [a,b]$ , 迭代过程 $x_{k+1}=\phi(x_{k})(k=0,1,2,\dots)$ 收敛, 且 $\lim_{ h \to \infty }x_{k} = x^{*}$
此定理为收敛性定理

2.3 迭代收敛的加速方法

2.3.1 迭代的收敛速度

$\lim_{ k \to \infty } \frac{\epsilon_{k+1}}{\epsilon_{k}^{k}}=C, C\ne 0)$ , 则称其为 $p$ 阶收敛

2.3.2 收敛过程的加速

艾特肯(Aitken)加速方法
$\begin{cases} x_{k+1}^{(1)}=g(x_{k})\\ x_{k+1}^{(2)}=g(x_{k+1}^{(1)}) \\ x_{k+1}=x_{k+1}^{(2)}-\frac{(x_{k+1}^{(2)}-x_{k+1}^{(1)})^{2}}{x_{k+1}^{(2)}-2x_{k+1}^{(1)}+x_{k}}\end{cases}$

2.4 牛顿迭代法

2.4.1 牛顿法的构造及牛顿迭代公式

一般迭代公式
$x_{k+1}=x_{k}-\frac{f(x_{k})}{f^{\prime}(x_{k})}$

2.4.3 初值的选取

对于初值 $x_{0}$
$2|f^{\prime}(x_{0})|^{2}> |f^{\prime\prime}(x_{0})||f(x_{0})|$

第 4 章插值法与曲线拟合

4.2 拉格朗日插值

拉格朗日插值多项式
$p_{n}(x)=\sum_{i=0}^{n}y_{i}\left( \prod_{\substack{j=0\\j\ne i}}^{n} \frac{x-x_{j}}{x_{i}-x_{j}} \right)$
插值余项
$R_{n}(x)= \frac{f^{n+1}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_{i})$

4.3 牛顿插值

4.3.2 差商的概念

一阶差商
$f[x_{0}, x_{1}] = \frac{f(x_{0})-f(x_{1})}{x_{0}-x_{1}}$
二阶差商
$f[x_{0},x_{1},x_{2}]=\frac{f[x_{0},x_{1}]-f[x_{1},x_{2}]}{x_{0}-x_{2}}$

4.3.4 牛顿插值公式

牛顿插值公式
$N_{n}(x) = f(x_{0})+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\dots+f[x_{0},x_{1},\dots,x_{n}](x-x_{0})(x-x_{1})\dots(x-x_{n-1})$
插值余项
$R_{n}(x)=f[x,x_{0},x_{1},\dots,x_{n}](x-x_{0})(x-x_{1})\dots(x-x_{n})$

4.4 埃尔米特插值

埃尔米特插值公式
$H_{2n+1}(x)=\sum_{i=0}^{n}\left[ y_{i}\left( 1-2(x-x_{i})\sum_{\substack{k=0\\k\ne i}}^{n} \frac{1}{x_{i}-x_{k}} \right) l_{i}^{2}(x)+y_{i}^{\prime}(x-x_{i})l_{i}^{2}(x)\right]$
~~感觉这个公式没什么用~~
插值余项
$R_{2n+1}(x)= \frac{f^{(2n+2)(\xi)}}{(2n+2)!}\prod_{i=0}^{n}(x-x_{i})$

4.5 分段插值

插值公式和不分段差不多
插值余项
- 分段线性插值
  $|f(x)-s_{1}(x)|\le \frac{1}{8} h_{i}^{2} \max_{x_{i}\le x \le x_{i+1}}|f^{\prime\prime}(x)|$
- 分段三次埃尔米特插值
  $|f(x)-s_{3}(x)|\le \frac{h^{4}}{384} \max_{a\le x\le b}|f^{(4)}(x)|, h=\max h_i$

第 5 章数值积分与数值微分

5.1 数值积分

5.1.1 代数精度

令 $f(x)=x^{k}$ , 代入原多项式, 使得原公式仍然成立的最大值k, 即为该公式的代数精度k

5.1.3 牛顿-科茨求积公式

~~记了也记不住的~~公式

$C_{k}= \frac{(-1)^{n-k}}{n\cdot k!(n-k)!}\int_{0}^{n}\prod_{\substack{j=0\\j\ne k}}^{n}(i-j)dt$
$R=\frac{h^{n+2}}{(n+1)!}\int_{0}^{n}f^{(n+1)}(\xi)\prod_{j=0}^{n}(t-j)dt, \xi \in[a,b]$
定理
当 $n$ 为偶数时, $n$ 阶 Newton-Cotes 求积公式的代数精度至少是 $n+1$

5.1.4 复化求积公式

梯形
$\int_{a}^{b}f(x)dx= \frac{h}{2} \left[ f(a) + 2\sum_{k=1}^{n-1}f(x_{k})+f(b) \right]=T_{n}$
$R_{T}=- \frac{1}{12}(b-a)h^{2}f^{\prime\prime}(\eta)$
Simpson
$\int_{a}^{b}f(x)dx= \frac{h}{3}\left[ f(a)+4\sum_{k=1}^{m}f(x_{2k-1})+2\sum_{k=1}^{m-1}f(x_{2k})+f(b) \right ]=S_{n}$
$R_{S}=- \frac{1}{180}(b-a)\left( \frac{h}{2} \right)^{4}f^{(4)}(\eta)$
Cotes
$\int_{a}^{b}f(x)dx = \frac{4h}{90}\left[ 7f(a)+32\sum_{k=1}^{m}f\left( x_{4k-3}\right)+12\sum_{k=1}^{m}f(x_{4k-2}) +32\sum_{k=1}^{m}f(x_{4k-1}) +14\sum_{k=1}^{m-1}f(x_{4k})+7f(b)\right]=C_{n}$
$R_{C}=- \frac{2}{945}(b-a)\left( \frac{h}{4} \right)^{6}f^{(6)}(\eta)$

5.1.5 龙贝格求积公式及算法

梯形法的递推化
$T_{k1}= \frac{h}{2}[f(x_{k})+f(x_{k+1})]$
$T_{k2}= \frac{T_{k1}}{2} + \frac{h}{2}f\left( x_{k+\frac{1}{2}} \right)$ 前一项系数为 $\frac{1}{2}$ , 后一项系数为 $\frac{h}{2}$
Romberg 公式
$S_{n}= \frac{4}{3}T_{2n}- \frac{1}{3}T_{n}$
$C_{n}= \frac{16}{15}S_{2n}- \frac{1}{15} S_{n}$
$R_{n} = \frac{64}{63}C_{2n}- \frac{1}{63}C_{n}$

第 6 章常微分方程数值解法

公式

欧拉法
$\begin{cases}y_{n+1}=y_{n}+hf(x_{n},y_{n})\\y_{0}=y(x_{0})\end{cases}$
梯形法
$\begin{cases}y_{n+1}=y_{n}+ \frac{h}{2}[f(x_{n},y_{n})+f(x_{n+1},y_{n+1})]\\y_{0}=y(x_{0})\end{cases}$
改进的欧拉法
$\begin{cases}y_{p}=y_{n}+hf(x_{n},y_{n})\\y_{c}=y_{n}+hf(x_{n+1},y_{p})\\y_{n+1}=\frac{1}{2}(y_{p}+y_{c})\end{cases}$
龙格-库塔法
~~感觉和前面的区别不大, 偷个懒~~
精度
省流
若 $y(x_{n+1})-y_{n+1} = O(h^{p+1})$
则此方法的精度为 $p$ 阶
不要把此处的精度和第 5 章里的代数精度搞混

第 1 章 绪论