PDF Publication Title:
Text from PDF Page: 131
5.4 convergence In the previous section, we showed that the algorithm corresponds to the power method when β = 0 or β = α. Convergence of the power method implies that the inner-outer iteration also converges with these parameters. In this section, we analyze the convergence for general 0 < β < α. We present the convergence analysis in two parts. First, we show that the outer iteration is a convergent scheme for the PageRank problem. Then we show that the outer scheme with an inner Richardson scheme will always converge on the PageRank problem. Lemma 15. Given 0 < α < 1, if the inner iterations are solved exactly, the scheme converges for any 0 < β < α. Furthermore, ∥x(k+1)−x∥≤α−β ∥x(k)−x∥, 1−β α−β where 1−β indicates that the closer β is to α, the faster the outer iterations converge. Proof. Let x be the PageRank vector and x(k) be the current iterate. The next iterate is x(k+1) = (I − βP)−1((α − β)Px(k) + (1 − α)v), and the solution is x = (I − βP)−1((α − β)Px + (1 − α)v). Subtracting these two expressions gives x − x(k+1) = (α − β)(I − βP)−1P(x − x(k)). The result now follows from applying 1-norms to both sides and using (5.7) (5.8) (5.9) (5.10) ∥(I−βP)−1P∥≤ 1 , 1−β which comes from ∥(I − βP)−1P∥ ≤ ∥∑∞ (βP)l∥ ≤ l=0 1 . 1−β 5.4 ⋅ convergence 109PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)