（计算数学专业论文）求解混合三角多项式方程组的同伦方法.pdf

摘要 非线性方程组的数值计算是科学与工程计算中的重要问题，而关于求方程组全部解 的研究是其难点同伦方法是求多项式方程组全部解的一种有效的数值方法本文主要 研究利用同伦方法求解混合三角多项式方程组及由混合三角多项式方程组转化来的多项 式方程组考虑以下问题。 1 、不进行变元替换，直接求解混合三角多项式方程组 2 、利用混合三角多项式方程组转化过来的多项式方程组的特殊结构，构造更加有 效的同伦进行求解 第一章首先对同伦方法特别是求解多项式方程组的同伦方法做了简要的综述然后 给出混合三角多项式方程组的一般模型，例举了一些它在工程和科学领域中的应用，并 阐述了混合三角多项式方程组与多项式方程组之间的相互转化关系 第二章给出了一些求解混合三角多项式方程组的直接同伦方法，即不将其化为多项 式组而直接构造同伦方法这样可避免增加问题的维数，使路径跟踪过程效率更高我 们首先给出了求解一般混合三角多项式方程组的标准同伦方法，进一步的，针对实际应 用中经常出现的亏欠混合三角多项式方程组，我们给出两种行之有效的随机线性乘积同 伦。多重齐次同伦以及基于广义b 6 z o u t 数构造的同伦，并且给出了一种新的变元分组方 法我们从理论上证明了所提出的方法的可用性，并将算法利用m a t l a b 语言编程实现， 通过数值试验验证了它们的实际有效性 第三章给出两种求解由混合三角多项式方程组转化而来的多项式方程组的高效率同 伦方法利用这类问题的特殊结构，我们提出了混合同伦方法，不仅同伦的形式是混合 的，而且求解方法也是符号计算方法和数值方法的结合进一步利用这类方程组的部分 对称性，我们给出了一种更加有效的方法：对称混合同伦方法我们建立了所提出方法 的理论基础并将其利用c + + 语言实现，通过数值试验验证了它们的有效性 第四章是进一步的数值试验及实际应用首先利用直接同伦方法和混合同伦方法两 种方法分别求解不同类型的混合三角多项式方程组，给出了数值实验结果，说明两种方 法各自适合求解的混合三角多项式方程组的类型；其后，我们着重讨论一个具有挑战性 的实际工程问题一声纳和雷达信号处理问题该问题用已有的方法很难求解，而当维数 较大时，甚至不能求解利用本文提出的混合同伦方法并结合系数参数同伦方法。我们 很好地解决了这个实际问题，实现了快速求解 关键词：混合三角多项式方程组；多项式方程组；同伦方法；符号计算方法；混合方法 i h o m o t o p ym e t h o d sf o rm i x e dt r i g o n o m e t r i cp o l y n o m i a l s y s t e m s a b s t r a c t s o l v i t l gn o n l i n e a rs y s t e m si sam a j o rt a s ko fc o m p u t a t i o n a lm a t h e m a t i c s f i n d i n ga l l s o l u t i o n st oan o n l i n e a rs y s t e mi sac h a l l e n g i n gp r o b l e ma n dh a sp r a c t i c a la p p l i c a t i o n si nm a n y f i e l d so fs c i e n c ea n de n g i n e e r i n g h o m o t o p ym e t h o di sa ne f f i c i e n tn u m e r i c a lm e t h o df o rf i n d i n g a l li s o l a t e ds o l u t i o n st os o m es p e c i a lk i n d so fn o n l i n e a rs y s t e m s ，e g ，p o l y n o m i a ls y s t e m s i n t h i sd i s s e r t a t i o n ，w ec o n s i d e rt os o l v em i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e m sa n dp o l y n o m i a l s y s t e m st r a n s f o r m e df r o mt h e mm o r ee f f i c i e n t l y w ep r e s e n tt w ok i n d so fm e t h o d sf o rs u c h p r o b l e m s ： 1 d i r e c th o m o t o ym e t h o d st os o l v em i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e m s ； 2 f o rt h ep o l y n o m i a l 趼f l t e l n 8t r a n s f o r m e df r o mt h em i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s - t e m s ，w eu t i l i z ei t ss p e c i a ls t r u c t u r et 0c o n s t r u c tm o r ee f f i c i e n th o m o t o p i e s i nc h a p t e r1 ，w eg i v ea ni n t r o d u c t i o no ft h eh o m o t o p ym e t h o da n di t sa p p l i c a t i o n si nt h e f i e l do fs c i e n c ea n de n g i n e e r i n g ，e s p e c i a l l yh o m o t o p ym e t h o d sf o rs o l v i n gp o l y n o m i a ls y s t e m s a l s ow ef o r m u l a t et h eg e n e r a lf o r mo fm i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e n m a sa sw e l l 鹪 t r a n s f o r m a t i o n sb e t w e e nam i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e ma n dap o l y n o m i a ls y s t e m s o m ep r a c t i c a le x a m p l e sa r ea l s ol i s t e d i nc h a p t e r2 ，w ep r e s e n ts o m ed i r e c th o m o t o p ym e t h o d sf o rm i x e dt r i g o n o m e t r i cp o l y - n o m i a ls y s t e m s ，t h a ti s ，w ec o n s t n l c th o m o t o p yd i r e c t l yf o rm i x e dt r i g o n o m e t r i cp o l y n o m i a l s y s t e m sa n dd on o tt r a n s f o r mt h e mi n t op o l y n o m i a ls y s t e m s b yd o i n gl i k et h i s ，n oa d d i t i o n a l v a r i a b l e si si n t r o d u c e da n dh e n c ec a ns o l v et h ep r o b l e mm o r ee f f i c i e n t l y f o rg e n e r a lm i x e d t r i g o n o m e t r i cp o l y n o m i a l 哟，s 乞e 脚，w ep r e s e n ts t a n d a r dh o m o t o p i 笛f u r t h e r m o r e ，b e c a u s e m i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e m sa r i s i n gi np r a c t i c ea r em a i n l yd e f i c i e n t w ep r e s e n t t w oe f f i c i e n tr a n d o ml i n e a rp r o d u c th o m o t o p i ：m u l t i - h o m o g e n e o u sh o m o t d p ya n d p r o d u c th o - m o t o p yb a s e do nt h eg e n e r a l i z e db d v 幻u tn u m b e rt os o l v et h i sc l a s so fs y s t e m s ，a n di nt h el a t t e r m e t h o d ，an e wa n dm o r ee f f i c i e n tv a r i a b l ep a r t i t i o nm e t h o di sp r e s e n t e d w eg i v es o m et h e o - r e t i c a lr e s u l t s ，i m p l e m e n tt h em e t h o d sb ya p p l y i n gm a t l a bp r o g r a m m i n gl a n g u a g e ，a n dm a k e ac o m p a r i s o nb e t w e e no u rd i r e c th o m o t o p ym e t h o d sa n dt h ee x i s t i n gm e t h o d st os h o wt h e i r e f f e c t i v e n e s s i nc h a p t e r3 ，e f f i c i e n tm e t h o d sf o rs o l v i n gp o l y n o m i a l8 1 f s t e m f lt r a n s f o r m e df r o mm i x e d t r i g o n o m e t r i cp o l y n o m i a ls y s t e m sa r eg i v e n t h i sc l a s so fp o l y n o m i a ls y s t e m sh a v eas p e c i a l 壅壁堡盒三塑垒塑壅矍塑丝匾丝壅鲞 s t r u c t u r e a p p l y i n gt h i ss p e c i a ls t r u c t u r e ，锄e f f i c i e n th y b r i dm e t h o di sp r e s e n t e d i tc o m - h i n e st h eh o m o t o p ym e t h o d ，i nw h i c ht h eh o m o t o p yi sac o m b i n a t i o no fc o e f f i c i e n tp a r a m e t e r h o m o t o p ya n dt h er a n d o mp r o d u c th o m o t o p y , w i t hs y m b o l i cc o m p u t a t i o nm e t h o d s ，翻圮h 髓 d e c o m p o s i t i o n ，v a r i a b l es u b s t i t u t i o na n dr e d u c t i o nt e c h n i q u e s f u r t h e r m o r e ，b a s e do nt h e 渺 n 捷触s t r u c t u r eo ft h el o w e rp a r to ft h et a r g e ts y s t e m ，as y m m e t r i ch o m o t o p ya n dh y b r i d m e t h o da r ep r e s e n t e d t h i sm e t h o dc a nk e e pt h es y m m e t r i cs t r u c t u r eo ft h et a r g e ts y s t e m , w h i c hc a ns a v ec o m p u t a t i o n a lw o r kg r e a t l y w ep r o v es o m et h e o r e t i c a lr e s u l t s ，i m p l e m e n to u r m e t h o db ya p p l y i n gc + + p r o g r a m m i n gl a n g u a g ea n dm a k eac o m p a r i s o nb e t w e e n 锄rm e t h o d s a n dt h ee x i s t i n gm e t h o d st os h o wt h e i re f f e c t i v e n e s s i nc h a p t e r4 ，b yf u r t h e rn u m e r i c a le x p e r i m e n t s ，w ed m c u s st h ea d v a n t a g e sa n dd i s a d v a n - t a g e so fd i r e c th o m o t o p ym e t h o d sa n dh y b r i dm e t h o d si ns o l v i n gd i f f e r e n t c l a s s e so fm i x e d t r i g o n o m e t r i cp o l y n o m i a ls y s t e m s t h e n ，w et u r nt oac h a l l e n g i n gp r a c t i c a lp r o b l e m ，w h i c h a r i s e si ns i g n a lp r o c e s s i n go fs o n a ra n dr a d 叠ra n di sh a r dt oh es o l v e db ye x i s t i n gs o l v i n $ m e t h - o d s w eg i v eaf a s ts o l v i n gm e t h o dw h i c hj 8t h ec o m b i n a t i o no ft h es y m m e t r i ch y b r i dm e t h o d a n dt h ec o e f f i c i e n t - p a r a m e t e rh o m o t o p ym e t h o d k e y w o r d s ：m i x e dt r i g o n o m e t r i cp o l y n o m i a ls y s t e m ；p o l y n o m i a ls y s t e m ；h o m o t o p y m e t h o d ；s y m b o l i cc o m p u t a t i o n ；h y b r i dm e t h o d 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：日期： 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解。大连理工大学硕士、博士学位论文版权使用 规定。，同意大连理工大学保留并向旨家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 导师签名。 一一乒 一& 一h 美坤 第一章绪论 摘要t 本章简要地介绍了同伦方法的发展和应用，多项式方程组和混合三角多项式 方程组在实际中的应用，以及同伦方法在求解多项式方程组及混合三角多项式方程组方 面的一些进展，最后介绍了本文的主要工作 1 1 同伦方法 同伦( h o m o t o p y ) 本身是拓扑学中的个概念，同伦方法是求解非线性方程组的一种 有效的具有大范围收敛性的数值方法古典的同伦方法不是构造性的，它不是算法1 9 5 3 年，d a v i d e n k o 1 】把这种方法改造为一种算法，称之为参数微分法g a v u r i n 2 1 更进步 发展了这种方法，提出了所谓迭代法的连续模拟，这就是最早的同伦方法d a v i d e n k o 和 g a v u r i n 的工作以及以后的一系列研究都只考虑了局部收敛问题，即仅当假定g ( z ) = 0 的解知= z ( o ) 充分接近f ( x ) = 0 的解x ( 1 ) 时，才能证明写( t ) 存在并且当t 一1 时， z ( d 一茁( 1 ) 1 9 7 4 年，k e l l o g g 、l i 和y o r k e 3 】利用微分拓扑工具解决了同伦算法的整体收敛性 问题，并用之给出了b r o u w e r 不动点定理的构造性证明，于是引起了对同伦方法的重新 研究接着s m a l e 4 发表了整体牛顿法的文章，c h o w 、m a l l e t - p a r e t 和y o r l m 5 】又利用 它们构造的同伦给出了一系列重要定理的构造性证明，并同时给出了可用的算法在此 之后，同伦方法的研究蓬勃起来几十年来，人们从非线性方程组、不动点问题、平衡 点问题、无约束优化、约束优化、互补问题、非线性两点边值问题、特征值问题、反特征 值问题等多种数学问题角度对同伦算法进行了广泛深入地研究，并成功地把它们用于经 济学、电子线路设计、自动控制、计算机辅助设计和机械制造等许多领域中( 见a l l g o w e r a n dg e o r g 6 ，7 】，g a r c i aa n dz a n g w i n 【8 l ，w a t s o n ，b i l l u p sa n dm o r g a n 9 及其引文) ，成为引 人注目的算法 应当说明，我们这里讨论的是同伦延拓法，或称为连续同伦方法还有一类同伦方 法，称为单纯形同伦方法，或分片线性同伦方法，这类方法最早的工作是s c a r t 的论文 【l o 】，在这篇文章中，s c a r t 提出了s p e n n e r 引理构造性证明，从而也实现了b r o u w e r 定 理的构造性证明，有关问题在【6 删中有详细的说明。因为这类算法与本文所研究的问题 无直接关系，将不讨论 下面扼要叙述同伦方法的基本思想：考虑有限维空间e n 上的非线性方程组f ( 动= 0 ，其中f ：e n _ e n 是光滑映射，选择易求解的方程组g ( 动= 0 ，构造同伦映射日( z ，t ) ， 1 求解混合三角多项式方程组的同伦方法 使得t h ( x ，0 ) 一g ( 动，日 ，1 ) = f 扛) ( 1 1 1 ) 如果同伦方程日( z ，t ) 一0 对任意t 【o ，1 ) 有解z ( t ) 存在，则z ( t ) 在t = 1 处的值 矿= ! i 玛z ( 亡) 即为f ( z ) = 0 的解其中，g ( z ) = 0 称为初始方程组，它的解是易求的， 称为初始解f ( $ ) = 0 称为目标方程组 从其基本思想可以看出，同伦方法主要包含两步。第一步，把方程组f ( z ) = 0 嵌入 到一族方程组日( 。，善) 一0 中，使得( 1 1 1 ) 式成立第二步，通过同伦延拓方法对解曲线 进行数值跟踪 最常使用的同伦有如下两种t ( 1 ) 、凸组合同伦， ( 2 ) 、牛顿同伦。 h ( x ，t ) 一( 1 一t ) ( z 一知) + 坍( z ) 日0 ，t ) = f 扛) 一( 1 一t ) f 0 0 ) 日( 茁，t ) = 0 为酽1 0 ，1 ) 上的方程，满足霉( o ) = x 0 的解( z ，t ) 为过x 0 的条曲线， 若能说明这条解曲线存在并且能够与t = l 平面相交与( 矿，1 ) ，则矿为f ( z ) = 0 的解 当h ( x ，t ) = 0 关于霉，t 可微时，由隐函数定理可知，若日( $ ，t ) 一0 的j a c o b i 矩阵满秩， 则( z ，t ) = 0 定义了个一维光滑流形过( x 0 ，0 ) 的分支就是我们所求的曲线也就是 验证当0 t l 时，0 为n ( x ，t ) = 0 的正则值如果再能证明曲线能达到t = 1 平面 则证明了f ( g ) = 0 解的存在性 综上所述，为应用同伦算法需验证。 1 平凡性( t r h 他a i t y ) ：p ( z ) 一0 解易求 2 光滑性( s m o o t h n e s s ) ：对所有的0 t 1 ，0 为h ( x ，t ) = 0 的正则值即日( z ，t ) = 0 的过( x o ，0 ) 的解为一条光滑曲线 3 可达性( a c c e s s i b i l i t y ) ：这条曲线能够达到平面t = 1 具有上面三个性质的同伦称为好的同伦，不具有上面性质的同伦称为坏的同伦 图1 1 描述了解路径的形态，左边是坏的同伦，右边是好的同伦 2 大连理工大学博士学位论文 i i x t olol 圈1 1 坏的同伦与好的同伦 t 可以看出，左边解路径的情况很糟糕，路径可能会掉头、分叉、停止或者对某个t o 1 趋于无穷；右边则是比较典型的好的同伦，路径只有在t _ + 1 的时候才会趋于无穷远 可以通过数值跟踪同伦路径，即日( z ，t ) = 0 的解曲线来求出f ( z ) = 0 的解不同的 曲线跟踪方法有不同的形式，但都具有如下的基本结构。 1 初始化步。确定以下三个量；初始点( z ，0 0 = ( x 0 , 0 ) ，初始步长h ，容许误差e 2 预估步t 利用各种预估方法，例如s日( z ，t ) = 0 在( z ，t ) o = ( x 0 ，0 ) 处的一阶或二 阶t a y l o r 展式，或3 次h e r m i t 七插值，或割线公式，得到预估点( z ，t ) ( 1 ) = ( z ( ，t ( 1 ) ) 3 校正步。以( 茁，t ) ( 1 ) 为初值，利用迭代方法产生个序列 ( z ，t ) ( ) 笔l ，使( z ，t ) ； ( z ，t ) ( 七) 为日- 1 ( o ) 中的点的近似且其误差不大于如果迭代不收敛，则缩小步长转回 预估步 4 调换步：根据某判别准则，若( z ，t ) 。满足要求，则置( ，0 0 = ( 霉，t ) ，并相应的调 整步长h 5 校验步：如果( z ，0 0 达到目标点，则停止否则转预估步 1 2 多项式方程组及其求解 多项式方程组是一类最基本最常见的非线性方程组在许许多多的应用领域中。如 机械结构设计，机器人设计，几何相交问题，电路分配，化学工程，反位置问题，运动学 问题等，经常需要对多项式方程组进行求解关于多项式方程组解的研究是代数几何的 核心问题 多项式方程组的一般形式为 p ( z ) = ( p l ( z ) + a l ，a i ( z ) + 口1 ) t = o ( 1 2 2 ) 3 其中 h a ( 甸= 叼z a “，霉n 材= z 产1 旌枷， ( 1 2 3 ) j = l 啦j k ( k 一1 ，n ) 为非负整数 下面给出两个实际应用中的例子【1 1 j l e x a m p l e1 几何相交问题，求以( o ，o ) 为圆，t , - ，5 为半径的圆与以( 8 ，o ) 为圆l - ，5 为 半径的圆的实交点 ( 研+ z 2 + z ；- 啦! 6 2 1 2 5 + 的) = o e x a m p l e2 化学平衡问题。在个容器里面以衡定温度加热氢气和氧气生成水 ( 蠢卜 形如( 1 2 3 ) 的多项式鼽( 妨的全次数画定义为 n 函= m 舣 ( 七i1 歹冬岛) 七= l n 元多项式方程组p ( 茹) = 0 的全次数d e g ( p ) 定义为 n d e g ( p ) = 1 - i 噍， i - - - - 1 也称为b d z o u t 数 p ( 卫) = 0 的j a c o b i 矩阵j p ( x ) 脚n n 矩阵，包含了所有的一阶偏导数，形式如 下 ，镑磬镑、 昂；i 挈挈：一晕1 瓣镑镪 如果p ( 矿) = 0 ，则称矿是多项式方魏m ) = 0 的解籼，如果d e t ( 妇( 矿) ) 0 ， 则解矿称为正则的；否则，称它是奇异的如果存在个解的球形邻域，使得球内不含 这个方程组的其它解，则称这个解是孤立的 4 大连理工大学博士学位论文 在实际应用中，我们常常需要求多项式方程组的多个有物理意义的解甚至是在c t i 上 的所有孤立解可惜的是，即使对于单变元多项式，当其次数大于4 时，绝大多数情况 下就已经没有直接的解法了牛顿法是一种有效的求解非线性方程组的方法，但它是局 部收敛的，只有在解的估计值与所要的解足够靠近时才会收敛，并且即使收敛，也可能 只是收敛到我们不关心的没有意义的解，因此我们需要的是一种具有全局收敛性的求解 方法 目前求多项式方程组的全部解的整体计算方法主要分为两种。一种是基于消元技术 的符号计算方法，例如t 吴方法【1 3 ，6 3 l 、g r o e b n e r 基方法f 1 4 、结式法【1 5 ，1 6 】和特征 值方法【1 7 - 2 1 】等，符号计算方法是计算机代数的基础，在数学理论研究和几何定理的机 器证明方面有重要的应用，但主要应用于求解中小规模的多项式方程组另外一种是数 值计算方法，同伦方法是目前求解多项式方程组全部解的主要数值方法 将同伦方法最早应用于求解多项式方程组的作者是g a r c i a 和z a n 觯i l l 2 2 1 以及d r e x l e r 【2 3 】类似于求解一般的非线性方程组，对于给定的目标方程组p ( z ) = 0 ，构造同伦映射 日( z ，t ) ：c n 【o ，1 1 叫c ，l ， 使得 日( z ，0 ) = q ( z ) ，日( z ，1 ) = p ( z ) 对于任一t 冗，日( $ ，t ) = 0 均为一关于z 的多项式方程组，并且具有如下性质t 1 平凡性初始方程组q ( z ) = 0 的解是易求的 2 光滑性：日( z ，t ) = 0 在0st 0 ， 妻+ 七 吣n 槲七 o ，七：1 ，m ( l 3 - 3 ) 若+ 七 0 ，+ m + 七 0 ， 若z n + 知 0 n譬髻譬譬等噪：匿 b z z 玳 + n 咀 雕 诚蔽 峨 璺 鲫 盯i ： 一 俨 一射 大连理工大学博士学位论文 脚，= ( 嚣兰2 ) = 1 。 m 4 ， z ；+ 遽一 戤 = b l ，霹 一b 2 ， i = l i = l n住 戤z ，州= 6 3 ，甄i mi t一6 4 ， i = 1i - - - - 1 nn 氟“ 一6 5 ，视“+ m + = k ， i - - - - 1i - - - - 1 nt l z + = b ， 霹+ m “ 一6 8 ， t = l i - - - - 1 nn z “ = 6 9 ， 霹+ t + m + i 一6 l o ， i = 1i - - - - 1 nn z + i z n + t ，h i = b n ， 霹+ i z 嚣+ m “ = h 2 ， i = li = 1 nn z + t z n + 玎l + i = b l s