我国古代数学家秦九韶.pptx

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次加法。,直接求和法,AB,f(x)=x5+x4+x3+x2+x+1=(x4+x3+x2+x+1)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年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道古，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）。精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著作数书九章，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。霍纳算法（Horneralgorithm或Hornerscheme）,数学九章秦九韶算法,设f(x)是一个n次多项式f(x)=anxn+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-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=3451.25-0.8=17255.2所以，当x=5时，多项式的值等于17255.2,算法步骤和程序框图,S1输入多项式次数n、最高次项的系数an和x的值。S2将v的值初始化为an，将i的值初始化为n-1。,开始,输入n,an,x,v=an,i=n-1,1,算法步骤和程序框图,S3判断i是否大于或等于0，若是，输入i次项的系数an；否则，输出多项式的值v。S4v=vx+ai,i=i-1。S5返回S3。,输入ai,v=vx+ai,i=i-1,i0?,1,输出v,结束,N,Y,逐项求和法,逐项求和法在直接求和法的基础上做了改进，先把多项式写成f(x)=anxn+an-1xn-1+a1x1+a0的形式，这样多项式的每一含x的幂的项都是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-10.5n(n+1),秦九韶算法逐项求和法0)。S2：用秦九韶算法算出f(x0)。S3：若f(x0)0，则c=0.1c；直到f(xi+c)=0或cd，这时x=xi+c为方程的一个根。,小结,一般高次多项式