PDF Publication Title:
Text from PDF Page: 100
80 4 ⋅ random alpha pagerank 4.7.3 Error bounds on Gaussian quadrature Quadrature methods are extremely old tools and many excellent error analysis techniques exist. For example, Davis and Rabinowitz [1984] devotes anentirechaptertotheirstudy.LetxGQ(N) betheapproximationtoE[x(A)] using an N-point quadrature rule. We can only achieve an error bound for any component and thus use the upper bound ∥E [x(A)] − xGQ(N)∥ ≤ n ∣E [x (A)] − xGQ(N)∣ . This bound is terrible for large n and we do not expect it to be tight. Instead, we focus on the error decay—how much the error drops when N. Computing the bound on a component is involved, as the following theo- rem and proof demonstrate. Theorem 14. Let A be a random variable with finite moments and support [0, r], where r < 1. The error in the Gauss quadrature approximation of E [x(A)] is bounded above by 32ωr ∣E[xi(A)]−xi ∣≤ −2 2N+2 , 15(1 − ρ )ρ where N is the number of points in the Gauss quadrature rule, √√ 111 ω= 1+ and ρ= + −1. r rr2 Proof. TherearemanystatementsfortheerrorinGaussquadratureandwe begin with a modern statement from Trefethen [2008, theorem 4.5]. Consider 1 I = ∫−1 f (x) dx for an analytic function f . Let IN be the N-point Gauss quadrature approximation to I. Then 64ω ∣I−IN∣≤ −2 2N+N , (4.41) 15(1−(ρa +ρb) )(ρa +ρb) where ∣ f (z)∣ ≤ ω for all z in the ellipse with foci ±1 and semi-major axis ρa > 1 and semi-minor axis ρb. Figure 4.7 illustrates the construction. Note that we are approximating the integral GQ(N) i i E[xi(A)] = r 0 xi(α)dα Figure 4.7 – The framework for Gauss quadrature error analysis. The ellipse of analyticity provides bounds on the error in a Gauss quadrature rule. Roughly, ∣error∣≤(ρa +ρB)2N. with an N-point quadrature rule. Each PageRank component is a rational function, which is a special case of an analytic function. In the remainder of the proof, we go through the details of applying the bound from (4.41) precisely. First, we transform the problem to the integration region [−1, 1] by a change of variables α to z. In this z-space, we build an ellipse in the complex plain where xi(z) is analytic. To study the function magnitude ω, we transform the ellipse back to α-space and examine the magnitude of PageRank as a function of α when α is complex.PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.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 | RSS | AMP |