无穷中的二分（一）

十 15

话说我平时只有在算法上接触了一点二分法。当今天数分教授告诉我们某定理要用二分法来证明的时候，我有点震精…

这个定理叫做……“Weierstrass定理”……好吧，只能说这个定理是某一个Weierstrass定理……下面称为魏氏定理好了……内容是这样的：对于任意的有界无穷数列，一定存在一个收敛的子序列。举个例子，对于数列0，1，0，1，0，1，……这里只需要将子序列定为0，0，0，0，0，……或者1，1，1，1，1，1，……即可。但是这个结果其实是不那么显然的，例如： $a_{n}={cos n}$ ,你能肯定地说一定能够找到收敛的子序列么~？所以这个结论又略显奇妙。

首先要声明（不是证明~）一个“区间套定理”。区间套指的是这样的一系列区间： $[a_{n+1},b_{n+1}]\subseteq[a_{n},b_n]$ 且 $\lim\limits_{n \to \infty}(b_n-a_n)=0$ 。那么对于每一个区间套，都存在一个唯一的实数 $r_0$ 满足 $\forall n\in N,r_0\in[a_n,b_n]$ 。这个从直观上是比较好理解的吧~

下面就来证明下那个魏氏定理。首先因为有界，我们就可以设数列位于区间 $[a_1,b_1]$ 内。那么，取这个区间的中点 $\frac{a_1+b_1}{2}$ ，于是将原来的数列分成了两部分，那么至少一个部分里面包含了无穷多项，就设这个区间为 $[a_2,b_2]$ ，然后对新的区间继续二分，选择任意一个含有无穷多项的区间重复操作。显然，因为每次区间的长度减半，所以最后得到的 ${[a_n,b_n]}$ 是一个区间套。最后这个套套网住了一个实数。那么，我们只需要在每一个 $[a_i,b_i]$ 中取一个 $x_{n_i}$ ，这样生成的子列就肯定是收敛到套套里的~

这个二分+区间套的方法确实很好用。在证明介值定理的时候也用上了。我们让区间套满足 $a_n<0,b_n>0$ ，即不断地二分，然后选取包含了0的那一部分。最后当然，套套套住了0.

在实数中的二分感觉更加飘渺~因为在操作实数，极限等一系列概念的时候有很多直观上容易理解的东西都需要去严谨地说明，有时候不知不觉地就用上了一个没有证明过的东西，从而让整个证明失去严谨性。而且任何问题一旦牵涉到无穷，那么就无法用直觉来咬定结果了。所以这里的二分对我来说就像是一种突破，带来的并不是算法效率方面的结果，而是思维的拓展。

本文由严酷的魔王创作，转载或引用前请联系我们。

标签：思维, 智慧, 证明, 趣题

2009年10月15日星期四

4条评论

2009年10月20日星期二 20:47:38

Hyacinth 说：

妙~话说你们的课都显得很飘渺

回复

严酷的魔王
2009年10月20日星期二 21:30:08

回复：
飘渺的东西多着咧

回复

Hyacinth
2009年10月20日星期二 22:42:24

回复：
这点让我很想不通。。。好不基础。。。

回复
2009年10月21日星期三 0:54:37

无穷中的二分（二） | f(Program,Poet)=Programet 说：

[...] 话说老师自从上次使用了二分之后，貌似就上瘾了。他很令人赞赏地没有照本宣科，而是讲了一串课本末尾的附录，即实数的连续性啊，紧致性啊，完备性啊之类的比较基础的内容。其中有一个有界性定理说的是这样一个东西：一个连续函数在区间上是有界的。这个东西老师给出了两个证明方法，都不是“显然”的方法。有些内容是上一篇里面说过的，没有看过的童鞋可以先去瞟两眼。 [...]

f(Program,Poet)=Programet

无穷中的二分（一）

4条评论

留下您的足迹

雁过留声

看一看，瞧一瞧~

随机阅读

最新评论

索引

This is Programet