（基础数学专业论文）非线性代数方程组与几何约束问题求解.pdf

0 i j 云f ! ! _ _ 摘要 鸷塞燕蔓 非线性代数方程组与几何约束问题求解 基础数学专业 研究生向晓林指导教师扬路研究员 非线性代数方程组的求解乃是非线性科学的核心；很多来自工程、机械、科学研究等 的实际问题最终都化为求解一个非线性代数方程组；而非线性代数方程组的求解，是一个 至今没有彻底解决的数学问题；特别地，来自工程、机械等的几何约束闻题，最终都将产 生一个非线性代数方程组，且该代数方程组中方程和未知趣的个数都非常多，且往往其中 的未知量的次数还非常高。因此解决这些几何约束问题极其困难。本文在上述几个方面 进行了大量、深入和细致的研究。在下面几个方面在导师杨路研究员的精心指导下做出了 独特的创新； 对非线性代数方程组的基本理论进行了深入研究，给出了多项式的商环的对偶空 间的基的显示表示的一个基本定理； 对非线性代数方程的求解算法进行了深入研究，给出了一个求一元高次代数方程 实根的定位算法。井用结式的基本理论给出了求代数数根界的一个有效算法。 使用距离几何理论。给出了能够对几何约束问题产生极少的方程个数的系统方法 和理论。并给出了将几何元素的距离坐标转化为直角坐标的系统方法； 对几何元素在歇氏空间的实现的理论。用构造性的方法进行了发展； 对数值最优化的基本理论进行了细致讨论，给出了其解的等价性的一些基本定 理： 结合数值方法和符号方法的优势。研究了非线性代数方程组的求解问题，得到了 解非线性代数方程组的有效算法： 将我们的系统方法用计算机代数系统编制了计算机程序。解决丁几个典型的几 何约束问题的求解。其中有些问题的求解还给出了其符号解，而这些问题按已有 的方法根本不能得到其符号解；等等。 关键词：非线性代数方程组几何约束 - 2 - 向晓林：非线性代数方程组与几何约束问题求解 n o n l i n e a r a l g e b r a i cp o l y n o m i a ls y s t e m a n d s o l v i n g g e o m e t r y c o n s t r a i n e d p r o b l e m s p e c i a l t y ：p u r em a t h e m a t i c s s c d c a n d i d a t e ：x i a n g x i a o l i n s u p e r v i s o r ：y a n gl u s o l v i n gn o n l i n e a ra l g e b r a i cs y s t e mi st h ek e r n e li nn o n l i n e a rs c i e n c e m a n yp r o b l e m st h a t c o m ef r o me n g i n e e r i n g ，m e c h a n i c so ri n v e s t i g a t i o np r o d u c es o m en o n l i n e a ra l g e b r a i cs y s t e m s ， b u ti ti sav e r yd i f f i c u l tp r o b l e ml i l ln o wt h a to n ew a n t st os o l v et h o s es y s t e m s e s p e c i a l l y , g e o m e t r yc o n s t r a i n e dp r o b l e m st h a tc o m e f r o mt h ee n g i n e e r i n ga n dm e c h a n i c su s u a l l yp r o d u c e n o n l i n e a ra l g e b r a i c p o l y n o m i a ls y s t e m st h a t h a v em a n ye q u a t i o n so ri n e q u a t i o n sw i t hm a n y v a r i a b l e sa n dh i g hd e g r e ea tl a s t s oi ti st o od i f f i c u l tt of i n dt h e i rs o l u t i o n sw i t h o u te f f e c t i v e m e t h o d si nt h i sp a p e r ，w eh a v ed e e p l yi n v e s t i g a t e da l lt h e s ea s p e c t sa sa b o v e u n d e rm y s u p e r v i s o rp r o f e s s o ry a n g l u sg r e a th e l p ，w eh a v e g o t s o m em a i nc o n c l u s i o n sa sf o l l o w s ： w eh a v ei n v e s t i g a t e dt h ef o u n d a t i o nt h e o r yi nn o n l i n e a ra l g e b r a i cs y s t e ma n dg i v e na f o u n d a t i o nt h e o r e mt h a tg i v ea ne x p l i c i te x p r e s s i o na b o u tt h eb a s i si nt h ed u a ll i n e a r s p a c eb yt h e l i n e a rs p a c eo fq u o t i e n t r i n go ft h ep o l y n o m i a l sr i n g t h i st h e o r e m r e s u l t si nav e r ye f f e c t i v et o o lf o rs o l v i n gn o n l i n e a ra l g e b r a i cs y s t e m ； w eh a v ei n v e s t i g a t e dt h ea l g o r i t h mo fs o l v i n gt h ea l g e b r a i cu n i v a r i a b l ep o l y n o m i a l e q u a t i o n w i t h h i g hd e g r e e w eg o tar e a lr o o tl o c a t e d a l g o r i t h m o fp o l y n o m i a l e q u a t i o ni no n eu n k n o w na n dh i g ho r d e r ；a n da l s og o tan e wc o n s t r u c t i v er o o t - b o u n d a l g o r i t h mb a s e d0 nr e s u l t a n tf o ra l g e b r a i ce x p r e s s i o n ； u s i n gt h et h e o r yi nd i s t a n c eg e o m e t r y , w eh a v eg i v e nas y s t e m a t i cm e t h o da n dt h e o r y t op r o d u c ean o n l i n e a ra l g e b r a i cs y s t e mw h i c hh a v em u c hf e w e rn o n l i n e a ra l g e b r a i c p o l y n o m i a l s t h a n u s i n gd e s c a m e s c o o r d i n a t e m e t h o d d i r e c t l y ，a n d a s y s t e m a t i c p r o c e d u r ew h i c hm a yh e l pu st oc o v e r tt h ed i s t a n c e sc o o r d i n a t es y s t e mt od e s c a g e s c o o r d i n a t eo ft h e g e o m e t r y e l e m e n t s e x p e d i e n t l y a l l o ft h o s er e s u l t s a r e v e r y i m p o r t a n t t os o l v i n gt h eg e o m e t r y - c o n s t r a i n e dp r o b l e m ； u s i n gc o n s t r u c t i v em e t h o d s w eh a v eg o ts o m en e wr e s u l t so nt h et h e o r yo fe m b e d d e d t h eg e o m e t r ye l e m e n t si n t oe i a c l i d e a ns p a c e ； w eh a v e d e e p l y d i s c u s s e dt h en u m e r i c a l o p t i m i z a t i o nt h e o r y , o b t a i n e d s o m e e q u i v a l e n tr e s u l t s ； c o m b i n i n g t h en u m e r i c a l a l g o r i t h m w i t ht h e s y m b o l i ca l g o r i t h m w eh a v e i n v e s t i g a t e dt h ep r o b l e mi ns o l v i n gn o n l i n e a ra l g e b r a i cp o l y n o m i a ls y s t e m ，g i v e n s o m ee f f i c i e n ta l g o r i t h m sf o rs o l v i n gt h es y s t e m ； 3 摘监 w eh a v ed e s i g n e dt h ep r o g r a mw i t hm a p l e u s i n g t h i sp r o g r a m w eh a v es o l v e dt h r e e t y p i c a lg e o m e t r yc o n s t r a i n e dp r o b l e m si nc o m p u t e r , i n c l u d i n go c t a h e d r o np r o b l e m ， l c o s i t e t r a h e d r o np r o b l e ma n dp a c k i n gp r o b l e m i n d e e d ，w eh a v eg i v e nt h ec o m p l e t e s y m b o l i cr e s u l t sf o rs o m ep r o b l e m s ，w h i c hi si m p o s s i b l ei nt h ep a s t k e yw o r d s ：n o n l i n e a r a l g e b r a i cp o l y n o m i a ls y s t e m ，g e o m e t r yc o n s t r a i n e d ，d i s t a n c e g e o m e t r y 向晓林：非线性代数方程组与几何约束问题求解 v 8 5 5 6 5 致谢 衷心感谢导师杨路研究员把作者领进机器证明这个多姿多彩的研究领域以及四年来 的精心指导谆谆教诲和无微不至的关心和帮助。本文的选题、写作及相应的编程工作自 始至终得到先生的糟心指导、热情地关心、鼓励和帮助。先生严谨的学风、对数学的深刻 理解及对机器证明的深建洞察力极大地启发和影响着作者，必将在我将来的学习、工作和 生活中产生深远的影响四年来杨先生为作者提供了许多学习、讨论以及研究的机会和 条件。不断将新的思想、方法和资料介绍给作者。同时，感谢先生对作者生活上的关怀与 支持。 感谢中国科学院成都计算机应用研究所的曾撮柄研究员、张景中院士以及宁波大学数 学系的侯晓荣教授对作者的指导、关心和鼓励，给作者提供的极其宝贵的学习资料以及一 个好的学习环境。 感谢汕头大学李永丰拦博士后、计算所的陈光喜博士和冯勇副研究员、中国科学院北京 计算所的夏时洪博士是他们在机器证明方面的渊博的知识以及有效的学习方法深深地影 响了我，我在学习中的每一点成就都与他们的影响分不开。 感谢刘武副教授、刘忠博士、冯山博士、陈世平博士，四川大学的胡世凯博士、顾晓 棼博士、王林山| 礴士等，北京大学的李光汉博士以及其它师兄师弟在我们一同学习中的有 益的讨论是和他们的讨论开启了我思维的大门。感谢北京大学夏壁灿博士，清华大学王 道顺博士等同门师兄对作者在学习上的有益的影响。 感谢我在论文中直接和问接引用了他们的研究成果的所有作者们。 感谢i 1 , 1 1 1 大学徐道义教授对我一贯的关心和帮助，感谢四川大学数学学院的老师们四 年来对我的培养- 感谢四川：= 学应用数学系、管理科学与工程系、工商管理学院的所有领 导、老师和同事对我学习的支持。 最后我还要再一次感谢中国科学院成都计算所的陈光喜博士和冯勇副研究员，是他们 四年来给我提供了学习上垒面的帮助和方便；感谢我的家人四年来对我的照顾和为我所做 出的一切付山以及对我学业的理解与支持。没有他们作者根难完成学业。 感谢所有支持、关心和帮助我完成学业的老师、同学、亲戚和朋友。 皇堕苎：! ! 些堡垡墼查墨望兰盐塑丝塑塞竺一 引言 计算机作为人类二十世纪的伟大发明，推动了人类社会的快速发展，它正从人们的思 想观念、工作方式、工作手段等方面彻底地改变着人类社会，它时时刻刻改变着人们的生 存和工作环境它已经对科学家的研究方法、手段和环境带来了深刻的影响利用它已经 使许多那些对于科学研究者来说原来不可能或者很难做的研究工作得以实现，现在每天都 会有数以万计的新的结论、成果、方法、技术和产品不断涌现，这无疑是与计算机的使用 分不开的。 数学和计算机科学具有密切的关系，数学是计算机的灵魂，数学为计算机科学提供理 论基础，计算机从数学上来说也仅仅是一个数学模型的具体实现。同时，数学为计算机能 够快速稳定的运算提供高效的算法；计算机也反过来对数学产生着深刻的影响，它使得数 学比以往任何时刻都更具有威力，直接影响着数学中的价值观念和方法平衡，通过其创新 性的应用。问接的改变着数学的内容和结构，计算机作为一种先进的工具，也正在改变着 数学家的工作方式，它正在逐渐的成为数学家不可替代的可靠助手和新思想的实验场所 它把数学家从繁复的演算中解放出来使之能把更多的精力注入到新的发现和创造中。 对于实际计算来说一个好的算法是至关重要的实际可行性问题不能容忍粗糙的算 法，某些算法即使在理论上不管多么完备，如果没有能够接受的时间复杂性和空间复杂性 也只能算是一个空谈。正是在这个意义下为了扩充有兴趣的计算机应用领域，出现了一 个崭新的数学学科；机械化数学它对实际可行性比对理论可能性更感兴趣，实际可行性 已经成为衡量数学进步的一个重要准则。数学的发展已经由抽象的、结构主义的道路转向 具体的、构造性的、结合实际的、结合计算机的道路。 迄今为止，定理机器证明领域相继出现了逻辑方法、代数方法以及几何不变量方法， 但是，对这一领域的研究可以追溯到古代数学机械化的主旨是寻求机械化的方法达到解 决一类问题的目的，而追求数学的机械化方法正是中国古代数学的特点中国古代数学研 究的中心问题是求解其方法是把问题分门别类。寻找出一类的解题模式。九章算术 就是把向题分成九大类，对每一类簿惩给出解题的办法 5 5 】。 以希腊的几何学为代袭的古代西方数学所研究的中心问题不是问题的分类求解。而是 在建立公理体系的基础上一个一个地证明各式各样的数学命题。强调运用公理、假设进行 逻辑推理，强烈地依赖于技巧与灵感。 1 7 世纪法国数学家笛卡儿创立了解析几何，使初等几何问惩代数化，在世界上第一 次把无章可循的凡何证明蘑纳入了有一定规范形式的代数框架，为后来的几何定理机器证 明打下了基础。后来，德国数学家莱布尼兹也曾提出过“推理机器”的设想。 然而，第一次真正提出对某一类几何命题的假设的机械化检验方法的是数学大师希尔 伯特。在距今1 0 0 多年前的t 8 9 9 年出版的他的名著 ”为z 嚣上的全序关系 2 如果口 局口，p , r e 咒，那么口+ ， + t 3 “ ”为z 品上的良序关系t 即；z 品上的任意非空集合在关系“ ”上都有最小 4 - 塑堕签! ! ! 些堡垡墼杰堡望兰凸塑丝塞塑墨苎簦一一 元素。 那么，称关系“ ”为多项式环k x l ，x 2 c ，矗 上的一个单项式序- 常用的单项式序有以下三种： l ，若“”：口 l e a 、a - p z ”，并且该差向量最左边的第一个非零数为正数， 如果d h 卢，那么我们记r kx 4 。可以证明，“ h 。满足单项式序的定义1 1 i 1 的 三个条件该序称为字典序。 2 若“，脚”：d g r l e x j a 4 = j 纠= 属，o r l-l“d 俐= - i p l a n d 口 。声。 如果口 脚，那么我们记， 咖，可以证明，。h ”也满足单项式序的定义1 1 1 r 1 的兰个条件该序称为分级字典序 3 若“ ，妇”：口 。m p 臼陋f - q 渊= 届。o rh = 例并且 扣hd 扩夕z “该差向量最右边的第一个非零数为负数如果口 f ，那么我们记 ， p “x 4 可以证明 眦也满足单项式序的定义1 1 1 1 的三个条件该序称 为分级逆字典序 定义1 1 1 2 令，= x 8 为多项式环x “，而，k 】上的多项式，关系“ 为多项式环研而，x ：，】上的一个单项式序， 1 多项式f 的多元次数定义为：m u l t f d e g ( f ) = n 蛆x ( c t i 口z 品，以。o ) 一其中的 最大是指关于序“ ”取最大。 2 多项式，的首项系数定义为：l c ( f ) = 口m 。出_ ，) e k 3 多项式，的酋单项式定义为：l m ( f ) = z “畦7 4 多项式的首项定义为：，( 。d = t o ( ) 厶v ( 力 算法1 1 1 1 【5 2 ( 除法算法) ( 输入：石，厶，z ，厂 输出：d l ，口2 ，口，) 苎= 兰斐垡丝垡墼堡墨望墨苎丝墨堡鎏一一 b e g i n 口l = o ，a 2 0 ，口，。o , r = 0 p = f w h i l e p 0 d o 芦l d i v i s l o n o c c u r r e a f a l s e w h i l e i q 屯 ) - 那么： q = g n 足【而+ i h ：，】 必为理想，的第，个消元理想的g r o e b n e r 基 定义l i 2 2 【5 1 1 ( 部分解) 称点( 口l + i ，口f + 2 ，a ) ey ( ，1 ) ck ”为一个部分解。 任意解( q ，口：，4 。) y ( j ) c k 5 均可以截出一个部分解，反之，对任意的 f e 粗耳，x 2 ，x 。】，如果将f 在理想f 的第1 个消元理想中记为： f = c 口( x ，+ i ，x ，+ 2 ，x 。) x ，+ + c o ( x m ，+ 2 ，x 。) 这里日是x ，在，中出现的最高次幂，我们称c 。为，的酋系数多项式我们有下面的扩展定 理： 定理1 1 2 2 s h s 2 ( 扩展走理) 如果正为一个代数闭域( 如j 。c ) 若一l 关于字典 序的g r o e b n c r 基的元素的首系数多项式在点( d f + i ，) 处不全为0 ，那么y ( ) 中的部 - 9 一 第一章非线性代数议程组及其符号解法 分解( 口+ 1 ，吼) 必能扩展为以一i ) 中的部分解( q ，a t + l ，口。) 上面两个g r o e b n e r 基的基本定理给出了一个解非线性代数方程组的一个简单方法：先 求理想的字典序g r o e b n e r 基g ，然后从解g 的含有最少变量( 如一个变量) 的多项式开 始，逐次解g 中增加一个变量的多项式，反复用扩展定理，直到找到理想，的解为止。这 样解非线性多项式方程组的问题就转化为解序列一元高次多项式的问题了。 算法1 1 2 1 ( g r o e b n e r 基算法) ( 输入：f = ( 石，以，正) ；输出：多项式方程组石= 嗄一= t = o 的解) b e g i n 求理想i _ ， ，正 关于字典序的g r o e b n e r 基g = 9 1 ，9 2 ，g ) ； f o r r = lt o n d o 求q = g n 置畴+ i ，札2 ，。工。】，= n - r ： 将部分解( 口，+ 2 ，口- ) 代入q 得到只含有变元而+ l 的多项式 ，如，k ； 铲g 的元豢的首多项式不全为0 t h e n 求 ， 2 ，k 的最大公因式i l = g c d ( ，h 2 ，k ) ， 解 = 0 得解q “，从而得到部分解( 口+ i ，口一) ； e l s e 方法失败- 算法停止： 肌 d d ： 肋： 注意在实际用该算法解非线性代教方程组时，h = o 往往有多个根，因而一个部分解 ( 口，“，a n ) 最后扩展为多个部分解( q + 1 ，a 。) ，因而，如果，扩展定理的条件总是满 足- 那么该算法能求出非线性代数方程组的所有解。当然，要求解h = o 也是很困难的，在 求解过程中往往扩展定理的条件会不满足而导致算法失败同时，该算法由于计算量太大， 实际计算时往往很慢 1 1 3 用理想的商代数解非线性代数方程组 设g = ( g l ，9 2 ，蜀 为理想j 的c r r o e b n e r 基。对于任意的，e k 【_ 。x 2 ，_ 】 由多项式的除法算法1 1 1 1 知： - l o 向晓林：非线性代数方程组与几何约柬问题求解 f = a l g l + 2 9 2 + + 口，g + 广( 1 1 3 1 ) 由g r o e b n e ，基理论7 6 为单项式r 仨 的线性组合。井g s q 5 2 ： 1 7 6 = 一g 曲，一g i 2 7 6 + 矿：两。 ，歹霄。：石。 在商环k x i ，x 2 。，】，中，记 f i = f + l = ( 厂+ ： e d ，显然有 【，】= 【g 】f g ，t 商环墨k ，x 2 ，x l l 由所有的组成，这里 f e k x i ，x 2 ，】。由上知7 6 f f 。并且7 g ，i f 之间具有一对应关系： 7 6 付【门，因而，7 6 可以作为商环足，屯，】，中的陪集【】的标准表示若在 商环足【一，x 2 ，】，中加入数乘运算( 商环中的常数为【c 】，( c 世) ) ，商环又具有向量 空间结构因而- 崭i k x l ，工】，为一个代敦。称为商代数，记为爿。因为a 中 的元素的标准表示均为单项式x 。芒 的线性组合，且这些单项式在一中线性无 关，因而可将它们组成的集合看成一的基，即：a 的基为：口= 缸a ：r 甚 ) 。 定理1 1 3 1 5 1 5 2 1 1 6 0 6 1 ( 有限定理) 令r c c 为一个域，c 足【 。x 2 ，矗】 为一个理想。那么，下面几条必等价； 1 代数= x x i ，也，x 1 为有限维代数 2 仿射簇矿( ，) cc ”为有限集。此时称理想，为零维理想。 3 如果g 是理想，的g 加e b n e r 那么，对任意的f ，1 s f s 一。必存在m j 0 ，g g ， 使x ，= l r ( g ) 。 该定理的一个宜接推论县： 苎二童苎些丝! ! 墼望堡堡墨苎笪曼壁鲨 一 推论1 1 3 1 理想，为零维理愆。当且仅当，对任意的i ，ls is ，必存在一个菲零的 多项式g ，蚀j n k 【t 】，并且g 生成消去理想j n x 阮】。多项式g 称为理想j 关于变 量x 的最小多项式。 只番用定理l 。1 ，3 ，1 的第三条，在求理想，的g r o e b n e r 基时，选用字典序。并将变量t 作为最小变量，便得推论1 1 3 1 。 该推论的一个应用是用它，可以很容易的求零维理想对应的商代数的基。因为g 是理 想川| 勺g r o e b n e r 基。矿= l t ( g ) ，所以p ，从而有，代数爿的基口中的 元素的幂应在下面矩形框内：d 。弛i 口z 品，v j ，0 s g is m l - l 。因此，我们只需在矩 形区域d 内检验是否有6 ：，便可求得基曰，即丑； r i 口d ，6 ：r ) ，若使 用计算机代数系统m a p l e 关于隶理想i 关于变量五的最小多项式g r o e b n e r 包中的函数 f i n d u m o ；检查理想i 是否是零维的。使用函数f i n z t e o 使有如下求代数爿的基占的算法。 算法1 1 3 1 ( 求代数的基丑算法) ( 输入：p l i s t = ( 石， ，正) ，v l i s t = ( 而，屯，工) 革项式序t o r d e r ；输出：代数彳 的基口) b e g m i f f l n l t e o d l s t , v l l j t ) t h e n g = g b a $ & ( p l i s t , v l 缸t , t o r d e r ) ； 且吨1 】； f o r v i nv l i s t d o m = d e g r e e o i n d u n t ( v , g v l i s o , v ) ； c = 8 ： f o r t 加c d d f o r l f r o mlt o _ p ld o f = f w i f r , o r m a l f 0 , g , v l i s t , t o m e r ) - - tt h e n b = o t , 固。l j ： ，- o d ： o d ； ，1 2 - 塑堕苎：! ! 垡丝垡塑查墨丝皇些塑丝查塑璺苎塑 0 1 3 ； r e t u r n ( b ) ； e l s e e 艘l ，尉、i d e a l 打n o t z e f o d i m e n s i o n a l , n o f i n i t e b o s i s ) f 1 , e n d ； 在以上算法中，还使用了计算机代数系统m a p l e 的如下函数：g b a s i s ( ) ：求理想的 g r o e b n e r 基；d e g r e e ( ) ；求一元多项式关于其变元的次数；n o r m a f ( ) ；求多项式关于多 项式组的约化；o p ( ) ：取出列的元素；r e t u r n ( ) ：返回结果：e r r o r ( ) ：返回错误 信息等等。关于更多的计算机代数系统m a p l e 及其函数参见眄4 1 5 6 j 。 该推论的应用之二是我们可以通过求最小多项式的根来计算非线性代数方程组的解 的每一个分量的值。但是这些分量怎样匹配才是要求的解却是一件报难的事情。 定义l l 3 1 令，仁芷阪，z 2 ，南】为多项式环足b ，善2 ，矗】上一个理想，如果对 任意的整数m 1 ，。1 j f 1 。那么我们称理想j 为根理想。 定义l l 3 2 令jc 以而，x 2 ，_ 】为多项式环足k ，x 2 ， 】上一个理想，理想i 的根理