1、1.3.3 1.3.3 秦九韶算法秦九韶算法-2010/12/24先做个计算A.计算多项式：35+34+33+32+3+1 =243+81+27+9+3+1 =364B.计算多项式：(3+1)3+1)3+1)3+1)3+1 =(12+1)3+1)3+1)3+1 =(39+1)3+1)3+1 =1213+1=364哪种方法快？运算次数A.35+34+33+32+3+1=364共做了1+2+3+4=10次乘法，5次加法。B.(3+1)3+1)3+1)3+1)3+1 =1213+1=364共做了5次乘法，5次加法。直接求和法ABf(x)=x5+x4+x3+x2+x+1 =(x4+x3+x2+x+1)
2、x+1 =(x3+x2+x+1)x+1)x+1 =(x2+x+1)x+1)x+1)x+1 =(x+1)x+1)x+1)x+1)x+1秦九韶算法秦九韶秦九韶（1208年1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道古，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）。精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著作数书九章，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。霍纳算法（Horner algorithm或Horner scheme）数学九章秦九韶算法设f(x)是一个n次多项式f(x)=anxn+
3、an-1xn-1+a1x+a0 =(anxn-1+an-1xn-2+a1)x+a0 =(anxn-2+an-1xn-3+a2)x+a1)x+a0 =(anx+an-1)x+an-2)x+a1)x+a0秦九韶算法f(x)=(anx+an-1)x+an-2)x+a1)x+a0要求多项式的值，应先计算最内层多项式：v0=an .v1=anx+an-1然后，由内到外逐层计算一次多项式的值：v2=v1x+an-2秦九韶算法v2=v1x+an-2v3=v2x+an-3 .vn=vn-1x+a0这种将求一个n此多项式f(x)的值转化成求n个一次多项式的值的方法，成为秦九韶算法。递推公式v0=anvk=vk-
4、1x+an-k(k=1,2,n)秦九韶算法的特点通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。例：已知一个五次多项式为f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求这个多项式当x=5时的值。f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8解：将多项式变形：f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8按由里到外的顺序，依此计算：v0=5v1=55+2=27v2=275+3.5=138.5v3=138.55-2.6=689.9v4=689.95+1.7=3451.2v5=3
5、451.25-0.8=17255.2所以，当x=5时，多项式的值等于17255.2算法步骤和程序框图S1 输入多项式次数n、最高次项的系数an和x的值。S2 将v的值初始化为an，将i的值初始化为n-1。开始输入n,an,xv=ani=n-11算法步骤和程序框图S3 判断i是否大于或等于0，若是，输入i次项的系数an；否则，输出多项式的值v。S4 v=vx+ai,i=i-1。S5 返回S3。输入aiv=vx+aii=i-1i0?1输出v结束NY逐项求和法逐项求和法在直接求和法的基础上做了改进，先把多项式写成f(x)=anxn+an-1xn-1+a1x1+a0的形式，这样多项式的每一含x的幂的项
6、都是ak与xk的乘积（k=1,2,n）。在计算akxk项时把xk的值保存在变量c中，求ak+1xk+1项时只需计算ak+1xc，同时把xc=xk+1的值保存入c中，继续下一项的运算，然后把这n+1项的值相加。计算机对于某程序的计算时间计算次数（主观）处理器内存及使用量计算计算机计算次数？真的快了？三种方法比较乘法运算次数直接求和法：0.5n(n+1)次逐项求和法：2n-1次秦九韶算法：n次一般用不到人工计算高速算法当n3时，n2n-1 0.5n(n+1)秦九韶算法逐项求和法0)。S2：用秦九韶算法算出f(x0)。S3：若f(x0)0,计算f(xi+c)，i=0，1，2，；（1）若f(xi+c)0，则c=0.1c；直到f(xi+c)=0或cd，这时x=xi+c为方程的一个根。x0 x1 xixi+ccxi+1小结一般高次多项式用秦九韶算法简化化简后每次运算的递推公式三种方法运算次数比较秦九韶算法应用求函数近似根v0=anvk=vk-1x+an-k(k=1,2,n)The EndThanks for Watching
浙ICP备2021020529号-1 | 浙B2-20240490 
