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

1. , , (3. ) (3. ) 其中其中现在的问题是,给定一个现在的问题是,给定一个 x x的值,要求的值,要求多项式函数多项式函数的值。对于这个问题,一种看起来的值。对于这个问题,一种看起来很很““自然自然””的方法是直接逐项求和。如果用的方法是直接逐项求和。如果用表示表示 x x 的的k k次次幂幂, ,表示式表示式(3. ) (3. ) 右端前右端前 k +l k +l 项的部分和, 项的部分和, 即即?? nn nxaxaxaaxP?????? 22101n??? xP n kt ku k kxt? kk 2210kxaxaxaau??????由于由于 x x的的k k次幂实际上等于其次幂再乘上次幂实际上等于其次幂再乘上 x x, ,而而前前 k+1 k+1 项的部分和等于前项的部分和等于前 k k项的部分和再加上第项的部分和再加上第 k +l k +l 项,因此,逐项求和的方法可以归结为如项,因此,逐项求和的方法可以归结为如下的递推关系: 下的递推关系: ????????kk1kk 1k ktauu xt tn,,2,1k??() 作为递推公式() 的初值为: ????? 00 0au 1t () 这样,就可以利用初值这样,就可以利用初值() () ,对于,对于 k=1 k=1 , , 2 2, ,……直到直到 n n, ,反复利用公式( 反复利用公式( ) ) 进行计算, 进行计算, 最后就可以得到。其算法描述如下最后就可以得到。其算法描述如下: : (1) 逐项法多项式求值。输入:存放的系数数组 A(0 :n); ?? xP n自变量 x值。其中 1n?输出: 值P ?? xP n PROCEDURE CPOLY PROCEDURE CPOLY ( (A A, ,n n, ,x x, ,P P) ) FOR i=2 TO n DO FOR i=2 TO n DO OUTPUT P OUTPUT P RETURN RETURN ???? xt;x1A0Ap???????? tiAPP;xtt?????在这个算法中,为了计算一个在这个算法中,为了计算一个 x x点处的函数点处的函数, ,共需要作共需要作 2 2 n- n- 1 1次乘法和次乘法和 n n次加法。还能不能减少乘法的次数呢?我们次加法。还能不能减少乘法的次数呢?我们可以将式可以将式(3. 4. 1) (3. 4. 1) 的右端按降幂次序重新排列,并将它的右端按降幂次序重新排列,并将它表述成如下嵌套形式表述成如下嵌套形式???????? 01 2n1nn naxaxaxaxaxP??????????这样,就可以利用式这样,就可以利用式() () 的特殊结构,从里往外一的特殊结构,从里往外一层一层地进行计算,即按如下递推关系进行计算: 层一层地进行计算,即按如下递推关系进行计算: ???????k1kk nnaxuu au0,1,,1???nk最后可得结果最后可得结果() () ( ( ) ) ?? 0 nuxP?这种多项式求值的方法是由我国宋代的一位这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的,我们称之为秦九数学家秦九韶最先提出的,我们称之为秦九韶方法,在有的书上也叫霍纳韶方法,在有的书上也叫霍纳( ( Horner) Horner) 方法。方法。其算法描述如下其算法描述如下: :算法算法 多项式求值的秦九韶方法. 多项式求值的秦九韶方法. 输入:存放输入:存放的系数数组的系数数组 A(0 A(0 : : n) n); ; 自变量自变量 x x值。其中值。其中。。输出: 输出: 值值P P。。?? xP n?? xP n1n? PROCEDURE CHORNER PROCEDURE CHORNER ( ( A,n,x,P A,n,x,P ) ) FOR i=n-1 TO 0 BY -1 DO FOR i=n-1 TO 0 BY -1 DO OUTPUT P OUTPUT P RETURN RETURN ?? nAP??? iAxPP???由秦九韶算法可以看出,多项式函数的求由秦九韶算法可