（应用数学专业论文）线性微分方程有理解问题.pdf

摘要 摘要 有许多计算机代数的算法基于构造多项式和有理函数本论文主要综述了线 性微分方程和线性微分方程组有理解的求解算法对线性微分和差分方程的研究 主要有两个方向，一个是寻找新的或者快速的算法来解决方程解的问题；另一个 方向是构造方程，所构造的新的方程可以用已知的算法求解对于线性差分和微 分方程解的研究，l i o u 、棚e 做出了很大的贡献后来，对于方程有理懈的算法， 又由a b r m d v - b r o s t e i n p e t k 0 嚼k 等人进行了改进同时，a b r 锄0 v 给出了寻找 差分和q 差分的有理解的算法 本文的第一部分内容为有理解相关的背景知识；第二部分介绍线性微分方程 有理解算法；第三部分介绍线性方程组的有理解算法 关键词；线性微分方程，差分方程，多项式解，有理解，铲微分，于差分，算法 a b 8 t r a c t a b s t r a c t m a n yc o m p u t e ra l g e b r a “g o r i t h i 衄雏eb 鹊e do nc o n 8 t r u c t i n g m ep 0 1 y n o - m i 砒舡l dr a t i o n a lf l l n c t i 咖i nt h i 8t k l 8 i 8 w ew mp r 部e n t8b v e yf o ra l g o - r i t h m 8w h i c h m p u t ea l lr a t i o n a l8 0 l u t i o 聃o fd 鼢e n t i a le q u a t i o 瑚衄ds y 8 t 鼬 o fd “f e r e i l t l a le a u a t i o n 8 t h e r ea r et w o l a 缸c i i r e c t i o n si nt h er e s e 砌衄l i n e a r d i 丘e r 衄t i ma n dd 诳e r 朗c ee q u a t i o 衄0 n ec o n 8 i s t 8i nd e v e l o p i n gn e wo rf 豁t 盯 越舶n t h m 8d e a n n gw i t ht h e8 0 l u t i o n 8o ft h e 8 ee q u a t i o n 8 a n o t h e ro n ec o n 8 i 8 t s i nc o n 8 t r u c t i n ge i 舭a t i o 璐8 u c ht h a tt h e f a s ta l g o r i t h m 8c a nb ea p p h e d t 0 - w 缸dt or a t i o n a l8 0 1 u t i o no f1 垃e a rd 诳e r e n c ea n dd l 行e r 唧1 t i a le q u a 上i o n 8 ，l l o u “u e ( 1 8 3 3 ) d i dm o s to fi t a 1 9 0 r i t h mf o rr a t i o n a ls o l u t i o 瑚h 雏b e e n 缸l p r o v e db y a b r 锄a v - b r o n s t e i n p e t k c 醣kla _ 钯r a b r 锄o v9 8 v ea 1 詹o r i t h 脚t o 丘n dt h er a t i o - n ds o i u t i o n 8o fd l 脑e n c ea n d 俨d i 伍e r e n c ee q u a t i o 娜 t h et h e 吕| i 8i s m p o s e d0 fp 甜t b ：b a c k g r o u i l df o rr a t i o n 8 18 0 l u t i o 璐；r a t i o n a l 8 0 l u t i o n 8f o rl i n e 缸d i 珏e r e n t i a le q u 抵n 8 ，r a 舡o n 8 ls o l u t i o n 8f o r8 y s t e m 8o d i f f 娃一 e 】1 t i a le q u a t i o n 8 ， k e ”r d s 1 i n e a rd i 歃t 即t i a le q u a t i o m ，d 证e r c ee q u a t i o 璐，r a t i o n 以雠d p o l y i l o m i a l8 0 1 u t i o 璐，q d i 行e r e n t i a l ，干d i 舶r e n c e ，a l g o r i t h m 8 i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：泛吼霞 砌年歹月勿日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名；学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年。可少于1 0 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：疋f 冠雹 卅年参月勿日 第一黎 l 言 第一耄雪 害 1 1 计冀机代数和哲理聪 静冀撬代数蓬戳黼戎骨篝穰港誓其研究钱敦漪象翡一稳新辩擎辩。弦黑代 数对象照指抽象的数学符号与概忿，如整数有理辩，多项式，嫂怨等计算机 代数秘特捱是符号与代数计算，它露副手遁常韵数谴甘算投数葬注盼设 ，分 辑，赛辑及庭幕搀藏了静葬撬我数霸掰完内寥静冀税代数毽宫逮群静一些蒸率 内窖- 膨精度数表拳。浆数运算多礤式的最大公黼平( 余式序划、模方法) 多 项式的麟式分解( b 船k h m p 算法、娃e b 辩l 拇遣) ，多臻式方程求髁e 窭撮隔离冀 裴，。线健方程缝承辩筹。许多葑葵税霞数骛箕辕基半擒造一壁多壤式嚣毒瑾蠢 程。计苒机代数系统诃蹦用来对函散_ i 篷行自动徽分。也可以用米构撩一大类秋分 阿题和黎鳇微分方程的耱 一敷培塞争孚辩 趣( ) ”绀( z ) = 圳 ( 1 1 ) ；0 这量。舶( # ，屯e # ，6 渤j f 旗( 嚣墨一个常数城，岛l 瓣o ，番望能够 零萁多壤残舞帮骞理解。鹱在，嚣韶骧建趣鹭是这一爨锾势方器爨蒲君翟盔簿采 解方法。这类方程的解的研究可以追溯到到十九世龆。在文章【1 卅中。l i o u 订n o 1 8 3 3 ) 辫微分方程避行丁较深入的零麓研究。在文避扛5 l 中，赫鞭s 吐啪缭 窭了等撬囊蘩囊努方程毒理舞鹭承鹅方凌。在交章臣毒鼙中。寻莛方毽 多项式解i l 及有理解的问题( 以致拭寓一些问题) 潍行了进一步舶讨论文拳 【1 5 2 7 1 辨飧出的方法憝基于待定象数法帮部分分数鼹开法通鬻槐避一个多磺 式髫器送襻翦耀步：蔗整嚣宅懿蠹靛上葬；二楚瘫用费定系絮竣求解。对手辫 第一章引言 造有理函数，人们一般要通过构造方程展开以后的结果的假设来求但是，通过 待定系数法求解所得到的代数方程组往往是很庞大的，而且有时候是非线性的 为了展开已知的有理方程，人们不得不把分母分解为因式，而且通常在常数域上 展开这里一般的形如方程( 1 1 ) 的方程的有理解求解算法可以被归纳如下； 输人， 线性方程c ( ) = 6 ( z ) ；这里c 是个算子，可以被写成 l = 扩+ + 0 1 j + 如 一般考虑四种情况的线性算子- 微分，差分，口微分，酽差分 输出； 其有理解”( z ) ( 其中( z ) 的形式为( z ) = 器) 开始： 1 寻找一个多项式( 或者相当于一个有理函数) ( 厂( 功，这样方程( 1 1 ) 的每个 有理解可以被写成g ( 。) = 稿，这里z ( z ) 是一个多项式 2 在c ( ) = 6 ( z ) 中，用器代替9 ( 互) ，然后进行整理 3 用求解多项式解的算法计算所有多项式解z ( z ) 计算完多项式解以后，就得 到要求的有理解器 显然，对于求有理解，算法的第一步是关键 我们假设方程c ( ) = 6 ( z ) 是非齐次的，也就是6 ( ) 是一个多项式 介绍完有理解求解的基本步骤，接下来给出一些基本的定义 2 第一章引言 1 2 有理解相关的基本定义 用k 表示关于微分算子丢的有理方程域且9 是k 的一个未知量用 ( ) 代表f 的 次求导，用k 嘲表示域k 上的微分多项式环，它是由域k 中 的元为系数的口( ) 的多项式构成 这里特征为零的域上所求到的方程的根可以表示为n 1 的形式，这里n z 。且1 是域k 的单位元求解的系数域，一般被称为恰当域我们求解的例子 当中的恰当域包含有理数域q ，有理复数域q ( 、( 一1 ) ) 以及有理方程t 1 ，如 的域在文章中，用k 表示这样的恰当域如果p ( 。) k m 且满足不等式 p 0 ) o ，则多项式p ( 。) 不等于环女旧中的幺元，也就是说多项式p ( 功至少有 个系数存在 我们定义算子q g ( z ) = ( q z ) ，这里g 是个未定参数我们的系数域耳是 一个g 一恰当域，它的定义如下： q ( 口) k ； 对于耳上的代数方程c ( g ) = 6 ( z ) ，我们的算法是寻找矿形式的根，这里 m 是卟非负的整数 显然，域q ( 口) 是个铲恰当域，且俨恰当域的简单扩张( 代数扩张或超越 扩张) 也是口- 恰当域 我们用岛表示于微分算子，令如( z ) = 勰( z ) = 鼍亭铲= 芒表! ，( 。) ，且 对于n = 2 ，3 ，时。令四= 毋( z ) = 蒜毋- 1 ( 功这样对于c ( 可) = 6 ( ) 的 g 一微分方程。使c ( 口) = ( z ) 嚣+ + 0 1 ( ) 如+ 0 0 ( z ) ，这里0 0 0 ) ，( z ) ，6 ( ) k m ，0 ( z ) 0 ，口是个未知参数，k 是一个特征为零的域 用d e g 可( z ) 表示多项式( z ) 关于的最高次幂，蚴( z ) 表示首项系数 3 第二章线性微分方程有理解 第二章线性微分方程有理解 2 1 微分方程多项式解 关于线性微分方程( 五d e s ) 的多项式解，是求解线性微分方程有理解的算 法中的关键步骤目前已知的关于线性微分方程有理解的算法 1 ，2 ，2 8 ，1 3 】是通 过计算亚纯解的极部分的一个公分母，然后计算线性微分方程的多项式解作为分 子在求解过程中，非零有理解存在性问题就转化为非零多项式解存在问题尽 管求解微分方程多项式解从概念上比较简单，但是许多微分以及差分代数的问题 都包含计算多项式解，而且这一计算过程也被同样的考虑到求解有理解的总计算 时间内因此，寻求多项式解的有效算法，对于提高求解有理解的算法也是有益 的 由于以上的原因，首先给出计算的步骤中包含的多项式解的求解算法这一 算法是当已知有理解的公分母情况下，计算分子的方法如果已知一个n 一阶微 分方程，它可以表示成方程( 1 1 ) 的形式，同时满足n 0 ( 茁) ， ( z ) ，6 ( 茹) k m 需要知道方程( 1 1 ) 是否具有多项式解 ( 功= 挑z + + l z + 珈( 2 1 ) 通常，需要求出它的所有的多项式解的集合对于多项式系数方程的多项式 解度的上界不能用简单的常系数方程解的估计方法求解，所以，我们从估计其度 的上阶开始显然，对任意的自然数s 口，有。( 。) = 胩一1 ) 似一。+ 1 ) z ( 一w ， 这样就求得d e g ( ( 。) 旷( z ) ) = d e g 扛) + d e g ( z ) 一口用已经定义的微分算子 4 第二章线性微分方程有理解 c 作用口( z ) ， c = ( 功酽，a 0 ( z ) o ( 2 2 ) = 0 同时令 m 2 蹿( d e 9 ( 功一 ) ( 2 3 ) 显然，m o 假设当口= 1 ， 2 ，咖s 1 sn 时，满足 d e 9 ( z ) 一口= m 如果d e 9 ( 茁) = m ，通过算子( 幺2 ) 作用y ( $ ) 可以得到 一个度不超过+ m 的多项式，它的z ”项的系数等于 弧z c ( a 。) 一1 ) 一仇+ 1 ) ， 仁1 这里f c ( ) 是所讨论的多项式的首相系数这样，当算子( 2 2 ) 作用后，就能计 算得到个非负整数m 并且构造一个多项式 o _ ) = z c ( ) r ( r 一1 ) ( r 一地+ 1 ) ( 2 4 ) t = l ( r 是一个新的变量，如果d e 9 9 ( ) = 竹，方程( 1 1 ) 的右边也就是6 ( z ) 的度 不超过+ m ，它的十”项的系数等于n ( ) 玑) 下面来估计的上界对于给出的线性微分方程( 1 1 ) ，有下列两种可能，+ m = 衄6 ( $ ) 或者+ m d e 9 6 ( z ) 这就说明了不超过 m 8 ) c ( 咖a ( r ) ，d 叼6 ( z ) 一m ，z ) ( 2 5 ) ( z 是方程a ( r ) = 0 的最大整数根) 估计完v ( z ) 的度的上界之后，就寻找度的多项式解的集合可以 利用待定系数法求解，适用于g r 明；法则求解但是利用这种方法有些时候并不 方便，因为分量z 的引入，使得到的界往往也是很大的数字对于方程组矩 阵更需要多步操作和庞大的存储空间除了待定系数法，我们采纳一个改进的递 5 第二章线性微分方程有理解 归算法求解这个改进算法是逐个求其系数，这样可能比用原始算法更加方便一 些 如果可0 ) 被看作个度不超过的多项式求得，当2 如9 a ( r ) 。z 的系 数满足这样的恒等式 a ( ) 柳= h + ，i( 2 6 ) 当 d 卵。( r ) 时，可以得到类似的等式现在，引入一个非负的数列m o ，”h 以及多项式序列a 0 ( r ) ，k ( r ) ，这里对算子鬣仁沙定义帆和画( r ) 与 对算子( 2 2 ) 定义的m 和a ( r ) 完全相同显然，竹= m ，五0 ( r ) = a ( r ) 现在当 咖a ( r ) ，就是当 n ，仍然有下面的等式成立 a ，l 一( ) 柳= 6 + 一。 ( 2 7 ) 如果柳已知，可以从方程( 1 1 ) 开始继续求解( 。) 的其它系数令 可( 卫) ；( 。) 一3 f z 在方程( 1 1 ) 的左边用圹( ) 代替( z ) ，方程的右边则变为 n 6 ( 功一射( 功z 口= o 继续这样的计算，就可以求得( 善) 的其它系数但是这样的计算过程。当a 。( ) = o 时就存在困难，因为此时无法利用( 2 7 ) 来计算鲫，就必须对逐个求系数的算 法进行一下改动首先假设6 ( z ) 的某些项的系数是关于某些参数的线性多项式， 这样鲫可以被看作新的参数引入而且，假设非负整数已知，开始对6 ( z ) 参数化这样又得到了如同( 1 1 ) 的独立方程，进而可以进行后续求解求出方 程( 1 1 ) 度数小于或者等于的多项式的集合这里参数等于零是一个特殊的 情况以后，还可以把它进一步推广到多参数的更一般的情况 1 4 】给出计算不同算子多项式解的几种算法去年，a l i nb o b t 姐和b r l l n os 小y 【7 】又给出了一个快速的求解微分方程多项式解的算法 6 第二章线性微分方程有理解 介绍完了求多项式解的一个改进算法，下面要开始介绍有理解的核心内容。 公分母的求解 2 2 微分方程有理解 在介绍有理解算法之前先介绍一些符号和基本的定义 如果给出微分方程c 0 ) = 6 0 ) ，其满足0 ) o ，把( 。) 转化为不含 平方项的因子乘积畦( ) 就是说如果“争( z ) 毋( z ) 是( 动的因式展开形式， 则u l 扛) ，啦( z ) 就是( $ ) 的因子展开形式 令u ( 。) 是畦( 。) 在环嘲上的个不可约因子，假设在其它的扩域露【卅 ( 这样的扩域对于实质的计算是无用，引入是为了从理论上证明算法的正确性) 上，可以把“( $ ) 分解为线性园子z 一以，z 一如，有了这样的d ，就可以把方 程( 1 1 ) 的系数( z ) 写成 o ) = 扛一。k 扛) ，口= o ，l ，n( 2 8 ) 这里 。( 。) k h ，而且k ( 功不能被z d 整除如果个多项式“( z ) 它的线 性因子中的每一个五，它在同个0 t | ( $ ) 中都具有相同的锄，这就相当于得到了 ( z ) = u ( $ ) “k ( 。) ， = o ，1 ，n ，满足k ( ? ) 吲，且k ( z ) 不能被u ( z ) 整 除，把这样的多项式“( 功称为方程( 11 ) 一个平衡多项式，多元组( o ，锄) 则被称为u ( z ) 的多幂集如果把0 ) 表示成这样的平衡多项式的乘积，就有 ( z ) = c l ( 功g i | ( z ) ，m 21 ( 2 9 ) 已知有理解f ( z ) 的分母u ( ) 的每一个根正6 膏也是多项式( z ) 的根；而 且因子z j 在分母中的幂指数等于定义方程【14 的最小负整数根的绝对值定 义方程可以通过下面的步骤获得把( 1 1 ) 的系数锄0 ) ，口n ( 。) 表示成( 28 ) 形式。而且它同时满足条件k ( z ) m ，而且k ( 。) 不能被。一6 整除令多 7 第二章线性微分方程有理解 项式d ( r ) 是 r ( r 一1 ) ( r 一口+ 1 ) 。( 6 ) ( z 一6 ) “一” ( 2 1 0 ) 中z 次数最低项的系数，而且要求的界是d ( r ) 为零的最小负整数根的绝对值如 果已经求解得到了方程( 1 1 ) 的平衡多项式和每个平衡多项式的多幂集，而且 ( z ) = c - ( z ) c l ( 功，是平衡多项式的乘积令c ( z ) 是这些平衡多项式中的一 个多项式，它的多幂集为多元组( o “，a 。) 考虑这些差分一口， = 1 ，n ， 选择使得一 最小的那些口的值，令这样的口为仇，0 ”l 扩z 如果个有理方程口= ：。t ，口圈且u ，口0 。令 d r d o o ( 8 ) = 一扩o = 一矿+ 扩”，且用( n ) 来标记霉”k ( 的系数， 口= f ( a ) 茁一耐( + t e r m 80 f0 r d e r d r d o o ( n ) 令0 r d 。( o ) = 一扩0 = + o 。 通过检查，每次替换后矩阵组右边的度以及在点的指标方程的整数根， 可以决定( “c ) 是否存在如果存在，就可以计算似，c ) 当这样的个对，c ) 找到以后，从z 所满足的方程找新的( p ，c ) 这过程重复到得到了这样形式的 方程m 彤= f = m ( c l 善m + 十c ；f “) 对于新得到的方程不存在非零的 多项式满足度 d r d 。( o ) 令 d r c k ( 0 ) = 一d 0 0 = + o 。 如果c ，是一个有理函数矩阵( 或者一个向量) ，定义它在无穷点的序( 记 作：d r d 。) 是u 的所有元有序的最小值定义矿u ：= 一口r d 。【厂 令p 为k ( z ) 的一个有限极点，而且p 是k m 中的不可约元 如果，是( z ) 中的非零元，定义d r 如，( ，在p 点序) 为唯一的整数n 使 得t ，一2 矿，o ，6 m o ，p f o 和p f6 我们令o r 由( o ) = + 。o ，对，9 ( ) 有 o r 南( ，+ 9 ) = m e n ( d r 由( ，) ，口r 由( 9 ) ) ，且当o r 岛( ，) o r 由( g ) 时等号成立； 2 l 第三章线性微分方程组的有理解 d r 矗( ，g ) = d r 南( ，) + d r 南( 9 ) 回忆，k ( z ) 具有唯一的p 一口出c 展开， ，；厶矿+ 厶+ l 矿+ 1 + 这里n = 0 r 由( ，) 。五是度小于d e g p 的多项式，且厶o ( 当，o ) 厶被称为是，在点p 的首项系数而且被记为b ( ，) 如果a = h j ) 是个矩阵( 或者向量) 以耳( ) 中的元素为矩阵元，定义 它在p 点的序为口r 由a = m i n ( o r 而( o i j ) ) 而且以耳( z ) 中的元素为矩阵元的矩 阵( 或者向量) 4 具有唯一的p 一础c 表示为t a = p 计面a ( 山，p + 础1 一) ， 这里a 口是矩阵( 或者向量) ，它的元素属于集合 d k id e g a d e g p ) 用z c ) 表示a 在p 点的p 一础f c 展开中a 的系数 如果4 = 等是个矩阵( 或者个向量，用d e ，l 伽( a ) 来表示的最小 公