最小。 齐次 B e z o u t 数的计算 和一类非线性方程组的同伦方法曹小飞专业:计算数学指导教师:于波教授摘要本文研究多项式方程组的最小二 齐次B e z o u t 数的计算方法和一 类非线性方程组的同伦算法.第一章简介了多项式方程组的一些定义以及同伦方法求解多项式方程组的基本思想.第二章首先介绍了B e z o u t 定理 由B e z o u t 定理及二B e z o u 七 定理， 我们知道 可以 通过求得最小的m - 齐次B e z o u t 数来给出孤立解的个数的上界.W a m p l e r 提出了计算、 齐次B e z o u t 数的几种方法， 并对各个方法的计算量以及优缺点 进 行了 分析讨论、 在求出所有的二 齐次B e z o u t 数之后， 可以通过对各种分组方案 的穷举法找到最小的. 然而， 随着多项式方程组未知量的增多，二 齐次B e z o u t 数的 情况也越来越复杂， 穷举法需要的 计算量也越来越大， 以至于在未知量大于 1 0 的时候， 求得最小的m - 齐次B e z o u t 数变得很困 难。 为此， 白峰杉等人 提出了 一 种局部搜索方法， 并随机选取若干个初始搜分组来增加求出 最小B e z o u t 数的 可 能 性. 他们 的 数值实 验表明 ， 他们 的 算 法大 大提高了 计算 效率， 并且对大 多数 例子。 可以得到最小的B e z o u t 数. 但是对有些例子，他们的算法没有得到最优 值. 我们提出了一种可以快速计算最小B e z o u 七 数的算法，称之为子树搜索法. 该算法从所有变元分在一组倩形出 发， 逐次加细每层( 分组个数相同者为一层) 最优 分组， 直至B e z o u t 数不再降低为止 对所能搜集到的所有例子进行了 数值 实 验， 结果表明 此算法具有很高的效率， 并无一例外地得到了 最有结果 但算法 是否一定能求到最优解，尚待理论证明.第三章介绍了解系数含参数的多项式方程组的骗子 ( 系数参数同伦) ， 并对摘要一类由混合三角多项式方程组r l ( x l , , x n , C O s 0 1 , ， c o s 0 . , s i n 0 1 ， 二r 2 . ( 二 : ， ， x n , C o s B 1 , ， c o s 0 . , s i n 0 1 ， 二 ， s i n 氏) 一a l R ( a , x , 0 ) = , s i n 0 . ) 一a 2 n( 1 ) ( 其中x i ， . . X - 0 1 . . . 氏为未知量，r i 为多项式函数，a , ， . . . , a 2 。 为参数) 通过变换: C o s B i =x n + is i n 氏=x 2 n + ii =1 , ， n转化而来的系数含参数的多项式方程组P ( a , x ) =r l ( x l , ， x 3 . ) 一 a 1 =0r 2 n ( x 1 , ， x 3 n ) 一a 2 n =0 x 2+ l + 二 盖 。 十 1 一 1 = 0( )烤 。 十 x 23 。 一 1 = 。提出了如下改进的系数参数同伦:H ( x , t ) = C ( 1 一 t ) k P ( a * , x ) + t P ( a , x ) ( 3 )并有定理: 若方程组尸 ( a * ) x ) 二0 的 解集合x * 含有d o 个孤立点( d o 为 对一 般的 a ， 方 程组( 2 ) 的 孤立解的 最大 个 数 夕 ， 则 对几 乎所有 的。 C 同 伦( 3 ) 具有 光滑 性和可达性.同 伦( 3 ) 兼 顾 了T .Y . L i 等 人 的 解 含 参 数 多 项 式 方 程 组P ( c , x ) = 0 骗 子 同 伦: H ( x , t ) =P ( ( 1 一t ) c +t c , x ) +( 1 一 t ) b ( 4 )和非线性参数同伦:H ( x , t ) =P ( ( 1 一t 一 t ( 1 一 t ) a ) c +( t 一t 一 t ( 1 一 t ) a ) c , x ) . ( 5 )摘买之长，具有如下优点:1 . 该同伦是线性同伦， 结构简单。2 . 该同 伦不 象同 伦( 4 ) 那 样 摄动P ( a , x ) 的 所有 常数项， 而 保持后、 个 方 程 不便 ( 除一个常数被以外).3 . c “ 不必随机选取，只 要取得使孤立解非奇异且个数达到最大.4若对某一组参数a ， 光滑 性和可达性不满足， 只需重新随机选取复数c ， 而并不需要重新求解难解的初始间 题.上述第2 条优点使得我们可以 把同伦 ( 3 ) 转化为如下直接求解原始混合三 角多 项式方程组( 1 ) 的同 伦:S ( x , 9 ) =c ( 1 一 t ) R ( a “ , x , B ) +t “ R ( a , x , 8 ) ( 6 )与同 伦( 3 ) 相比 ， 同 伦( 6 ) 的 维 数由3 。 降为2 n ， 这可以 大大减 少计算量.第四章， 我们用所提出算法求解一类实际应用课题中提出的含参数混合三角 多项式方程组:E n=a l艺 几 1 I , c o s 氏 二a 2艺 几 ， 几 s i n B 二a 3 ; = 1 I ; c o s t 8 ;二a 4艺 几 ; 几 c o s 氏 s i n 氏 =a ;Z 几 I I i二a s艺 畏 1 玲g o s B ;=a 7E n= = 1 刀s i n 8 ;=a sE 几 1 I i c o s , 9 ,=。 。 Z 急 1 I i c o s 8 ; s i n 8 i=a l o E n;= 1 玲c o s t 8 ; s in 8 ;= a l l E ni = 1 玲 c o s 9 ; s i n g g ; = a , 2 E !,= 1 1 ; c o s 3 B ; s in 8 ; = a 1 3艺 几 1 1 ,1 c o s 4 8 ;= a 1 4( 7 )其中。 。 ， 氏E阳 ， 2 司; a l ， 一， a i a 为已知量.当n 0 , B i E 0 , 2 7 r ) ; a 1 , ， a l 4 i s k n o w n.w h i l e n0而且经常表示成 x r = 玲 嵘2 nx. . . x单项式的 全次数 定义为 r 卜艺 r i复空间C n 上由X 1 ， 一， 组成的含系 数的多项式是有限个单项式的线性组合， 可以表示如下 p = 艺 a r x r1第一章绪论这里非 零复常数a ， 为系数，a r x ， 为一项， 多项式P的全次数定义为所有单 项式中 全次 数的 最大者， 记为d e g 伽 ) . 多 项 式P 被称 为 是齐次的， 如 果它 所有 单项式的全次数都相同.在各种科学及工程领域中，我们常常碰到含有。 个未知量、个多项式方 程的方程组，我们把这样的n元 多项式方程组 ，表示成以下形式;八月一一、.，.口产P i ( x i , P 2 ( x i , x . ) ， 工 。 )( 1 . 1 ) ， x “ )户zf.1.、一一、1户X了.且、尸常常记为项式。x =( x i , ， 二 ， x n ) E C n ，P . ( x l , 。P ( x ) 二( P l ( x ) , ， 二 ， P n ( x ) ) =0 ， 这里P i 为多。 元多项式方程组P的全次数( 表示为d e g ( P ) ) 定义为d e g ( P ) = nd e g (P i )尸的J a c o b矩 阵( 表示为办( 习) 是一 个n x 。 矩阵 ， 包含了 所有的 一阶 偏 导 数，形式如下:J p ( x )一 忽 一 8 x ,1纽肠纽扬纽如勿肠，Op . O P .19 x 2 8 x 8 e x了才1.、-我们 称x 是 多项 式方 程组P ( x ) 的解， 如 果P ( x * ) =0 ; 一个解x 说是lE则 的， 如 果d e t ( J p ( x * ) ) 7 0 ， 否 则， 我们 说它 是奇 异的; 一个 解称 作是孤立的， 如果在这个解附近存在一个非空的球不含这个方程组的其它解.在 很 多 情 况 下， 我 们 要讨 论 解C k i x C 1“ x x C 上的 多 项 式 方 程 组. 令一 个 多项 式 方程 组的 变量为二 =( x i , ， ) C n ， 把这些变量分 成。组， 记为二 =( x t 1 7 , ， x t“ )，。 ， ， 刃2 .以x t j ) 二其中( x ? i , , x j k , ) , .1 = 2 解多项式 方程组的同 伦方法我 们 称 x ( 1 ) , . . . ， x (m ) 为x 的 一 个 组 数 为。的剖 分( 也可 称 为分 组 ) ， 称 K = k 1 , . . . 呱 为剖 分 向 f， 如 果 用C k j ( 1 1 时， 在每条解路径的刚开始和快 结 束 的 时 候 步 长 都 会比 较小 。 而同 伦 映 射H ( x , t ) : C “ x 0 , 1 *。 ， 有起 始 方 程 组 Q ( x ) = 0 ， 它 的 解 被 称 作起 始 解，P ( x ) = 0 则 被 称 作目 标 方 程 纸， 而 对 任 意t E R, H ( x 沟均为一 关于二 的 多 项式 方程 组.定 义1 . 2 : 一个好的同 伦 H ( 二 ， 约， 应当 具有下 列 三条性 质:1 . ( 平凡 性t r i v i a l i t y )Q ( 劝=。 的 解是已 知的;2( 光滑 性 s m o o t h n e s s ) 当0 0 ) 乘以 对应 “ 子 式” 的B e z o u t 数的 总 和， 然后每 个子式的 B e z o u t 数可以 通过相同的 行展开程序递归的 算出来.为了 严格起 见， 令M( K , 力是 通过 让向 量K的气减1 而得到的 新向 量， 然后，行展开算法可以描述如下:b ( D, K , i )1 , E d j b ( D , M( K , j ) , i +1 ) 夕 =1 k 1 护0如果乞 =n +1 ;其它矛1了、ee、一-B e z o u t 数其实就是B=b ( D , K , 1 )相对于基本算法， 这种方法节省了运算， 因为递归通过将元素乘以下一级递 归的子乘积的和而把它们当成了因子， 在运算次数的比 较中我们发现， 对。二1 两种方法完全相同，因为这时只有一个次数乘积， 但是，在最复杂的情况 ( 即 。=n) ， 所 有勺=1 ， 乘 法 的 次 数 为 ( 1 / 1 ! +1 / 2 ! +1 / ( n 一1 ) ! ) n ! ， 当 n 增加时， 这个数快速接近 ( 。 一1 ) n ! ， 因 此， 这种情况下行展开算法的乘法次 数与 基本 算法所需的 乘法次数的比 值大约 为 ( 。 一1 ) / ( 。 一1 ) ，。取中间 值时 ( 即1 1 ) b ( 2 , 2 ) =d i I b ( 1 , 2 ) +d i 2 b ( 2 , 1 )B e z o u t 数 就 是B=b ( 2 , 2 ) ， 使 用T 1 2 次 乘 法， 还 可以 通 过b ( 0 , 0 ) =1 消 去 乘 法而使乘法次数降低到 1 0 次， 可以通过下图更好的得到更