第1章多項(xiàng)式的計(jì)算

1、17第1章 多項(xiàng)式的計(jì)算第1章 多項(xiàng)式的計(jì)算1.1 一維多項(xiàng)式求值1功能計(jì)算多項(xiàng)式p(x)=an-1xn-1+an-2xn-2+a1x+a0在指定點(diǎn)x處的函數(shù)值。2方法說明首先將多項(xiàng)式表述成如下嵌套形式：p(x)=(an-1x+an-2)x+an-3)x+a1)x+a0 然后從里往外一層一層地進(jìn)行計(jì)算。其遞推計(jì)算公式如下：un-1=an-1 uk=uk+1x+ak，k=n-2，1，0最后得到的u0即是多項(xiàng)式值p(x)。3函數(shù)語句與形參說明double plyv(a，n，x)形參與函數(shù)類型參 數(shù) 意 義double an存放n-1次多項(xiàng)式的n個(gè)系數(shù)int n多項(xiàng)式的項(xiàng)數(shù)double x指定的自變

2、量值double plyv()返回多項(xiàng)式值p(x)4函數(shù)程序（文件名：1plyv.c）double plyv(a，n，x)int n；double x，a； int i； double u； u=an1； for (i=n2； i=0； i) u=u*x+ai； return(u)；5例計(jì)算多項(xiàng)式p(x)=2x6-5x5+3x4+x3-7x2+7x-20在x=0.9，1.1，1.3處的函數(shù)值。主函數(shù)程序（文件名：1plyv0.c）如下：#include stdio.h#include 1plyv.cmain() int i； static double a7=20.0，7.0，7.0，1.0，

3、3.0，5.0，2.0； static double x6=0.9，0.9，1.1，1.1，1.3，1.3； printf(n)； for (i=0； i=5； i+) printf(x(%d)=%5.2lf p(%d)=%13.7en， i，xi，i，plyv(a，7，xi)； printf(n)；運(yùn)行結(jié)果為：x(0)= 0.90 p(0)=1.856227e+01x(1)=0.90 p(1)=2.671537e+01x(2)= 1.10 p(2)=1.955613e+01x(3)=1.10 p(3)=2.151303e+01x(4)= 1.30 p(4)=2.087573e+01x(5)=

4、1.30 p(5)=6.340432e+001.2 一維多項(xiàng)式多組求值1功能利用系數(shù)預(yù)處理法對(duì)多項(xiàng)式p(x)=an-1xn-1+an-2xn-2+a1x+a0進(jìn)行多組求值。其中n=2k（k1）。2方法說明首先將多項(xiàng)式變?yōu)槭滓欢囗?xiàng)式，即T(x)=p(x)/an-1=xn-1+tn-2xn-2+t1x+t0其中tk=ak/an-1（k=n-2，1，0）。然后對(duì)首一多項(xiàng)式T(x)的系數(shù)進(jìn)行預(yù)處理。其預(yù)處理過程如下：將T(x)分解為T(x)=(x j+b)q(x)+r(x)其中j=2k-1，q(x)與r(x)均為2k-1-1次的首一多項(xiàng)式。b，q(x)與r(x)按以下規(guī)則確定：多項(xiàng)式中的中項(xiàng)系數(shù)減1即

5、為b，即b=多項(xiàng)式左半部分除以x j即為q(x)，即q(x)=xs-1+qs-2xs-2+q1x+q0其中s=2k-1，qi=ti+s（i=s-2，1，0）。多項(xiàng)式右半部分減去b與q(x)的乘積即為r(x)，即r(x)=xs-1+rs-2xs-2+r1x+r0其中ri=ti-bqi（i=s-2，1，0）。由于q(x)與r(x)還是首一多項(xiàng)式，因此，它們也可以按照上述方法分別進(jìn)行分解。這個(gè)過程一直做到q(x)與r(x)的次數(shù)為1為止。在分解過程中，每次分解后的系數(shù)仍存放在T(x)的各系數(shù)的存儲(chǔ)單元中，最后得到T(x)經(jīng)分解處理后的系數(shù)。首一多項(xiàng)式T(x)的系數(shù)經(jīng)預(yù)處理后，就可以用這些預(yù)處理后的系

