欢迎来到论文网! 加入收藏 | 设为论文网 | 网站地图 | Tags标签 | RSS
论文网 论文网8200余万篇毕业论文、各种论文格式和论文范文以及9千多种期刊杂志的论文征稿及论文投稿信息,是论文写作、论文投稿和论文发表的论文参考网站,也是科研人员论文检测和发表论文的理想平台,lunwenf@yeah.net。
您当前的位置:论文网 > 科技论文 > 数学论文

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

时间:2016-08-10  作者:李治强龙法宁洪月华

摘要:本文基于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]代替拉格朗日算法。

查看相关论文专题
-------------------------------------------------------------------------
加入收藏  打印本文
上一篇论文:谈中学数学与大学数学的衔接
下一篇论文:返回列表
科技论文分类
科技小论文 数学建模论文
数学论文 节能减排论文
数学小论文 低碳生活论文
物理论文 建筑工程论文
网站设计论文 农业论文
图书情报 环境保护论文
计算机论文 化学论文
机电一体化论文 生物论文
网络安全论文 机械论文
水利论文 地质论文
交通论文
相关数学论文
最新数学论文
读者推荐的数学论文