王老师言语备忘录分享 http://blog.sciencenet.cn/u/dongmingwang

博文

阿狗传道——方程术(下) 精选

已有 3921 次阅读 2018-4-8 10:10 |个人分类:阿狗数学|系统分类:科普集锦| 方程求解, 方程组, 消去理论, 计算机代数

阿狗传道——方程术(上):点击进入

上升下降 左右进退 互通变化 乘除往来 用假象真 以虚问实 错综正负 分成四式 必以寄之 剔之 余筹易位 横冲直撞 精而不杂 自然而然 消而和会 以成开方之式也

——《四元玉鉴》序言

多项式方程求解是代数学的中心问题,也是代数学发展的动力和源泉。千百年来无数数学家都研究过这个问题。著名的Fermat大定理就是一个有关不定方程不存在非零整数解的断言,它曾困扰数学家358年之久。就像一元五次方程的可解性问题一样,这个断言本身也非常简明易懂,但它的证明却让三个世纪以来的数学大师们夜不能寐、魂牵梦萦。

1637年,数学家P. D. Fermat在阅读丢番图的《算术》一书时作出这样一个断言:方程 xn + yn = zn (n > 2) 不存在非零整数解。这个断言被Fermat写在《算术》的页边上。这位幽默的天才还在断言旁附加了一个评注:“我对该命题有一个十分美妙的证明,这里空白太小,写不下”。Fermat是否真的能够证明他的断言,我们已经不得而知,而他留下的这个轻描淡写的猜想,不仅推动了十九世纪代数数论的发展,而且为数学史写下了传奇的一页。为了寻求这个猜想的答案,数学家不断引入新的概念、提出新的理论、发展新的方法,取得了大量研究成果。譬如,E. E. Kummer引进了理想数的概念并创立了Kummer理论,S. Germain定义了Germain素数,L. J. Mordell提出了Mordell猜想等等,他们的工作夯实了现代代数数论的理论基础。从L. Euler,A.-M. Legendre,P. G. L. Dirichlet等数学大家对n取特殊值时的证明,到现代数学家使用计算机对数以万计的n取值进行验证,人们证明Fermat猜想的步伐从未停歇,但这个过程漫长而又艰辛。十几代数学家前赴后继的尝试都没能寻得最终答案,很多人对此沮丧不已却又心存幻想。当下的数学工具是否还能解决这个难题?Fermat猜想的证明也被吉尼斯世界纪录列为“世界上最难的数学问题”。

奇迹在1994年发生了,英国数学家A. Wiles最终给出了Fermat大定理的证明。早在童年时期Wiles就开始追求Fermat猜想的答案。后来,他彻底放弃了对其他问题的研究,将自己关在书房里,皓首穷经、潜心研读,探寻着证明Fermat猜想的思路。经过七年长期不懈的努力,Wiles的付出终于有了回报:1993年,他完成了Fermat猜想的证明并在一个学术会议上宣布他的结果。Wiles的证明震撼了数学界,但在论文的评审过程中,专家却发现了一个极为严重的错误。在几近绝望的补救之后,Wiles于1994年又将他的最终证明公布于世。Wiles的两篇证明论文共有130页,是历史上被核查得最为彻底的数学稿件,最终于次年发表在《数学年刊》上。至此Fermat猜想变成了定理,Wiles也凭此获得了2016年的阿贝尔奖。

图1:丢番图《算术》书页和Andrew Wiles(1953—)

从一元到多元、从低次到高次、从单个方程到方程组,方程求解的理论不断扩充、发展、完善,其应用范围越来越广,它们已经成为众多数学和其它科学分支的理论基础和基本工具。与一元高次方程求解问题一样,多元多项式方程组的求解也是一个经典的数学问题。最常见的多元多项式方程组是形式简单、应用广泛的线性方程组,其求解方法很早就被深入研究。比较完整的方法见诸于我国古代数学名著《九章算术》,称为“方程术”。三国时期数学家刘徽为其作注时给出的解释是:“令少行减多行,反复相减,则头位必先尽”。其实质相当于对方程组的增广矩阵进行初等变换从而消去未知变元的方法,也即19世纪由J. C. F. Gauss所提出的现在广为人知的Gauss消去法。Gauss消去法的思想是将多元线性方程组转化成下三角形式,使得从上到下每个方程中变元的个数依次减少。于是线性方程组的求解问题可以转化为一元线性方程的求解问题。在西方,线性方程组的研究是在17世纪后期由G. W. Leibniz开创的,随后É. Bézout,A.-T. Vandermonde等数学家对线性方程组解的结构及相关理论进行了系统研究。

Gauss消去法完全解决了线性多项式方程组的求解问题,该方法可以推广到高次多项式方程组,其核心思想是将方程组的求解问题转化为一元方程的求解问题。本文开始引用的那段充满哲思的玄论就是对中国元代数学名著《四元玉鉴》中用消去法求解四元方程组的一个概括性描述。《四元玉鉴》中只考虑求解四个未知元是由于受当时计算工具(算筹和算板)的限制,实际上书中给出的解方程的思想和方法完全可以扩展到任意多个变元的情形。西方学者还利用Hermite正规形式和Smith正规形式等将这类方法推广,用于研究一般的线性不定方程以及阿贝尔群。

