※ [本文转录自 Keelungman 信箱] 作者: [email protected] ("[email protected]") 标题: 关於李天岩(二) 时间: Mon Oct 18 05:03:07 2004 作者: DarthRaider (...........) 看板: BBMak 标题: 关於李天岩(二) 时间: Sun Oct 17 00:40:11 2004 （三）现代同伦算法 学过代数拓朴或非线性泛函分析的人都知道有名的布劳尔不动点定理：n 维闭球 Dｎ到此 自身的光滑映射 g：Dｎ → Dｎ 必有不动点。此定理的一个漂亮证明是用反证法。若 g 无不动点，则对闭球 Dｎ上任一点 x，令 f(x) 为由 g(x) 到 x 的线段延长到与球面之 交点。易知当 x 在球面上时，f(x) = x。这样我们得到一个由闭球到其边界 Sｎ 上且在 Sｎ 上为恒同映射的光滑映射。而拓朴学告诉我们，这是不可能的。 1973年，当李天岩在旁听美国马里兰大学数学系凯洛格教授的研究生课程“非线性方程组 数值解”时听到布劳尔不动点定理的属於美国拓朴学家赫希 (Morris W. Hirsh) 的发表 於1963年的如上证明时，一个奇妙的想法在他脑海中涌现：既然在赫希的证明中若假设 g 无不动点时，则对如上定义的 f ，f ({y}) 这条光滑曲线无处可跑，则 f ({y}) 必然 跑到 g 的不动点集合中去。更精确地说，若令 F 为光滑映射 g : D ----> D 的所有不 动点组成的非空集合，则利用如上反证法的思想，我们可定义n 维流形 D \ F 到 n - 1 维球面 S 中的一个光滑映射 f : D \ F -----> S 。由微分拓朴的沙德 (A. Sard) 定理 可知，对几乎所有的球面上的点 y ， y 是 f 的正则值，因而 y 在 f 下的逆象 f ({y} ) 为起始於 y 的一维流形，即一条光滑曲线。这条曲线的另一端不能再回到球面上，也 不能在 D \ F 中停止，故必定趋向於 g 的不动点集。如果能数值逼近这条曲线，就能计 算出 g 的一个不动点。在凯洛格和约克两位教授的鼓励下，李天岩开始了这一卓越思想 的数值实现。 在接下来的三个月时间内，他几乎每天都与学校计算中心那台只能卡片输入的电脑打交道 ，但总是无功而返，电脑吐出的厚厚一迭纸预示着程序的失败。但李天岩契而不舍，坚持 不懈地修改程序。改错、输入、再改错、再输入，从一个实际计算的门外汉逐步登堂入室 。直到有一天，他惊喜地发现电脑仅仅输出一张打印纸，上面正是成功计算出的布劳尔不 动点！他成功了！一个全新的布劳尔不动点算法诞生了。这同时也给出了现代同伦算法的 肇始。 古典的同伦算法早在上世纪五十年代就有研究，尤其是前苏联数学家戴维登科 (D. Davi- denko) 引入相应的常微分方程初始值问题来数值求解同伦方程。如果我们要计算一个非 线性映射 f : Rn → Rn 的零点，我们可将一个零点 x０ 已知的平凡映射 f０：Rn → Rn（譬如说 f (x) = x - x ) 与 f 同伦，即定义同伦映射 H(x, t) = (1 - t) f (x) + t f(x)，其中参数 0 < t < 1。传统的同伦算法的思想是假设 H 的零点集 H (0) 可表 示成曲线 (x(t), t) R x [0, 1]， 0 < t < 1，此曲线连接 x０ 与 f 的一个零点 x 。 若对恒等式 H(x(t), t) ≡ 0 求关於 t 的导数，我们就得到可以数值求解的戴维登科常 微分方程初值问题：x' (t) = - H (x, t) H (x, t), x(0) = x 。由 t = 0 起数值积分 到 t = 1 时，就可得到 f 的一个零点 x。然而，这一方法的致命弱点在於，在一般情况 下同伦曲线不一定总能定义 x 为 t 的单值函数。凯洛格－李－约克同伦方法的革命性思 想是：只要能保证 0 是映射 H(x, t) 的正则值，则由於沙德定理及隐函数定理，光滑同 伦曲线必定存在。坐标变量 x 与参变量 t 应具有同等的地位，它们均可视为曲线长度 s 的函数。这样，无论曲线关於ｔ是否“转弯”，运用“预测－校正”(predictor - corrector)的数值手段，我们均能追踪此同伦曲线而得到解。这是现代理论数学，尤其是 微分拓朴，在计算数学领域中的重要应用。 有趣的是，凯洛格－李－约克关於布劳尔不动点的计算，并非是历史上的首次尝试。尽管 他们当时不知道，早在1967年，美国耶鲁大学 (Yale University) 经济学教授斯卡夫 (H. Scarf) 在研究数量经济学时将求解一个经济模型的均衡点问题归结为求解定义在 n 维标准单纯形上的一个连续映射 f 的不动点问题。根据布劳尔不动点定理，这样的不动 点存在。斯卡夫采用了所谓的单纯三角剖分方法，运用组合数学中的斯泊讷 (E. Sperner) 引理，跟随一条折线来近似 f 的不动点，从而设计了一种单纯剖分不动点算法。在七十 年代，此算法被推广成求解非线性方程组的单纯不动点算法，成了热极一时的研究领域。 1974年，当在美国克莱姆森大学 (Clemson University) 举行的第一届国际不动点算法大 会组委会获悉凯洛格-李-约克的新方法时，立即提供了两张飞机票让他们赴会报告这一激 动人心的结果。正如斯卡夫在其会议论文集《不动点算法及其应用》序文中所述：“对 我们众多与会者而言，克莱姆森会议之令人惊奇之处在於凯洛格 - 李 - 约克关於计算连 续映射不动点的文章。他们提出了第一个基於微分拓朴思想 --- 而不是我们习以为常的 组合技巧 --- 的计算方法”。虽然单纯不动点算法的研究目前已趋沉寂，以凯洛格 - 李 - 约克方法为初始点的现代同伦延拓法研究依然方兴未艾，在不同的领域生根发芽。如 今，李天岩与凯洛格 和约克一道是目前世界上被公认为非线性问题同伦法数值计算的创 始人，并且对此重要的领域作出了巨大的贡献。 （四）多项式系统数值解 自七十年代提出计算布劳尔不动点的同伦方法後至今，李天岩一直在求解多项式系统同伦 算法这一领域辛勤地开拓着。解多项式方程组的根是相当有趣而且经常出现在应用科学上 的问题。譬如说电路分配问题，机械手问题等等。同时这种问题也出现在混沌理论的研究 中，如洛伦茨研究的具有混沌现象的四维常微分方程组的定常状态事实上是其右端多项式 方程组的解。 对具有 n 个变数的 n 个多项式方程组，设其第 i 个多项式的阶为d , 则代数几何中古 典的比左(Bezout)定理给出此方程组所有孤立解总数的一个上界d d ... d , 称之为对应 於该方程组的比左数。 但在绝大多数情况下， 此上界远大於实际孤立解的个数。 其典 型例子为代数特徵值问题。 对应於 n x n 矩阵 A 的特徵值问题的二次多项式系统之比 左数为 2 ， 但 A 最多仅有 n 个特徵值。 最近这些年来，用同伦算法来解多项式方程组“所有”孤立解的研究引起了很大的注意。 1979年，迦协-赞格维尔(C. B. Garcia -- W. I. Zangwill) 对解 n 元 n 个多项式方程 组P(x) = (p (x), p (x), ..., p (x)) = 0 首先建立同伦 H : C x [0, 1] ----> C ， H(x, t) = (1 - t) Q(x) + t P(x)。 这里 Q = (q , q , ..., q )的分量 q : C ---> C 是 q (x , x , ..., x ) = x - 1, 其中 d 是 p 的阶数。他们证明了: 若 H 是正 则的， 则 P(x) = 0 的每一个孤立解都是同伦方程 H(x, t) = 0 的一个相应的解曲线 x(t) 当t = 1时的终点。重要的是，曲线 x(t) 绝不转弯回头。这样求解常微分方程初始 问题 x'(t) = - H (x(t), t) H (x(t), t), x(o) = x ，其中 x 是 Q(x) = 0 的解，我 们就可以在数值上逼近 x(t), 因此可找出 P(x) = 0 的所有孤立解的逼近值。由比左定 理知，P(x) = 0 最多有 d = d d ... d 个孤立解，而 Q(x) = 0 却有 d' = (d +1) (d + 1) ... (d + 1) 个解。因此，为了保证找到P(x) = 0 的所有孤立解，我们必须去 逼近d' 条曲线x(t)。这样在 t ----> 1 时，许多曲线都跑到无穷远去了。跟随这些曲线 是个很大的浪费。 同伦算法计算多项式方程组所有孤立解的一大优点是它可并行化，因可在并行机器上同时 求解对应於不同初始条件的同一常微分方程。为了克服上述 迦协 - 赞格维尔同伦法的缺 陷，周修义(S. N. Chow)、莫莱特-派瑞特(J. Mallet-Paret) 以及约克介绍了一个同伦 H(x, t) = (1 - t) Q(x) + t P(x) + t (1 - t) R(x), 其中 q = x - b 及 r = a x , j = 1,..., n。他们证明，除了测度为零的集合外，对几乎所有的 (a, b) C x C , 追 随同伦方程 H(x, t) = 0 的所有 d 条解曲线，就可将 P(x) = 0 的所有孤立解找出来。 八十年代初，李天岩大大改进了同伦映射的构造。他证明，对於初始多项式方程组 q (x) = a x - b = 0, j = 1, 2, ... , n, 对几乎所有的 (a，b) C x C , 追随同伦映射 H( x, t ) = (1 - t) Q(x) + t P(x) = 0 的 d 条解曲线一样可以找到 P(x) = 0 的 所有孤立解。 从八十年代开始，李天岩继续探索求解孤立解总数大大小於其比左数的多项式方程组。 这样的方程组被称之为亏损 (Deficient) 方程组。若用同伦法求解这种多项式方程组， 从 t = 0 开始我们必须追随 d 条曲线，在 t ---> 1 时，大多数的曲线都跑到无穷远去 了，只能少数的曲线收敛，因此造成极大的浪费。 对於数值代数中最重要也是最常见的亏损多项式系统------ 矩阵特徵值问题，李天岩与 他的合作者们及学生们提出了用同伦思想求解大型 矩阵所有特徵值：将一个特徵值为已 知或易於求得的同阶矩阵 D 与所求矩阵 A 同伦，即定义同伦 H(t) = (1 - t) D + t A ，然後从 t = 0 出发数值追随 H(t) 的特徵值和特徵向量曲线，而当 t =1 时得到A 的 特徵值与特徵向量。他和其韩国博士生李弘九 (Noah Rhee) 第一个将这一思想在电脑上 实现。此後他指导他的中国学生张红、李奎元、曾钟钢、黄良椒、丛栾、金鸣等进一步完 善这一算法思想与数值实现。他们成功地发展了用於实对称矩阵、一般实矩阵、以及大型 稀疏矩阵特徵值计算的同伦算法。即使未考虑其可并行化的优势，仅用单个处理器，对许 多大规模代数特徵值问题，同伦算法优於基於 QR 分解的标准程序。 对於一般的亏损多项式方程组，构造一个好的同伦算法依赖於初始多项式系统的有效选取 。这是因为不光多项式方程组 P(x) = 0 的每一个孤立解均来自於初始多项式方程组 Q(x) = 0 的某个解出发的同伦曲线，更重要的是我们希望尽可能少的同伦曲线当 t ---> 1 时趋於无穷。最理想的构造是 Q(x) 与 P(x) 有同样数目的在无穷远处的零点。近二十 年来，李天岩与索耶尔 (T. Sauer)、约克以及他的学生王筱沈、李星、高堂安等人运用 代数几何的理论和方法，先後发明出选取 Q(x) 的一些行之有效的方法，如随机乘积同伦 法和 Cheater 同伦法。近十年来，由於伯恩希坦 (D. N. Bernshtein) 定理的应用，基 於解个数组合计数的多面体同伦法倍受青睐。在其中，所谓的“混合体积”(mixed volume ) 之计算至关重要。李天岩与他过去及现在的学生们已取得一系列令人瞩目的新成果，其 详情可见他近期应邀所撰写的长篇综述性论文 [ ]。 在多项式方程组数值解领域，李天 岩无愧於其领军人之一之称号。 --

※ 发信站: 批踢踢兔(ptt2.cc) ◆ From: 218.167.228.139 -- 爱因斯坦的广义相对论 不过是另一个精致的手编藤篮罢了. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.102.37