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



Iterative matrix inversion with $L^\infty$ norm
One approach is to solve the optimization problem:
\begin{equation\*}
\min\_x\quad \|Ax-y\|\_\infty.
\end{equation\*}
This is a nonsmooth optimization problem, but is amenable to a variety of scalable optimization techniques, for instance, [Nesterov's smooth minimization of non-smooth functions](https://link.springer.com/article/10.1007/s10107-004-0552-5). Of course, the above problem can also be cast as a linear program, and thus solved more accurately using interior point methods.


**However**, if you meant that you wish to minimize $\|Ax-y\|\_2$, while ensuring that $\|Ax-y\|\_\infty \le \delta\|y\|\_\infty$, then you have at your hands a [second order cone program](https://en.wikipedia.org/wiki/Second-order_cone_programming), for which there are interior point methods, as well as other more scalable methods.


