为什么计算高维凸体的体积非常困难?什么是数学的纯粹存在证明?

康托的天堂 2022-12-06 23:05:37

从一个简单的方程说起,

显然,这个方程(至少)有一个解。因为,令 f(x)= x^5-x-13,有f(1)=-13,f(2)=17。所以,在1和2之间必有一个x使f(x)=0。

这是纯粹存在论证的一个例子,这种论证告诉你有什么东西存在(在此例中,是一个方程的解),但是没有说怎样去求它。如果方程是x^2-x-13=0,就可以用一种全然不同的论证。二次方程求根的公式告诉我们,恰好有两个解,它甚至告诉我们解是什么它们是

但是对于五次方程就没有类似的公式。

这两种论证表现了数学的基本的两分法。如果要证明一个数学对象的存在,有时可以显式地证明,就是实实在在地描述那个对象;也可以间接地去证明,就是证明如果它不存在就会引起矛盾。

介于其间还有种种可能性,形成一个谱。如所说明过的,上一个论证只是说明,在1与2之间,方程x^5-x-13=0有一个解,但它也建议了一种方法来计算这个解,精确到如你所需。例如,如果需要精确到两位小数,可以取一串数∶1,1.01,1.02,…,1.99,2,然后在每一点估算f的值。就会发现,f(1.71)近似为 -0.0889,而 f(1.72)近似为0.3337,所以其间必有一个解(计算表明,此解更靠近1.71)。事实上还有更好的方法,例如牛顿方法去逼近一个解。对于许多目的,一个漂亮的解的公式不如计算或逼近这个解的方法更重要。而如果有了一个方法,它是否有用,还要看它运行快不快。

这样,在谱的一端有简单的定义一个熟悉对象的公式,它还可以容易地用来求出这个对象,而在谱的另一端,则有能够确立对象的存在性但不给出进一步的信息的证明,介乎其间的还有能够用以找出对象的算法,这些算法执行起来越快,其用处就越大。

和关于严格性的问题一样,如果一切其他条件都相同,则严格的论证优于不严格的论证。现在,(在直接和间接论证的问题上,也是)即使已经知道有间接存在证明,找到一个显式的有算法的论证仍然是值得的,其理由也是类似的∶寻求显式论证所花的力气时常导致新的数学洞察(不那么明显的是∶寻找间接论证的努力,有时也会带来新的洞察)。

纯粹存在证明的最著名的例子之一是关于超越数的。超越数就是那些不可能是任意整数系数的多项式方程的根的实数。有这种数存在的第一个证明是刘维尔在1844年给出的。他证明了有一个条件足以保证一个数是超越的,而且证明了构造出满足这种条件的数也是容易的。 后来,各种重要的数如e,π都被证明是超越数,但是这些证明都很难。甚至到了现在,仍有许多数几乎肯定是超越数,但是就是证明不出来。

以上所说的证明全都是直接显式的。然后,到了1873年康托利用了他的可数性理论给出了超越数存在的完全不同的证明。他证明了代数数成一可数集合,而实数构成一个不可数集合。因为可数集合远小于不可数集合,这表明几乎每一个实数(虽然不一定是几乎每一个你真正见到的实数)都是超越数。

就这个例子而言,两种论证的每一种都告诉了我们另一种论证所没有告诉我们的事。康托的证明告诉了我们确有超越数存在,但却一个例子也没有给我们。

严格说来,这也不是真的∶可以指定一种方法把代数数排成一个单子,然后对这个单子应用康托著名的对角线论证法,就可以找到一个超越数,然而这样找出来的超越数基本上没有任何含义。

刘维尔的证明在一个方面要好得多,因为它给了我们一个方法,用直截了当的定义来构造出几个超越数。然而,如果只知道刘维尔的那种直接论证以及e,π为超越数的证明,就可能得到一个印象,即超越数是一种很特殊的数。 有一种洞察在这些论证里完全见不到,但在康托的证明里面出现了,即典型的实数是超越数。

在 20世纪的大部分时间里,高度抽象的间接证明大行其道,但是在最近的年代,特别是因为有计算机的发明,态度起了变化。近来,得到更多注意的是∶一个证明是否为显式的,如果是,又是否能导出有效率的算法。

无需说明,算法本身就是有趣的,这还不尽是由于它们给予数学证明的视角。 我们简短地描述一个特别有趣的算法,它给出了一种计算高维凸体体积的方法。

一个图形

称为凸体,是指在K内任取两点z与y,则连接x与g的直线段全在K内。例如,正方形和三角形都是凸的,而五角星就不是。这个概念可以直接推广到 n 维情况,n 是任意正整数。面积和体积的概念也能这样推广。

现在设在以下意义上指定了一个 n 维的凸体K,即设有了一个运行很快的计算机程序,它能告诉我们每一个点(x_1,…,x_n)是否属于K。怎样来估计K的体积呢?对于像这样的问题,最有力的方法之一是统计方法∶随机地取一点,看它是否属于K,把对K的体积的估计建立在这个点落入K中的频度上。例如,想估计π,就取一个半径为1的圆,把它放在一个边长为2的正方形里面,然后从这个正方形里随机地取许多点。每一个点属于此圆的概率都是π/4,所以把落入圆内的点占点的总数的比乘以4,就得到π的估计。

这个途径对于很低的维数是很容易起作用的,但是当维数很高时,却会遇到很大的困难。例如设我们想用这个方法估计n维球的体积。把这个球放在一个 n 维立方体里面,也去看这个点落入球内的频度。然而,n维球的体积占n维立方体体积的比却是指数的小,这就是说,在球内找到一个点前,先要投的点的数目是指数的大。所以这个方法变得不切实用。

然而,因为还有一个计策可以绕过这个困难。可以定义一个凸体的序列K_0,K_1,…,K_m,使每一个凸体都包含于下一个凸体内,而从想要计算其体积的凸体开始(即想计算Ko的体积),而终于一个立方体(即K_m是一个立方体),并且使得K_i的体积至少是K+1的体积的一半。于是对每一个i,都要估计一下K_(i-1)与K_i的体积之比。这些比的乘积就是K_0与K_m的体积比。但是K_m(立方体)的体积是知道的,所以就得到 K_0的体积。

怎样来估计K_(i-1)与K_i的体积之比呢?只需简单地随机取K_i的点,并且看有多少落入 K_(I-1)中。然而就是在这里,问题的微妙之处出现了∶怎样从知之不多的凸体里随机取点呢?在n维立方体里随机取点是容易的,只需要独立地选取n个随机数x_1,…,x_n,而每一个x_i都在 -1和 +1 之间。但是对于一个凸体这就非常不容易了。

有一个奇妙的聪明办法来回避这个问题。这就是小心地设计一个随机游动,从凸体内的一点开始,而在每一步,移动到的点可以从几个不多的可能性中随机选择。 随着随机的游动步数越多,对于这点所到达的地方所知就越少。如果这个游动是适当定义的,可以证明,在不多几步以后,点的位置就是纯粹随机的了。然而,证明完非常难。

3 阅读:146
评论列表
  • 2024-04-01 19:29

    一多半能看懂。少见

康托的天堂

简介:科学如此美妙,我想让你知道