勵志

勵志人生知識庫

秦九韶算法

秦九韶算法是中國南宋時期的數學家秦九韶提出的一種多項式簡化算法,在西方被稱作霍納算法霍納規則

秦九韶算法的原理是把一個n次多項式f(x)=anxn+an-1xn-1+...+a1x+a0改寫成如下形式:f(x)=(...((anx+an-1)x+an-2)x+...+a1)x+a0。求多項式的值時,首先計算最內層括弧內一次多項式的值,然後由內向外逐層計算一次多項式的值。對於一個n次多項式,至多做n次乘法和n次加法。該算法最大的意義在於將求n次多項式的值轉化為求n個一次多項式的值,大大簡化了運算過程。

此外,秦九韶算法還可以配合牛頓法用來求解一元高次多項式的根,其在現代計算機解決多項式求值問題時仍然是最優的算法,可以大大減少計算中乘法的次數,縮短CPU的運算時間。