最後更新：2026-06-06

多項式求值

多項式 P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + … + a₁x + a₀ 定義了 x 的一個代數函數，求值即在給定 x₀ 的情況下計算 P(x₀) 的數值。若逐項展開——先對每個次冪分別計算 xᵏ，再乘以對應係數、最後加總——n 次多項式約需 n(n+1)/2 次乘法，計算量隨次數平方成長。霍納法（Horner's method）透過巢狀乘法將相同的多項式改寫，使計算量降至恰好 n 次乘法與 n 次加法：

$P(x) = (\cdots((a_n \cdot x + a_{n-1}) \cdot x + a_{n-2}) \cdot x + \cdots + a_1) \cdot x + a_0$

本計算機接受由高次到低次排列的係數（例如輸入 1, -3, 2, 5 代表 x³ − 3x² + 2x + 5）以及一個 x 值，輸出多項式次數、標準式，以及以霍納法計算的 P(x)，並附有以求值點為中心的曲線圖。

秦九韶演算法的歷史

霍納法在中國數學史上有更早的記載。宋代數學家秦九韶於西元 1247 年的《數書九章》中，以「正負開方術」系統記載了相同的巢狀計算程序，用以求解高次方程。此法因而在漢語學術文獻中常稱為秦九韶演算法，比英國數學家 William George Horner 於 1819 年的發表早了五百七十餘年。兩者在代數結構上完全相同，僅在應用情境上略有不同。

演算步驟

演算法維護一個累算器，初始值設為最高次項係數 aₙ。之後對每個後續係數執行一次「乘 x 再加」：

$r \leftarrow r \cdot x + a_{n-k} \quad \text{for } k = 1, 2, \ldots, n$

執行 n 步後，累算器的值即為 P(x)。此演算法在乘法次數上已達理論最小值，任何多項式求值演算法均無法以更少的乘法完成。

計算實例： 計算 P(x) = x³ − 3x² + 2x + 5 在 x = 2 的值（係數：1, -3, 2, 5）

步驟	運算	累算器
初始	r = 1	1
k=1	r = 1 × 2 + (−3) = −1	−1
k=2	r = −1 × 2 + 2 = 0	0
k=3	r = 0 × 2 + 5 = 5	5

所以 P(2) = 5，與逐項展開驗算一致：2³ − 3×4 + 2×2 + 5 = 8 − 12 + 4 + 5 = 5。

效率比較

逐項展開法需對每一次冪個別計算，n 次多項式最多需要 n(n+1)/2 次乘法，加總後才是最終結果。霍納法每步只用一次乘法與一次加法，中間結果被完整複用，運算次數精確為 n 次乘法與 n 次加法。

次數	逐項展開乘法次數	霍納法乘法次數
2	3	2
5	15	5
10	55	10
20	210	20

效率差距在高次多項式中尤為明顯。此外，霍納法過程中產生的中間值較小，當各係數數量級相差懸殊時，數值穩定性也優於逐項展開法。

係數的輸入方式

係數必須由最高次項到常數項依序輸入，以逗號分隔，並且缺次項必須補 0，不可省略——省略 0 會導致各係數移位，對應到錯誤的次數。

多項式	係數輸入
x³ − 3x² + 2x + 5	1, -3, 2, 5
2x² + 3x − 1	2, 3, -1
x⁴ − 1	1, 0, 0, 0, -1
−3x + 7	-3, 7
常數 4	4

係數個數減一即為多項式次數，輸入單一數值即為零次（常數）多項式。

與綜合除法的關係

霍納法在代數上等同於綜合除法——以線性因式 (x − c) 除多項式 P(x) 的速算程序。除法的餘式等於 P(c)，商式 Q(x) 則滿足：

$P(x) = (x - c)\,Q(x) + P(c)$

執行一次霍納法即同時得到 P(c)（餘式）與 Q(x) 的各項係數。對 Q(x) 再執行一次霍納法可得 Q(c) = P′(c)，這也是牛頓法求解 P(x) = 0 的計算基礎——每次迭代只需兩次霍納法即可取得 P(c) 與 P′(c)。

實際應用

多項式求值廣泛應用於計算機科學與工程領域：

• 電腦圖形：貝茲曲線（Bézier curve）與樣條曲線（spline）均為參數化多項式，繪製一條三次貝茲曲線時，每個像素每幀都需對三次多項式求值數百次。
• 訊號處理：有限脈衝響應（FIR）濾波器在 Z 域表示為多項式乘法，對每個取樣點求值即透過霍納法迴圈完成。
• 求根計算：牛頓法求解 P(x) = 0 時，每次迭代需同時計算 P(x₀) 與 P′(x₀)，兩者可在一次綜合除法中一併取得。
• 雜湊與校驗碼：循環冗餘校驗（CRC）對二進位多項式以生成多項式取模，本質上是在 GF(2) 上的霍納法迴圈。
• 控制系統：傳遞函數為 s 域（拉普拉斯）或 z 域的有理多項式，穩定性分析需對特徵多項式在虛軸上求值。

延伸計算

若需同時計算 P(x) 與 P′(x)，可使用 多項式導數計算機。若需對多項式積分，可使用 多項式定積分計算機。若需求解 P(x) = 0，二次方程可使用 二次方程式求解器，三次方程可使用 三次方程式求解器。

常見問題（FAQ）

霍納法（秦九韶演算法）是什麼？

霍納法（亦稱秦九韶演算法）是計算多項式 P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + … + a₁x + a₀ 的一種演算法，透過巢狀乘法將多項式改寫為 P(x) = (…((aₙ · x + aₙ₋₁) · x + aₙ₋₂) · x + … + a₁) · x + a₀。每步只進行一次乘法與一次加法，n 次多項式共需 n 次乘法與 n 次加法，是理論上的最少運算次數。中國宋代數學家秦九韶在西元 1247 年即已系統性地記載此法，比 William George Horner 的 1819 年發表早五個多世紀。

霍納法為何比逐項展開法更有效率？

逐項展開法需分別計算各次冪：x² = x·x、x³ = x²·x，依此類推，n 次多項式約需 n(n+1)/2 次乘法。霍納法則逐步累積中間結果，整個過程只需 n 次乘法與 n 次加法。以 20 次多項式為例，逐項展開法需 210 次乘法，霍納法僅需 20 次，效率提升十倍以上。此外，霍納法中間值較小，數值穩定性也優於逐項展開法。

可以用霍納法同時求導函數值嗎？

可以。霍納法在代數上等同於綜合除法，即以 (x − x₀) 除 P(x)。餘式等於 P(x₀)，商式 Q(x) 滿足 P(x) = (x − x₀)Q(x) + P(x₀)，而 Q(x₀) = P′(x₀)。因此，執行一次霍納法即可同時得到 P(x₀)（餘式）與 Q(x) 的係數；再對 Q(x) 執行一次霍納法即可得到 P′(x₀)。

係數應如何輸入？

請由最高次項係數輸入至常數項係數，以逗號分隔，缺次項必須補 0，不可省略。範例：x³ − 3x² + 2x + 5 → 「1, -3, 2, 5」；2x⁴ − 7 → 「2, 0, 0, 0, -7」；常數 4 → 「4」。係數個數減一即為多項式次數。