6、數(shù)對(duì)不同的x求函數(shù)值。這種方法特別適用于對(duì)多個(gè)x進(jìn)行求值，減少求值中的乘法次數(shù)。如果原來的多項(xiàng)式不滿足n=2k這個(gè)條件，則可以添加系數(shù)為0的各項(xiàng)及系數(shù)為1的最高次項(xiàng)。3函數(shù)語句與形參說明void plys(a，n，x，m，p)形參與函數(shù)類型參 數(shù) 意 義double an存放n-1次多項(xiàng)式的n個(gè)系數(shù)。返回時(shí)其值將被改變int n多項(xiàng)式的項(xiàng)數(shù)double xm存放給定的m個(gè)自變量值int m給定自變量的個(gè)數(shù)double pm返回時(shí)存放與給定m個(gè)自變量值對(duì)應(yīng)的多項(xiàng)式值void plys()過程4函數(shù)程序（文件名：1plys.c）#include math.h#include stdlib.hvoi

7、d plys(a，n，x，m，p)int n，m；double a，x，p； int i，j，mm，nn，ll，t，s，kk，k； double *b，y，z； b=malloc(2*n*sizeof(double)； y=an1； for (i=0； i=n1； i+) bi=ai/y； k=log(n0.5)/log(2.0)+1； nn=1； for (i=0； i=k1； i+) nn=2*nn； for (i=n； inn1； i+) bi=0.0； bnn1=1.0； t=nn； s=1； for (i=1； i=k1； i+) t=t/2； mm=t； for (j=1； j=s

8、； j+) mm=mm+t+t； bmm1=bmm11.0； for (kk=2； kk=t； kk+) bmmkk=bmmkkbmm1*bmm+tkk； s=s+s； for (kk=1； kk=m； kk+) for (i=0； i=(nn2)/2； i+) ai=xkk1+b2*i； mm=1； z=xkk1； for (i=1； i=k1； i+) mm=mm+mm； ll=mm+mm； z=z*z； for (j=0； j=nn1； j=j+ll) aj/2=aj/2+a(j+mm)/2*(z+bj+mm1)； z=z*z/xkk1； if (nn!=n) a0=a0z； pkk1=

9、a0*y； return；5例利用系數(shù)預(yù)處理法計(jì)算多項(xiàng)式p(x)=2x6-5x5+3x4+x3-7x2+7x-20在x=0.9，1.1，1.3處的函數(shù)值。主函數(shù)程序（文件名：1plys0.c）如下：#include stdio.h#include 1plys.cmain() int i； double p6； static double a7=20.0，7.0，7.0，1.0，3.0，5.0，2.0； static double x6=0.9，0.9，1.1，1.1，1.3，1.3； plys(a，7，x，6，p)； printf(n)； for (i=0； i=5； i+) printf(x

10、(%d)=%5.2lf p(%d)=%13.7en， i，xi，i，pi)； printf(n)；運(yùn)行結(jié)果為：x(0)= 0.90 p(0)=1.856227e+01x(1)=0.90 p(1)=2.671537e+01x(2)= 1.10 p(2)=1.955613e+01x(3)=1.10 p(3)=2.151303e+01x(4)= 1.30 p(4)=2.087573e+01x(5)=1.30 p(5)=6.340432e+001.3 二維多項(xiàng)式求值1功能計(jì)算二維多項(xiàng)式p(x，y)=在給定點(diǎn)(x，y)處的函數(shù)值。2方法說明將二維多項(xiàng)式變形如下：p(x，y)=令si=，i=0，1，m-1

