多项式求值的秦九韶方法.ppt

如果给定一个多项式,
(3. )
其中现在的问题是,给定一个x的值,要求多项式函数的值。对于这个问题,一种看起来很“自然”的方法是直接逐项求和。如果用表示x的k次幂, 表示式(3. )右端前k +l项的部分和,即
由于x的k次幂实际上等于其次幂再乘上x,而前k+1项的部分和等于前k项的部分和再加上第k +l项,因此,逐项求和的方法可以归结为如下的递推关系:
()
作为递推公式()的初值为:
()
这样,就可以利用初值(),对于k=1,2,…直到n,反复利用公式()进行计算,最后就可以得到。其算法描述如下:
(1)逐项法多项式求值。
输入:存放的系数数组A(0:n);
自变量x值。其中
输出: 值P
PROCEDURE CPOLY(A,n,x,P)
FOR i=2 TO n DO
OUTPUT P
RETURN
在这个算法中,为了计算一个x点处的函数,共需要作2n-1次乘法和n次加法。还能不能减少乘法的次数呢?我们可以将式(3. 4. 1)的右端按降幂次序重新排列,并将它表述成如下嵌套形式
这样,就可以利用式()的特殊结构,从里往外一层一层地进行计算,即按如下递推关系进行计算:
最后可得结果
()
()
这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的,我们称之为秦九韶方法,在有的书上也叫霍纳(Horner)方法。其算法描述如下:
.
输入:存放的系数数组A(0:n);
自变量x值。其中。
输出: 值P。
PROCEDURE CHORNER(A,n,x,P)
FOR i=n-1 TO 0 BY -1 DO
OUTPUT P
RETURN
由秦九韶算法可以看出,多项式函数的求值只要用一个很简单的循环就能完成,并且在这个循环中只需要作n次乘法和n次加法就够了。它在实际使用中是一个很有效的方法。
例. 中国剩余定理(孙子定理)若k>2,且m1,m2,…mk是两两互素的k个正整数,令M= m1m2…mk=m1M1=m2M2=…=mkMk。
则同余式组:x1=b1(modm1),x2=b2(modm2),…xk=bk(modmk)
其正整数解是:X≡b1M1’M1+b2M2’M2+…+bkMk’Mk(modM)
其中Mi’是满足同余式: Mi’Mi≡1(mod mi) (i = 1,2…k)
∴用孙子定理解同余式组: xi=bi(modmi) ( i = 1,2…k )的算法步骤如下: