優(yōu)秀畢業(yè)論文Grobner基理論及其應(yīng)用

《優(yōu)秀畢業(yè)論文Grobner基理論及其應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、Grobner基理論及其應(yīng)用理學(xué)院數(shù)學(xué)系：張菁偉指導(dǎo)教師：陳勝摘要：本文介紹了運(yùn)用Grobner棊求整系數(shù)線性方程組的非負(fù)整數(shù)解的算法，并給出了一些求解Frobenius問題的例子。另外，本文還簡要介紹了Hilbert基及其在求整系數(shù)線性方程組的非負(fù)整數(shù)解上的應(yīng)用。最后，本文研究了源于符號動力系統(tǒng)理論的判斷兩個非負(fù)整數(shù)矩陣是否z步轉(zhuǎn)移等價問題，給出了算法及例子。關(guān)鍵詞：Grobner基；非負(fù)整數(shù)解；Ililbert基；轉(zhuǎn)移等價Abstract:Inthispaper,weintroduceanalgorithmforcomputingthenon-negativeintege

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

3、quivalenceoflag/fromonenonnegativematrixtoanother,whicharisesfi*omthetheoryofsymbolicdynamicalsystems,andpresentanalgorithmandsomeexamples?Keywords:GrobnerbasesnonintegersolutionHilbertbasesshiftequivalence1引言對于環(huán)中理想的刻畫是I?分怵I難的，然而在實(shí)際中有大量問題都要求我們能夠?qū)Νh(huán)中理想冇進(jìn)一步的刻価，不只單純回答與存在性相關(guān)的問題，更重要的是能夠具體求解。Grobn

4、er基理論的木質(zhì)是從多變元多項(xiàng)式環(huán)中任一理想的一組生成元出發(fā)，刻化和計(jì)算出一組具冇“好的”性質(zhì)的生成元，而具冇“好的”性質(zhì)的生成元，可幫助我們研究理想的結(jié)構(gòu)和進(jìn)行某些理想運(yùn)算。2求整系數(shù)方程組的非負(fù)整數(shù)解2.1求整系數(shù)方程組的非負(fù)整數(shù)解對于勺w,b占,j=…曲，j=?，加，其屮是整數(shù)環(huán)，求下列方程組?。2口+。22”2~E(2?])■■0“口十陽2”2+???+%%=%的解(0,???,0”)W其中是非負(fù)整數(shù)集合。為了使用Grobner基解這個問題，首先將它轉(zhuǎn)換成多項(xiàng)式問題，然后用Grobner基的技巧解決相應(yīng)的問題，最后再將多項(xiàng)式問題的解轉(zhuǎn)換成方程組求解問題的解。分二步來求

5、解。⑴設(shè)勺和)=1,…，加都是非負(fù)報(bào)數(shù)。判斷方程紐(2?1)是否有解，如果有解則求出一個解。首先，我們引進(jìn)變元西,…,乙，并且考慮方程組工聽A?！?x?,l

6、.1.1使用上邊的記號。設(shè)所有的知和也都是非負(fù)整數(shù)。如果g…洽是°的一個象，則它是環(huán)k［y}，…,兒］中某個幕積屮…必的象?，F(xiàn)在我們給岀判斷（2?1）在條件（1）之下是否有解，如果有解，給出求解的算法⑴。⑴計(jì)算環(huán)燦州，…心」,…，兒］屮的理想I=<兒一卅々了...Xy\的相對兀變元大于y變元的消元序的Grobner基G。（ii）計(jì)算幕積腫垮…￡；模G的余多項(xiàng)式力。（iii）如果燦X，…,兒］,則方程組（2?1）沒有非負(fù)整數(shù)解。如果力=屮…對，則（°,???,0”）是方程組（2?1）的非負(fù)整數(shù)解。（2）設(shè)勺和b「i=,???,n,丿=1,…，加，是整數(shù)（不一定是非

7、負(fù)的）。判斷方程組（2?1）是否有解，如果有解則求出一個解。首先需要處理負(fù)幕次。令W是一個新的變元，I=ck［x},--,xn,w］是環(huán)燦兀i，…*“，叱I中的理想。對于任何（切,。2八…，知），15j5m，存在非負(fù)整數(shù)dj和幻，使得（仙，。2八…，為）=（%?衛(wèi)2/,）+勺（一1廠1，…廠1）°由于兀］兀2?…￡w=l(mod7)于是(x{x2???￡)?=w(mod/)xf,y才...xy=xcy兀;2j...xywaj(mod/)類似地，?,…如=(時,…，盯)+0(-1