1.6 再议多项式求值

对于多项式

$$p(x) = \sum_{i=0}^d a_i x^i$$

如果用 Horner 规则计算：

$\begin{aligned} &p = a_d\\ &\text{for } i = d-1 \text{ down to } 0\\ &\quad p = x*p + a_i\\ &\text{end for} \end{aligned}$

然后对原来的结果增加下标，使得对每一个值有唯一的符号($p_0$ 是最后的结果):

$\begin{aligned} &p_d = a_d\\ &\text{for } i = d-1 \text{ down to } 0\\ &\quad p_i = x*p_{i+1} + a_i\\ &\text{end for} \end{aligned}$

然后对每个浮点运算考虑舍入误差，可得:

$\begin{aligned} &p_d = a_d\\ &\text{for } i = d-1 \text{ down to } 0\\ &\quad p_i = \left[(x*p_{i+1})(1 + \delta_i) + a_i\right](1+\delta_i')\\ &\text{end for} \end{aligned}$

展开，可以得到多项式最后计算值的表达式：

$$p_0 = \sum_{i=0}^{d-1} \left[(1+\delta_i^\prime)\prod_{j=0}^{i-1} (1 +\delta_j)(1+\delta_j^\prime)\right]a_ix^i + \left[\prod_{j=0}^{d-1} (1 +\delta_j)(1+\delta_j^\prime)\right]a_dx^d$$

假设 $j\varepsilon \le 1$， 并用二项式展开定理及 $\frac{1}{1-x}$ 的泰勒展式可得如下不等式成立：

$$\begin{aligned} (1 +\delta_1)\cdots(1 +\delta_j)\leq &(1 +{\varepsilon})^j\leq \frac{1}{1-j\varepsilon} =1 + j\varepsilon + O(\varepsilon^2)\\ (1 +\delta_1)\cdots(1 +\delta_j)\ge &(1 - {\varepsilon})^j\ge1 - j\varepsilon \end{aligned}$$

通常做合情合理的假设 $j\varepsilon\ll 1$ 并做近似

$$1 - j\varepsilon\leq(1 +\delta_1)\cdots(1 +\delta_j)\leq1 + j\varepsilon\qquad(*)$$

可以重写 $p_0$ 的表达式

$$p_0 = \sum_{i=0}^d (1+\overline{\delta}_i)a_ix^i = \sum_{i=0}^d \overline{a}_ix^i, \text{ 其中 }\mid{\overline{\delta}_i}\mid\leq2d\varepsilon,$$

故 $p(x)$ 的实际计算值 $p_0$ 可以看成是具有不同系数的一个多项式的精确值，进 而可得如下的误差估计式：

$$\begin{align} |p_0-p(x)| & = |\sum_{i=0}^d(1+\overline{\delta}_i)a_ix^i - \sum_{i=0}^da_ix^i|\\ & = |\sum_{i =0}^d \overline{\delta}_ia_ix^i|\\ & \le \sum_{i=0}^d\varepsilon2d|a_i\cdot x^i|\\ & \le 2d\varepsilon\sum_{i=0}^d|a_i\cdot x^i| \end{align}$$

说明：

• $\sum_{i=0}^d|a_i\cdot x^i|$ 是可以计算的最大值。
• 若取 ${\overline{\delta}_i} = \varepsilon\cdot \text{sign}(a_ix^i)$ 误差估计 式中的等号是可以成立的， 乘了一个适当的系数 $2d$。
• 可使用 $$\frac{\sum_{i=0}^d|a_ix^i|}{|\sum_{i=0}^da_ix^i|}$$ 作为多项式求值的相对条件数。

花费双倍运算量容易计算多项式的值及其误差界:

$\begin{aligned} &p_d = a_d,\, bp = |a_d|\\ &\text{for } i = d-1 \text{ down to } 0\\ &\quad p = x*p + a_i\\ &\quad bp = |x|\cdot bp + |a_i|\\ &\text{end for}\\ &\text{eror bound}=bp=2d\cdot\varepsilon\cdot bp \end{aligned}$

故多项式的正确值位于区间

$$[p-bp,p+bp]$$

之间，并且确保正确的十进制数字位数是

$$-log_{10}(|\frac{bp}{p}|)$$

定义 1.1 条件数为无穷大的问题称为是病态(ill-posed)的，否则称为适定 (well-posed)的.

定义 1.2 设

$$p(z) = \sum_{i=0}^da_iz^i$$

和

$$q(z) = \sum_{i=0}^db_iz^i.$$

定义 $p$ 到 $q$ 的相对距离 $d(p,q)$ 为满足

$$|a_i - b_i| \le d(p,q)\cdot |a_i|, \forall 0 \le i \le d$$

的最小值。若所有的 $a_i \not= 0$，则有

$$d(p, q)= \text{max}_{0\le i \le d}\left|\frac{a_i - b_i}{a_i} \right|$$

另外，若 $a_i = 0$, 则因 $d(p,q)$ 有限，$b_i$ 必为零。

定理 1.2 假如 $p(z) = \sum_{i=0}^da_iz^i$ 不恒等于零，则

$$\min\left\{d(p,q):q(x) = 0\right\} = \frac{|\sum_{i=0}^da_ix^i|}{\sum_{i=0}^d|a_ix^i|}$$

换言之, 在 $x$ 点处距 $p$ 最近的病态多项式 $q$ 到 $p$ 的距离是 $p(x)$ 的条件数的倒数。

证明：

记

$$q(z) = \sum b_iz^i = \sum(1 + \varepsilon_i)a_iz^i$$

使得

$$d(p,q) = \max_i|\varepsilon_i|，$$

则由

$$q(x) = 0$$

推出

$$\begin{align} |p(x)| & = |q(x) - p(x)|\\ & = |\sum_{i=0}^d\varepsilon_ia_ix^i|\\ & \le \sum_{i=0}^d|\varepsilon_ia_ix^i|\\ & \le \max_i|\varepsilon_i|\sum_i|a_ix^i| \end{align}$$

由此可得

$$d(p,q) = \max|\varepsilon_i|\ge \frac{|p(x)|}{\sum_i|a_ix^i|}$$

取下界的多项式 $q$ 是存在的，只需选择

$$\varepsilon_i = \frac{-p(x)}{\sum|a_ix^i|}\cdot sign(a_ix^i)$$

证毕。 $\square$

说明：

• 给定问题的条件数与该问题到最近病态问题的距离之间的互为倒数关系是一个非常普遍的 关系。
• 知道了矩阵的 Jordan 标准型，则计算矩阵的特征值就是一件非常容易的事情。
• 同样如果知道多项式的根，则多项式求值也是一件非常容易的事情。

$$p(x) = a_d\Pi_{i=1}^d(x - r_i)，$$

其中 $r_i, 1\le i\le d$ 为 $d$ 次多项式的 $d$ 个根, 算法流程如下：

$\begin{aligned} &p = a_d\\ &\text{for } i = 1 \text{ down to } d\\ &\quad p = p\cdot(x - r_i)\\ &\text{end for} \end{aligned}$

计算值 $p$ 与 $p(x)$ 的关系如下：

$$p = p(x)\cdot (1 + \delta),\text{ 其中 } |\delta| \le 2d\varepsilon$$

但需要知道多项式根！