11、則計(jì)算si的遞推公式如下：un-1=ai,n-1x juj=uj+1y+aijxi，j=n-2，1，0其中最后的u0即為si 。最后將所有的si(i=0，1，m-1)累加，即p(x，y)=3函數(shù)語句與形參說明double bply(a，m，n，x，y)形參與函數(shù)類型參 數(shù) 意 義double amn存放二維多項(xiàng)式的系數(shù)int m自變量x的最高次數(shù)為m-1int n自變量y的最高次數(shù)為n-1double x，y給定的一對(duì)自變量值double bply()返回函數(shù)值p(x，y)4函數(shù)程序（文件名：1bply.c）double bply(a，m，n，x，y)int m，n；double a，x，y；

12、 int i，j； double u，s，xx； u=0.0； xx=1.0； for (i=0； i=0； j) s=s*y+ai*n+j*xx； u=u+s； xx=xx*x； return(u)；5例計(jì)算二維多項(xiàng)式p(x，y)=在給定點(diǎn)(0.6，-1.3)處的函數(shù)值。其中系數(shù)矩陣為A=主函數(shù)程序（文件名：1bply0.c）如下：#include stdio.h#include 1bply.cmain() double z； static double a45=1.0，2.0，3.0，4.0，5.0， 6.0，7.0，8.0，9.0，10.0， 11.0，12.0，13.0，14.0，15

13、.0， 16.0，17.0，18.0，19.0，20.0； printf(n)； z=bply(a，4，5，0.6，1.3)； printf( p(0.60，1.30)=%13.7en，z)； printf(n)；運(yùn)行結(jié)果為：p(0.60，1.30)= 3.966554e+011.4 復(fù)系數(shù)多項(xiàng)式求值1功能計(jì)算復(fù)系數(shù)多項(xiàng)式p(z)=an-1zn-1+an-2zn-2+a1z+a0在給定復(fù)數(shù)z時(shí)的函數(shù)值。2方法說明同1.1節(jié)，只是改成復(fù)數(shù)運(yùn)算。有關(guān)復(fù)數(shù)乘法的方法說明見2.1節(jié)。3函數(shù)語句與形參說明void cply(ar，ai，n，x，y，u，v)形參與函數(shù)類型參 數(shù) 意 義double arn

14、，ain分別存放多項(xiàng)式系數(shù)的實(shí)部與虛部int n多項(xiàng)式的項(xiàng)數(shù)，其最高次數(shù)為n-1double x，y給定復(fù)數(shù)z的實(shí)部與虛部double *u，*v指向返回多項(xiàng)式值p(z)的實(shí)部與虛部void cply()過程4函數(shù)程序（文件名：1cply.c）void cply(ar，ai，n，x，y，u，v)int n；double x，y，ar，ai，*u，*v； int i； double p，q，s，t； void cmul(double，double，double，double，double *，double *)； s=arn1； t=ain1； for (i=n2； i=0； i) cmul(s

15、，t，x，y，&p，&q)； s=p+ari； t=q+aii； *u=s； *v=t； return；static void cmul(a，b，c，d，e，f)double a，b，c，d，*e，*f； double p，q，s； p=a*c； q=b*d； s=(a+b)*(c+d)； *e=pq； *f=spq； return；5例計(jì)算復(fù)系數(shù)多項(xiàng)式p(z)=(2+j2)z3+(1+j)z2+(2+j)z+(2+j)當(dāng)z=1+j時(shí)的函數(shù)值。主函數(shù)程序（文件名：1cply0.c）如下：#include stdio.h#include 1cply.cmain() double x，y，u，v；

