摘要：本文基于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]代替拉格朗日算法。
1/3 1 2 3 下一页 尾页 |
