1.3.2秦九韶.ppt

秦九韶算法
例:设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7
当x=5时的值的算法,并写出程序.
x=5
f=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7
PRINT f
END
程序
?问:上面算法中,共用了多少次乘法和加法?
有没有稍微高效的算法?
分析:可以利用前面的计算结果,以减少计算量
即先计算x2,然后依次计算
的值.
例:求f(x)=2x5-5x4-4x3+3x2-6x+7在x=5时的值。
?问:上面算法中,共用了多少次乘法和加法?
?问:能否有更好的算法,提高效率来解决任意多项式的求值问题?
f(x)=2x5-5x4-4x3+3x2-6x+7
=(2x4-5x3-4x2+3x-6)x+7
=((2x3-5x2-4x+3)x-6)x+7
=(((2x2-5x-4)x+3)x-6)x+7
=((((2x-5)x-4)x+3)x-6)x+7
v5=v4x+7=534×5+7=2677
v4=v3x-6=108×5-6=534
v3=v2x+3=21×5+3=108
v2=v1x-4=5×5-4=21
v1=-5=2×5-5=5
v0=2
所以,当x=5时,多项式的值是2677.
例1:求f(x)=2x5-5x4-4x3+3x2-6x+7在x=5时的值。
《数书九章》——秦九韶算法
V1
V2
例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.
解: f(x)=((((2x-5)x-4)x+3)x-6)x+7
v5=v4x+7=534×5+7=2677
v4=v3x-6=108×5-6=534
v3=v2x+3=21×5+3=108
v2=v1x-4=5×5-4=21
v1=v0x-5=2×5-5=5
v0=2
所以,当x=5时,多项式的值是2677.
然后由内向外逐层计算一次多项式的值,即
这是怎样的一种改写方式?最后的结果是什么?
《数书九章》——秦九韶算法
设f(x)是一个n次的多项式
对该多项式按下面的方式进行改写:
问:当知道了x的值后该如何求多项式的值?
f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.
然后由内向外逐层计算一次多项式的值,
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.
v1=anx+an-1,
v2=v1x+an-2,
v3=v2x+an-3
vn=vn-1x+a0.
……
v0=an,
vK=vK-1x+an-k(k=1,2,……,n)
?问:当x=x0(x是任意实数)时的值,需要多少次乘法运算,多少次加法运算?
《数书九章》——秦九韶算法
f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0.
v0=an,
vK=vK-1x+an-k(k=1,2,……,n)
练****利用秦九韶算法分别计算f(x)=8x7+5x6+3x4+2x+1在x=2与x=-1的值,并判断多项式f(x)在区间[-1,2]上有没有零点。
解:f(x)=8x7+5x6+3x4+2x+1
=8x7+5x6+0·x5+3x4+0·x3+0·x2+2x+1
=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1
V0=8
V1=8×2+5=21
V2=21×2+0=42
V3=42×2+3=87
V4=87×2+0=174 V5=174×2+0=348
V6=348×2+2=698
V7=698×2+1=1397
∴
∴ a7=8,a6=5,a5=0,a4=3,a3=0,a2=0,a1=2,a0=1
所以,x=2时f(x)=1397
练****利用秦九韶算法分别计算f(x)=8x7+5x6+3x4+2x+1在x=2与x=-1的值,并判断多项式f(x)在区间[-1,2]上有没有零点。
所以,x=2时f(x)=1397
……
所以当x= -1时,f(x)= -1
因为f(-1)f(2)<0,所以在区间[-1,2]有零点。
注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.