同伦方法

出处：按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第113页（3700字）

设f：C→Cⁿ是n维复空间的连续自映射，则求解n×n方程组f(x)=0，就是求映射f的零点。

为此，引入便于把握的零点清楚的辅助映射g：Cⁿ→Cⁿ，形成连接f和g的同伦映射：H：［0，1］×Cⁿ→Cⁿ，即要求H连续，并且对所有x∈Cⁿ都成立H(1，x)=g(x)和H(0，x)=f(x)，那么，从H(1，x)=g(x)的已知零点出发，沿着同伦H的零点集

H^－1(0)=｛(t，x)∈［0，1］×Cⁿ：H(t，x)=0｝

若同伦参数t从1变到0，就得到目标映射H(0，x)=f(x)的零点，即得到原问题的解。这就是同伦方法(homotopy methods)的基本思想。

由于维尔斯特拉斯(Weierstrass)逼近定理，在下面的叙述中，我们都不妨假定所论的映射都是可微二次以上的光滑映射。

同伦方法对于非线性计算和值分布讨论都是有力的工具。和20世纪70年代以前的延拓法(continuation methods)相比，现代同伦方法的主要标志是运用参数的萨德定理(Parametrized Sard’s Theorem)，它使我们可以在同维空间的一个满测度子集中选择同伦的设计参数，有足够的自由度保证所采用的同伦以原点为正则值，于是同伦的零点集H^－1(0)是［0，1］×Cⁿ中的实一维光滑流形，即光滑简单道路。如果辅助映射和目标映射匹配得好，有界性条件就成立，即同伦的零点集中的光滑简单曲线都不会跑到无穷远的地方。

如果所用的同伦对每个固定的同伦参数t都是解析的映射，那么利用哥西－黎曼条件(Cauchy-Riemann condition)可以证明，这些光滑简单曲线对同伦参数t具有严格的单调性。在上述条件之下，从辅助映射g的平凡零点出发的光滑简单道路，引导到达目标映射f的零点，从而按重数计算，f和g的零点数目相同。

基于这种思想，高堂安将单复变函数的罗歇定理(Rouche Theorem)很容易地推广到多复变的情形，做了通常需要借助度理论(Degreé theory)的工作，同时大大放宽了定理的边界条件。这一推广，是演示现代同伦方法要义的范例。

就非线性数值计算来说，因为是循从辅助映射g的平凡零点出发导向目标映射f的零点的光滑曲线走，所以也说这是一种路径跟踪(path-following)方法。通常，人们把这作为微分方程初值问题处理，采用数值分析中已经相当成熟的算法来实现。

例如，所谓预估－校正法(predictor-corrector method)就是这样一种算法：沿切线走一步预估，再用比如说牛顿法校正，一步一步走下去。于是，自然就要处理步长选择和步长调节的问题。

同伦方法的先驱工作，是凯洛克(R．B．Kellogg)、李天岩和约克(J．Yorke)的论文《布劳维尔不动点定理的一个构造性证明及计算结果》和斯梅尔(S．Smale)的论文《价格调节的一种收敛过程和整体牛顿方法》，它们都以数理经济学一般经济均衡理论为背景，因为有限纯交换经济的价格调节机制都可以表示为凸包腔的连续自映射，而均衡价格就是相应自映射的布劳维尔(Brouwer)不动点。虽然不动点的存在早已解决，但是不动点的计算方法直到60年代末才发展起来。随后，在周修义(S．N．Chow)、马勒－帕雷(J．Mallet-Paret)和约克1978年的论文《寻找映射的零点：概率－构造性的同伦方法》和1979年的论文《计算多项式方程组全部零点的一种同伦方法》中，现代同伦方法的基本架构已经形成。

前已述及，现代同伦方法如果在同维空间的一个满测度子集中选择同伦的设计参数，即可保证所采用的同伦以原点为正则值，从而从辅助映射g的平凡零点出发的光滑简单道路，引导到达目标映射f的零点，方法即可成功。