通过消去多项式系统中的某些变元,将系统化简至易于处理的特殊形式是求解多项式系统的主要思路。基于这种思路建立发展起来的消去理论和方法已经成为许多与解方程有关的数学分支的基础工具。现代数学更是离不开方程求解。有关超越函数方程、差分方程、微分和积分方程的研究已经并将继续作为基础和应用数学的主要分支向前发展。

图2:《四元玉鉴》影像

19世纪末20世纪初,消去理论作为构造性代数几何的基本工具在欧洲发展活跃,出现了形式多样的结式和判别式。最常用的求解高次方程组的消去法就是基于结式计算的。结式的构造源自18世纪法国数学家É. Bézout,其理论后经J. J. Sylvester,A. L. Dixon,F. S. Macaulay等英国数学家发展完善,成为经典的消去方法。这种方法的主要思想是通过构造各种形式的结式矩阵,将多项式方程组的解投影到一元多项式方程的解。B. L. van der Waerden 在其《现代代数学》的早期版本中对结式消去理论和方法有较为详细的论述。此后,消去理论受到冷遇,被视为过时的理论,在《现代代数学》的新版中 “消去理论”一章也被删除。

随着计算技术的发展,或者更确切地说,随着计算机代数这门交叉学科的兴起,消去理论得以重新展示其威力,特别在方程求解中发挥其专长。现代消去理论和方法相继提出并得到空前发展。基于特征列、Gröbner基和柱形代数分解的消去方法已成为计算机代数领域的三大核心方法。

特征列方法是我国数学家吴文俊在上世纪70—80年代提出的、适用于多项式系统和微分多项式系统的消元与分解方法,其理论基础是美国数学家J. F. Ritt有关微分代数的工作和古代方程术中的算法思想。以吴-Ritt命名的特征列方法可以看作是高斯消去法对非线性情形的推广,所使用的主要运算是高次多项式之间的伪除。该方法后经王东明、高小山等学者发展完善,已作为机械化数学特别是代数计算和几何推理的基本方法写入《计算机代数》和《多项式代数》等研究生教材。

1965年,奥地利数学家B. Buchberger在他的博士论文中提出了以他导师的姓命名的Gröbner基方法。该方法可以在多项式组构成的理想中找到一组基,而这组基中的某些多项式构成三角列,因此可以通过计算Gröbner基将多项式方程组的求解问题转化为一元多项式方程的求解问题。在20余部著作和数千篇论文中得到深入研究和发展,Buchberger的Gröbner基方法理论优美、应用高效,是研究多项式理想的基本工具,也是支撑计算机代数系统的基石。

初等代数与几何的判定问题最早由A. Tarski解决。该问题可以归结为实闭域上的量词消去问题。美国数学家G. E. Collins提出的柱形代数分解方法可以用来完整地解决这一问题,并能为含有多项式等式和不等式的半代数系统的求解和实解分类提供有效工具。柱形代数分解方法的基本思想是通过投影和提升将实空间中的任意半代数集分解为有限多个由同一组多项式定义的、互不相交的半代数集,而在每个半代数集上定义多项式的符号保持不变,再通过选取半代数集上的样本点确定定义多项式在样本点的符号。量词消去、半代数系统求解和实解分类等问题都可以通过柱形代数分解获得解决。

图3:吴文俊(1919—2017,左)和George E. Collins(1928—2017,右)

图4:Bruno Buchberger(1942—)

现代消去理论和方法不仅是方程求解的计算工具,也是构造性交换代数与代数几何的算法基础。它们在机器人、计算机辅助设计、密码攻击、机器证明、知识发现等诸多科学技术领域有广泛应用。从3600年前古埃及纸草文献中的数学到上世纪末刚被解决的Fermat大定理,在不同的时代,方程术都被赋予不同的内涵,但人们对方程求解的痴迷却始终如一,方程的艺术魅力无限,不曾因时光流逝而悄然失色。

横看成岭侧成峰,远近高低各不同;

欲解方程真面目,求源算术九章中。

阿狗与方程相依为伴,为方程术美颜添色,紧随方程求解者奋力前行、攀越奇峰峻岭,领略山中之无限风光!

(本文经王东明教授审阅,文中部分内容参考了M. Kline的《Mathematical Thought From Ancient to Modern Times》,冯承天的《从一元一次方程到伽罗瓦定理》和S. Singh的《Fermat’s Last Theorem》等著作;图片均来自网络)

(徐娟)

来源:阿狗数学AlgoMath



http://blog.sciencenet.cn/blog-1362128-1107972.html

上一篇:阿狗下注——数字游戏的艺术
下一篇:Gröbner基——Buchberger的发现,却以他导师的姓命名

8 彭鹏程 黄博 严家新 赵克勤 刘忠波 黄永义 康建 许卓颐

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-7-19 00:19

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部