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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1.3.3,秦九韶算法,2010/12/24,先做个计算,A.,计算多项式,：,3,5,+3,4,+3,3,+3,2,+3+1,=243+81+27+9+3+1,=364,B.,计算多项式：,(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.3,5,+3,4,+3,3,+3,2,+3+1=364,共做,了,1+2+3+4=10,次乘法，,5,次加法。,B.(3+1)3+1)3+1)3+1)3+1,121,3+1=364,共做,了,5,次,乘法，,5,次加,法。,直接求和法,AB,f,(,x,),=x,5,+x,4,+x,3,+x,2,+x+,1,=,(,x,4,+x,3,+x,2,+x+,1),x+,1,=,(,x,3,+x,2,+x+,1),x+,1),x+,1,=,(,x,2,+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,),=a,n,x,n,+a,n-,1,x,n-,1,+a,1,x+a,0,=,(,a,n,x,n-,1,+a,n-,1,x,n-,2,+a,1,),x+a,0,=,(,a,n,x,n-,2,+a,n-1,x,n-,3,+a,2,),x+a,1,),x+a,0,=,=,(,a,n,x+a,n-,1,),x+a,n-,2,),x+a,1,),x+a,0,秦九韶算法,f,(,x,),=,(,a,n,x+a,n-,1,),x+a,n-,2,),x+a,1,),x+a,0,要求多项,式,的,值，应先计算最内层多项式：,v,0,=a,n,.,v,1,=a,n,x+a,n-,1,然,后，由内到外逐层计算一次多项式的值：,v,2,=v,1,x+a,n-,2,秦九韶算法,v,2,=v,1,x+a,n-,2,v,3,=v,2,x+a,n-,3,.,v,n,=v,n-,1,x+a,0,这,种将求,一,个,n,此多项式,f,(,x,),的值转化成求,n,个一次多项式的值的方法，成为,秦九韶算法,。,递推公式,v,0,=a,n,v,k,=v,k-,1,x+a,n-k,(,k,=1,2,n,),秦九韶算法的特点,通过一次式的反复计算，逐步得出高次多项式的值，对于一个,n,次多项式，只需做,n,次乘法和,n,次加法即可。,例：,已知一个五次多项式,为,f,(,x,),=,5,x,5,+2,x,4,+3.5,x,3,-2.6,x,2,+1.7,x,-0.8,用秦九韶算法求这个多项式当,x,=5,时的值。,f,(,x,),=,5,x,5,+2,x,4,+3.5,x,3,-2.6,x,2,+1.7,x,-0.8,解：将多项式变形：,f,(,x,),=,(,5,x,2),x,+3.5),x,-2.6),x,+1.7),x,-0.8,按由里到外的顺序，依此计,算：,v,0,=,5,v,1,=,5,5,+,2=27,v,2,=,27,5,+,3.5=138.5,v,3,=,138.5,5,-2.6=689.9,v,4,=,689.9,5,+,1.7=3451.2,v,5,=,3451.2,5-0.8,=17255.2,所以，当,x,=5,时，多项式的值等于,17255.2,算法步,骤和程序框图,S1,输,入多项式次数,n,、最高次项的系数,a,n,和,x,的,值。,S2,将,v,的值初始化为,a,n,，将,i,的值初始化为,n,-1,。,开始,输入,n,an,x,v=a,n,i,=,n,-1,1,算法步骤和程序框图,S3,判,断,i,是否大于或等于,0,，若是，输入,i,次项的系数,a,n,；否则，输出多项式的值,v,。,S4,v=vx+a,i,i=i,-1,。,S5,返回,S3,。,输入,a,i,v=vx+a,i,i=i-,1,i,0?,1,输出,v,结束,N,Y,逐项求和法,逐项求和法在直接求和法的基础上做了改进，先把多项式写成,f,(,x,),=a,n,x,n,+a,n-,1,x,n-,1,+a,1,x,1,+a,0,的形式，这样多项式的每一含,x,的幂的项都是,a,k,与,x,k,的乘积（,k,=1,2,n,）。在计算,a,k,x,k项时把,x,k,的值保存在变量,c,中，求,a,k,+1,x,k,+1,项时只需计算,a,k,+1,xc,，同时把,xc,=,x,k,+1,的值保存入,c,中，继续下一项的运算，然后把这,n,+1,项的值相加。,计算机对于某程序的计算时间,计算次数（主观）,处理器,内,存及使用量,计算计算机计算次数？,真的快了？,三种方法比较,乘法运算次数,直接求和法：,0.5,n,(,n,+1),次,逐项求和法：,2,n,-1,次,秦九韶算法：,n,次,一般用不到,人工计算,高速算法,当,n,3,时，,n,2,n,-1 0.5,n,(,n,+1),秦九韶算,法,逐项求和法,0),。,S2,：用秦九韶算法算出,f,(,x,0,),。,S3,：若,f,(,x,0,)0,计,算,f,(,x,i,+,c,),，,i,=0,，,1,，,2,，,；,（,1,）若,f,(,x,i,+,c,)0,，,则,c,=0.1,c,；,直,到,f,(,x,i,+,c,)=0,或,c,d,，这时,x,=,x,i,+,c,为方程的一个根。,x,0,x,1,x,i,x,i,+c,c,x,i+,1,小结,一般高次多项式用秦九韶算法简化,化简,后每次运算的递推公式,三种方,法运算次数比较,秦九韶算,法应用,求函数近似根,v,0,=a,n,v,k,=v,k-,1,x+a,n-k,(,k,=1,2,n,),The End,Thanks for Watching,