霍纳法是一种求多项式值的算法,其做法是将多项式改写为乘法与加法相互嵌套的形式。对于以幂基表示的 n 次多项式,它需要 n 次乘法和 n 次加法,无须显式计算自变量的各次幂。同一计算过程还能给出多项式除以一次多项式所得商的系数,并可扩展用于计算导数。它是数值分析、符号计算和数值求根中的标准方法。
嵌套形式与递推关系
考虑多项式
p(x)=anxn+an−1xn−1+⋯+a1x+a0,an=0.
反复提取因子 x,可得到它的霍纳形式:
p(x)=(⋯((anx+an−1)x+an−2)x+⋯+a1)x+a0.
要计算它在 x=c 处的值,定义如下递推关系:
bn=an,bk=ak+cbk+1(k=n−1,n−2,…,0).
结果为
p(c)=b0.
每一步都纳入一个新的系数,从最高次项依次进行到常数项。如果不需要保留中间值,实现时只需一个累加变量:
function horner(a[0..n], c):
value = a[n]
for k = n-1 down to 0:
value = value*c + a[k]
return value
这里的系数数组按次数从低到高编号,但算法按次数从高到低读取。有些接口则按相反顺序存储系数,因此使用软件实现时,必须注意系数的排列约定。
示例
对于
p(x)=2x3−6x2+2x−1,
其嵌套形式为
p(x)=((2x−6)x+2)x−1.
在 x=3 处,累加变量的值依次为
2,2⋅3−6=0,0⋅3+2=2,2⋅3−1=5.
因此 p(3)=5。
缺失的幂次必须用零系数表示。例如,
x4+3x−2=(((x+0)x+0)x+3)x−2.
方法原理
处理完从 an 到 ak 的各个系数后,累加变量中保存的是
bk=ancn−k+an−1cn−k−1+⋯+ak.
将其乘以 c,再加上 ak−1,就得到下一步对应的表达式。由此可通过数学归纳法证明结果成立。
这一恒等式本质上是代数恒等式,并不局限于数值计算。它适用于系数为实数或复数的多项式,更一般地,也适用于交换环上的多项式。由于不需要除法,它同样适用于模算术和有限域上的计算。
计算成本
对于 n≥1 的 n 次多项式,基本算法恰好执行:
用大O记号表示,其算术运算成本为 O(n);如果只需要求值,辅助存储空间为 O(1)。
若通过反复相乘来独立计算每一个幂,可能需要 O(n2) 次算术运算。依次生成各次幂可以将这种方法的运算次数降至 O(n),但直接实现时,乘法次数通常仍多于霍纳法。
这些运算次数基于单位成本算术模型。对于大整数、有理数运算或符号表达式,单次运算的成本取决于操作数的大小;因此,算术运算次数呈线性增长,并不一定意味着运行时间也呈线性增长。
霍纳法特别适合以幂基表示的稠密多项式,但它并非在所有情况下都是最快的求值策略。对于稀疏多项式,利用指数之间间隔的算法可能更有优势;具有特殊结构的多项式则可能通过因式分解来减少运算次数。
与综合除法的联系
将 p(x) 除以 x−c 时,中间值 bn,bn−1,…,b1 就是商多项式的系数:
p(x)=(x−c)q(x)+b0,
其中
q(x)=bnxn−1+bn−1xn−2+⋯+b1.
因此,霍纳递推在执行综合除法的同时,也计算出了余数 b0=p(c)。
在前面的示例中,除以 x−3 得到
2x3−6x2+2x−1=(x−3)(2x2+2)+5.
如果 p(c)=0,那么 x−c 就是一个精确因子。除去这样的因子称为降阶。降阶在多项式求根中很有用,但使用近似根可能会使商的系数发生扰动,降低后续所求根的精度。
导数求值
经过修改的递推关系可以在一遍计算中同时求出 p(c) 及其导数 p′(c)。初始化为
v=an,d=0.
对于 k=n−1,…,0,依次更新
d←cd+v,v←cv+ak.
更新 d 时必须使用 v 的旧值。计算结束后,
v=p(c),d=p′(c).
这一结果可通过对每一步嵌套运算求导得到:如果一个部分多项式由 v(x) 更新为 xv(x)+ak,其导数就变为 xv′(x)+v(x)。这是自动微分的一个简单实例。
这种高效的同时求值方式对牛顿法很有用。对于多项式,只要分母不为零,牛顿法的迭代公式为
xj+1=xj−p′(xj)p(xj),
。
更高阶导数也可以通过相关递推关系或反复进行综合除法得到。如果
p(x)=r0+(x−c)(r1+(x−c)(r2+⋯)),
那么
rj=j!p(j)(c).
因此,反复除以 x−c 可以将幂基系数转换为以 c 为中心的展开系数,从而得到多项式在该点的有限项泰勒级数展开。
浮点计算精度
在浮点运算中,乘法和加法通常都会引入舍入误差。霍纳法具有良好的数值稳定性,但这并不能保证对所有多项式和自变量取值都能得到较小的相对误差。
在标准舍入模型下,假设不发生上溢或下溢,计算值 p(c) 满足如下形式的误差界:
∣p(c)−p(c)∣≤γ2nk=0∑n∣ak∣∣c∣k,
其中
γm=1−mumu,mu<1,
而 u 是单位舍入误差。这一误差界将每次乘法和加法视为分别进行舍入的运算。
该方法也可以从逐系数后向误差的角度来解释:计算结果等于某个多项式在 c 处的精确值,而这个多项式的各个系数与输入系数仅有微小差异。
尽管如此,相消仍可能使最终结果远小于参与合并的各项的量值。当 p(c)=0 时,一个相关的逐系数条件数为
κcoeff(p,c)=∣p(c)∣∑k=0n∣ak∣∣c∣k.
当这个量很大时,微小的系数扰动或舍入误差就可能导致结果出现较大的相对误差。这种情况常发生在根附近。例如,在 x=1 附近计算 (x−1)m 展开后的幂基形式时,可能会发生严重的相消,尽管其因式分解形式很容易求值。
支持融合乘加的硬件可以在计算每个表达式 cv+ak 时只进行一次最终舍入,而不是两次,从而改善误差界,并且通常也能提高性能。霍纳法的补偿变体则通过估计并修正舍入误差来提高精度。
应用与替代方案
霍纳求值广泛用于函数逼近,在这类应用中,数学函数在局部用多项式表示。它也用于插值、多项式求根,以及将位值制记数法表示的数转换为数值。例如,以 B 为基数的数字序列可按下式求值:
dmBm+⋯+d1B+d0=(⋯(dmB+dm−1)B+⋯)B+d0.
这种嵌套算法具有顺序依赖性:累加变量的每一个值都依赖于前一个值。这可能限制单次求值过程中的并行计算。埃斯特林法等方案通过将各项分组,并使用 x2,x4,… 等幂来增加可并行执行的运算,但其算术运算成本和存储成本也会有所不同。
霍纳法还依赖于所选的基。对于使用切比雪夫多项式等正交多项式表示的多项式,通常更适合直接利用针对该基的递推关系求值,而不是先将其转换为幂基形式。
历史背景
这一方法以英国数学家威廉·乔治·霍纳的名字命名,他于1819年发表了一种数值方程求解方法。他的工作关注的是根的近似计算,而不仅仅是如今通常以他的名字教授的那段简洁的多项式求值循环。
相关方法的出现远早于该文献的发表。中国传统数学曾通过逐次变换系数来开方和求解多项式方程,秦九韶在十三世纪的工作就是其中的著名例子。因此,“霍纳法”狭义上可以指多项式的嵌套求值方法;而在历史叙述中,也可以更广泛地指基于反复进行多项式变换的求根方法。