  In this paper we derive novel families of inclusion sets for the spectrum and
pseudospectrum of large classes of bounded linear operators, and establish
convergence of particular sequences of these inclusion sets to the spectrum or
pseudospectrum, as appropriate. Our results apply, in particular, to bounded
linear operators on a separable Hilbert space that, with respect to some
orthonormal basis, have a representation as a bi-infinite matrix that is banded
or band-dominated. More generally, our results apply in cases where the matrix
entries themselves are bounded linear operators on some Banach space. In the
scalar matrix entry case we show that our methods, given the input information
we assume, lead to a sequence of approximations to the spectrum, each element
of which can be computed in finitely many arithmetic operations, so that, with
our assumed inputs, the problem of determining the spectrum of a band-dominated
operator has solvability complexity index one, in the sense of Ben-Artzi et al.
(C. R. Acad. Sci. Paris, Ser. I 353 (2015), 931-936). As a concrete and
substantial application, we apply our methods to the determination of the
spectra of non-self-adjoint bi-infinite tridiagonal matrices that are
pseudoergodic in the sense of Davies (Commun. Math. Phys. 216 (2001) 687-704).
