在估计函数f(x)的n次拉格朗日插值多项式近似代替f(x)所产生的误差时，我们的课本上首先假设了一个误差函数：

由于在n+1个插值节点处误差为0，故误差函数至少有n+1个零点。课本上于是设

其中为插值节点。
当初看到这里的时候觉得有点不对劲，难道一个函数有这些零点，就可以表示成如上形式吗？假如f(x)=log(x)，那么误差函数就是log(x)减去一个多项式，怎么可能展开成上述形式？ 阅读全文 »

在微分几何中，两个度量空间之间的同胚映射的是这样定义的(WIKI)：
在两个度量空间X和Y上建立的一个映射f:X->Y，如果满足以下三条：
1.f是双射
2.f是连续的
3.f的逆映射f^-1也是连续的
则称f为同胚映射。
当看到这个定义时，我产生了一个疑问：第3条性质的声明有意义吗？存在满足1,2但不满足3的映射吗？模糊的说，f连续的意思不就是当X中两个元素的距离足够小的时候，Y中两个元素的距离也足够小吗？这样看来，f的连续与f^-1的连续好像是对称的，因为如果上一句话满足，那么当Y中两个元素的距离也足够小的时候，X中两个元素的距离不也足够小吗？
今天大牛胡勇给我举了一个反例：
阅读全文 »

Google应用PageRank算法给每个网站分配了一个从0～10的数字，它代表了一个网站的重要性。PageRank根据网页之间的超链接来确定一个页面的等级。大家在我博客的右边栏中搜索框的下方可以看到我博客的PageRank，也可以在一些信息查询网站上查询任意网站的PageRank。那么，这个数值是如何计算出来的呢？
其实，PageRank算法的计算过程可以形象的看作“投票”过程。比如我的网站上挂了Wikipedia的超链接，那么我就给Wikepedia投了一票，那么他的PageRank值就会升高。粗略的说，每个网站的PageRank值就是其他各个网站给它“投票”的总和。如果简单的把每一个网站所投的票都看成相同的，这样又会不公平。因为重要的网站所投的票应该有较大的分量。那么，如何确定哪个网站重要，哪个网站不重要呢？还是要根据PageRank。这就产生了一个看似矛盾的过程，我们需要用PageRank值来衡量一个网站的重要性，而它本身的计算中又需要用到PageRank值！
这听起来很像递归，或迭代。PageRank的算法正是基于这种思考产生的。
我们定义PR(A)为A网站的PageRank。为了叙述方便，我们不再使用google的0~10度量，而是使用0~1度量。这和概率的取值范围是一致的。事实上，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，google才更改了度量。
在计算的开始，我们假设考虑的所有网站的PageRank是均匀分布的。这意味着，如果互联网上共有N个网站，那么每个网站的PageRank都是1/N。现在，假设我们仅仅考虑4个网站A,B,C,D组成的一个小网络。初始时，它们的PageRank都是1/4。假如B,C,D的网站上都有且仅有A的链接，那么它们每个人都为A贡献了0.25的PageRank。
（图1）
定义

则PR(A)=0.75
现在假设B网站上还有C的链接，网站D上有其它三个网站的链接。如下图所示：
（图2）
此时，对于B来讲，他把自己的总价值分散投给了两个网站A和C，那么每个网站就应该得到一半的PageRank，即0.125。只有1/3的PR(D)给了A。在这种情况下，

所以，按如此定义，一个网站X上有网站Y的链接，那么它给Y贡献的PageRank等于它的PageRank除以它网站的所有外部链接。（在这里我们做了一个假定，即X网站上对Y站的多个链接不重复计算。不难发现，这样的假定是很合理的。否则像http://worlds-highest-website.com/这样的一个网站上从头到尾全是www.charlesgao.com的链接，那我博客的PageRank就不会这么惨了。—–当然，这是不公平的。）
一个网站u的PageRank的普遍表达式为：

其中B_u是所有链接到u的网站的集合。v为相应网站所链接到的网站总数。
有一点值得注意的是：所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：
初始：所有网站的PageRank均等
第一次迭代：每个网站得到了一个新的PageRank
第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRank
…
我们最关心的问题是：
如此迭代下去，这些网站的PageRank值最终会收敛么？
大家再回头看我们一开始提到的两个例子。对于图1所示的例子来说，很显然第二次迭代所有的PageRank就都是0了。过程如下：

