霍內演算法(Horner’s Algorithm)

霍內演算法(Horner’s Algorithm)
國立中央大學數學系單維彰副教授責任編輯
 
高中課程由除法的直式計算，化約成所謂的綜合除法，然後經過餘式定理而得到多項式函數 $$f(x)$$ 的求值算法。這個算法，比直接代入而計算的方法優秀，因為計算量較少。

例如當 $$f(x)=x^4-4x^3+2x^2-x+1$$，

直接代入 $$x=\frac{1}{2}$$ 需要算 $$(\frac{1}{2})^4=\frac{1}{16}$$、$$(\frac{1}{2})^3=\frac{1}{8}$$、$$(\frac{1}{2})^2=\frac{1}{4}$$，然後計算

$$\displaystyle{f(\frac{1}{2})}=\frac{1}{16}-\frac{4}{8}+\frac{2}{4}-\frac{1}{2}+1=\frac{1-8}{16}+1=1-\frac{7}{16}=\frac{9}{16}$$

但是如果使用綜合除法，形式如下：

實際執行的計算步驟，只是連續做乘法和加法而已，不必做次方計算，程序如下：

1.  $$\displaystyle{1}\times{\frac{1}{2}}-4=-{\frac{7}{2}}$$

2.  $$\displaystyle(-{\frac{7}{2}})\times{\frac{1}{2}}+2=\frac{1}{4}$$

3.  $$\displaystyle{\frac{1}{4}\times\frac{1}{2}-1}=-{\frac{7}{8}}$$

4.  $$\displaystyle-{\frac{7}{8}}\times\frac{1}{2}+1=\frac{9}{16}=f(\frac{1}{2})$$

如果不必知道 $$f(x)\div(x-a)$$ 的商而只是求 $$f(a)$$ 的值，在思考上不必繞道除法，而直接想到上述的快速求值算法，稱為霍內演算法（Horner’s algorithm），簡稱Horner算法。這是一種標準算法，所有的電腦專業軟體，都以這個算法計算多項式函數的值。Horner算法不必繞道綜合除法來了解，可以直接地認識它。基本想法只是：

按降冪順序，一次做兩項，提出共同的低次項，則每次計算只有一個乘法和一個加法。

例如，對於二次多項式函數：

$$f(x)=a_2x^2+a_1x+a_0=(a_2x+a_1)x+a_0$$

對於三次多項式函數：

$$\begin{array}{ll}f(x)&=a_3x^3+a_2x^2+a_1x+a_0\\&=(a_3x+a_2)x^2+a_1x+a_0\\&=((a_3x+a_2)x+a_1)x+a_0\end{array}$$

對於四次多項式函數：

$$\begin{array}{ll}f(x)&=a_4x^4+a_3x^3+a_2x^2+a_1x+a_0\\&=(a_4x+a_3)x^3+a_2x^2+a_1x+a_0\\&=((a_4x+a_3)x+a_2)x^2+a_1x+a_0\\&=(((a_4x+a_3)x+a_2)x+a_1)x+a_0\end{array}$$

令 $$f(x)=a^nx^n+a_{n-1}x{n-1}+\mbox{…}+a_1x+a_0$$，以「口語化」描述求 $$f(a)$$ 的Horner算法，就是：

$$(1)$$ 令 $$p=a_n$$

$$(2)$$ 依序以 $$n-1,n-2,…, 1, 0$$ 代入 $$i$$，做 $$p\times{a}+a_i$$，並令計算結果是新的 $$p$$ 執行結束時，$$p$$ 就是 $$f(a)$$。

再以 $$f(x)=x^4-4x^3+2x^2-x+1$$ 的 $$f(\frac{1}{2})$$ 計算為例，

此時 $$n=4$$, $$a_4=1,a_3=-4, a_2=2, a_1=-1$$ 和$$a_0=1$$。

一開始，令 $$p=a_4=1$$。然後依序執行以下計算：

$$\displaystyle i=3, p={1}\times{\frac{1}{2}}+a_3=-{\frac{7}{2}}$$

$$\displaystyle i=2, p=-{\frac{7}{2}}\times\frac{1}{2}+a_2=\frac{1}{4}$$

$$\displaystyle i=1, p=\frac{1}{4}\times\frac{1}{2}+a_1=-{\frac{7}{8}}$$

$$\displaystyle i=0, p=-{\frac{7}{8}}\times\frac{1}{2}+a_0=\frac{9}{16}$$

最後的 $$p=\frac{9}{16}$$ 就是 $$f(\frac{1}{2})$$ 的值。

向前連結：多項式除法，演算法
向後連結：