16、 static double ar4=2.0，2.0，1.0，2.0； static double ai4=1.0，1.0，1.0，2.0； printf(n)； x=1.0； y=1.0； cply(ar，ai，4，x，y，&u，&v)； printf(p(1.0+j1.0)=%10.7lf +j %10.7lfn，u，v)； printf(n)；運(yùn)行結(jié)果為：p(1.0+j1.0)=7.0000000 +j 6.00000001.5 多項(xiàng)式相乘1功能求兩個(gè)多項(xiàng)式P(x)=pm-1xm-1+pm-2xm-2+p1x+p0Q(x)=qn-1xn-1+qn-2xn-2+q1x+q0的乘積多項(xiàng)式S(

17、x)=P(x)Q(x) =sm+n-2xm+n-2+s2x2+s1x+s02方法說明乘積多項(xiàng)式S(x)中的各系數(shù)按如下公式進(jìn)行計(jì)算：sk=0，k=0，1，m+n-2si+j=si+j+piqj，i=0，1，m-1；j=0，1，n-13函數(shù)語句與形參說明void pmul(p，m，q，n，s，k)形參與函數(shù)類型參 數(shù) 意 義double pm存放多項(xiàng)式P(x)的系數(shù)int m多項(xiàng)式P(x)的項(xiàng)數(shù)，其最高次數(shù)為m-1double qn存放多項(xiàng)式Q(x)的系數(shù)int n多項(xiàng)式Q(x)的項(xiàng)數(shù)，其最高次數(shù)為n-1double sk返回乘積多項(xiàng)式的系數(shù)int k乘積多項(xiàng)式S(x)的項(xiàng)數(shù)，其最高次數(shù)為k-1

18、，其中k=m+n-1void pmul()過程4函數(shù)程序（文件名：1pmul.c）void pmul(p，m，q，n，s，k)int m，n，k；double p，q，s； int i，j； for (i=0； i=k1； i+) si=0.0； for (i=0； i=m1； i+) for (j=0； j=n1； j+) si+j=si+j+pi*qj； return；5例計(jì)算下列兩個(gè)多項(xiàng)式P(x)=3x5-x4+2x3+5x2-6x+4Q(x)=2x3-6x2+3x+2的乘積多項(xiàng)式S(x)=P(x)Q(x)。其中m=6，n=4，k=9。主函數(shù)程序（文件名：1pmul0.c）如下：#inc

19、lude stdio.h#include 1pmul.cmain() int i； static double p6=4.0，6.0，5.0，2.0，1.0，3.0； static double q4=2.0，3.0，6.0，2.0； double s9； pmul(p，6，q，4，s，9)； printf(n)； for (i=0； i=8； i+) printf( s(%d)=%13.7en，i，si)； printf(n)；運(yùn)行結(jié)果為： s(0)= 8.000000e+00 s(1)= 0.000000e+00 s(2)=3.200000e+01 s(3)= 6.300000e+01 s

20、(4)=3.800000e+01 s(5)= 1.000000e+00 s(6)= 1.900000e+01 s(7)=2.000000e+01 s(8)= 6.000000e+001.6 復(fù)系數(shù)多項(xiàng)式相乘1功能求兩個(gè)復(fù)系數(shù)多項(xiàng)式P(z)=pm-1zm-1+pm-2zm-2+p1z+p0Q(z)=qn-1zn-1+qn-2zn-2+q1z+q0的乘積多項(xiàng)式S(z)=P(z)Q(z) =sm+n-2zm+n-2+s2z2+s1z+s0其中所有的系數(shù)均為復(fù)數(shù)。2方法說明同1.5節(jié)，只是改成復(fù)數(shù)運(yùn)算。有關(guān)復(fù)數(shù)乘法的方法說明見2.1節(jié)。3函數(shù)語句與形參說明void cpml(pr，pi，m，qr，qi

21、，n，sr，si，k)形參與函數(shù)類型參 數(shù) 意 義double prm，pim存放多項(xiàng)式P(z)系數(shù)的實(shí)部與虛部int m多項(xiàng)式P(z)的項(xiàng)數(shù)，其最高次數(shù)為m-1double qrn，qin存放多項(xiàng)式Q(z)系數(shù)的實(shí)部與虛部int n多項(xiàng)式Q(z)的項(xiàng)數(shù)，其最高次數(shù)為n-1double srk，sik返回乘積多項(xiàng)式系數(shù)的實(shí)部與虛部int k乘積多項(xiàng)式S(z)的項(xiàng)數(shù)，其最高次數(shù)為k-1，其中k=m+n-1void cpml()過程4函數(shù)程序（文件名：1cpml.c）void cpml(pr，pi，m，qr，qi，n，sr，si，k)int m，n，k；double pr，pi，qr，qi，sr，

