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

牛顿插值算法在因式分解中的设计与实现 摘要：本文基于 Kronecker 所提供的一元多项式因式分解的构造算法、一元整系数多项 式在整数环上因式分解理论，利用牛顿向前差分插值算法代替拉格朗日插值算法，把有理 域上一元高次多项式因式分解化为在整数环上的因式分解，得到了整数环上的一元多项式 因式分解的构造性算法及其具体实现过程。 论文关键词：Newton 插值、不可约多项式、因式构造、算法 0 引言 计算机出现以后，研究多项式因式分解的构造和算法实现问题成为计算机代数的重要课题， 对此国内外很多学者做了大量的工作，吴文俊教授在文献2中作了系统详细的研究，给出 因式分解方法，A.K.Lenstra,H.K.Lenstra 和 L.Lovasz 三人于 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 有： fx0、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)。整除有以下几 个定理来判断： 定理 26:若 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)的次数 kn/2且 facmom=0,则 f(x)是不可约多项式；若构造的 g(x)的次数 kn/2且 facmom=1，则输出 f(x)的最后一个因式 f(x)，否则继续构造。 3 结束语 本文利用多项式整除性的一些性质，对多项式可能存在的因式进行判断，找出多项式的因 式。一般情况下，人工可以进行低次多项式的分解，而高次多项式很难进