带大家了解数学的纯粹存在证明(带大家了解数学问题)

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

原文标题:《为什么计算高维凸体的体积非常困难?什么是数学的纯粹存在证明?》

从一个简单的方程说起,

显然,这个方程(至少)有一个解。因为,令 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 之间。但是对于一个凸体这就非常不容易了。

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

本文来自微信公众号:老胡说科学 (ID:LaohuSci),作者:我才是老胡

带大家了解数学的纯粹存在证明(带大家了解数学问题)

免责声明:以上内容(如有图片或文字亦包括在内)为网络用户上传并发布,不代表本网站的观点和立场,本平台仅提供信息存储服务,如有侵权直接联系作者:远生,如若转载,请注明出处:https://www.leniuwang.com/7584.html