同一个方程,两种数值困难
代数恒等式在精确运算中成立,计算机却必须使用有限精度。设存储的实系数就是精确输入,a=0,且 D=b2−4ac>0,所以 ax2+bx+c=0 有两个不同实根。先假设 c=0;零常数项将在后面单独处理。求根时要区分两件事:公式中的近数相减,以及根对系数变化的敏感性。改变公式可以改善前者,却无法消除后者。
记 s=D,约定 b≥0 时 sgn(b)=1,否则为 −1。构造
q=−21(b+sgn(b)s),xL=aq,xS=qc.
这里 L 指绝对值不小于另一根,而非数值上较大的有符号根。在上述假设下 q=0。括号内两项同号或其中一项为零,因此这一步不会相减两个几乎相等的正数。
上述 xL,xS 恰好是两个根,并且 ∣xL∣≥∣xS∣。
第一个式子是二次公式的一个选项,因此给出一根。两根之积为 c/a,所以另一根是 (c/a)/(q/a)=c/q;这里无需计算两个近数之差。∣q∣=(∣b∣+s)/2,另一根的绝对值为 ∣∣b∣−s∣/(2∣a∣)。因为 ∣b∣+s≥∣∣b∣−s∣,次序成立。若 b=0,约定选出两个绝对值相等、符号相反的根之一。
例题 8.2.3
(binary64 算术中的消去)
在 IEEE binary64 算术(最近舍入)中取 a=1、b=108、c=1。精确根为 −5⋅107±25⋅1014−1,故小根为 −1.00000000000000010…×10−8。所存储的判别式 1016−4 是精确的,算得的平方根为 99999999.99999999。在 108 附近,相邻的 binary64 数相距 2−26≈1.49×10−8,所以直接公式的分子 −b+s 只能是 2−26 的小倍数;此处它等于 −2−26。除以 2 得 −7.45×10−9,相对误差约为 25%。稳定公式则得 q=−21(108+s)=−108,并返回 c/q=−10−8,约有十六位正确数字;大根 q/a=−108 的精度相同。
例题 8.2.4
(b=0 时两根绝对值相等)
对 x2−4=0,有 b=0、D=16、s=4。约定 sgn(0)=1,故 q=−21(0+4)=−2,xL=q/a=−2,xS=c/q=−4/(−2)=2。两根都得到,而且 ∣xL∣=∣xS∣:标记 L 只保证绝对值不小于另一根,所以在这个边界情形,它仅记录符号约定选出了哪一根。
若写成 q=−21(b−sgn(b)s),或总是取 −b+s,那么当 ∣b∣ 接近 s,即 ∣4ac∣ 远小于 b2 时,就重新引入了这个恒等式原本要避免的相减。s 的符号必须与 b 的符号一致。
舍入界需要什么假设?
设计算采用最近舍入,单位舍入误差为 u;有关运算均满足 fl(z)=z(1+δ)、∣δ∣≤u,并且没有溢出或使此模型失效的下溢。再假设所算非负平方根 s 有独立证明的相对误差界
s=s(1+η),∣η∣≤ρ<1.
这一假设同时包括判别式计算和开方的误差;仅有正确舍入的开方指令并不能保证它。先以一次舍入加法和一次舍入乘以 −1/2 得到 q,再计算 xL=fl(q/a) 及 xS=fl(c/q)。设
e=(1+ρ)(1+u)2−1.
若 e<1,两个计算根均非零,而且
xLxL−1≤(1+e)(1+u)−1,xSxS−1≤1−ee+u.
b 与 sgn(b)s 同号或 b=0。将 s 换成 s 时,和的绝对变化至多 ρs,原来和的绝对值为 ∣b∣+s≥s,因此相对变化至多 ρ,即未舍入的和等于精确和乘以 1+θ,其中 ∣θ∣≤ρ。再计入两次舍入,可写成 q=q(1+ξ),其中 ∣ξ∣≤e:乘积上界为 (1+ρ)(1+u)2,向下偏离 1 的幅度不超过这一上偏差。故 1+ξ≥1−e>0。
第一次除法满足 xL/xL=(1+ξ)(1+δ),同样估计乘积得到第一界。第二次除法则满足 xS/xS=(1+δ)/(1+ξ),因此
1+ξ1+δ−1=∣1+ξ∣∣δ−ξ∣≤1−eu+e.这里把除法视为单独舍入;若运算溢出、下溢使模型失效,或编译器改变运算次序,就不能直接照搬此证明。
证明透视
符号约定在哪里发挥作用
整个证明建立在一个结构事实上:唯一的加法 b+sgn(b)s 把两个同号的数相加。正因如此,平方根的绝对扰动 ρs 才会变成和的至多 ρ 的相对扰动,因为和的绝对值至少是 s。若符号相反,同一绝对扰动要除以可以任意小的 ∣∣b∣−s∣,便得不到任何相对界。此后一切都是乘法:1+θ、1+δ1、1+δ2 三个因子给出 q,每个根再多一个因子。小根是除以 q 得到的,所以它的误差因子以倒数出现,这就是分母出现 1−e、并且需要 e<1 的原因。关于 s 的假设只用了一次,而且此处并未证明;定理的可靠程度取决于这个外部误差界。
十进制计算例子
假设机器保留三位有效数字,每次运算都舍入到最近值,指数范围足够大。取 a=1、b=−104、c=1,精确根是 (104±108−4)/2。在此算术中,108−4 舍入为 108,开方后为 104。直接公式的小根分子 104−104 因而为零。新公式给出 q=104,小根算为 10−4。实际小根约为 0.000100000001,故新式保留了三位有效数字;直接式却给零。大根约为 9999.9999,在此格式中也舍入为 104。这只是一个算术例子,不是对所有问题的精确性保证。
稳定公式修补的是直接公式本身造成的精度损失。根对系数的敏感性则是问题本身的性质,任何重排运算都不能消除。
反例模式
稳定公式不能补回缺失的判别式信息
令 a=c=1、b=−2,方程有重根 1。只将 b 改为 −2−ϵ,判别式变为 4ϵ+ϵ2>0,根为 1+ϵ/2±ϵ+ϵ2/4。系数变化量为 ϵ 阶,根的分离却为 ϵ 阶。反之,令 b=−2+ϵ 且 0<ϵ<4,判别式为负。重根附近,连实根的数目也对数据敏感。前面的相对误差定理明确要求 D>0 和有效的 s 误差界;判别式被舍入成零或改变符号时不可使用。
下面的互动图把每步运算舍入到 t 位有效数字,并排执行教科书公式与利用两根之积的公式;降低 t,即可看到 −b+s 的消去,以及重根附近 D 的符号如何丢失。
探索MATH3230 · ax² + bx + c = 0
教科书公式的消去误差,与任何公式都无法补救的部分
十进制机器把每一步运算舍入到 t 位有效数字(最近舍入,平手取偶)。它以 D = b² − 4ac、s = √D 解 ax² + bx + c = 0:一次用 (−b ± s)/(2a),一次用 q = −(b + sgn(b)s)/2、x_L = q/a、x_S = c/q。降低 t,并与 80 位有效数字算出的参考值比较。
试试这些值
方程: (1, −10000, 1), t = 3 位.
判别式:精确值与 t 位有效数字值| 量 | 精确 | t 位机器 |
|---|
| b² | 1×10⁸ | 1×10⁸ |
|---|
| 4ac | 4 | 4 |
|---|
| D | 9.9999996×10⁷ | 1×10⁸ |
|---|
运算记录,每步舍入到 t 位有效数字| 方法 | 步骤 | 算式 | 结果 |
|---|
| 两种方法共用 | 计算 b² | fl(b·b) | 1×10⁸ |
|---|
| 两种方法共用 | 计算 4a | fl(4·a) | 4 |
|---|
| 两种方法共用 | 计算 4a 乘 c | fl(4a·c) | 4 |
|---|
| 两种方法共用 | 舍入后的判别式 D̂ | fl(b² − 4ac) | 1×10⁸ |
|---|
| 两种方法共用 | 平方根 ŝ | fl(√D̂) | 10000 |
|---|
| 教科书公式 (−b ± s)/(2a) | 计算 2a | fl(2·a) | 2 |
|---|
| 教科书公式 (−b ± s)/(2a) | 绝对值较大之根的分子 | fl(−b + ŝ) | 20000 |
|---|
| 教科书公式 (−b ± s)/(2a) | 绝对值较小之根的分子 | fl(−b − ŝ) | 0 |
|---|
| 教科书公式 (−b ± s)/(2a) | 绝对值较大的根 | fl((−b + ŝ) / 2a) | 10000 |
|---|
| 教科书公式 (−b ± s)/(2a) | 绝对值较小的根 | fl((−b − ŝ) / 2a) | 0 |
|---|
| 稳定公式(q = −(b + sgn(b)s)/2) | 同号两项之和 | fl(b − ŝ) | −20000 |
|---|
| 稳定公式(q = −(b + sgn(b)s)/2) | 中间量 q̂ | fl(−(b − ŝ) / 2) | 10000 |
|---|
| 稳定公式(q = −(b + sgn(b)s)/2) | 绝对值较大的根 x̂_L | fl(q̂ / a) | 10000 |
|---|
| 稳定公式(q = −(b + sgn(b)s)/2) | 绝对值较小的根 x̂_S | fl(c / q̂) | 0.0001 |
|---|
计算所得的根与 80 位参考值比较| 根 | 教科书公式 | 稳定公式 | 参考值 | 教科书公式的相对误差 | 稳定公式的相对误差 |
|---|
| 绝对值较大 | 10000 | 10000 | 9999.999899999998999999979999999499999985999999579999986799999570999985699999514 | 1×10⁻⁸ | 1×10⁻⁸ |
|---|
| 绝对值较小 | 0 | 0.0001 | 0.00010000000100000002000000050000001400000042000001320000042900001430000048620001679 | 1 | 1×10⁻⁸ |
|---|
- 精确的 D
- 9.9999996×10⁷
- 实根个数(精确数据)
- 2
- t 位的 D̂
- 1×10⁸
- 实根个数(此算术)
- 2
- |D| / (b² + |4ac|)(精确)
- 1
- 教科书公式的相对误差(小根)
- 1
- 稳定公式的相对误差(小根)
- 1×10⁻⁸
教科书公式算出的小根没有一位正确数字(相对误差不小于 1),稳定公式则保持很小的相对误差。
此图显示什么、不显示什么
正文的定理要求 D > 0 以及 ŝ 的有效误差界。这里 ŝ 由舍入后的 D̂ 开方得到,所以接近重根时失效的正是这个误差界。
稳定公式借两根之积 x_S = c/q,避开最后一步中两个近数相减;它不改变数据,也无法补回 D̂ 中被舍入毁掉的信息。
小数至多 8 位有效数字,绝对值在 10⁻⁸ 至 10¹² 之间,且 a ≠ 0、c ≠ 0。精确值与 80 位参考值都以整数运算得出,不涉及二进制浮点数。
直接计算 b2−4ac 本身也可能相减近数。将全部系数乘以同一非零常数不改变根,有时能减少溢出或下溢,但不能仅凭缩放认证判别式的符号或消除病态。需要严格保证时,必须用适当的精确运算、更高精度或区间运算等控制误差。若 c=0,直接返回 0 与 −b/a;若 b 也为零,则零是重根。D=0 时重根为 −b/(2a),但要判断 D 精确为零需有数据依据。D<0 时需要复数算术,本节不讨论。
概念视角分析
判别式控制根的条件数
对单根 r,把系数扰动 δa,δb,δc 后,它在一阶近似下移动
δr=−2ar+bδar2+δbr+δc,∣2ar+b∣=D.若每个系数的相对变化都不超过 ϵ,则在一阶近似下根的相对变化至多为 ϵ(∣a∣r2+∣b∣∣r∣+∣c∣)/(∣r∣D)。因子 1/D 属于问题本身,而不属于任何公式;当 D→0 时线性估计完全失效,由此得到反例中的平方根行为。
在重根附近,b2 与 4ac 几乎相等,所以算得的 D 可能被舍入成零,甚至符号错误。只凭浮点计算的 D 来判断是两个实根、重根还是复根并不可靠;作此判断需要 D 的误差界。
练习与解答
快速检查
(对 x2+108x+1=0,哪个直接公式分子有消去问题?给出小根的替代表达式。)
解答 · 答案
−108+1016−4 相减两个近数。取 q=−(108+1016−4)/2,小根为 1/q。
快速检查
(假设 u=10−4、ρ=10−3。用 0.001201 作为 e 的上界,求小根相对误差界。)
展开 e=(1+ρ)(1+u)2−1,再用定理的第二个界。
解答 · 答案
展开得 e=1.001(1.0001)2−1=0.00120021001<0.001201。定理给出 (e+u)/(1−e)<0.001303。这依赖独立的平方根误差界和所述舍入模型。
快速检查
(求 x2−2x+(1−10−8)=0 的精确根,说明为何系数相对误差小,根的相对误差未必同样小。)
解答 · 答案
判别式为 4⋅10−8,根为 1±10−4。将常数改为 1,其相对变化约 10−8,两根却合并到 1,每根移动 10−4。这是接近重根时的敏感性。
快速检查
(对 2x2+3x=0,为何实现中不应无条件套用 c/q?)
解答 · 答案
单独处理得 0 和 −3/2。虽然此例 q=0,当 b=c=0 时 q=0,c/q 无定义。统一处理 c=0 可涵盖两种情况并避免不必要的异常除法。