Numerical Methods Using MATLAB(4版)-01-Preliminaries

引自Numerical Methods Using MATLAB(4版)书籍，如有侵权请联系删除

前言

最近做项目要自学一下这本书，于是想在博客下记录下自己的学习过程，并标记自己疑惑的地方。第一部分主要回顾了高数的一些重要定理，第二部分就是讲进制，第三部分讲误差分析。第三部分比较重要。

学习过程

<1>计算机误差
1、舍入误差 Round-off Errors
2、截断误差 Truncation Errors
3、解误差（求解结果与理论结果的误差）
4、残差：abs(f(x)=0,f((x')=0)

<2>eps
Floating-point relative accuracy
Matlab上精确度一般是2.2204e-16

<3>Horner's method
设 $n$ 项多项式 $P(x)$ 有以下形式
$(20)P(x)=a_nx^n+...+a_1x+a_0.$
霍纳法或合成法是用来评估多项式的方法。它是一种嵌套乘法的思想。比如，一个5项多项式可以写为嵌套乘法的形式
$P_5(x)=((((a_5x+a_4)x+a_3)x+a_2)x+a_1)x+a_0.$

理论1.13（霍纳法） 假设 $P(x)$ 是等式20中给出的级数且 $x=c$ 是评估 $P(c)$ 的数字。
设 $b_n=a_n$ 并计算
$(21)b_k=a_k+cb_{k+1},k=n-1,n-2,...,1,0;$
则 $b_0=P(c)$ 。如果
$(22)Q_0(x)=b_nx^{n-1}+...+b_2x+b_1.$
那么
$(23)P(x)=(x-c)Q_0(x)+R_0,$
$Q_0(x)$ 是 $n-1$ 项多项式的商且 $R_0=b_0=P(c)$ 是余数。

证明将22式中的右边和 $b_0$ 代入到23式中
$(24)P(x)=(x-c)(bx^{n-1}+...+b_2x+b_1)+b_0\\ =b_nx^n+(b_{n-1}-cb_n)x^{n-1}+...+(b_1-cb_2)x+b_0-cb_1.$

通过比较等式20和24中 $x^k$ 的系数来确定 $b_k$ ，如表1.1所示。
$P(c)=b_0$ 可以通过在等式22中代入 $x=c$ 并且用 $R_0=b_0$ 简单得出：
$(25)P(c)=(c-c)Q_0(c)+R_0=b_0.$
式子21中 $b_k$ 的递归公式可以很容易通过计算机得到。

Table1.1

当霍纳法手算时，也可以将 $P(x)$ 的系数列出然后根据式子 21简单计算，如表1.2。

Table1.2

<4>误差分析
假设 $\hat{p}$ 是近似于 $p$ 的值，则
绝对误差： $E_p=|p-\hat{p}|$
相对误差： $R_p=|p-\hat{p}|/|p|$
（相对误差较于绝对误差能够更好的表达误差）
定义：如果 $R_p<\frac{10^{1-d}}{2}$ ，我们称 $\hat{p}$ 近似于 $p$ 到 $d$ 位有效位数.
截断误差
舍入误差 vs 切断误差
误差抵消：精简后的泰勒和嵌套乘法可能会有更少误差

<5>big Oh 近似阶
如果存在常量 $C$ 和 $c$ 使得任何 $h \leq c$ 时有 $|f(h)| \leq C|g(h)|$ ，则称 $f(h)=O(g(h))$ 。
$h$ 要尽可能小且不超过1。
假设 $f(h)=p(h)+O(h^n)$ ， $g(h)=q(h)+O(h^m)$ ， $r=min \{ m,n \}$ ，则
$f(h)+g(h)=p(h)+q(h)+O(h^r)$
$f(h)g(h)=p(h)q(h)+O(h^r)$
$\frac{f(h)}{g(h)}=\frac{p(h)}{q(h)}+O(h^r)$
一些性质：1、 $O(h^p)+O(h^p)=O(h^p)$ 2、 $O(h^p)+O(h^q)=O(h^r),r=min\{p,q\}$ 3、 $O(h^p)O(h^q)=O(h^s),s=p+q$

<6>数列收敛顺序
如果存在常量 $K>0$ 使得 $\frac{|x_n-x|}{|r_n|} \leq K$ ，其中 $n$ 足够大，那么称 $\{x_n\}_{n=1}^{\infty}$ 以 $O(r_n)$ 的顺序收敛到 $x$ 。

<7>误差的传播
在运算过程中，一开始的误差会随着运算使得误差越来越大。如何误差真的特别特别小时，才有 $R_{pq}$ 近似于等于 $\hat{p}$ 和 $\hat{q}$ 误差之和。
如果这个运算使得误差不会越来越大，则称这个运算是稳定的，否则称这个运算是不稳定的。

词汇学习

formula：公式
calculus：微积分学
integral：积分
convergent：收敛
diverge：发散
intermediate：中间的
solution：解
arithmetic：算术
transparency：透明
parenthes：括弧
terminology：术语
truncation：截断
compound：复合
mantissa：尾数
practitioner：专业人员
implementation：实施
propagate：传播
quadratic：二次的
analogous：类似的
magnification：放大