优秀毕业论文Grobner基理论及其应用

《优秀毕业论文Grobner基理论及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Grobner基理论及其应用理学院数学系：张菁伟指导教师：陈胜摘要：本文介绍了运用Grobner棊求整系数线性方程组的非负整数解的算法，并给出了一些求解Frobenius问题的例子。另外，本文还简要介绍了Hilbert基及其在求整系数线性方程组的非负整数解上的应用。最后，本文研究了源于符号动力系统理论的判断两个非负整数矩阵是否z步转移等价问题，给出了算法及例子。关键词：Grobner基；非负整数解；Ililbert基；转移等价Abstract:Inthispaper,weintroduceanalgorithmforcomputingthenon-negativeintege

2、rsolutionstoalinearsystemofequationsoverintegers,andwealsosolvetheFrobeniusprobleminsomesimplecases・Inaddition,wealsobrieflyintroduceHilbertbasesanditsapplicationsincomputingthegeneralnonnegativesolutionstoalinearsystemoverintegers.Finally,westudytheproblemofdeterminingwhetherthereisashifte

3、quivalenceoflag/fromonenonnegativematrixtoanother,whicharisesfi*omthetheoryofsymbolicdynamicalsystems,andpresentanalgorithmandsomeexamples・Keywords:GrobnerbasesnonintegersolutionHilbertbasesshiftequivalence1引言对于环中理想的刻画是I•分怵I难的，然而在实际中有大量问题都要求我们能够对环中理想冇进一步的刻価，不只单纯回答与存在性相关的问题，更重要的是能够具体求解。Grobn

4、er基理论的木质是从多变元多项式环中任一理想的一组生成元出发，刻化和计算出一组具冇“好的”性质的生成元，而具冇“好的”性质的生成元，可帮助我们研究理想的结构和进行某些理想运算。2求整系数方程组的非负整数解2.1求整系数方程组的非负整数解对于勺w,b占,j=…曲，j=•，加，其屮是整数环，求下列方程组«。2口+。22”2~E(2・])■■0“口十陽2”2+•・・+%%=%的解(0,・・・,0”)W其中是非负整数集合。为了使用Grobner基解这个问题，首先将它转换成多项式问题，然后用Grobner基的技巧解决相应的问题，最后再将多项式问题的解转换成方程组求解问题的解。分二步来求

5、解。⑴设勺和)=1,…，加都是非负報数。判断方程纽(2・1)是否有解，如果有解则求出一个解。首先，我们引进变元西,…,乙，并且考虑方程组工听A兀『=x?,l

6、.1.1使用上边的记号。设所有的知和也都是非负整数。如果g…洽是°的一个象，则它是环k［y}，…,儿］中某个幕积屮…必的象。现在我们给岀判断（2・1）在条件（1）之下是否有解，如果有解，给出求解的算法⑴。⑴计算环灿州，…心」,…，儿］屮的理想I=<儿一卅々了...Xy\的相对兀变元大于y变元的消元序的Grobner基G。（ii）计算幕积肿垮…£；模G的余多项式力。（iii）如果灿X，…,儿］,则方程组（2・1）没有非负整数解。如果力=屮…对，则（°,・・・,0”）是方程组（2・1）的非负整数解。（2）设勺和b「i=,・・・,n,丿=1,…，加，是整数（不一定是非

7、负的）。判断方程组（2・1）是否有解，如果有解则求出一个解。首先需要处理负幕次。令W是一个新的变元，I=ck［x},--,xn,w］是环灿兀i，…*“，叱I中的理想。对于任何（切,。2八…，知），15j5m，存在非负整数dj和幻，使得（仙，。2八…，為）=（%•卫2/,）+勺（一1厂1，…厂1）°由于兀］兀2•…£w=l(mod7)于是(x{x2•••£)»=w(mod/)xf,y才...xy=xcy兀;2j...xywaj(mod/)类似地，©,…如=(时,…，盯)+0(-1