求解PageRank问题的多步幂法修正的内外迭代法.pdfVIP

2014年 12月 第 28卷第 4期 Dec．2014 CommunicationOilAppliedMathematicsandComputation Vo1．28 NO．4 DOI10．3969／j．issn．1006—6330．2014．04．009 求解 PageRank问题的多步幂法修正的内外迭代法 顾传青， 马先磊 (上海大学理学院，上海 200444) 摘要 引用两种加速计算 PageRank的算法，分别为内外迭代法和两步分裂迭代算法．从这 两种方法中，得到多步幂法修正的内外迭代方法．首先，详细介绍了算法实施过程．然后，对 此算法的收敛性进行证明，并且将此算法的谱半径与两步分裂迭代算法的谱半径进行比较． 最后，数值试验说明该算法的计算速度比两步分裂迭代法要快． 关键词 内外迭代法；幂法；两步分裂迭代；多步分裂迭代；阻尼因子 2010数学分类号 65F10；65F50 中图分类号 TP391．9；0242．2 文献标志码 A 文章编号 1006—6330(2014)04-0454—07 Inner．outeriteration methOd modifledwith multi—step powerforcom putingPageRank GU Chuan—qing， MA Xian—lei (CollegeofSciences，ShanghaiUniversity，Shanghai200444，China) Abstract Thispaperpresentstwo methodsforspeeding up the computation ofthe PageRank．which arethe inner—outeriteration method and thetwo—step splitting iteration method． From the two methods，weachievetheinner—outer iterationmethodmodifiedwiththemulti—steppowermethod．First．weintroduce thealgorithm implementationprocessindetail．Second．weprovethetheoretical ratesoftheconvergenceofthenew approach．Weprovethespectralradiusofour approachiSlessthanthespectralradiusofthepowerinner—outeriterationmethod． Last，wepresentresultsofan experimentalcomparisonto demonstratethatthe CPU timeofournew approachachievingtheprescribedaccuracyiSlessthanthe CPU timeofthetwo—stepsplittingiterationmethod． Key words inner—outeriterationmethod；powermethod；two—stepsplittingiter— ation；multi-stepsplittingiteration；dampingfactor 2010M athematicsSubiectClassification 65F10；65F50 ChineseLibrary Classification TP391．9：O242．2 收稿 日期 2014—09—10； 修订 日期 2014—11—15 基金项目 国家 自然科学基金资助项 目；上海市教委科研创新重点资助项 目(13ZZ068)；上海市重 点学科建设资助项 目($30104) 通信作者 顾传青，研究方向为数值逼近、数值代数及其应用． E—mail：