计算多项式 Evaluating a Polynomial

求多项式的值的最佳方式是什么？

What is the best way to evaluate a Polynomial？

• 普通办法：直接一次一次算
• 降幂系数：将多项式写成降幂系数形式后嵌套

一般嵌套（Horner）过程：

---

二进制数 Binary Numers

二进制转十进制

对于一个二进制数

转为十进制为

关于小数部分的小妙招

将小数部分设x后求解

则可以得到

试一试：把$(11.1\overline{101})_{2}$转为十进制（点击查看答案）

答案：$(11.1\overline{101})_{2} = 3 + \frac{6}{7} = \frac{27}{7}$

十进制转二进制

假如我们要把十进制数53.7转为二进制数

整数部分

对于整数部分53

所以它的二进制为

小数部分

对于小数部分.7

所以它的二进制为

所以53.7的二进制即为

---

IEEE 浮点格式 IEEE Floating Point Formats

浮点数由三部分组成：符号（+ 或 −）sign bits、包含有效位串的尾数 mantissa bits，以及指数 exponent bits。这三个部分被存储在一个计算机字中。

这样我们就能表示任何一个值了

试一试：把5.75用single表示（点击查看答案）

先把十进制写成二进制科学计数法

$$\begin{array}{rcl} 5.75_{10} &=& 101.11_{2} \\ &=& 1.0111_{2} \times 2^{2} \end{array}$$

我们可以得到

$$\begin{array}{rcl} \text{sign} &=& +1 \\ \text{exponent} &=& 2 \\ \text{mantissa} &=& 1.0111_{2} = 1 + 2^{-2} + 2^{-3} + 2^{-4} = 1.4375 \end{array}$$

真实的指数为

$$\begin{array}{rcl} \text{exponent} &=& 2 + 127 \\ &=& 129 \\ &=& 10000001_{2} \end{array}$$

对应 32 位布局就是

$$\begin{array}{c|c|c} \hline \text{sign (1)} & \text{exponent (8)} & \text{mantissa bits (23)} \\ \hline 0 & 10000001 & 01110000000000000000000 \\ \hline \end{array}$$

计算机算术中的舍入误差 Rounding Error

由于位数有限，因此会出现0.1 + 0.2 ≠ 0.3 的情况（因为0.1和0.3无法用有限位数来表示）

---

误差 Errors

绝对误差与相对误差 absolute error and relative error

设$x$是真值 exact value，$x^{*}$是 $x$ 的近似值 approximate。

绝对误差 absolute error（或直接说error） of $x^{*}$

相对误差 relative error of $x^{*}$

误差界 Error bound

真值 $x$ 往往不知道，因而 $e(x^{*})$算不出来，只能找一个上界。若

则称 $\varepsilon(x^{*})$为 $x^{*}$的 误差界 error bound

误差估计 Estimation of error

设 $y=f(x)$。用近似值 $x^*$代替真值 $x$，则 $y$的误差由中值定理给出：

其中 $\xi$ 在 $x$x 与 $x^{*}$ 之间。若 $x^{*}$ 很接近 $x$，可用 $f'(x^{*})$近似 $f'(\xi)$，则

其中 $\dfrac{|e(y)|}{|e(x)|}$​称为 放大因子 amplification factor ，也叫 绝对条件数 absolute condition number。

多变量误差估计

设 $y=f(x_{1},x_{2})$。用 $x_{1}^{*},x_{2}^{*}$ 代替真值后，

取绝对值，得到绝对误差上界：

---

有效数字 Significant Digits

如何计算有效数字？

若 $x^{*}$ 作为 $x$ 的近似值，其绝对误差不超过某一位数字的半个单位，而该数字到 $x^{*}$的第一位非零数字共有 $n$ 位，则称 $x^{*}$近似 $x$时具有 $n$位有效数字。

即存在某个十进制位（单位为 $10^{k}$），使得

666，看得我头晕。。。让我们来把他变得简单一点

如果绝对误差≤.00…05（n个0），则称n+1位有效数字

避免有效数字损失的办法

1. 避免两个接近数字之间直接相减
   1. 开方相减 $\begin{array}{rcl} \sqrt{x+\epsilon}-\sqrt{x} &=& \dfrac{\epsilon}{\sqrt{x+\epsilon}+\sqrt{x}} \end{array}$
   2. 对数相减 $\begin{array}{rcl} \ln(x+\epsilon)-\ln x &=& \ln\left(1+\dfrac{\epsilon}{x}\right) \end{array}$
   3. $\begin{array}{rcl} 1-\cos(\epsilon) &=& 2\sin^{2}\!\left(\dfrac{\epsilon}{2}\right) &=& \dfrac{\sin^{2}(\epsilon)}{1+\cos\epsilon}\end{array}$
2. 避免大数字直接和小数字运算
3. 避免大乘数和小除数

---

课后作业

把十进制数14.65化为二进制

答案：

把二进制数$\begin{array}{rcl} (11.1\overline{101})_{2} \end{array}$化为十进制。

答案：

下面的数各有几位有效数字？绝对误差界和相对误差界分别是多少？
$\begin{array}{rcl} x_{1}^{*} &=& 4.7021 \\ x_{2}^{*} &=& 0.067 \\ x_{3}^{*} &=& 280.20 \end{array}$

答案：

为避免有效数字丢失，应如何计算下列表达式？
$\begin{array}{rcl} \sqrt{x+\dfrac{1}{x}} – \sqrt{x-\dfrac{1}{x}}, \qquad |x|\gg 1 \end{array}$
$\begin{array}{rcl} \displaystyle\int_{N}^{N+1}\dfrac{1}{1+x^{2}}\,\mathrm{d}x, \qquad N\text{ 很大} \end{array}$

答案：