秦九韶算法课堂教学PPT

§1.3.3秦九韶算法-2010/12/24先做个计算A.计算多项式：35+34+33+32+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=121×3+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=121×3+1=364共做了5次乘法，5次加法。直接求和法A→B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=5v1=5×5+2=27v2=27×5+3.5=138.5v3=138.5×5-2.6=689.9v4=689.9×5+1.7=3451.2v5=3451.2×5-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。S4v=vx+ai,i=i-1。S5返回S3。输入aiv=vx+aii=i-1i≥0?1输出v结束NY逐项求和法逐项求和法在直接求和法的基础上做了改进，先把多项式写成f(x)=an·xn+an-1·xn-1+…+a1·x1+a0的形式，这样多项式的每一含x的幂的项都是ak与xk的乘积（k=1,2,…,n）。在计算ak·xk项时把xk的值保存在变量c中，求ak+1·xk+1项时只需计算ak+1·x·c，同时把x·c=xk+1的值保存入c中，继续下一项的运算，然后把这n+1项的值相加。计算机对于某程序的计算时间计算次数（主观）处理器内存及使用量计算计算机计算次数？真的快了？三种方法比较乘法运算次数直接求和法：0.5n(n+1)次逐项求和法：2n-1次秦九韶算法：n次一般用不到人工计算高速算法当n≥3时，n2n-10.5n(n+1)秦九韶算法逐项求和法直接求和法练习已知多项式f(x)=3x4-2x3+10x2+5x+1用秦九韶算法求这个多项式当x=-2时的值。计算机程序实现求函数近似根f(x)=anxn+an-1xn-1+…+a1x+a0（设根的精确度为d）S1：给定自变量一个初值x0，给定自变量初始增量c(c0)。S2：用秦九韶算法算出f(x0)。S3：若f(x0)0,计算f(xi+c)，i=0，1，2，…；（1）若f(xi+c)0，则xi+1=xi+c；（2）若f(xi+c)0，则c=0.1c；直到f(xi+c)=0或cd，这时x=xi+c为方程的一个根。x0x1…xixi+ccxi+1小结一般高次多项式用秦九韶算法简化化简后每次运算的递推公式三种方法运算次数比较秦九韶算法应用——求函数近似根v0=anvk=vk-1x+an-k(k=1,2,…,n)TheEndThanksforWatching