22、si； int i，j； double a，b，c，d，u，v； void cmul(double，double，double，double，double *，double *)； for (i=0； i=k1； i+) sri=0.0； sii=0.0； for (i=0； i=m1； i+) for (j=0； j=n1； j+) a=pri； b=pii； c=qrj； d=qij； cmul(a，b，c，d，&u，&v)； sri+j=sri+j+u； sii+j=sii+j+v； return；static void cmul(a，b，c，d，e，f)double a，b，c，d，*

23、e，*f； double p，q，s； p=a*c； q=b*d； s=(a+b)*(c+d)； *e=pq； *f=spq； return；5例求下列兩個(gè)多項(xiàng)式P(z)=(3+j2)z5+(-1-j)z4+(2+j)z3+(5-j4)z2+ (-6+j3)z+(4+j2)Q(z)=(2+j)z3+(-6-j4)z2+(3+j2)z+(2+j)的乘積多項(xiàng)式S(z)。其中m=6，n=4，k=9。主函數(shù)程序（文件名：1cpml0.c）如下：#include stdio.h#include 1cpml.cmain() int i； static double pr6=4.0，6.0，5.0，2.0，

24、1.0，3.0； static double pi6=2.0，3.0，4.0，1.0，1.0，2.0； static double qr4=2.0，3.0，6.0，2.0； static double qi4=1.0，2.0，4.0，1.0； double sr9，si9； cpml(pr，pi，6，qr，qi，4，sr，si，9)； printf(n)； for (i=0； i=8； i+) printf( s(%d)=%13.7e +j %13.7en，i，sri，sii)； printf(n)；運(yùn)行結(jié)果為： s(0)= 6.000000e+00 +j 8.000000e+00 s(1)=

25、7.000000e+00 +j 1.400000e+01 s(2)=2.600000e+01 +j 3.400000e+01 s(3)= 8.000000e+01 +j 1.600000e+01 s(4)=5.800000e+01 +j 8.000000e+00 s(5)= 9.000000e+00 +j 1.500000e+01 s(6)= 1.000000e+01 +j 2.600000e+01 s(7)=1.100000e+01 +j 2.700000e+01 s(8)= 4.000000e+00 +j 7.000000e+001.7 多項(xiàng)式相除1功能求多項(xiàng)式P(x)=pm-1xm-1+

26、pm-2xm-2+p1x+p0被多項(xiàng)式Q(x)=qn-1xn-1+qn-2xn-2+q1x+q0除得的商多項(xiàng)式S(x)和余多項(xiàng)式R(x)。2方法說明本函數(shù)采用綜合除法求商多項(xiàng)式S(x)中的各系數(shù)。設(shè)商多項(xiàng)式S(x)的最高次數(shù)為k=m-n，則S(x)的系數(shù)由下列遞推公式進(jìn)行計(jì)算：sk-i=pm-1-i/qn-1pj=pj-sk-iqj+i-k，j=m-i-1，k-i其中i=0，1，k。最后的p0，p1，pn-2即為余多項(xiàng)式的系數(shù)r0，r1，rn-2。3函數(shù)語句與形參說明void pdiv(p，m，q，n，s，k，r，l)形參與函數(shù)類型參 數(shù) 意 義double pm存放多項(xiàng)式P(x)的系數(shù)。返回

27、時(shí)其中的值將被破壞int m多項(xiàng)式P(x)的項(xiàng)數(shù)，其最高次數(shù)為m-1double qn存放多項(xiàng)式Q(x)的系數(shù)int n多項(xiàng)式Q(x)的項(xiàng)數(shù)，其最高次數(shù)為n-1double sk返回商多項(xiàng)式S(x)的系數(shù)int k商多項(xiàng)式S(x)的項(xiàng)數(shù)，其最高次數(shù)為k-1，其中k=m-n+1double rl返回余多項(xiàng)式R(x)的系數(shù)int l余多項(xiàng)式R(x)的項(xiàng)數(shù)，其最高次數(shù)為l-1，其中l(wèi)=n-1void pdiv()過程4函數(shù)程序（文件名：1pdiv.c）void pdiv(p，m，q，n，s，k，r，l)int m，n，k，l；double p，q，s，r； int i，j，mm，ll； for (i

28、=0； i=1； i) si1=pll/qn1； mm=ll； for (j=1； j=n1； j+) pmm1=pmm1si1*qnj1； mm=mm1； ll=ll1； for (i=0； i=l1； i+) ri=pi； return；5例求多項(xiàng)式P(x)=3x4+6x3-3x2-5x+8被多項(xiàng)式Q(x)=2x2-x+1除得的商多項(xiàng)式S(x)和余多項(xiàng)式R(x)。其中m=5，n=3，k=3，l=2。主函數(shù)程序（文件名：1pdiv0.c）如下：#include stdio.h#include 1pdiv.cmain() int i； static double p5=8.0，5.0，3.0，

