  We show that certain Graph Laplacian linear sets of equations exhibit optimal
accuracy, guaranteeing that the relative error is no larger than the norm of
the relative residual and that optimality occurs for carefully chosen
right-hand sides. Such sets of equations arise in PageRank and Markov chain
theory. We establish new relationships among the PageRank teleportation
parameter, the Markov chain discount, and approximations to linear sets of
equations. The set of optimally accurate systems can be separated into two
groups for an undirected graph -- those that achieve optimality asymptotically
with the graph size and those that do not -- determined by the angle between
the right-hand side of the linear system and the vector of all ones. We provide
supporting numerical experiments.
