The usual conjugate gradient type algorithms for iteratively finding the inverse of a matrix applied to a vector, $x = A^{-1} y$, works by minimizing $||Ax - y||^2$ where $|| \ldots ||$ is the $L^2$-norm. The stopping criterion is usually $||Ax - y|| < \varepsilon||y||$ with some small $\varepsilon$.

Is there an efficient algorithm if I'm interested in the same problem but using the $L^p$-norm for the stopping criterion? 

I've actually found some papers with $1 \leq p \leq 2$, but I'd need large $p$, more precisely what I'm really interested in is the $L^\infty$-norm.

Are there efficient algorithms for $L^\infty$?