29、6.0，3.0； static double q3=1.0，1.0，2.0； double s3，r2； pdiv(p，5，q，3，s，3，r，2)； printf(n)； for (i=0； i=2； i+) printf( s(%d)=%13.7en，i，si)； printf(n)； for (i=0； i=1； i+) printf( r(%d)=%13.7en，i，ri)； printf(n)；運(yùn)行結(jié)果為：s(0)=3.750000e01s(1)= 3.750000e+00s(2)= 1.500000e+00r(0)= 8.375000e+00r(1)=9.125000e+001.8

30、 復(fù)系數(shù)多項(xiàng)式相除1功能求復(fù)系數(shù)多項(xiàng)式P(z)=pm-1zm-1+pm-2zm-2+p1z+p0被復(fù)系數(shù)多項(xiàng)式Q(z)=qn-1zn-1+qn-2zn-2+q1z+q0除得的商多項(xiàng)式S(z)和余多項(xiàng)式R(z)。2方法說明同1.7節(jié)，只是改成復(fù)數(shù)運(yùn)算。有關(guān)復(fù)數(shù)乘法的方法說明見2.1節(jié)，復(fù)數(shù)除法的方法說明見2.2節(jié)。3函數(shù)語句與形參說明void cpdv(pr，pi，m，qr，qi，n，sr，si，k，rr，ri，l)形參與函數(shù)類型參 數(shù) 意 義double prm，pim存放多項(xiàng)式P(z)系數(shù)的實(shí)部與虛部。返回時(shí)將被破壞int m多項(xiàng)式P(z)的項(xiàng)數(shù)，其最高次數(shù)為m-1double qrn，qi

31、n存放多項(xiàng)式Q(z)系數(shù)的實(shí)部與虛部續(xù)表形參與函數(shù)類型參 數(shù) 意 義int n多項(xiàng)式Q(z)的項(xiàng)數(shù)，其最高次數(shù)為n-1double srk，sik返回商多項(xiàng)式S(z)系數(shù)的實(shí)部與虛部int k商多項(xiàng)式S(z)的項(xiàng)數(shù)，其最高次數(shù)為k-1，其中k=m-n+1double rrl，ril返回余多項(xiàng)式R(z)系數(shù)的實(shí)部與虛部int l余多項(xiàng)式R(z)的項(xiàng)數(shù)，其最高次數(shù)為l-1，其中l(wèi)=n-1void cpdv()過程4函數(shù)程序（文件名：1cpdv.c）#include math.hvoid cpdv(pr，pi，m，qr，qi，n，sr，si，k，rr，ri，l)int m，n，k，l；double

32、pr，pi，qr，qi，sr，si，rr，ri； int i，j，mm，ll； double a，b，c，d，u，v； void cmul(double，double，double，double，double *，double *)； void cdiv(double，double，double，double，double *，double *)； for (i=0； i=1； i) a=prll； b=pill； c=qrn1； d=qin1； cdiv(a，b，c，d，&u，&v)； sri1=u； sii1=v； mm=ll； for (j=1； j=n1； j+) a=sri1； b=sii1； c=qrnj1； d=qinj1； cmul(a，b，c，d，&u，&v)； prmm1=prmm1u； pimm1=pimm1v； mm=mm1； ll=ll1； for (i=0； i=l1；