When running any iterative algorithm it is useful to know when to stop. Here we review LSQR and LSLQ, two iterative methods for solving \min_x \|Ax-b\|_2 based on the Golub-Kahan bidiagonalization process, as well as estimates for the 2-norm error \|x-x_*\|_2, where x_* is the minimum norm solution. We also review the closely related Craig’s method, which has a smaller error than either LSQR or LSLQ when Ax=b has a solution, but does not converge on inconsistent problems. We introduce a new method for estimating the 2-norm error as well as an algorithm that can be safely terminated sooner than LSQR provably, and we show that our method is, in a sense, optimal. Experimental results are discussed, as well as the implications of our work for the conjugate gradient method.