二次方程与低精度算法


低级二次公式有什么有趣的?这是一个公式毕竟。你只要把数字塞进去。

嗯,有一个有趣的问题。当线性系数b相对于其他系数而言很大,当在浮点运算中实现时,二次公式可能会给出错误的结果。

二次公式与精度损失

二次公式表明:

由以下人员给出:

没错,但是让我们看看当我们有a=c= 1和b= 108

    from math import sqrt

    def quadratic(a, b, c):
        r = sqrt(b**2 - 4*a*c)
        return ((-b + r)/(2*a), (-b -r)/(2*a))

    print( quadratic(1, 1e8, 1) )

这将返回:

    (-7.450580596923828e-09, -100000000.0)

第一根错了大约25%,尽管第二根是正确的。

发生了什么事?二次方程违反了数值分析的基本规则:避免减去几乎相等的数字。两个数字越相似,减去它们的精确度就越低。在这种情况下,√(b- 4交流电)非常接近于b

如果我们要求Python评估:

    1e8 - sqrt(1e16-4)

我们得到了1.49e-8当正确答案是2.0e-8

提高二次公式的精度

解决这个问题的方法是通过将二次公式的分子乘以1使其合理化,其形式如下:

(∓这个符号远没有。这一定意味着如果你在二次公式中取+号,取上面的-号,反之亦然。(

当我们乘以上面的表达式并简化后,我们得到:

让我们用Python对此进行编码并尝试一下。

    def quadratic2(a, b, c):
        r = sqrt(b**2 - 4*a*c)
        return (2*c/(-b - r), 2*c/(-b+r))

    print( quadratic2(1, 1e8, 1) )

这将返回:

    (-1e-08, -134217728.0)

那么,我们的新二次方程更好吗?它给出了第一个根的正确答案,精确到机器精度以内。但是现在第二根错了34%。为什么第二根是错的?和以前一样的原因:我们减去了两个几乎相等的数字!

二次公式的熟悉版本正确计算较大的根,新版本正确计算较小的根。这两个版本总体上都不好。我们总是使用新的二次公式不会比旧的更好或更坏。当避免减去几乎相等的数字时,每一个都更好。

解决方法是使用两者二次公式,对你要计算的根使用合适的公式。

低精度算术

这是一个实际问题吗?是的,这就是原因:一切旧的又都是新的。

在双精度(64位浮点)算法变得普遍之前,二次公式中可能存在的不准确性是严重的。回到过去,工程师们更可能熟悉二次公式的替代形式。你仍然可以碰到二次方程,甚至在双精度运算中也会给你带来麻烦,就像上面的例子一样,但是当你有更多的位可以支配时,这就不太可能成为问题。

现在,我们又对低精度算术感兴趣了。中央处理器已经变得更快了,但是在内存中移动比特却没有。相对于CPU速度,内存操作变得更慢。这意味着我们需要更加关注内存管理,而不是浮点运算速度。

相对于中央处理器来说,内存不仅处理速度慢,而且需要更多的能量。根据Gustafson,从动态随机存取存储器读取64位需要65倍于浮点乘加的能量,因为它发生在芯片外。下面的表格来自古斯塔夫森的书的第六页,给出了细节。使用精度较低的浮点可以节省能源,因为在相同位数的内存中可以读入更多的数字。(这里,pJ =微微焦耳。(

因此,我们可能对低精度算法感兴趣,以节省电池供电的移动设备的能量,或者节省处理大量数据的服务器应用程序的时钟周期。这意味着大多数人已经忘记的数字技巧又有意义了。