数值方法计算复杂性理论

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

复杂性的科学研究，大体分为两个方面：计算机科学的复杂性理论和数值计算的复杂性理论。

两者既有密切的联系，又有明确的界限。

一种数值计算方法，通常是对于一类问题提出来的。

本来，研究计算方法，就一定要考虑计算成本或算法效率的问题。

在这个意义上，数值方法的效率讨论源远流长。

然而，直到20世纪70年代，仍局限于计算速度和收敛阶的讨论，即在通常关于初始值的一定条件下，计算有几阶敛速。这是一种局部的和渐近的讨论。进入80年代以来，人们开始从整体上，而不是在局部探讨某种算法的总成本或者平均成本，回答在随机地选取一个初始值的条件下，解决某种类型的数值计算问题的平均成本是多少这样的问题。

随着社会经济和科学技术的发展，人们所面对的科学计算问题规模越来越大。

同一种算法，解小规模的问题须花费时间少，解大规模问题花费时间多。值得研究的是，随着问题规模的增大，使用这种算法解决问题所需要的计算时间如何增加。设想把问题的规模记作n，关于用某种算法求解问题所需的时间的理论估计记作T(n)。我们试从两个角度比较T(n)=n⁵和T(n)=2ⁿ这样两种算法。

首先假定机器的速度不变，比方说都是1μs(1×10^－6s)进行一次运算，那么当问题规模n增大时，为了解决问题所需要的时间增加的情况如下：

换一个角度，如果在现有的计算机上，两种算法在1h内所能解决的问题的规模都是n=1000，那么当机器的运算速度提高时，1h内所能解决的问题的规模增大的情况如下：

T(n)=n⁵是多项式关系的代表，T(n)=2ⁿ是指数式关系的代表。由此可见，如果某种算法所面对的问题的规模和解决问题所需要的时间之间是多项式关系，那么尽管用现有的机器不能求解规模太大的问题，但是随着机器速度的提高，将来这种算法将足以对付那样规模的问题。相反，如果是指数式关系，那么就这种算法而言，机器速度的提高，很可能将赶不上人们所面临的问题的规模的增长，从而我们不得不寻求新的算法。基于这样的认识，如果T(n)与n的关系是多项式型的关系，算法将被认为是可接受的，并且称为是多项式时间算法(polynomial-time algorithms)；否则，如果T(n)与n的关系是指数型的关系，算法将被认为是不可接受的，那是所谓指数时间算法。

这里要注意的是：①T(n)不必是绝对的机器时间，也不必是基本机器动作的数目。为讨论的方便，使用更多的是执行所论算法的基础步骤的数目，例如方程或方程组求解的牛顿方法的牛顿迭代次数，线性规划问题单纯形法的转轴运算次数，等等。②某些原来不看作指数函数关系，但是肯定不是多项式的情形，例如T(n)=cn^logn，c常数，也看作是指数式的关系。所以，计算复杂性理论所说的指数时间算法，可以理解为多项式时间算法以外的算法。

数值方法计算复杂性理论的基本内容，就是判别和论证现有的各种算法是不是多项式时间算法，帮助寻找和设计新的多项式时间算法。

从最坏情形分析，发展到平均情形分析或概率情形分析，是80年代以来数值方法计算复杂性讨论的新的特征。

我们以代数方程牛顿方法(Newton method)为例，说明这一进展的意义。设f(x)是一个多项式，那么f(x)=0就是一个代数方程。

求解代数方程的牛顿方法，可以表为下面的迭代公式：

x_k=x_k－1－f(x_k－1)／f′(x_k－1)，k=1，2，3…

其中，x₀称为迭代初值。如果初值选得好，牛顿方法收敛很快；如果初值选得不好，牛顿方法收敛很慢，甚至根本不收敛。数学研究，有着眼于最坏情况的传统。一个命题，只有当所述结论在命题条件的最坏情况下也能成立，才算成立。

这就是所谓一般性(generality)的含义。算法效率的讨论，就其本义来说，是以计算收敛为前提的。

如果不收敛，即计算不成功，就谈不上计算的效率。这种传统，导致最坏情形分析的计算复杂性讨论，它把牛顿方法等许多虽然有时失效但是经常用得很好的算法拒之门外。

近年来，除了必然发生的事件以外，数学开始十分关注“几乎必然要发生”的事件，关心发生概率为一(即百分之百)的事件。这就是通有性(genericity)的含义。就应用问题而言，它包括讨论所谓大概率(即接近百分之百)的事件。牛顿方法计算之收敛，就是大概率事件，从而可以进行牛顿方法计算复杂性讨论。

斯梅尔(S．Smale)就代数方程的牛顿方法提出逼近零点(approximate zero)的概念。多项式的每个单零点，都联系一个牛顿方法的快速收敛邻域，逼近零点构成该邻域的核心部分。

一旦找到逼近零点，余下的计算量就微不足道了。斯梅尔设置步长参数h，0＜h≤1，先用比较细致的参数的牛顿迭代

x(k)=x(k－1)－hf(x(k－1))／f′(x(k－1))，k=1，2，3，…

寻求逼近零点。

他不是让x(0)去配多项式，而是固定x(0)=0，看哪一些多项式能与这个x(0)匹配得好。结果发现，在整个多项式空间中，匹配得不好的多项式只占据测度为零的一个子集。

把这些最坏的多项式和其它一些较坏的多项式排除在外，对余下的多数多项式，参数的牛顿迭代会很快找到多项式的逼近零点。循此思路，斯梅尔证明，给定p，0＜p＜1，和正整数n，以下结论成立的概率至少为1－p：参数牛顿迭代将在cn⁹／p⁷步内为任一n阶多项式找到一个逼近零点，这里c＞0是一个常数。

采用计算复杂性理论的行话，那就是：概率地说来，牛顿方法是多项式时间算法。

有资料表明，当今世界经济效益最大的科学计算方法，是线性规划问题的单纯形算法。

几十年来，单纯形算法的实际应用记录极好，以致它的创始人丹齐克(G．B．Dantzig)撰文表示，他相信单纯形算法的计算成本，是问题规模的线性函数。但是另一方面，有人在70年代初设计了一类线性规划问题，证明对于这类问题，单纯形算法虽然仍然有效，但计算成本是问题规模的指数函数。

按照斯梅尔的思路，对于单纯形算法，那类人为设计而实用中迄今未遇到过的问题，恰恰是最坏的情况。斯梅尔证明，概率地说来，单纯形算法不但属于多项式时间算法，而且是其中最好的线性时间算法。

其它重要的工作包括对增量算法、一般收敛算法、单纯同伦算法的计算复杂性的讨论，学科本身的理论构架，还有以有限成本达到无限精度的讨论。动力系统理论、拓扑学、图论、辫群理论、代数几何、几何概率、单叶函数理论，都在这一讨论中扮演重要的角色。

在这里，纯粹数学的若干深层研究，显示与数值方法计算复杂性理论的关联。

。

【参考文献】：

1 Smale S．The fundamental theorem of algebra and complexity theory Bull．AMS(N．S．)，1981，4：1～36

2 Smale S．Math Prog，1983，27：241～262

3 王则柯等．中国科学(A辑)，1984，27：8～16

4 Shub M & Smale S. SIAM J Comput, 1986,15:145～161

5 Smale S. Proceedings of International Congress of Mathe-maticians, AMS,1987,87～121

6 Renegar J. Math. Prog, 1988,40:113～163

7 Smale S. SIAM Review,1990,30:211～220

8 Renegar J, Shub M Math Prog, 1992,53:1 ～16

9 王则柯．计算的复杂性．长沙：湖南教育出版社，1993

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