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了？
为了讨论上面情况发生的条件，我们暂时抛开网站，把问题抽象出来——研究有向图。
首先说明一点，对于如下这种不连通的图：

我们可以分别研究每一部分，而并不影响各个部分的收敛性。 Read the rest of this entry »

零点定理又名根的存在定理，它是连续函数介值性定理的一个特殊情况。具体表述如下：
若函数f(x)在闭区间[a,b]上连续，且f(a)与f(b)异号，则在(a,b)内至少存在一点x0,使得f(x0)=0.
下面我们就用这个定理解决一个实际问题：
在一块不平的地面上，能否找到一个适当的位置将一张方桌的四脚同时着地？
对于这个实际问题，我们首先假设：
(1)方桌的四条腿同长
(2)将方桌的桌脚与地面接触处看成是一个几何点，四脚连线为正方形(严格方桌)
(3)地面相对平坦，即在旋转所在地面范围内，方桌在任何位置至少有三只脚同时着地
(4)地面高度不会出现间断，亦即不会出现台阶式地面
依假设条件，以正方形的中心为坐标原点，当方桌绕中心转动时，正方形对角连线向量CA与x轴所成之角为@(@就代表角sita)

设A、C两脚与地面距离之和为g(@)，B、D两脚与地面距离之和为f(@)。由假设(3)可知，对任何@，f(@)与g(@)中总有一个为零。由假设(4)可知，f(@)与g(@)皆是连续函数。这样，方桌问题就被归结为以下数学问题：
对连续函数f(x)与g(x),g(0)=0,f(0)>=0,而且对任意的x有f(x)g(x)=0。证明存在一点x0,使得f(x0)=0,g(x0)=0.
证明： Read the rest of this entry »