例3-8　解方程组

解　利用Matlab生成稀疏矩阵及求解，并与满阵的解法作时间上的对比，程序如下：

运行得到，解稀疏方程组所用时间为

Page Rank-Google的民主表决式网页排名技术

Google能成为如此高效的网络搜索引擎的一个重要原因是，拉里·佩奇（Larry Page）和谢尔盖·布林（Sergey Brin）开发的Page Rank（网页排名）算法，这两位Google的创始人，在美国斯坦福大学读研究生时就提出了这个算法.Page Rank算法完全由WWW（World Wide Web）的超链接结构所决定，它大约每隔一个月重新计算一次，而与任何网页的实际内容或者搜索请求无关.然后，当网络用户提出搜索请求时，Google找出符合搜索要求的网页，并按它们的Page Rank大小依次列出.

Page Rank算法作为Google革命性的发明，这项技术彻底解决了搜索结果排序的问题.其实最先试图给互联网上的众多网站排序的并不是Google.Yahoo！公司是第一个用目录分类的方式让用户通过互联网检索信息的，但由于当时计算机容量和速度的限制，当时的Yahoo！和同时代的其他搜索引擎都存在一个共同的问题：收录的网页太少，而且只能对网页中常见内容相关的实际用词进行索引.那时，用户很难找到很相关的信息.1999年以前查找一篇论文，要换好几个搜索引擎.后来DEC公司开发了AltaVista搜索引擎，只用一台ALPHA服务器，却收录了比以往引擎都多的网页，而且对里面的每个词进行索引.AltaVista虽然让用户搜索到大量结果，但大部分结果却与查询不太相关，有时找想看的网页需要翻好几页.所以最初的AltaVista在一定程度上解决了覆盖率的问题，但不能很好地对结果进行排序.

Google的Page Rank算法是怎么回事呢？其实简单说就是民主表决.打个比方，假如我们要找某人，有一百个人举手说自己是这个人.那么谁是真的呢？也许有好几个真的，但即使如此谁又是大家真正想找的呢？如果大家都说在Google的那个是真的，那么他就是真的.(www.daowen.com)

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高.这就是Page Rank算法的核心思想.当然Page Rank算法实际上要复杂得多.例如，对来自不同网页的链接对待不同，本身网页排名高的链接更可靠，于是给这些链接较大的权重.Page Rank算法考虑了这个因素，可是现在问题又来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了先有鸡还是先有蛋的问题了吗？

拉里和谢尔盖把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题.他们先假定所有网页的排名是相同的，并且根据这个初值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名.他们两人从理论上证明了不论初值如何选取，这种算法都保证了网页排名的估计值能收敛到它们的真实值.值得一提的是，这种算法是完全没有任何人工干预的.

理论问题解决了，又遇到实际问题.因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目的平方个元素.如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素，这样大的矩阵相乘，计算量是非常大的.拉里和谢尔盖两人利用稀疏矩阵计算的技巧，大大地简化了计算量，并实现了这个Page Rank算法.今天Google的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多.

拉里和谢尔盖是怎么想到Page Rank算法的.拉里说：“当时我们觉得整个互联网就像一张大的图（Graph），每个网站就像一个节点，而每个网页的链接就像一个弧.我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现写篇博士论文.”他和谢尔盖就这样发明了Page Rank算法.

Page Rank算法的高明之处在于它把整个互联网当作一个整体对待，它无意识中符合了系统论的观点.相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系.

今天，Google搜索引擎比最初形式更复杂并完善了许多.但是Page Rank算法在Google所有算法中依然是至关重要的.在学术界，这个算法被公认是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程的教程.