资源描述：
《牛顿插值算法在因式分解中的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、牛顿插值算法在因式分解中的设计与实现摘要：本文基于Kronecker所提供的一元多项式因式分解的构造算法、一元整系数多项式在整数环上因式分解理论，利用牛顿向前差分插值算法代替拉格朗日插值算法，把有理域上一元高次多项式因式分解化为在整数环上的因式分解，得到了整数环上的一元多项式因式分解的构造性算法及其具体实现过程。论文关键词：Newton插值、不可约多项式、因式构造、算法0引言计算机出现以后，研究多项式因式分解的构造和算法实现问题成为计算机代数的重要课题，对此国内外很多学者做了大量的工作，吴文俊教授在文献[2]
2、中作了系统详细的研究，给出因式分解方法，A.K.Lenstra,H.K.Lenstra和L.Lova’sz三人于1982年首次提出了一元整系数多项式分解算法[3]，即著名的L3算法。本文基于Kronecker因式分解的基本思想[4]：在有理数域内，任何n次多项式都能经有限此算术运算分解为不可约多项式的乘积。设f(x)为整系数多项式且f(x)=g(x)q(x),则适当调整系数后，可使f(x)的因式g(x)、q(x)也为整系数多项式。对于整数a，等式f(a)=g(a)q(a)中的g(a)的数值必为f(a)的因数，
3、数学论文由于f(a)的因数是有限个，所以只能得到有限个g(a)；设f(x)有k次因式g(x)，f(x)在某k+1个点x0、x1、…、xk处的值分别为f(x0)、f(x1)、…、f(xk)，再对f(xi)(其中i=0,1,…,k)进行因式分解，所得的因数个数为pi(其中i=0,1,…,k),从f(xi)的因数集中取一个因数，一共有种不同的方法，利用拉格朗日插值公式求出多项式g(x)，判定所求多项式g(x)是否为f(x)的因式。在因式分解中涉及多项式的整除性，本文利用多项式整除性的一些性质，对多项式可能存在的因式
4、进行判断，找出多项式的因式。一般情况下，人工可以进行4次及一下的多项式的分解，而高于4次的多项式很难进行分解，于是设想用计算机来解决这个问题，把高次多项式分解成一些不可约多项式的积，提高解题效率。1算法原理分析1.1Newton向前差分插值算法在Kronecker提供的因式分解构造性算法中，采用了朗格朗日插值算法。拉格朗日插值算法虽格式整齐和规范，但计算量大、没有承袭性，当需要增加差值节点时，不得不重新计算所有插值基函数，同时内存消耗大[5]。且有时会产生切断误差而不能进行精确因式分解。于是本文用牛顿向前差分
5、差值算法[6]代替拉格朗日算法。定义：设等距节点xi=x0+ih，h是步长，i=0，1，2，…记函数f的值fi=f(xi)，i=0，1，2，…则称一阶向前差分△fi=fi+1-fi，n阶向前差分△nfi=△n-1fi+1-△n-1fi定理1：向前差分与函数的关系为： 其中现讨论等距节点情形：x0由定理1有：f[x0、x1、…、xk]=△kfi/(k!hk)于是牛顿插值公式简化为Nn(x)=f0+(x-x0)△1f0/(1!h1)+(x-x0)(x-x1)△2f0/(2!h2)+…+(x-x0)(x-x1)…(
6、x-xn-1)△nf0/(n!hn)本算法采用等距节点h=1的情况，于是k次多项式Nk(x)的系数分别为： 1.2因式判断在本文中F(x)表示数域上F上的全体，设f(x)、g(x)F(x)，物流管理毕业论文范文如果存在多项式f(x)=g(x)q(x)，则称f(x)能被g(x)整除，记为f(x)g(x)。整除有以下几个定理来判断：定理2[6]:若R是整数环，R(x)也是整数环，因而必有商域称为R上的一元有理分式域。于是有:(1)若g(x)=0，那么根据整除的定义，g(x)只能整除零多项式；(2)若g(x)0，那
7、么由以上定理，当且仅当g(x)除以f(x)的余式r(x)=0时，g(x)能整除f(x)。1.3多项式相除算法设f(x)=g(x)q(x)则 (0tn)亦，当a0=0，ai0时，f(x)必有因式g(x)=x；当c0=0时，f(x)可能有因式g(x)=x；当c00时，d0=a0/c0,dn-k=an/ck (t=1,2,…,n-k-1)2算法分析及实现用构造性算法(如图1)找出f(x)可能的因式g(x)，若g(x)为整系数多项式且最高项系数不为0，则flag=1;否则flag=0。若flag=1并验证出g(x)是
8、f(x)的因式，则输出g(x),facmon=1,f(x)=f(x)/g(x)(即令n=n-k)；否则继续构造。若构造的g(x)的次数k>[n/2]且facmom=0,则f(x)是不可约多项式；若构造的g(x)的次数k>[n/2]且facmom=1，则输出f(x)的最后一个因式f(x)，否则继续构造。3结束语本文利用多项式整除性的一些性质，对多项式可能存在的因式进行判断，找出多项式的因式。一般情况下
