（运筹学与控制论专业论文）groebner基理论及其在一些优化问题上的应用.pdf

中南大学硕士学位论文 摘要 论文的主要工作是研究和讨论g r o e b n e r 基理论及其应用。 全文由四章组成，第一章是关于计算代数的综述，介绍了计算代 数及计算机代数中的相关概念、g r o e b n e r 基理论的形成及常用的数学 软件m a p l e 第二章阐述多项式约化问题并介绍了g r o e b n e r 基约化 算法。第三章介绍了g r o e b n e r 基理论在整数规划中的应用，得到一 个关于o 1 规划的算法，并应用到离散数学中的一些逻辑推理问题上： 将逻辑命题中的变项看成多项式的项，根据题设条件将它转化成相应 的多项式，然后计算g r o e b n e r 基，从而得到问题的结论。文章第四章 是关于g r o e b n e r 基的应用。一是应用g r o e b n e r 基求城市交通双向路 线的最短路径：针对城市交通路线双向这一特征，先找到起始点和目 标点必须要经过的第一个路口和最后一个路口，然后转化成有向图 建立双向路线的多项式模型，并应用g r o e b n e r 基理论对该模型给出 了一种可用计算机计算求解的代数方法；另一个则是运用g r o e b n e r 基和约化理论对机场分配问题进行讨论：通过分析各个航班使用停机 位的时间上的冲突情况，建立多项式模型，然后运用计算代数方面的 知识，计算理想的g r o e b n e r 基，得到了一种求机场停机位分配的方 法。 关键词g r o e b n e r 基，约化，逻辑命题，最短路径，停机位分配 a b s t r a c t t h em a jo rt a s ko ft h ea r t i c l ei st os t u d ya n dd i s c u s st h et h e o r ya n d t h ea p p l i c a t i o no fg r o e b n e rb a s i s t h ea r t i c l eh a sf o u rc h a p t e r s t h ef i r s t c h a p t e ri si n t r o d u c t i o no f c o m p u t e ra l g e b r a t h ea u t h o ri n t r o d u c e st h ep r i n c i p l ec o n c e p t si n c o m p u t a t i o n a la l g e b r a i ca n dc o m p u t e ra l g e b r a ，f o r m a t i o no ft h e t h e o r yo fg r o e b n e rb a s i sa n dc o m m o nm a t h e m a t i c a ls o f t w a r ei n c o m p u t e ra l g e b r a m m a p l e c h a p t e r2g i v e sa n a c c o u n to ft h e r e d u c i n go fp o l y n o m i a l sa n dt h er e d u c i n ga l g o r i t h mo fg r o e b n e rb a s i s c h a p t e r3 t e l l sa b o u tt h e a p p l i c a t i o no fg r o e b n e rb a s i si n i n t e g e r p r o g r a m m i n g ，t h e na l la l g o r i t h ma b o u to - 1p r o g r a m m i n gi sg i v e na n d u s e di ni n f e r e n c eq u e s t i o no fd i s c r e t em a t h e m a t i c ：t h ep r o p o s i t i o n a ll o g i c i t e mi sv a r i a b l ea st h ep o l y n o m i a li t e m ，w i t ht h ec o n d i t i o n st h a ti t i s t r a n s f o r m e di n t ot h ee q u i v a l e n to f p o l y n o m i a l s ，t h e nc a l c u l a t e sg r o e b n e r b a s i s ，t h u so b t a i n st h ec o n c l u s i o no ft h ep r o p o s i t i o n t h el a s tc h a p t e ri s t h ea p p l i c a t i o no fg r o e b n e rb a s i s f i r s t ，t h et h e o r yo fg r o e b n e rb a s i si st o r e s e a r c ht h es h o r t e s t p a t hf o rt w o w a yt r a n s p o r t a t i o nr o u t e so fc i t i e s ： f o rt h ef e a t u r eo ft w o w a yl i n ea g a i n s tc i t yt r a f f i c ，ak i n do f p o l y n o m i a l m o d e lf o rt w o - w a yl i n ea g a i n s tc i t yt r a f f i ci ss e tu p ，t h e nt h ef i r s ta n dt h e l a s tt r a f f i cj u n c t i o n sc a nb ef o u n d ，a f t e rc h a n g i n gt h et r a f f i cl i n em a p i n t o t h ed i r e c t e dg r a p h ，t h et h e o r yo fg r o e b n e rb a s i si su s e dt og i v et h ek i n d o fa l g e b r am e t h o dw h i c hc a nb es o l v e dw i t hc o m p u t e r a n o t h e ri sa b o u t t h eg a t ea s s i g n m e n ti n a i r p o r t ：w es e tak i n do fp o l y n o m i a lm o d e la f t e r a n a l y z i n gt h er e l a t i o na m o n ga l lo ft h ef l i g h t s ，t h e nc o m p u t er e d u c e d g r o e b n e rb a s i so fi d e a la c c o r d i n gw i t ht h ek n o w l e d g ea b o u tc o m p u t e r a l g e b r a ，t h u san e wk i n do fs o l u t i o nf o rg a t ea s s i g n m e n ti so b t a i n e d 中南大学碛士学位论文 a b s t r a c t k e yw o r d sg r o e b n e rb a s i s ，r e d u c i n g ，p r o p o s i t i o n a ll o g i c ，s h o r t e s t p a t h ，g a t ea s s i g n m e n t i i i 学位论文原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：奎至墼日期：旦年旦月兰日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校 可根据国家或湖南省有关部门规定送交学位论文。 作者签名：监堕聊签恤日期：4 年旦月赴日 中南大学硕士学位论文第一章绪论 1 1 数学与计算 第一章绪论 在人类生活、经济建设和科技发展过程中，“计算始终都扮演着非常重要 的角色。在对自然界和人类社会各种事物发展规律的研究中，当从定性分析过渡 到定量分析时，就必然涉及计算。 人类的计算能力与计算工具密切相关，早期 的计算主要是靠人的大脑再加上一些简单的计算工具来完成，计算效率低，可靠 性也很差。电子计算机的出现大大地提高了人类的计算能力，从而也促进了科学 技术的迅猛发展。最初的电子计算机多用一般规模的数值计算，因此计算机的出 现也催生了计算数学研究在计算机实现数值计算的理论与算法的数学分支。 顾名思义，计算机是用于计算的机器，有了这样的机器，数学的计算问题就 迎刃而解了。当然事情并没有我们那么简单，有许多理论问题和实际问题需要我 们去考虑和解决。我们将数学计算分为两种：符号计算与数值之计算。数值计算 是指浮点数之间的运算。通常一个数值计算问题的解决需要通过很多步浮点运算 来完成，因而会有累积误差。在使用数值计算时还需要考虑算法的稳定性，即输 入数据的微小扰动是否会引起输出的大幅波动。在数值逼近时，又需要考虑逼近 是否收敛以及收敛的速度。与数值计算不同，符号计算所处理的对象都是具有含 义的抽象符号，主要研究如何进行这些符号之间的精确运算，因而没有误差。这 些符号可以是整数、数学常数、有理函数、多项式理想，也可以是几何图形、逻 辑公式和计算程序。 理论和实际计算之间存在着巨大的鸿沟。对实际计算来说，一个好的算法是 至关重要的，但实际可行性问题不能容忍粗糙的算法。正是在这个问题下，为了 扩充计算机应用领域，要求研究一种新的数学，这种数学的发展使得计算机有着 越来越强大的生命力。 这种新数学一般称为机械化数学【l 】。它对实际可行性比对理论可能性更感兴 趣。实际可行性甚至已经成为衡量数学进步的一个重要准则。在这种新数学中， 算法的实际可行性往往是以牺牲它的完全性或可靠性为代价的。对于一个问题 类，如果找不到实际可行的完全算法，很多时候仅仅给出实际可行的部分算法， 即对问题类的某个子类给出实际可行的完全算法也有着重要意义；有时微不足道 的出错概率可能大量节省计算所需的资源。这些观念强烈地体现着数学发展动力 的现实性的一面，它们在传统的所谓核心数学中却是难以立足的，是经常被忽略 了的。数学所面临的这些新的机遇和挑战，促使数学的发展由抽象的、结构主义 的道路转向具体的、构造性的、结合实际的、结合计算机发展的道路。 中南大学硪士学位论文第一章绪论 1 2 计算祝代数 代数学是数学的一个基本分支，是其他数学分支的基础。它所处理和研究的 数学对象是抽象的代数符号与概念，如整数、有理数、多项式、理想等。从数学 发展的历史来看，代数与算法有密切的联系。旱在吉希腊时代，在几何原本 关于数论的论述中，e u c h i l d 就给出了求两个正数的最大公因数的方法，这就是 著名的e u c h i l d 算法。代数学的基本问题是解方程组问题。对于r 元一次方程组， 可以用高斯消元法求解，对于一元二次、三次、四次方程可以找到公式解。这些 方法都是构造性的方法，哥以用算法来实现。僵是对于一元五次和更高次的方程 就找不到公式解了，对于多元多项式方程组更没有一般性的算法。为了解决这些 问题，至1 9 世纪以来，一种新的方法引入到了代数学的研究中，这就是“公理 化方法 。“公理化方法采用抽象的证明，非构造性的论证研究代数问题，获得 了巨大的成功。现在“公理纯方法”已经成为代数学的主要方法。 不过，数学家依然在寻找髂决某一类问题的算法解。例如h i l b e r t 第十问题 就是这类问题。这类问题的提出促进了现代数理逻辑的发展。在2 0 世纪3 0 年代， a l a nt u r i n g , a l o n z oc h u r c h 首先提出了可计算性的概念，从数学上论证了算法的 含义。k u r tg o d e l 证明了某些数学问题没有算法解。到了年代，a l f r e dt a r s k i 系统的研究了一些代数问题的可解性和不可解性。正是这些逻辑学家的工作奠定 了现代计算机科学的基础。 由于代数算法都是建立在数学基础之上豹，所以代数及代数凡何的发展为代 数计算提供了广泛的数学理论基础，同时代数计算的研究也促进了代数理论，特 别是构造性代数及代数几何理论的发展。近年来产生了计算交换代数与计算代数 几何等新的研究领域，或者可以说是更为一般的数学机械化的新的研究领域。 几何定理的机械证明是吴文俊先生在7 0 年代来蓄先提出来的。其基本原理 是将几何定理代数化，然后采用一种机械化的方法判定几何定理是否正确。吴文 俊特别强调方程求解的应用，将他的方法用于解决力学、物理、化学等领域与机 器入、几何造型、连杆设计等高科技的问题。吴的方法还被爝于多项式因式分解， 发现微分系统新的极限环，求解微分方程的行波解与孤立子解，理论物理，几何 造型中的曲面形式转换问题，一阶逻辑公式的证明，计算机视觉，连杆设计问题， 智能c a d ，组合恒等式自动证明等。 随着计算机技术的发展，以及计算枧的普及，应用计算视解决代数问题成为 了可能。计算代数【2 5 】就是在这种条件下出现的一个新的研究方向。从代数的观 点看，计算代数主要探讨代数学中可计算性问题，以及解决这些问题的算法。从 2 中南大学硕士学位论文第一章绪论 计算机科学的角度来看，我们要考虑代数算法的有效性及复杂性。因此计算代数 可以看作代数学与计算机科学相结合的产物。它没有作为一个独立的学科分支， 因为它的演算与推导主要是以符号为主，因此我们也可以把它归入计算机代数这 类中。 计算机代数是用计算机迸行符号推演及准确计算的- - f 7 科学【n 。它也称为符 号和代数计算，是与数值计算并行翡一种数学计算，起源予本世纪六十年代。象 数值计算一样，随着计算机的发展，符号和代数计算办得到迅速发展。现已经成 为数学、计算机科学中的一个独立分支，在理论研究及实际中都有广泛应用。 与数值计算不同，代数算法1 5 的研究与计算机代数的软件系统的研制几乎是 同时的。经3 0 余年的发展，许多计算枧代数系统已投入使用，这些系统的功能 网益强大，效率不断提高这些代数系统的主要功能如下。 ( 1 ) 提供基本命令集，可使机器做许多复杂的计算，包括数值的和符号的 计算。这个特点使得代数系统具有可用性。 ( 2 ) 提供一种能定义高层命令或扩展原始命令的程序语言。使褥系统具有 可开发性。 现有的代数系统可处理的问题如下： ( 1 ) 数的计算，包括整数、有理数、实数和复数的计算，且既可进行浮点 计算又可进行精确计算。 ( 2 ) 多项式、有理式的各种计算。 ( 3 ) 矩阵的计算，且其元素可为符号的。 1 ) 今多项式的最大公因式， 相当于求由它们生成的理想的生成元。判别一个多项式是否属于这个理想，只要 判别这个多项式是否被此理想的生成元整除【1 2 】。但是，数域上的多元多项式环 不是主理想环，它的类似问题比一元多项式环相关问题要复杂得多。不过，数域 上酶多元多项式环的每个理想都是有限生成的【2 , 1 7 , 1 8 ，酃其生成元仅有有限个。 在实际问题中，常常要求有种算法能求出具有某些性质的生成元系，代数方程 组的求解就属于这类问题。还要求有算法，判别一个多项式是否属于该理想，在 代数编码中，码字的判别就属于此类闯题。在计算机代数，计算代数，计算代数 数论，计算代数a 何，代数编码和密码学以及整数规划等中的许多闻题，最后都 归结为某种环上的多项式理想的计算，即找到一个有效算法，求出理想的具有某 些性质的生成元系，解决与理想相关的各类问题。g r o e b n e r 基理论就是为了解决 这些 蠢题丽产生和发展起来的1 2 鼬l 。 g r o e b n e r 基理论的形成可追溯到1 9 2 7 年f s 。n l a c a u l y 的工作。他首先在多 元多项式环的由全体单项式组成的集合中引入全序的概念，研究其理想的某些不 变量。h h i r o n a k 钆于1 9 6 4 年在研究关于奇性分解时引进了多元多项式的除法算 法。在1 9 6 5 年，b b u c h b e r g e r 翻用除法算法系统地研究了域上多元多项式环的 理想生成元问题。他的基本思想是在单项式的集合中引入保持单项式的乘法的全 序，称为项序，以保证多项式相除后所得余多项式唯一他引进了s 一多项式，给 如了一种算法，使得对多项式环中的任意给定理想，从它的一组生成元，可计算 褥到一组被称为g r o e b n e r 基的生成元，它具有唯一性的良好性质。剩用g r o e b n e r 基可以解决与理想相关的许多问题。从此，g r o e b n e r 基的理论及其应用方面得到 了迅速发展。1 9 7 2 年，h g a u e r t 研究了域上的形式幂级数环的相应问。l9 7 8 年， g b e r g r n a n 对结合( 非交换) 代数和更一般的代数系统研究了g r o e b n e r 基的形式， 褥次发现了b u c h b e r g e 在交换情形下的算法。1 9 8 3 年，d 。l a z a r d 提出了用 g r o e b n e r 基解代数方程的思想。1 9 8 5 年，b u c h b e r g e r 系统地研究了g r o e b n e ：基 的算法。1 9 8 6 年，l r o b b i a n 。发展了比较抽象的g r o e b n e r 基理论刘木兰教授 等将g r o e b n e r 基理论用于研究环上的线性递舞阵列，刻划线性递萝j 阵列的结构。 近年来，g r o e b n e r 基应用研究得到了迅速发展。g r o e b n e r 基的应用研究包括代数 方程组求解，多项式的因子分解，多项式在代数扩域和代数函数域中的因子分解， 4 中南大学硕士学位论文 第一章绪论 素理想的检验，代数流形的分解，纠错码中循环码和代数几何码的译码，密码学 中多条序列的综合和高维线性递归阵列的分析与综合，多维系统理论等诸多领 域。g m e b n e r 基在计算机科学和数学的交叉学科计算机代数，计算代数，计算代 数数论和计算代数几何中占有重要地位。g r o e b n e r 基在定理机器证明方面也有重 要应用。2 0 0 0 年，d i m i 仃i sb e n s i m a l s ，g e o 西ap e r a l 【i s 和s f i d h a rt a y u r 利用e b n e r 基，提出t 一种解整数规划的新方法。2 0 0 1 年，j o l l l lb l i 砌e 将g r o e b n e r 基用 于信号处理许多计算机代数系统软件都包含计算舶c b n c r 基的程序包。意大利 的g e i l o v a 大学的关于计算机代数的研究小组提供的用于进行交换代数中计算的 软件系统c o c o a4 1 可直接计算多元多项式环的理想的g r o e b n e r 基。 近十几年来，关于g r o e b n e r 基的应用研究发展十分迅速，这包括给出切实 可行的域上多项式环中的理想的准素分解算法，其中零维理想的准素分解的研究 比较彻底虽然早在v 觚d e r w a e r d e i l 的5 0 年代出版的代数学一书中就讲述 了理想的准素分解，但那只是理论上可行，并没有具体的算法去实现。 特别是在方程的求解方面，方法论大师笛卡尔( r d e s c r y ) 在其著作思 维的法则里，提出了一个大胆的设想( 并对之作了伟大的实践，从而创立了解 析几何学) ：一切问题可以化为数学问题，一切数学问题可以化为代数问题， 一切代数问题可以化为方程求解问题。事情当然不都可以这样一刀切，可仍不失 其为一条值得珍藏的锦囊妙计。我们所讲述的g m e b n e r 基的应用很大一方面就 是在方程求解中的应用，只是由于g r o e b n e r 基本身的求解算法还有一定的局限 性，及其整套理论虽然是非常的成熟，可是在计算复杂度上还不是很理想，所以 还没有得到广泛的应用。 计算机代数、计算代数、计算代数几何、计算代数数论等都是近些年发展起 来的计算机科学与数学的交叉学科分支，而e b n c r 基在其中占有重要地位随 着计算机的小型化、大容量、高速度，可以断言，觚e b n e r 基的应用前景将愈来 愈广泛，同时m e b n e r 基理论和算法的研究将会吸引更多的人【1 9 】。 1 4m a p l e 介绍 由于计算机代数在科学研究与工程技术中越来越广泛的应用，每个科研工 作者。包括数学、计算数学、计算机科学以及其他领域的研究人员，必须掌握计 算机代数的基本知识与熟练使用相关的计算机代数软件。 目前比较流行的通用的有m a p l e 、m a t i l 锄a t i c 、m a t l a b 、c o c o a 、r 耐v e 和r e d u c e 这些计算机代数系统不但能进行符号运算，还能进行数值计算，这为 使用者进行交互计算提供了方便。对有些符号运算问题，特别是各个学科特有的 问题，使用者均可基于该系统去编制求解模块，系统语言为用户提供了程序设计 中南大学硕士学位论文第一章绪论 语句，用户使用它们可以编制自己的求解软件碡9 】。计算机代数系统的优越性主 要在予它能够遴行大规模的代数运算。逶常我们用笔和纸进行代数运算只麓处理 符号较少的算式，当算式的符号上升到百位数霖，手工计算便成为可能丽不可行 的事，主要原因是在做大量符号运算时，我们很容易出错，并且缺乏足够的耐心。 当算式的符号个数上升到四位数后，手工计算便成为不可能的事，这时用计算机 代数系统进行运算就可以做到准确、快捷、有效。计算机代数的这些优点使得诗 算机代数系统能够应用到许多应用领域，譬如：电路设计、理论物理、化学、生 物学、人工智能、工程设计和经济学等。下面就主要介绍现在比较流行的一种计 算机代数系统m a p l e 。 m a p l e 是譬前应用j # 常广泛的符号计算软件之一，它拥有非常强大的符号计 算和数值计算功能。 1 9 8 0 年9 月，加拿大w a t e r l o o 大学的符号计算机研究小组成立，开始了符号 计算在计算机上实现的研究项目，数学软件m a p l e 是这个项目的产品。目前，这 仍是一个燕在研究的项基。 m a p l e 的第一个商业版本是1 9 8 5 年出版的。随后几经更新，到1 9 9 2 年。 w i n d o w s 系统下的m a p l e2 面世后，m a p l e 被广泛地使用，得到越来越多的用 户。特别是1 9 9 4 年，m a p l e3 出版后，兴起了m a p l e 热【翻。1 9 9 6 年初，m a p l e4 闻世，1 9 9 8 年初，m a p l e5 正式发行。 m a p l e 是一个具有强大符号运算能力、数值计算能力、图形处理能力的交互 式计算机代数系统( c o m p u t e ra l g e b r as y s t e m ) 。它可以借助键盘和显示器代替原 来的笔和纸进行各种科学计算、数学推理、猜想的证明以及智能化文字处理。 m a p l e 这个超强数学工具不仅适合数学家、物理学家、工程师，还适合化学 家、生物学家和社会学家，总之，它适合于所有需要科学计算的人。 m a p l e 软件主要幽三个部分组成：用户界面( i r i s ) 、代数运算器( k e r n e l ) 、外 部函数库( e x t e r n a ll i b r a r y ) 。用户界面和代数运算器是用c 语言写成的，只占整 个软佟的一小部分，当系统启动时，即被装入，主要负责输入命令和算式的初步 处理、显示结果、函数图象的显示等。代数运算器负责输入的编译、基本的代数 运算( 如有理数运算、初等代数运算等) 以及内存的管理。m a p l e 的大部分数学函 数和过程是用m a p l e 翻身的语言写成的，存予外部函数库中。当一个函数被调 用时，在多数情况下，m a p l e 会自动将该函数的过程调入内存，一些不常用的丞 数才需要用户自已调入，如线性代数包、统计包等，这使得m a p l e 在资源的利用 上具有很大的优势，只有最有用的东西才留驻内存，这保证了m a p l e 可以在较小 内存的计算机上正常运行。用户可以查看m a p l e 的j 内存函数豁源程序，也可 以将自己编的函数、过程加到m a p l e 的程序库中，或建立自己的函数库。 6 中南大学硕士学位论文第一章绪论 利用m a p l e 可以进行大量的数学运算，它不但具有精确的数值处理功能， 而且具有无与伦比的符号计算功能。m a p l e 的计算能力还是m a t h c a d 和m a t l a b 等软件的符号处理的核心。m a p l e 提供了3 0 0 0 多种数学函数，涉及范围包括： 初等数学、高等数学、线性代数、数论、图论、图形学等。它还提供了一套内置 的编程语言，用户可以开发自己的应用程序，而且m a p l e 自身的3 0 0 0 多种函数 基本上是用此语言开发的。m a p l e 采用字符行输入方式，输入时需要按照规定的 格式输入，虽然与一般常见的数学格式不同，但符合一般高级语言的语法规则， 灵活方便，易于理解。输出则可以字符方式和图形方式，产生的图形结果可以很 方便地剪贴到窗口应用程序内。m a p l e 可以完成特定功能的程序包，如线性代数 程序包、微分方程程序包，统计程序包、偏微分方程程序包以及画图程序包等， 这些程序包可以满足各种实际需要，并提供给不同的用户。在这里我们简要的介 绍一下在这里简要地介绍一下m e b n e r 基软件包中的一些常用的命令。 1 g b a s i s ( p o l y l i s t ，v a r l i s t ，t e r m o r d e r ) ；按一项序求多项式集合的g r o e b n e r 基； 2 p r e t e n d _ g b a s i s ( p o l y l i s t ，p o l y l i s t ，t e r m o r d e r ) ；加一个g r o e b n e r 基到己知的 g r o e b n e r 基中： 3 1 e a d c o e f f ( p o l y n o m i a l , t e r m o r d e r ) ；计算一个多项式的首系数； 4 1 e a d t e r m ( p o l y n o m i a l ，t e r m o r d e r ) ；计算一个多项式的首项； 5 1 e a d m o n ( p o l y n o m i a l ，t e r m o r d c r ) ；计算一个多项式的首单项式； 6 s p o l y ( p o l y n o m i a l ，p o l y n o m i a l ，t e r m o r d e r ) ；计算两个多项式的s 多项式； 7 t e r m o r d e r ( p o l y n o m i a l ，t e r m o r d e r ) ；g l j 建一个项序； 8 t e s t o r d e r ( t e r m ，t e r m ，t e n n o r d e r ) ；测试两项是否符合递增序列； 9 n o r m a l f ( f , p o l y l i s t ，v a r l i s t ，t e r m o r d e r ) ；计算多项式f 模理想的范式； 1 0 i sf i n i t e ( p o l y l i s t ) ；决定一个给定的多项式系统是否有有限多个解； 1 1 i ss o l v a b l e ( p o l y l i s t ) ；决定一个给定的多项式系统是否稳定； 1 2 h i l b e r t d i m ( p o l y l i s t ，t e r m o r d e r ) ；计算一个理想的h i l b e r t 维数； 1 3 h i l b e r t p o l y ( p o l y l i s t ，t e r m o r d e r ) ；计算一个理想的h i l b e r t 多项式； 1 4 h i l b e r t s e r i e s ( p o l y l i s t ，t e r m o r d e r ) ；计算一个理想的h i l b e r t 级数。 7 中毒大学硕士学位论文第二章多项式代数及g r o e b n e r 基约化 第二章多项式代数及g r o e b n e r 基约化 2 1 基础知识 本节我们要介绍的是在科学计算中有很多应用的环。这些理论是g r o e b n e r 基理论和应用所需要的最基本的代数学知识。 环具有两个代数系统，其中第一个运算是交换群的运算，第二个运算是半 群的运算。把这两个运算分别称为加法和乘法的运算，分别用“+ 和搿，表 示。下蕊我们介绍相关概念。 定义2 1 1 【3 j 个半群是指一个非空集合m 和m 上满足结合率的= 元运 算“辩，记为( m ，) ，即m 喾彩，对任何口，b em ，有a 6 膨，为简单起觅记 a b = a b ，并对饪何蛙，b , c m ，有a ( b c ) = a b ) c 。m 中的一个元素e 称为单 位元，如果对任何a m ，都有e a 端a e 黧a 。 定义2 1 2 【3 l 半群g 如果有单位元，而且每个元素都可逆，则称g 为群。 定义2 1 3 瀚如果g 为群且g 满足交换髓，即对g 中的任何两个元素口，b ， 都有a b = b a ，则稼g 为交换群或阿贝尔( a b e l ) 群。 定义2 。1 4 【3 】个环是指个非空集合r 和r 上的两个二元运算，通常表 示成( r ，+ ，) ，其中“+ 和“，分别称为加法运算和乘法运算，它们满足 下列条件： ( 1 ) 集会r 与加法运算构成交换群； ( 2 ) 集合r 与乘法运算构成半群； ( 3 ) 乘法对加法是分配的，即对任何口，6 c r ，有 露( 办+ 力= a o b + a c ，+ e 弘a = b a + c 露 当运算明确时，这个环简记为r ，运算a b 简记为如 若关于数的加法与乘法构成环，则称为数环。整数集z ，有理数q ，实数集尺， 复数集c 都是数环。 设k 是一个数环，囊【x 】表示系数属于k 的所有多项式的集合，剡艇x 】关于 多项式的加法和乘法构成一个环，称为k 上未知量x 的多项式环。 定义2 1 5 1 3 l 设r 为一个环，若其中乘法适合交换律，即v a b r 都有 a b = b a ，则称冗为交换环。若环r 只含有有限个元素，则称r 为有限环。 定义2 1 。誉垃】设( r ，+ ，) 是一个环，s 是定的一个非空子集，若关于爻两 个运算( “+ 一与“”) ，s 作为一个环，则称s 是r 的一个子环。若环月的子环 s 的真字集，则称s 是尺的真子环。 8 中南大学硕士学位论文第二章多项式代数及g r o e b n e r 基约化 定义2 1 7 【1 2 1 设，是环r 的一个子环，若锨r ，a i 皆有r a 1 ，a r 1 ， 则称，是r 的理想。 任意环r 总有尺自身及 0 ) 两个理想，称尺为单理想， o ) 为零理想。 定义2 1 8 【1 2 】设尺为一个环a r ，则尺中含有a 的最小理想称为由a 生成 的主理想，记为 。 主理想 是环尺的所有含a 的理想的交。若整环月的任一理想都是主理 想，则称r 为主理想环。 定义2 1 9 i 1 2 l 设尺为一个环，是环r 的一个理想，则( r i ，+ ，) 称为尺关 于，的商理想，或者称为只关于j 的剩余类环。 定义2 1 1 0 【1 2 】若d 为有单位元的环，至少含有两个元素，且所有非零元素 对乘法构成一个群，则称d 为除环。 一个交换除环成为域。 定义2 1 1 1 【4 】令，是任意域，研五，屯9 , oo 是f 上关于五，屯，的刀元多 项式环，令n 是所有非负整数的集合， t ”= 届乇岛毛危i 屈n ，f = 1 ，2 ，刀) 。 将届岛磊记为x 声，其中= ( 届，屈，尾) n “t “上的一个全序“ 被 称为p 的一个项序，如果“ ”满足下列条件： ( 1 ) 对所有t ，且，1 ，有1 ，； ( 2 ) 若， 的一个字典序，记为“概”，定义如下： 对于口= ( 口，) ，= ( 屈，危，尼) n ”，则 “，营1 i 砜砘o m - k x 2 毛的一个次数字典序，记为“d e g l e x ”，定义如下： 对于口= ( ，口：，口。) ，= ( 屈，反，尾) ，则 x n t 。x x 自 ： 的字典前口 x 2 毛的一个次数反字典序，记为“d e g r e v l e x ，定义 如下： 对于口= ( q ，) ，= ( 屈，屈，孱) n “，则 9 中南大学硕士学位论文第二章多项式代数及g r o e b n e r 基约亿 r 姆妇 二吒 砖 对变量，毛，的幂积一，置和变量蔓，魏，咒的幂积誓，墨，定义： l 五 ，置 五z 置艺 或 | 五= 置且x ， ，记f ( x ) = ( f ( x ) ) ，_ ，= 1 ，2 ，m ， t ( x ) = ( f ，o ) ) ，j = l ，2 ，朋，则存在初式( x ) 使得g ( x ) = 厂( 彳) 一，( x ) ( ，( x ) ) ，且 五在g ( x ) 中的幂一定是要比厂( x ) 要小或是相等。我们也可以记之为 厂( x ) 一g ( x ) 。显然g ( x ) 中的五的幂是匕h f ( x ) 要小了，同时变元的个数 也可能减少了，但是序列后面的变元的幂通常来说是增大。 定义2 3 1 【2 】设k 是数域，g ，k x i ，x 2 ， ，江l ，2 ，m ，如果存在 a t 研，x 2 ，毛】使得 f = ：a i q i + g a ( g ) a ( 门 则说厂可模q 尸一约化为g ，其中q = q i ) ，记作中g ，如果g 不能再被p 一 约化，则称g 是厂的p 一范式。 引理2 3 2 【2 】设q = q l , 9 2 ，吼) c 7 研，x 2 ，吒】，且厂k e x , ，x 2 ，】，则存 在a i 粗，而，艺】使得 f = 口，q ，+ g o ( g ) o ( f ) 在上面p 一约化可以得出，经约化后的p 一范式g 肯定存在，但并不一定是 唯一的，因此在计算机进行计算时，首先提出化简通常所要遵循的两个准则是： ( 1 )多项式分解因子的各变元的幂尽量低； ( 2 ) 若是变元能减少而对准则( 1 ) 的影响不是很大的话，尽量减少变元。 显然这两个准则就是矛盾的，一般所说的约化往往是能满足( 2 ) ，却难以满足 中南大学硕士学位论文第二章多项式代数及g r o e b n e r 基约化 准则( 1 ) 。因此必须对约化的方法加以改进，在约化的过程中，有一个前提就 是给出了变元的序关系，所以我们采用一种动态的序关系机制【1 7 , 1 8 1 。也就是说 每经过一次约化就对序关系进行一次修正。采用一种动态的序关系机制，这样 主要是用于在化简的同时防止某些变元的幂增长过高。在约化的程序设计中， 通常采用类似一元多项式的“辗转相除法一的方法是对一变元进行约化 厂( x ) 耐g ( x ) ，然后再把g ( z ) 赋给f ( x ) 。而对序关系进行修正的主要依 据是看f ( x ) 的变元中的最高次变元的变化，把最高次变元x ，作为这次首先约 化的对象。在约化的过程中，还须考虑的问题是对f ( x 1 的排序，为了减少计算 的复杂度，我们只需按约化的对象工，在f ( ) 的幂进行排序即可。 当然，有可能认为最简的多项式在约化过程中出现，因此在程序的循环过 程中，所以最好在循环中设置一个中间变量，用于这次约化的结果与上一次的 结果比较，还可以设置一个标准( 1 ) 、( 2 ) 进行取舍的判断条件。 2 3s 多项式及g r o e b n e r 算法 上节介绍的高次多项式化简的原理及其算法也适用于多元高次方程组的求 解。在具体的计算过程中，若是次数的浮动不是很高，且精度要求也不是很高， 就采用一般的计算方法【2 8 3 4 1 ；但是在精确计算中或在精度要求比较高的情况下， 采用这种降幂约化法化简是很必要的，同时也是一种有效的计算方法。同时，在 符号运算的程序设计中，这类化简也非常重要。但在一般的计算机上很难用 m a p l e 里的g r o e b n e r 基软件包对稍高次幂的多项式组进行求解。例如用m a p l e 中的g r o e b n e r 基软件包对7 次的三元多项式组求解，速度就非常慢，因此得到 一种优化算法是非常有意义的。本节所要研究的是降幂约化算法对g r o e b n e r 基 算法的优化。 定义2 3 1 1 2 , 5 1 设蜀，9 2 七k ，x 2 ，工。】是非零多项式，取定一个单项式序， 设t j = l t ( g f ) ，口j = l c ( g j ) ，f = 1 , 2 并且f = s i t ，= l c m ( t i ，t 2 ) ，l c m ( t l ，t 2 ) 表示t l ，t 2 的最小公倍式，其中j ，t ( x l ，x 2 ，) 则称 s ( g l ，9 2 ) = a 2 s l g l 一口l s 2 9 2 为g l ，9 2 的s - 多项式。 定义2 3 2 ( s 簇) 1 9 2 0 2 1 1 设鲥x l ，z 2 ，x 。】是域k 上多项式环， 是 k x 。，x 2 ，x 。】的理想0 仨i ，对任意g 萑i 0 ) ，由g ，f 确定的s 一多项式组 成的集合叫做厂在理想，中的s 簇，记为s ， 容易证明s 一簇有以下性质： 1 ) i = o f ； 1 2 中南大学硕士学位论文第二章多项式代数及g r o e b n e r 基约化 2 ) s ns g = s ( f ，g ) ； 3 ) t 3 时，一切元互素，则ns s = 矽 f 这三点性质是后面算法中对多项式集合中进行分解和约化的主要依据。 引理2 3 3 0 1 理想，中有限集合g = 国l ，9 2 ，g ，) 是，的g r o e b n e r ，当且 仅当对一切f ，j = 1 , 2 ，j ，i ，有页而g