由此可见，对于设计参数的几乎所有可能的选取，同伦方法都能成功。根据几何概率，人们就说：对于设计参数的每一随机选取，同伦方法成功的概率为1。

实际使用中，同伦方法成功的概率接近1。

除了计算均衡价格和不动点以外，现代同伦方法最早在计算多项式方程组全部零点的问题上取得令人注目的结果。这一工作的理论背景是代数几何的代数流形讨论。设

f=(f₁，…，f_n)：Cⁿ→Cⁿ

是一个多项式映射，每个分量f_j由有限个形如ax₁^q1…x_n^qn的项组成，其中a为非零复常数，q₁，…，q_n为非负整数，x₁，…，x_n为n个复变量。

称q₁+…+q_n为项ax₁^q1…x_n^qn的次数，记f_j中所有项的次数的最大者为d_j，称为f_j的次数。最后，称(d₁，…，d_n)为多项式映射f的次数。经典的贝索特(Bezout)定理断定，映射f的孤立零点的数目不超过d₁…d_n，后者称为多项式映射f的贝索特数。如果多项式映射f的孤立零点的数目正好等于它的贝索特数，就称该多项式映射满零点。

已经证明，如果f的齐次多项式映射只有0这个“平凡零点”，那么f就满零点，即按重数计算，f的孤立零点的数目达到它的贝索特数。

值得注意的是，实际应用中提出的多项式映射的孤立零点的数目常常比它的贝索特数少，我们称这类多项式映射为亏欠(deficient)多项式映射。

因为辅助多项式映射通常总是满零点的，如果仍依原来的方式从辅助多项式映射的全部零点出发进行构造和计算，势必有许多计算发散到无穷，造成很大的浪费。为了有效地估计亏欠多项式映射的孤立零点的数目并且经济地算出它的全部孤立零点，李天岩等人提出随机乘积同伦(random product homotopy)的概念，针对存在无穷远零点这个造成亏欠的原因，按照映射的具体结构来构造同伦，从而根本不跟踪无界的曲线。

同伦方法的另一个热点是特征值问题的讨论。特征值问题是亏欠多项式映射的典型例子。为了求解顶多只有n个解的特征值问题，原来的同伦方法需要跟踪2ⁿ条曲线，其中只有占很小比例的n个路径跟踪过程是收敛的，其余2ⁿ－n个计算都浪费了。不仅如此，在这2ⁿ个路径跟踪之中，判断哪n个将收敛，尤其是棘手的问题。

引入随机乘积同伦以后，只需跟踪n条路径，并且它们都将收敛到所论的特征值问题的解。就完全解决相应问题所必需跟踪的曲线的数目来说，这已是最好可能的结果。

还要指出的是，只要有足够的处理器，就可以互不干扰地跟踪从辅助映射的各个平凡零点出发的光滑曲线。所以，同伦方法本身具有并行实现的结构。

此外，从以上介绍可知，它还具有经常大范围收敛的特点和整批求解的特点。

。

【参考文献】：

1 Kellogg R B, et al. SIAM J Numer Anal, 197.6,4:473 ～ 483

2 Smale S A. Math Economics, 1976,3:1 ～14

3 ChowSN.etal. Math Comp, 1978,32:887～899

4 Chow S N et al. Springer Lecture Notes in Math, 1979, 730:77～78

5 Li T Y, Sauer T. Lin Alg Appl, 1987,91:65～74

6 Li T Y, Sauer T, Yorke J Numer Math, 1987,51:481～ 500

7 李天岩．数学进展，1988，17：260～266

8 王则柯．自然杂志，1989，12：664～667

9 王则柯，高堂安．同伦方法引论．重庆：重庆出版社，1990

10 Li T Y，Wang X．Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant．Math．Comp，1991，56：693～710

(中山大学王则柯教授撰)