计算科学 - 多项式符号的准确评估 - 吾爱随笔录

多项式符号的准确评估

计算科学浮点多项式准确性

2021-12-20 20:43:46

令为具有浮点系数的多项式，令为浮点值。 $p$ $a$

有没有一种方法可以在浮点运算中准确评估 $p(a)$

我不关心实际值，只关心它的符号。但我想要确切的标志。 $f(a)$

如果有帮助，我们可以假设。 $0 \le a \le 1$

3个回答

补偿 Horner 方法 ( http://www-pequan.lip6.fr/~jmc/polycopies/Compensation-horner.pdf ) 具有以下形式的错误界限其中是单位舍入，所以只要。除了非常靠近根部外，这将无处不在。由于您可以缩放多项式，以便除了之外也成立，因此根周围的故障区域大小约为，其中

| c o m p h o r n e r (p, x) - p (x) | \leq u | p (x) | + γ_{2 n}^{2} \tilde{p} (x), \tilde{p} (x) = \sum_{i} | a_{i} | | x |^{i}, γ_{n} = \frac{n u}{1 - n u},

$|\mathrm{comphorner}(p, x) - p(x)| \leq u|p(x)| + \gamma_{2n}^2\tilde p(x), \qquad \tilde p(x) = \sum_i |a_i||x|^i, \quad \gamma_n = \frac{n u}{1-n u},$

u

$u$

| p (x) | \geq γ_{2 n}^{2} \tilde{p} (x)

$|p(x)| \geq \gamma_{2n}^2\tilde p(x)$

| a_{i} | \leq 1

$|a_i|\leq 1$

| x | \leq 1

$|x|\leq 1$

u^{2 / m}

$u^{2/m}$

m

$m$ 是根的重数。对于单根，这意味着只有当给定的参数恰好是根时才可能失败，而对于双根，它必须与一些机器 epsilon 一起出现。

我不认为有一种方法可以在不依赖额外精度的情况下普遍有效，这是根附近的一个非常病态的问题。

为此，您可以使用区间算术。

您可以将扩展算法 [1] 与算术过滤器 [2] 结合使用来提高性能。这个想法是首先使用标准浮点算术以及指示符号是否准确的边界进行计算，并且仅在无法评估符号时使用（更昂贵的）扩展算法。另请参阅我的调查文章 [3] 以及我的编程库 geogram [4] 中的配套实现。它具有作为 .h/.cpp 文件对的独立实现（使用下载部分中的 multiprecision_PSM）。

[1] https://people.eecs.berkeley.edu/~jrs/papers/robusr.pdf

[2] https://hal.inria.fr/inria-00344297/fr/

[3] https://hal.inria.fr/hal-01225202

[4] http://alice.loria.fr/software/geogram/doc/html/index.html

其它你可能感兴趣的问题

上一篇IEEE-754 标准是否要求 exp2 正确舍入？下一篇Crank-Nicolson 方案中虚假振荡的起源是什么？