牛顿插值算法在因式分解中的设计与实现

牛顿插值算法在因式分解中的设计与实现摘要：本文基于 Kronecker 所提供的一元多项式因式分解的构造算法、一元整系数多项式在整数环上因式分解理论，利用牛顿向前差分插值算法代替拉格朗日插值算法，把有理域上一元高次多项式因式分解化为在整数环上的因式分解，得到了整数环上的一元多项式因式分解的构造性算法及其具体实现过程。论文关键词：Newton 插值、不可约多项式、因式构造、算法0 引言计算机出现以后，研究多项式因式分解的构造和算法实现问题成为计算机代数的重要课题，对此国内外很多学者做了大量的工作，吴文俊教授在文献[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)的因数，数学论文由于 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 次的多项式很难进行分解，于是设想用计算机来解决这个问题，把高次多项式分解成一些不可约多项式的积，提高解题效率。1 算法原理分析1.1 Newton 向前差分插值算法在 Kronecker 提供的因式分解构造性算法中，采用了朗格朗日插值算法。拉格朗日插值算法虽格式整齐和规范，但计算量大、没有承袭性，当需要增加差值节点时，不得不重新计算所有插值基函数，同时内存消耗大[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)… (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，那么由以上定理，当且仅当 g(x)除以 f(x)的余式 r(x)=0 时，g(x)能整除 f(x)。1.3 多项式相除算法设 f(x)= g(x)q(x)则 (0 t n)亦，当 a0=0，ai 0 时，f(x)必有因式 g(x)=x；当 c0=0 时，f(x)可能有因式 g(x)=x；当 c0 0 时，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)是 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 结束语本文利用多项式整除性的一些性质，对多项式可能存在的因式进行判断，找出多项式的因式。一般情况下，人工可以进行低次多项式的分解，而高次多项式很难进行分解，于是设想用计算机来解决这个问题，把高次多项式分解成一些不可约多项式的积，提高解题效率。本文把有理数域上一元高次多项式因式分解化为在整数环上的因式分解，得到了整数环上的一元多项式因式分解的构造性算法及其具体实现过程。