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 $\| \cdot \|$ 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$?