图2所示的情况也将导致最后所有网站的PageRank变为0。因为没有网站链接到D，那么第一次迭代后PR(D)=0。这将导致PR(B)=0，继而导致PR(C)=0,and then PR(A)=0:

咦？如果PageRank算法是这样的话，那岂不是每个网站的PR都是0了？
为了讨论上面情况发生的条件，我们暂时抛开网站，把问题抽象出来——研究有向图。
首先说明一点，对于如下这种不连通的图：

我们可以分别研究每一部分，而并不影响各个部分的收敛性。 阅读全文 »

在实变函数中，Levi定理，又名Levi单调收敛定理，是说非负可测函数的求极限和积分运算可以交换顺序。具体表述如下：
设和 都是可测集D上的非负可测函数，而且对几乎所有的，单调增加收敛于，则
在周性伟编著的《实变函数》一书中，上述定理的证明思想如下：由于非负可测函数的Lebesgue积分是由单调增加的非负简单函数列的积分的极限来定义的，所以对每一个，都用一列单增非负简单函数列来逼近，设为。然后，按下图所示的方式构造一个新的函数列 ：

即令

这样得到具有两个重要的性质：
(1)单调增加
(2)
在第(2)条性质中，我们先令 ，再令便可得到的极限即为，又根据第(1)条性质，的积分可以用的积分的极限来定义。
这个证明颇具启发性，它的关键在于非负简单函数列的构造。其实，的构造方法并不是唯一的，只要构造出的函数列满足上述两条性质便可。在这里，我们采用如下图所示的构造方式（是否似曾相识？还记得上篇博客中“至多可数个可数集的并是可数集”的证明方法吗？）：

证明：,设的积分由单调增加的非负简单函数列定义。现令


…

则为非负简单函数，且满足
(1)单调增加
(2)
由(2)，得
(3)

在(2),(3)中，令(则 )，得到
(4)
(5)
在(4),(5)中，令，得


则

参考资料：周性伟，《实变函数》，科学出版社

如果集合A和集合B之间存在一个一一映射(双射)，则称A和B等价。如果A和正整数集N等价，我们称A是可数的。换句话说，A可数的充要条件是A中的全体元素可以排列成a₁,a₂,…,a_n,..的形状。
根据这个定义，我们很容易得出整数集是可数的。因为我们可以构造如下正整数集到整数集的一一映射：

一个更有意思的命题是：
可数个可数集的并是可数集。
它的证明使用了经典的“对角线”法，这种方法被各种实变函数或集合论的书广泛采用。
证明：假设{A_m}是一列可数集，其中A_m={a_m1,a_m2,…}，把它们按如下顺序排列

可以按如图箭头所指的方向数U{A_m}中的元素，即把U{A_m}中元素排列成a₁₁,a₂₁,a₁₂,a₃₁,…}，于是U{A_m}是可数的，命题得证。
上述证明虽然已经说明U{A_m}可数，却没有给出它与正整数之间的一一映射关系。能否写出这个映射呢？
仔细观察发现，每个“对角线”上元素a_mn的下标之和m+n是一个常数。于是我们可以得到，按上图所示的排列方法，a_mn所处的位置为：

其中m+n≥3，a₁₁=1
这样我们就得到了U{A_m}到正整数集的一个一一映射：

这个命题的一个应用就是：有理数集是可数的。因为有理数可以被看作一个二元有序对(p,q)。但当我们用类似的方法排列有理数时，却发现了上述映射的一个致命错误：

(图片来自维基百科，它采用了“蛇状”的盘旋数法)
注意到图中红色的有理数，它们的分子和分母有公约数，这些数都已经被数过了。也就是说，我们上面构造的映射中忽略了a_mn中会有重复元素的情况。
我试图把重复的情况考虑进去，构建从正有理数到正整数的一一映射，但发现这时问题变得异常复杂，最终没能写出一个通式来。
那么，到底能不能找到这样的一个映射关系呢？ 阅读全文 »