#  On the infinite-dimensional QR algorithm

Matthew J. Colbrook111Corresponding author<EMAIL_ADDRESS>Anders
C. Hansen

###### Abstract

Spectral computations of infinite-dimensional operators are notoriously
difficult, yet ubiquitous in the sciences. Indeed, despite more than half a
century of research, it is still unknown which classes of operators allow for
computation of spectra and eigenvectors with convergence rates and error
control. Recent progress in classifying the difficulty of spectral problems
into complexity hierarchies has revealed that the most difficult spectral
problems are so hard that one needs three limits in the computation, and no
convergence rates nor error control is possible. This begs the question: which
classes of operators allow for computations with convergence rates and error
control? In this paper we address this basic question, and the algorithm used
is an infinite-dimensional version of the QR algorithm. Indeed, we generalise
the QR algorithm to infinite-dimensional operators. We prove that not only is
the algorithm executable on a finite machine, but one can also recover the
extremal parts of the spectrum and corresponding eigenvectors, with
convergence rates and error control. This allows for new classification
results in the hierarchy of computational problems that existing algorithms
have not been able to capture. The algorithm and convergence theorems are
demonstrated on a wealth of examples with comparisons to standard approaches
(that are notorious for providing false solutions).We also find that in some
cases the IQR algorithm performs better than predicted by theory and make
conjectures for future study.

Keywords: spectra, eigenvectors, computation, infinite-dimensional Hilbert
spaces, hierarchies of computational problems

Mathematics Subject Classification (2010): 47A10, 65J10, 46N40, 03D55

##  1 Introduction

Spectral computations are ubiquitous in the sciences with applications in
solutions to differential and integral equations, spline functions, orthogonal
polynomials, quantum mechanics, quantum chemistry, statistical mechanics,
Hermitian and non-Hermitian Hamiltonians, optics etc. [63, 31, 74, 10, 30, 71,
72, 38]. The computational problem is as follows. Letting $T$ denote a bounded
linear operator on the canonical separable Hilbert space $l^{2}(\mathbb{N})$,
one wants to design algorithms to compute the spectrum of $T$, denoted by
$\sigma(T)$. Given the many applications, this problem has been investigated
intensely since the 1950s [3, 6, 7, 4, 17, 21, 20, 69, 32, 33, 40, 42, 47, 50,
51, 76, 22, 16, 29, 67, 68, 70, 39, 41, 65], and we can only cite a small
subset here.

In the paper “On the Solvability Complexity Index, the $n$-pseudospectrum and
approximations of spectra of operators” [42] the Solvability Complexity Index
(SCI) was introduced. The SCI provides a classification hierarchy [42, 8, 9,
25, 27, 24, 26] of spectral problems according to their computational
difficulty. The SCI of a class of spectral problems is the least number of
limits needed in order to compute the spectrum of operators in this class.
From a classical numerical analysis point of view such a concept may seem
foreign. Indeed, the traditional sentiment is that one should have an
algorithm, $\Gamma_{n}$, such that for an operator
$T\in\mathcal{B}(l^{2}(\mathbb{N}))$,

$\Gamma_{n}(T)\longrightarrow\sigma(T),\quad n\rightarrow\infty,$ (1.1)

preferably with some form of error control of the convergence. As this
philosophy forms the basics of numerical analysis, it naturally permeates the
classical literature on the computational spectral problem. However, as is
shown in [42, 8, 9], an algorithm satisfying (1.1) is impossible even for the
class of self-adjoint operators. Indeed, in the general case, the best
possible alternative is an algorithm depending on three indices
$n_{1},n_{2},n_{3}$ such that

$\lim_{n_{3}\rightarrow\infty}\lim_{n_{2}\rightarrow\infty}\lim_{n_{1}\rightarrow\infty}\Gamma_{n_{3},n_{2},n_{1}}(T)=\sigma(T).$

In fact, any algorithm with fewer than three limits will fail on the general
class of operators. Moreover, no error control nor convergence rate on any of
the limits are possible, since any such error control would reduce the number
of limits needed. However, for the self-adjoint and normal cases two limits
suffice in order to recover the spectrum. This phenomenon implies that the
only way to characterise the computational spectral problem is through a
hierarchy classifying the difficulty of computing spectra of different
subclasses of operators. This is the motivation behind the SCI hierarchy,
which also covers general numerical analysis problems. Indeed, the SCI
hierarchy is closely related to Smale’s question on the existence of purely
iterative generally convergent algorithm for polynomial zero finding [73]. As
demonstrated by McMullen [53, 54] and Doyle & McMullen [34], this is a case
where several limits are needed in the computation, and their results become
special cases of classification in the SCI hierarchy [8, 9].

Informally, the SCI hierarchy is characterised as follows (see the Appendix
§A.2 for a more detailed summary describing the SCI hierarchy).

$\Delta_{0}$:

The set of problems that can be computed in finite time, the SCI $=0$.

The set of problems that can be computed using one limit, the SCI $=1$,
however one has error control and one knows an error bound that tends to zero
as the algorithm progresses.

The set of problems that can be computed using one limit, the SCI $=1$, but
error control may not be possible.

For $m\in\mathbb{N}$, the set of problems that can be computed by using $m$
limits, the SCI $\leq m$.

The class $\Delta_{1}$ is of course a highly desired class, however, most
spectral problems are much higher in the hierarchy. For example. we have the
following known classifications [42, 8, 9].

  * (i)

The general spectral problem is in $\Delta_{4}\setminus\Delta_{3}$.

  * (ii)

The self-adjoint spectral problem is in $\Delta_{3}\setminus\Delta_{2}$.

  * (iii)

The compact spectral problem is in $\Delta_{2}\setminus\Delta_{1}$.

Here, the notation $\setminus$ indicates the standard “setminus”. Note that
the SCI hierarchy can be refined. We will not consider the full generalisation
in the higher part of the hierarchy in this paper, but recall the class
$\Sigma_{1}$ [28]. This class is defined as follows. $\Sigma_{1}$:

We have $\Delta_{1}\subset\Sigma_{1}\subset\Delta_{2}$ and $\Sigma_{1}$ is the
set of problems that can be computed by passing to one limit. Error control
may not be possible, however, there exists an algorithm for these problems
that converges and for which its output is included in the spectrum (up to an
arbitrarily small accuracy parameter $\epsilon$).

In the context of computing $\sigma(T)$, a $\Sigma_{1}$ classification means
the existence of an algorithm $\Gamma_{n}$ such that

$\Gamma_{n}(T)\subset\sigma(T)+B_{2^{-n}}(0)$

and $\Gamma_{n}$ converges to $\sigma(T)$ in the Hausdorff metric. The
$\Sigma_{1}$ class is very important as it allows for algorithms that never
make a mistake. In particular, one is always sure that the output is sound but
we do not know if we have everything yet. The simplest infinite-dimensional
spectral problem is that of computing the spectrum of an infinite diagonal
matrix and, as is easy to see, we have the following.

  * (iv)

The problem of computing spectra of infinite diagonal matrices is in
$\Sigma_{1}\setminus\Delta_{1}$.

Hence, the computational spectral problem becomes an infinite classification
theory in order to characterise the above hierarchy. In order to do so, there
will, necessarily, have to be many different types of algorithms. Indeed,
characterising the hierarchy will yield a myriad of different approaches, as
different structures on the various classes of operators will require specific
algorithms. The key contribution of this paper is to investigate the
convergence properties of the Infinite-dimensional QR (IQR) algorithm, its
implementation properties, and how this algorithm provides classification
results in the SCI hierarchy.

###  1.1 Main contribution and novelty of the paper

The main contributions of the paper can be summarised as follows: New
convergence results, algorithmic results (the IQR algorithm can be
implemented), classification results in the SCI hierarchy and numerical
examples.

We provide new convergence theorems for the IQR algorithm with convergence
rates and error control. The results include eigenvalues, eigenvectors and
invariant subspaces.

We prove that for infinite matrices with finitely many non-zero entries in
each column, it is possible to implement the IQR algorithm exactly (on a
finite machine) as if one had an infinite computer at one’s disposal. This can
be extended to implementing the IQR algorithm with error control for general
invertible operators.

As a result of (1) and (2), we provide new classification results for the SCI
hierarchy. In particular, the convergence properties of the IQR algorithm
capture key structures that allow for sharp $\Delta_{1}$ classification of the
problem of computing extremal points in the spectrum. Moreover we establish
sharp $\Sigma_{1}$ classification of the problem of computing spectra of
subclasses of compact operators.

Finally, we demonstrate the IQR algorithm and the proven convergence results
on a variety of difficult problems in practical computation, illustrating how
the IQR algorithm is much more than a theoretical concept. Moreover, the
examples demonstrate that the IQR algorithm performs much better than what our
theory covers and works on much larger classes of operators than our theorems
predict. Hence, we are left with many open problems on the theoretical
understanding of the potential and limitations of this algorithm. The
computational experiments include examples from

  * (i)

Toeplitz/Laurent operators and their perturbations,

  * (ii)

$PT$-symmetry in quantum mechanics,

  * (iii)

Hopping sign model in sparse neural networks,

  * (iv)

NSA Anderson model in superconductors.

###  1.2 Connection to previous work

Our results connect to many different approaches in the vast literature on
spectral computation in infinite dimensions. The infinite-dimensional
computational spectral problem is very different from the finite-dimensional
computational eigenvalue problem, and even though the IQR algorithm is
inspired by the finite-dimensional version, this paper solely focuses on the
infinite-dimensional problem. Thus, the paper is aimed at the analysis and
numerical analysis audience focusing on infinite-dimensional problems rather
than the finite-dimensional numerical linear algebra discipline.

The IQR algorithm provides an alternative to the standard finite section
method in several cases where it fails. Whereas the finite section method
would extract a finite section from the infinite matrix and then apply, for
example, the finite-dimensional QR algorithm, the IQR algorithm first performs
the infinite QR iterations and then extracts a finite section. In general
these two processes do not commute. The finite section method (or any
derivative of it) cannot work in general because of the general classification
results in the SCI hierarchy mentioned in §1. Typically, it may provide false
solutions. However, in the cases where it converges, it provides invaluable
$\Delta_{2}$ classifications in the SCI hierarchy. The finite section method
has often been viewed in connection with Toeplitz theory and the reader may
want to consult the work by Böttcher [15, 14], Böttcher & Silberman [18],
Böttcher, Brunner, Iserles & Nørsett [16], Brunner, Iserles & Nørsett [22],
Hagen, Roch & Silbermann [39], Lindner [48], Marletta [50] and Marletta &
Scheichl [51]. From the operator algebra point of view the work of Arveson [6,
5, 7] has been influential as well as the work of Brown [21].

Deift, Li and Tomei [32] provided the first results on the IQR algorithm in
connection with Toda flows with infinitely many variables. Their results are
purely functional analytic and do not take implementation and computability
issues into account. However, these results provide the fundamentals of the
IQR algorithm. In [40] these results were expanded with a convergence result
for eigenvectors corresponding to eigenvalues outside the essential numerical
range for normal operators. Yet, this paper did not consider convergence
rates, actual numerical calculation nor any classification results.

Olver, Townsend and Webb have provided a practical framework for infinite-
dimensional linear algebra and foundational results on computations with
infinite data structures [77, 59, 58, 57, 60]. This includes efficient codes
as well as theoretical results. The infinite-dimensional QL (IQL) algorithm is
an important part of this program. The IQL algorithm is rather different from
the IQR algorithm, although they are similar in spirit. In particular, both
the implementation and the convergence results are somewhat contrasting.

The results in this paper follow in the long tradition of infinite-dimensional
spectral computations. This field contains a vast literature that spans more
than half a century, and the references that we have cited in the first
paragraph of §1 represent a small sample. However, we would like to highlight
the recent work by Bögli, Brown, Marletta, Tretter & Wagenhofer [13] who were
able to computationally confirm, with absolute certainty, a conjecture on a
certain oscillatory behaviour of higher auto-ionizing resonances of atoms.
Note that problems that are classified as $\Delta_{1}$ and $\Sigma_{1}$
problems in the SCI hierarchy may allow for computer assisted proofs.

###  1.3 Background and notation

Here we briefly recall some definitions used in the paper. We will consider
the canonical separable Hilbert space $\mathcal{H}=l^{2}(\mathbb{N})$ (the set
of square summable sequences). Moreover, we write $\mathcal{B}(\mathcal{H})$
for the set of bounded operators on $\mathcal{H}.$ For orthogonal projections
$E,F$, we will write $E\leq F$ if the range of $E$ is a subspace of the range
of $F$. We denote the canonical orthonormal basis of $\mathcal{H}$ by
$\\{e_{j}\\}_{j\in\mathbb{N}}$, and if $\xi\in\mathcal{H}$ we write
$\xi(j)=\langle\xi,e_{j}\rangle.$ Note that $T\in\mathcal{B}(\mathcal{H})$ is
uniquely determined by its matrix elements $t_{ij}=\langle
Te_{j},e_{i}\rangle$. Hence we will use the words bounded operator and
infinite matrix interchangeably. Given a sequence of operators $\\{T_{n}\\}$
we will use the notation

$T_{n}\stackrel{{\scriptstyle\text{SOT}}}{{\longrightarrow}}T,\qquad
T_{n}\stackrel{{\scriptstyle\text{WOT}}}{{\longrightarrow}}T$

to mean convergence in the strong and weak operator topology respectively. The
spectrum of $T\in\mathcal{B}(\mathcal{H})$ will be denoted by $\sigma(T)$, and
$\sigma_{d}(T)$ denotes the set of isolated eigenvalues with finite
multiplicity (the discrete spectrum).

In connection with the spectrum we need to recall some definitions which will
appear in the statement of our theorems. We recall that, for
$T\in\mathcal{B}(\mathcal{H})$, the essential spectrum222Of course in the case
of non-normal $T$ there are different definitions of the essential spectrum.
However, these differences will not matter regarding the results of this
paper. and the essential spectral radius are given by

$\sigma_{\mathrm{ess}}(T)=\\{z\in\mathbb{C}:T-zI\text{ is not
Fredholm}\\},\quad
r_{\mathrm{ess}}(T)=\sup\\{|z|:z\in\sigma_{\mathrm{ess}}(T)\\}.$

Moreover, the numerical range and the essential numerical range of $T$ are
defined by

$W(T)=\\{\langle T\xi,\xi\rangle:\|\xi\|=1\\},\quad
W_{e}(T)=\bigcap_{K\,\text{compact}}\overline{W(T+K)}.$

In addition, we need the Hausdorff metric as defined by the following. Let
$\mathcal{S},\mathcal{T}\subset\mathbb{C}$, be compact. Then their Hausdorff
distance is

$d_{H}(\mathcal{S},\mathcal{T})=\max\\{\sup_{\lambda\in\mathcal{S}}d(\lambda,\mathcal{T}),\sup_{\lambda\in\mathcal{T}}d(\lambda,\mathcal{S})\\},$
(1.2)

where $d(\lambda,\mathcal{T})=\inf_{\rho\in\mathcal{T}}|\rho-\lambda|.$ We
also recall a generalisation of the spectrum, known as the pseudospectrum.
Indeed, for $\epsilon>0$ define the $\epsilon$-pseudospectrum as

$\sigma_{\epsilon}(T)=\\{z\in\mathbb{C}:\left\|(T-zI)^{-1}\right\|\geq{\epsilon}^{-1}\\},$

where we interpret $\left\|S^{-1}\right\|$ as $+\infty$ if $S$ does not have a
bounded inverse. This is easier to compute than the spectrum, converges in the
Hausdorff metric to the spectrum as $\epsilon\downarrow 0$ and gives an
indication of the instability of the spectrum of $T$. We shall use it as
comparison for the IQR algorithm and as a means to detect spectral pollution
for finite section methods.

Finally, we need a notion of convergence of subspaces. We follow the notation
in [45]. Let $M\subset\mathcal{B}$ and $N\subset\mathcal{B}$ be two non-
trivial closed subspaces of a Banach space $\mathcal{B}.$ The distance between
them is defined by

$\delta(M,N)=\sup_{\stackrel{{\scriptstyle x\in M}}{{\|x\|=1}}}\inf_{y\in
N}\|x-y\|,\qquad\hat{\delta}(M,N)=\max[\delta(M,N),\delta(N,M)].$

Given subspaces $M$ and $\\{M_{k}\\}$ such that
$\hat{\delta}(M_{k},M)\rightarrow 0$ as $k\rightarrow\infty,$ we will use the
notation $M_{k}{\rightarrow}M$. If we replace $\mathcal{B}$ with a Hilbert
space $\mathcal{H}$ we can express $\delta$ and $\hat{\delta}$ conveniently in
terms of projections and operator norms. In particular, if $E$ and $F$ are the
orthogonal projections onto subspaces $M\subset\mathcal{H}$ and
$N\subset\mathcal{H}$ respectively then

$\delta(M,N)=\sup_{\stackrel{{\scriptstyle x\in M}}{{\|x\|=1}}}\inf_{y\in
N}\|x-y\|=\sup_{\stackrel{{\scriptstyle x\in
M}}{{\|x\|=1}}}\|F^{\perp}x\|=\|F^{\perp}E\|.$

Since the operator $E-F=F^{\perp}E-FE^{\perp}$ is essentially the direct sum
of operators $F^{\perp}E\oplus(-FE^{\perp}),$ its norm is $\hat{\delta}(M,N),$
i.e.

$\hat{\delta}(M,N)=\max(\|F^{\perp}E\|,\|E^{\perp}F\|)=\max(\|F^{\perp}E\|,\|FE^{\perp}\|)=\|E-F\|.$
(1.3)

This allows us to extend the definition to allow the trivial subspace
$\\{0\\}$ and gives rise to a metric on the set of all closed subspaces of
$\mathcal{H}$ (first introduced by Krein and Krasnoselski in [46]). We also
define the (maximal) subspace angle, $\phi(M,N)\in[0,\pi/2]$, between $M$ and
$N$ by

$\sin\big{(}\phi(M,N)\big{)}=\hat{\delta}(M,N).$ (1.4)

Finally, we will use two further well known properties in the Hilbert space
setting. First, if $M$ and $N$ are both finite $l$-dimensional subspaces, then

$\delta(M,N)\leq l^{\frac{1}{2}}\delta(N,M),$ (1.5)

which shows that to prove convergence of finite dimensional subspaces, it is
enough to prove $\delta$-convergence. Second, suppose we have

$M=\bigoplus_{j=1}^{n}M_{j},\quad N^{(k)}=N_{1}^{(k)}+...+N_{n}^{(k)},$

where the $N_{j}^{(k)}$ need not be orthogonal. Then a simple application of
Hölder’s inequality yields

$\delta(M,N^{(k)})\leq\Big{(}\sum_{j=1}^{n}\delta(M_{j},N_{j}^{(k)})^{2}\Big{)}^{\frac{1}{2}},$
(1.6)

which shows that if the dimensions of $M_{j}$ and $N_{j}^{(k)}$ are finite and
equal, then to prove convergence $N^{(k)}\rightarrow M$ we only need to prove
that $\delta(M_{j},N_{j}^{(k)})\rightarrow 0$ as $k\rightarrow\infty$. For
further properties (including other notions of distances between subspaces)
and a discussion on two projections theory, we refer the reader to the
excellent article of Böttcher and Spitkovsky [19].

###  1.4 Organisation of the paper

The paper is organised as follows. In Section 2 we define the IQR algorithm
(simple codes are also provided in the appendix). Section 3 contains and
proves our main theorems including convergence rates. The outcome is more
elaborate than the finite-dimensional case, as the infinite-dimensional
setting includes more intricate instances. Our key practical result is that,
despite being an algorithm dealing with infinite amount of information, it can
be implemented on any standard computer and this is discussed in Section 4.
The fact that the IQR algorithm can be computed allows for its use in order to
provide new classification in the SCI hierarchy as discussed in Section 5. In
particular, we demonstrate $\Delta_{1}$ classification for the extremal part
of the spectrum and dominant invariant subspaces, as well as $\Sigma_{1}$
results for spectra of certain classes of compact operators. Note that the
general spectral problem for compact operators is not in $\Sigma_{1}$. The IQR
algorithm and convergence theorems are demonstrated on a large collection of
examples from the sciences on difficult computational spectral problems in
Section 6 with comparisons to the finite section method. The IQR algorithm is
also found to perform better than theory predicts and we conjecture conditions
on the operator for this to be the case. Finally, we conclude with a
discussion of the opportunities and limits of the IQR algorithm in Section 7.

##  2 The infinite-dimensional QR algorithm (IQR)

The IQR algorithm has existed as a pure mathematical concept for more than
thirty years and it first appeared in the paper “Toda Flows with Infinitely
Many Variables” [32] in 1985. However, the analysis in [32] covers only self-
adjoint infinite matrices with real entries, and since the analysis is done
from a pure mathematical perspective, the question regarding the actual
numerical algorithm is left out. We will in this paper extend the analysis to
more general operators and answer the crucial question: can one actually
implement the IQR algorithm? The answer is affirmative, and we also prove
convergence theorems, generalising the well known finite dimensional case.

###  2.1 The QR decomposition

The QR decomposition is the core of the QR algorithm. If
$T\in\mathbb{C}^{n\times n},$ one may apply the Gram-Schmidt procedure to the
columns of $T$ and store these columns in a matrix $Q$ and this gives us the
QR decomposition

$T=QR,$ (2.1)

where $Q$ is a unitary matrix and $R$ upper triangular. It is no surprise that
a QR decomposition should exist in the infinite dimensional case, however, we
need more than just the existence. A key ingredient in the QR algorithm is the
Householder transformation used for computational reasons (they are backwards
stable). It is crucial that we can adopt these tools in the infinite
dimensional setting. Our goal is to extend the construction of the QR
decomposition, via Householder transformations, to infinite matrices and to
find a way so that one can implement the procedure on a finite machine. To do
this we need to introduce the concept of Householder reflections in the
infinite-dimensional setting.

######  Definition 2.1.

A Householder reflection is an operator $S\in\mathcal{B}(\mathcal{H})$ of the
form

$S=I-\frac{2}{\|\xi\|^{2}}\xi\otimes\bar{\xi},\qquad\xi\in\mathcal{H},$ (2.2)

where $\bar{\xi}$ denotes the associated functional in $\mathcal{H}^{*}$ given
by $x\rightarrow\langle x,\xi\rangle$. In the case where
$\mathcal{H}=\mathcal{H}_{1}\oplus\mathcal{H}_{2}$ and $I_{i}$ is the identity
on $\mathcal{H}_{i}$ then

$U=I_{1}\oplus\left(I_{2}-\frac{2}{\|\xi\|^{2}}\xi\otimes\bar{\xi}\right)\qquad\xi\in\mathcal{H}_{2},$

will be called a Householder transformation.

A straightforward calculation shows that $S^{*}=S^{-1}=S$ and thus also
$U^{*}=U^{-1}=U.$ An important property of the operator $S$ is that if
$\\{e_{j}\\}$ is an orthonormal basis for $\mathcal{H}$ and
$\eta\in\mathcal{H}$ then one can choose $\xi\in\mathcal{H}$ such that

$\langle
S\eta,e_{j}\rangle=\langle(I-\frac{2}{\|\xi\|^{2}}\xi\otimes\bar{\xi})\eta,e_{j}\rangle=0,\qquad\forall
j\neq 1.$

In other words, one can introduce zeros in the column below the diagonal
entry. Indeed, if $\eta_{1}=\langle\eta,e_{1}\rangle\neq 0$ one may choose
$\xi=\eta\pm\|\eta\|\zeta,$ where $\zeta=\eta_{1}/|\eta_{1}|e_{1}$ and if
$\eta_{1}=0$ choose $\xi=\eta\pm\|\eta\|e_{1}.$ The following theorem gives
the existence of a QR decomposition, even in the case where the operator is
not invertible.

######  Theorem 2.2 ([40]).

Let $T$ be a bounded operator on a separable Hilbert space $\mathcal{H}$ and
let $\\{e_{j}\\}_{j\in\mathbb{N}}$ be an orthonormal basis for
$\mathcal{H}\cong l^{2}(\mathbb{N}).$ Then there exist an isometry $Q$ such
that $T=QR$ where $R$ is upper triangular with respect to $\\{e_{j}\\}$.
Moreover,

$Q=\underset{n\rightarrow\infty}{\text{SOT-lim \,}}V_{n}$

where $V_{n}=U_{1}\cdots U_{n}$ are unitary and each $U_{j}$ is a Householder
transformation.

###  2.2 The IQR algorithm

Let $T\in\mathcal{B}(\mathcal{H})$ be invertible and let $\\{e_{j}\\}$ be an
orthonormal basis for $\mathcal{H}$. By Theorem 2.2 we have $T=QR,$ where $Q$
is an isometry and $R$ is upper triangular with respect to $\\{e_{j}\\}.$
Since $T$ is invertible, $Q$ is in fact unitary. Consider the following
construction of unitary operators $\\{\hat{Q}_{k}\\}$ and upper triangular
(w.r.t. $\\{e_{j}\\}$) operators $\\{\hat{R}_{k}\\}.$ Let $T=Q_{1}R_{1}$ be a
QR decomposition of $T$ and define $T_{1}=R_{1}Q_{1}.$ Then QR factorize
$T_{1}=Q_{2}R_{2}$ and define $T_{2}=R_{2}Q_{2}.$ The recursive procedure
becomes

$T_{m-1}=Q_{m}R_{m},\quad T_{m}=R_{m}Q_{m}.$ (2.3)

Now define

$\hat{Q}_{m}=Q_{1}Q_{2}\ldots Q_{m},\quad\hat{R}_{m}=R_{m}R_{m-1}\ldots
R_{1}.$ (2.4)

This is known as the QR algorithm and is completely analogous to the finite
dimensional case. Note also that we have $T_{n}=\hat{Q}^{*}_{n}T\hat{Q}_{n}.$
In the finite dimensional case and under favourable conditions
$\hat{Q}_{n}^{*}T\hat{Q}_{n}$ converges to a diagonal operator and the columns
of $\hat{Q}_{n}$ converge to the corresponding eigenvectors as
$n\rightarrow\infty$ (see Theorem 3.1 below). We will see that the IQR
algorithm behaves similarly for the extreme parts of the spectrum.

######  Definition 2.3.

Let $T\in\mathcal{B}(\mathcal{H})$ be invertible and let $\\{e_{j}\\}$ be an
orthonormal basis for $\mathcal{H}$. The sequences $\\{\hat{Q}_{j}\\}$ and
$\\{\hat{R}_{j}\\}$ constructed as in (2.3) and (2.4) will be called a
$Q$-sequence and an $R$-sequence of $T$ with respect to $\\{e_{j}\\}.$

  * Remark 2.4

Note that since the Householder transformations used in the proof of Theorem
2.2 are unique up to a $\pm$ sign, we will with some abuse of language refer
to the QR decomposition constructed as the QR decomposition. In general for an
invertible operator, the IQR algorithm is uniquely defined up to phase - see
Section 4.2. This will not be a problem for our theorems or numerical
examples.

The following observation will be useful in the later developments. From the
construction in (2.3) and (2.4) we get

$T=Q_{1}R_{1}=\hat{Q}_{1}\hat{R}_{1},$
$T^{2}=Q_{1}R_{1}Q_{1}R_{1}=Q_{1}Q_{2}R_{2}R_{1}=\hat{Q}_{2}\hat{R}_{2},$
$T^{3}=Q_{1}R_{1}Q_{1}R_{1}Q_{1}R_{1}=Q_{1}Q_{2}R_{2}Q_{2}R_{2}R_{1}=Q_{1}Q_{2}Q_{3}R_{3}R_{2}R_{1}=\hat{Q}_{3}\hat{R}_{3}.$

An easy induction gives us that

$T^{m}=\hat{Q}_{m}\hat{R}_{m}.$ (2.5)

Note that $\hat{R}_{m}$ must be upper triangular with respect to
$\\{e_{j}\\}_{j\in\mathbb{N}}$ since $R_{j},\,j\leq m$ is upper triangular
with respect to $\\{e_{j}\\}_{j\in\mathbb{N}}.$ Also, if $T$ is invertible
then $\langle Re_{i},e_{i}\rangle\neq 0.$ From this it follows immediately
that

$\mathrm{span}\\{T^{m}e_{j}\\}_{j=1}^{J}=\mathrm{span}\\{\hat{Q}_{m}e_{j}\\}_{j=1}^{J},\quad
J\in\mathbb{N}.$ (2.6)

##  3 Convergence theorems

In finite dimensions we have the following well known theorem:

######  Theorem 3.1 (Finite dimensions).

Let $T\in\mathbb{C}^{N\times N}$ be a normal matrix with eigenvalues
satisfying $|\lambda_{1}|>\ldots>|\lambda_{N}|$. Let $\\{Q_{m}\\}$ be a
$Q$-sequence of unitary operators. Then (up to re-ordering of the basis)

$Q^{*}_{m}TQ_{m}\longrightarrow\bigoplus_{j=1}^{N}\lambda_{j}e_{j}\otimes
e_{j},\qquad\text{as }m\rightarrow\infty.$

In this section we will address the convergence of the IQR algorithm for
normal operators under similar assumptions and prove an analogue of Theorem
3.1 in infinite dimensions (Theorem 3.9). As well as this, and for more
general operators $T$ that aren’t necessarily normal, we address block
convergence (Theorem 3.13), relevant when the eigenvalues do not have distinct
moduli, and convergence to (dominant) invariant subspaces (Theorem 3.15).

###  3.1 Preliminary definitions and results

To state and prove our theorems we need some preliminary results. The reader
only interested in the results themselves is referred to Section 3.2. If $T$
is a normal operator, we will use $\chi_{S}(T)$ to denote the indicator
function of the set $S$ defined via the functional calculus. Without loss of
generality, we deal with the Hilbert space $\mathcal{H}=l^{2}(\mathbb{N})$ and
the canonical orthonormal basis $\\{e_{j}\\}_{j\in\mathbb{N}}$. Our first set
of results concerns convergence of spanning sets under power iterations and is
analogous to the finite dimensional case. The following proposition can be
found in [40] and together with Lemma 3.6 below, these are the only results we
will use from [40].

######  Proposition 3.2.

Suppose that $T\in\mathcal{B}(\mathcal{H})$ is normal, is invertible and that
$\sigma(T)=\omega\cup\Psi$ is a disjoint union such that
$\omega=\\{\lambda_{i}\\}_{i=1}^{N}$ consists of finitely many isolated
eigenvalues of $T$ with
$\left|\lambda_{1}\right|>\left|\lambda_{2}\right|>...>\left|\lambda_{N}\right|$.
Suppose further that
$\mathrm{sup}\\{\left|z\right|:z\in\Psi\\}<\left|\lambda_{N}\right|$. Let
$l\in\mathbb{N}$ and suppose that $\\{\xi_{i}\\}_{i=1}^{l}$ are linearly
independent vectors in $\mathcal{H}$ such that
$\\{\chi_{\omega}(T)\xi_{i}\\}_{i=1}^{l}$ are also linearly independent. Then

  1. (i)

The vectors $\\{T^{k}\chi_{\omega}(T)\xi_{i}\\}_{i=1}^{l}$ are linearly
independent and there exists an $l$-dimensional subspace
$B\subset\mathrm{ran}\chi_{\omega}(T)$ such that

$\mathrm{span}\\{T^{k}\xi_{i}\\}_{i=1}^{l}\rightarrow B,\quad\text{as
}k\rightarrow\infty.$

  2. (ii)

If

$\mathrm{span}\\{T^{k}\xi_{i}\\}_{i=1}^{l-1}\rightarrow
D\subset\mathcal{H},\quad\text{as }k\rightarrow\infty,$

where $D$ is an $(l-1)$-dimensional subspace, then

$\mathrm{span}\\{T^{k}\xi_{i}\\}_{i=1}^{l}\rightarrow
D\oplus\mathrm{span}\\{\xi\\},\quad\text{as }k\rightarrow\infty,$

where $\xi\in\mathrm{ran}\chi_{\omega}(T)$ is an eigenvector of $T$.

In order to extend this proposition to describe rates of convergence and prove
our main theorems, we need to describe the space $B$ in more detail. This is
done inductively as follows. The first step is to choose
$\nu_{1,1}\in\\{\lambda_{i}\\}_{i=1}^{N}$ of maximum modulus such that

$\mathrm{span}\\{\chi_{\nu_{1,1}}(T)\xi_{1}\\}\neq\\{0\\}.$

We then let $\xi_{1,1}$ be a linear multiple of $\xi_{1}$ such that
$\chi_{\nu_{1,1}}(T)\xi_{1,1}$ has norm one. Now suppose that at the $m$-th
stage we have constructed vectors $\\{\xi_{m,i}\\}_{i=1}^{m}$ with the same
linear span as $\\{\xi_{i}\\}_{i=1}^{m}$ and such that there exist
$\\{\nu_{m,j}\\}_{j=1}^{s_{m}}\subset\\{\lambda_{i}\\}_{i=1}^{N}$ with the
following properties. After re-ordering the vectors
$\\{\xi_{m,i}\\}_{i=1}^{m}$ if necessary, there exist integers
$0=k_{m,0}<k_{m,1}<k_{m,2}<...<k_{m,s_{m}}=m$ such that

  1. (1)

$\left|\nu_{m,s_{m}}\right|<\left|\nu_{m,s_{m}-1}\right|<...<\left|\nu_{m,1}\right|.$

  2. (2)

$\chi_{\lambda}(T)\xi_{m,i}=0$ if $i>k_{m,j}$ and
$\lambda\in\\{\lambda_{i}\\}_{i=1}^{N}$ has
$\left|\lambda\right|>\left|\nu_{m,j+1}\right|$.

  3. (3)

$\\{\chi_{\nu_{m,j}}(T)\xi_{m,i}\\}_{i=k_{m,j-1}+1}^{k_{m,j}}$ are
orthonormal.

We seek to add the space spanned by the vector $\xi_{m+1}$ whilst preserving
these properties.

First we deal with (2). Let $\eta_{m+1}\in\\{\lambda_{i}\\}_{i=1}^{N}$ be of
maximal modulus such that
$\chi_{\\{\lambda_{1},...,\eta_{m+1}\\}}(T)\xi_{m+1}\notin\mathrm{span}\\{\chi_{\\{\lambda_{1},...,\eta_{m+1}\\}}(T)\xi_{j}\\}_{j=1}^{m}$.
If $\left|\eta_{m+1}\right|<\left|\nu_{m,1}\right|$ then let $t({m+1})$ be
maximal such that $\left|\eta_{m+1}\right|<\left|\nu_{m,t({m+1})}\right|$. We
then choose complex numbers $\\{a_{m,j}\\}_{j=1}^{k_{m,t({m+1})}}$ such that
writing

$\tilde{\xi}_{m+1,m+1}=\xi_{m+1}+\sum_{j=1}^{k_{m,t({m+1})}}a_{m,j}\xi_{m,j}$

we have that $\chi_{\lambda}(T)\tilde{\xi}_{m+1,m+1}=0$ if
$\lambda\in\\{\lambda_{i}\\}_{i=1}^{N}$ has
$\left|\lambda\right|>\left|\eta_{m+1}\right|$. Note that by (2), (3) and the
definition of $\eta_{m+1}$, the coefficients $a_{m,j}$ are determined uniquely
in terms of $\\{\xi_{m,i}\\}_{i=1}^{k_{m,t({m+1})}}$. If
$\left|\eta_{m+1}\right|\geq\left|\nu_{m,1}\right|$ then let $t({m+1})=0$ and
we set $\tilde{\xi}_{m+1,m+1}=\xi_{m+1}$. In this case we still have that
$\chi_{\lambda}(T)\tilde{\xi}_{m+1,m+1}=0$ if
$\lambda\in\\{\lambda_{i}\\}_{i=1}^{N}$ has
$\left|\lambda\right|>\left|\eta_{m+1}\right|$.

We then define $\xi_{m+1,j}=\xi_{m,j}$ for $1\leq j\leq m$ and now deal with
(3). If $\eta_{m+1}\notin\\{\nu_{m,j}\\}_{j=1}^{s_{m}}$ then let
$\xi_{m+1,m+1}$ be a linear multiple of $\tilde{\xi}_{m+1,m+1}$ such that
$\chi_{\eta_{m+1}}(T)\xi_{m+1,m+1}$ has norm 1 and we let
$\\{\nu_{m+1,j}\\}_{j=1}^{s_{m}+1}$ be a re-ordering of
$\\{\nu_{m,j}\\}_{j=1}^{s_{m}}\cup\\{\eta_{m+1}\\}$. Otherwise, we have
$\eta_{m+1}=\nu_{m,t({m+1})+1}$ and we apply Gram-Schmidt to

$\\{\chi_{\nu_{m,t({m+1})+1}}(T)\xi_{m+1,i}\\}_{i=k_{m,t({m+1})}+1}^{k_{m,t({m+1})+1}}\cup\\{\chi_{\nu_{m,t({m+1})+1}}(T)\tilde{\xi}_{m+1,m+1}\\}$

(without changing
$\\{\xi_{m+1,i}\\}_{i=k_{m,t({m+1})}+1}^{k_{m,t({m+1})+1}}$). Note that by (2)
and the definition of $\eta_{m+1}$ these vectors are linearly independent.
This gives $\xi_{m+1,m+1}$ such that

$\\{\chi_{\nu_{m,t({m+1})+1}}(T)\xi_{m+1,i}\\}_{i=k_{m,t({m+1})}+1}^{k_{m,t({m+1})+1}}\cup\\{\chi_{\nu_{m,t({m+1})+1}}(T)\xi_{m+1,m+1}\\}$

are orthonormal and $\chi_{\lambda}(T)\xi_{m+1,m+1}=0$ if
$\lambda\in\\{\lambda_{i}\\}_{i=1}^{N}$ has
$\left|\lambda\right|>\left|\nu_{m,t({m+1})+1}\right|.$ After re-ordering
indices if necessary, we see that (1)-(3) now hold for $m+1$.

After $l$ steps the above process terminates giving a new basis
$\\{\tilde{\xi}_{i}\\}_{i=1}^{l}=\\{\xi_{l,i}\\}_{i=1}^{l}$ for
$\mathrm{span}\\{\xi_{i}\\}_{i=1}^{l}$ along with
$\\{\nu_{j}\\}_{j=1}^{n}=\\{\nu_{l,j}\\}_{j=1}^{n}\subset\\{\lambda_{i}\\}_{i=1}^{N}$
and $0=k_{0}<k_{1}<k_{2}<...<k_{n}=l$ such that

  1. (i)

$\left|\nu_{n}\right|<\left|\nu_{n-1}\right|<...<\left|\nu_{1}\right|.$

  2. (ii)

$\chi_{\lambda}(T)\tilde{\xi}_{i}=0$ if $i>k_{j}$ and
$\lambda\in\\{\lambda_{i}\\}_{i=1}^{N}$ has
$\left|\lambda\right|>\left|\nu_{j+1}\right|$.

  3. (iii)

$\\{\chi_{\nu_{j}}(T)\tilde{\xi}_{i}\\}_{i=k_{j-1}+1}^{k_{j}}$ are
orthonormal.

The subspace $B$ can then be described as

$B=\bigoplus_{j=1}^{n}\mathrm{span}\\{\chi_{\nu_{j}}(T)\tilde{\xi}_{i}\\}_{i=k_{j-1}+1}^{k_{j}}.$

######  Definition 3.3.

With respect to the above construction we define the following:

$E_{j}:=\mathrm{span}\\{\chi_{\nu_{j}}(T)\tilde{\xi}_{i}\\}_{i=k_{j-1}+1}^{k_{j}},\quad
Z(T,\\{\xi_{j}\\}_{j=1}^{l}):=\Big{(}\sum_{i=1}^{l}(\|\tilde{\xi}_{i}\|^{2}-1)\Big{)}^{\frac{1}{2}}.$
(3.1)

Since the Gram-Schmidt process is defined uniquely up to phases we see that
$Z(T,\\{\xi_{j}\\}_{j=1}^{l})$ is well-defined. The above construction also
shows that if $\\{\chi_{\omega}(T)\xi_{i}\\}_{i=1}^{l+1}$ are linearly
independent then

$Z(T,\\{\xi_{j}\\}_{j=1}^{l+1})\geq Z(T,\\{\xi_{j}\\}_{j=1}^{l}).$

We can now prove the following refinement of Proposition 3.2:

######  Proposition 3.4.

Suppose the assumptions of Proposition 3.2 hold. Let $J\leq N$ be minimal such
that $\\{\chi_{\\{\lambda_{1},...,\lambda_{J}\\}}(T)\xi_{i}\\}_{i=1}^{l}$ are
linearly independent. Set

$\displaystyle\rho$
$\displaystyle=\mathrm{sup}\\{\left|z\right|:z\in\Psi\cup\\{\lambda_{J+1},...,\lambda_{N}\\}\\},$
$\displaystyle r$
$\displaystyle=\max\\{\left|\lambda_{2}/\lambda_{1}\right|,...,\left|\lambda_{J}/\lambda_{J-1}\right|,\rho/\left|\lambda_{J}\right|\\}.$

Then $r<1$ and ${\delta}(B,\mathrm{span}\\{T^{k}\xi_{i}\\}_{i=1}^{l})\leq
Z(T,\\{\xi_{j}\\}_{j=1}^{l})r^{k}$. Since the spaces are $l$-dimensional, it
follows from (1.5) that we have the convergence rate

$\hat{\delta}(B,\mathrm{span}\\{T^{k}\xi_{i}\\}_{i=1}^{l})\leq
Z(T,\\{\xi_{j}\\}_{j=1}^{l})l^{\frac{1}{2}}r^{k}.$

###### Proof.

Consider the subspaces

$E_{j}^{k}=\mathrm{span}\\{T^{k}\tilde{\xi}_{i}\\}_{i=k_{j-1}+1}^{k_{j}}.$

Let
$\zeta=\sum_{i=k_{j-1}+1}^{k_{j}}\alpha_{i}\chi_{\nu_{j}}(T)\tilde{\xi}_{i}\in
E_{j}$ be a unit vector (hence
$\sum_{i=k_{j-1}+1}^{k_{j}}\left|\alpha_{i}\right|^{2}=1$) and consider

$\eta_{k}=\sum_{i=k_{j-1}+1}^{k_{j}}\alpha_{i}T^{k}\tilde{\xi}_{i}/\nu^{k}_{j}\in
E_{j}^{k}.$

By construction, we have for any such $\tilde{\xi}_{i}$ in the above sum that

$\tilde{\xi}_{i}=(\chi_{\nu_{j}}(T)+\chi_{\theta_{j}}(T))\tilde{\xi}_{i},\qquad\theta_{j}=\\{\lambda\in\sigma(T):|\lambda|<|\nu_{j}|\\}.$

This gives
$T^{k}\tilde{\xi}_{i}=\nu^{k}_{j}\chi_{\nu_{j}}(T)\tilde{\xi}_{j,i}+T^{k}\chi_{\theta_{j}}(T)\tilde{\xi}_{i}.$
Now, by the assumption on $\sigma(T),$ we have

$\rho_{j}=\sup\\{|z|:z\in\theta_{j}\\}<|\nu_{j}|.$

Thus, since

$\|T^{k}\chi_{\theta_{j}}(T)\tilde{\xi}_{i}\|/|\nu_{j}^{k}|<|\rho_{j}/\nu_{j}|^{k}\|\chi_{\theta_{j}}(T)\tilde{\xi}_{i}\|,$

we have

$\left\|\zeta-\eta_{k}\right\|\leq|\rho_{j}/\nu_{j}|^{k}\sum_{i=k_{j-1}+1}^{k_{j}}\left|\alpha_{i}\right|\|\chi_{\theta_{j}}(T)\tilde{\xi}_{i}\|\leq\Big{(}\sum_{i=k_{j-1}+1}^{k_{j}}(\|\tilde{\xi}_{i}\|^{2}-1)\Big{)}^{\frac{1}{2}}r^{k}.$

Here we have used Hölder’s inequality together with the fact that
$\|\chi_{\theta_{j}}(T)\tilde{\xi}_{i}\|^{2}=\|\tilde{\xi}_{i}\|^{2}-1$ by
orthonormality of
$\\{\chi_{\nu_{j}}(T)\tilde{\xi}_{i}\\}_{i=k_{j-1}+1}^{k_{j}}$. The right hand
side gives an upper bound for $\delta(E_{j},E_{j}^{k})$. Analogous rates of
convergence hold for the other subspaces and from (1.6) we have

$\delta(B,\mathrm{span}\\{T^{k}\tilde{\xi}_{i}\\}_{i=1}^{l})\leq
Z(T,\\{\xi_{j}\\}_{j=1}^{l})r^{k},$ (3.2)

since the spaces $E_{j}$ are orthogonal. ∎

For the rest of this section we shall assume the following:

(A1) $T\in\mathcal{B}(\mathcal{H})$ is an invertible normal operator and
$\\{e_{j}\\}_{j\in\mathbb{N}}$ an orthonormal basis for $\mathcal{H}$.
$\\{Q_{k}\\}$ and $\\{R_{k}\\}$ are $Q$\- and $R$-sequences of $T$ with
respect to the basis $\\{e_{j}\\}_{j\in\mathbb{N}}.$ (A2)
$\sigma(T)=\omega\cup\Psi$ such that $\omega\cap\Psi=\emptyset$ and
$\omega=\\{\lambda_{i}\\}_{i=1}^{N},$ where the $\lambda_{i}$s are isolated
eigenvalues with (possibly infinite) multiplicity $m_{i}$. Let
$M=m_{1}+...+m_{N}=\mathrm{dim}(\mathrm{ran}\chi_{\omega}(T))$ and suppose
that $|\lambda_{1}|>\ldots>|\lambda_{N}|.$ Suppose further that
$\sup\\{|\theta|:\theta\in\Psi\\}<|\lambda_{N}|.$

To apply Propositions 3.2 and 3.4 to prove the main result Theorem 3.9, we
need to take care of the case that some of the $e_{j}$ may have
$\chi_{\omega}(T)e_{j}=0$.

######  Definition 3.5.

Suppose that (A1) and (A2) hold and let $K\in\mathbb{N}\cup\\{\infty\\}$ be
minimal with the property that
$\dim(\mathrm{span}\\{\chi_{\omega}(T)e_{j}\\}_{j=1}^{K})=M.$ Define

$\displaystyle\Lambda_{\omega}=\\{e_{j}:\chi_{\omega}(T)e_{j}\neq 0,j\leq
K\\},$ $\displaystyle\Lambda_{\Psi}=\\{e_{j}:\chi_{\omega}(T)e_{j}=0,j\leq
K\\},$
$\displaystyle\tilde{\Lambda}_{\omega}=\\{e_{j}\in\Lambda_{\omega}:\chi_{\omega}(T)e_{j}\in\mathrm{span}\\{\chi_{\omega}(T)e_{i}\\}_{i=1}^{j-1}\\}.$

Define also the corresponding subset
$\\{\hat{e}_{j}\\}_{j=1}^{M}\subset\\{e_{j}\\}_{j=1}^{K}$ such that
$\\{\hat{e}_{j}\\}_{j=1}^{M}=\Lambda_{\omega}\setminus\tilde{\Lambda}_{\omega}$
and such that writing $\hat{e}_{j}=e_{p_{j}}$, the $p_{j}$ are increasing.

Note that we have the following decomposition of $T$ into

$T=\left(\sum_{j=1}^{M}\lambda_{c_{j}}\,\xi_{j}\otimes\bar{\xi}_{j}\right)\oplus\chi_{\Psi}(T)T,\quad\lambda_{c_{j}}\in\omega,$

where $\\{\xi_{j}\\}_{j=1}^{M}$ is an orthonormal set of eigenvectors of $T$.
The following simple lemma extends Lemma 39 in [40] to infinite $M$ but the
proof is verbatim so omitted.

######  Lemma 3.6.

If $e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega},$ then

$\mathrm{span}\\{\chi_{\omega}(T)q_{k,j}\\}_{j=1}^{m}=\mathrm{span}\\{\chi_{\omega}(T)\hat{q}_{k,j}\\}_{j=1}^{s(m)},\quad
q_{k,j}=Q_{k}e_{j},\quad\hat{q}_{k,j}=Q_{k}\hat{e}_{j},$

where $s(m)$ is the largest integer such that
$\\{\hat{e}_{j}\\}_{j=1}^{s(m)}\subset\\{e_{j}\\}_{j=1}^{m}.$

The following theorem is the key step of the proof of Theorem 3.9 and concerns
convergence to the eigenvectors of $T$.

######  Theorem 3.7.

Assume (A1) and (A2) and define

$\rho=\mathrm{sup}\\{\left|z\right|:z\in\Psi\\},\quad
r=\max\\{\left|\lambda_{2}/\lambda_{1}\right|,...,\left|\lambda_{N}/\lambda_{N-1}\right|,\rho/\left|\lambda_{N}\right|\\}.$

Then there exists a collection of orthonormal eigenvectors
$\\{\hat{q}_{j}\\}_{j=1}^{M}\subset\mathrm{ran}\chi_{\omega}(T)$ of $\ T$ and
collections of constants $A(m)$, $B(j)$ and $C(\mu)$ such that

  1. (a)

If $e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega}$ and $\mu$ is maximal
with $p_{\mu}<m$ (recall that $\hat{e}_{j}=e_{p_{j}}$), then we have

$\left\|\chi_{\omega}(T)q_{k,m}\right\|\leq
A(m)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}.$ (3.3)

In the case that $m<p_{1}$, we interpret this as
$\left\|\chi_{\omega}(T)q_{k,m}\right\|=0$ which holds from Lemma 3.6.

  2. (b)

For any $j<M+1$,

$\hat{\delta}(\mathrm{span}\\{\hat{q}_{j}\\},\mathrm{span}\\{\hat{q}_{k,j}\\})\leq
B(j)Z(T,\\{\hat{e}_{i}\\}_{i=1}^{j})r^{k}.$ (3.4)

  3. (c)

For any $\mu<M+1$,

$\delta(\mathrm{span}\\{\hat{q}_{j,k}\\}_{j=1}^{\mu},\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu})\leq
C(\mu)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}$ (3.5)

and hence

$\hat{\delta}(\mathrm{span}\\{\hat{q}_{j,k}\\}_{j=1}^{\mu},\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu})\leq\mu^{\frac{1}{2}}C(\mu)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}.$
(3.6)

Here, as in Lemma 3.6, $q_{k,j}=Q_{k}e_{j}$ and
$\hat{q}_{k,j}=Q_{k}\hat{e}_{j}$. Finally, if $M$ is finite then we must have
$\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{M}=\mathrm{ran}\chi_{\omega}(T).$

We will provide an inductive proof of Theorem 3.7 which requires the following
for the inductive step of part (a).

######  Lemma 3.8.

Assume the conditions in the statement of Theorem 3.7. Suppose also that (b)
in Theorem 3.7 holds for $j=1,...,\mu$ and that (c) holds for a given $\mu<M$.
Let $e_{p_{\mu+1}}=\hat{e}_{\mu+1}$, then if
$e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega},$ where $m<p_{\mu+1}$,
(3.3) also holds with

$A(m)=\Big{\\{}\sum_{j=1}^{\mu}\big{[}C(\mu)+B(j)\big{]}^{2}\Big{\\}}^{\frac{1}{2}}+C(\mu).$

###### Proof.

First note that from (2.6), invertibility of $T$ and the fact that
$\\{\chi_{\omega}(T)\hat{e}_{j}\\}_{j=1}^{\mu}$ are linearly independent, it
must hold that $\\{\chi_{\omega}(T)\hat{q}_{k,j}\\}_{j=1}^{\mu}$ are linearly
independent also. Then by using the assumptions stated and the fact that
$\chi_{\omega}(T)\hat{q}_{j}=\hat{q}_{j}$ we have

$\displaystyle\delta(\mathrm{span}\\{\chi_{\omega}(T)\hat{q}_{k,j}\\}_{j=1}^{\mu},\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu})$
$\displaystyle\leq\delta(\mathrm{span}\\{\hat{q}_{k,j}\\}_{j=1}^{\mu},\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu})$
$\displaystyle\leq C(\mu)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}.$

Also, we have that $s(m)\leq\mu$ and Lemma 3.6 implies

$\mathrm{span}\\{\chi_{\omega}(T)q_{k,j}\\}_{j=1}^{m}=\mathrm{span}\\{\chi_{\omega}(T)\hat{q}_{k,j}\\}_{j=1}^{s(m)}\subset\mathrm{span}\\{\chi_{\omega}(T)\hat{q}_{k,j}\\}_{j=1}^{\mu}.$

Using the fact that $\left\|\chi_{\omega}(T)q_{k,m}\right\|\leq 1$ and the
definition of $\delta$ (along with the fact that
$\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu}$ is finite dimensional), it
follows that there exists some
$v_{k}=\sum_{j=1}^{\mu}\beta_{j,k}{\hat{q}_{j}}\in\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{\mu}$
with $\left\|v_{k}\right\|\leq 1$ and

$\left\|\chi_{\omega}(T)q_{k,m}-v_{k}\right\|\leq
C(\mu)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}.$ (3.7)

We also have from assumption (b) that

$\left|\langle\chi_{\omega}(T)q_{k,m},\hat{q}_{j}\rangle\right|=\left|\langle
q_{k,m},\hat{q}_{j}\rangle\right|\leq
B(j)Z(T,\\{\hat{e}_{i}\\}_{i=1}^{j})r^{k}+\left|\langle
q_{k,m},\hat{q}_{k,j}\rangle\right|=B(j)Z(T,\\{\hat{e}_{i}\\}_{i=1}^{j})r^{k},$
(3.8)

since $q_{k,m}$ is orthogonal to $\hat{q}_{k,j}$. This together with (3.7)
gives that
$\left|\beta_{j,k}\right|\leq\big{[}C(\mu)+B(j)\big{]}Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}$.
Hence we must have

$\left\|v_{k}\right\|\leq\Big{\\{}\sum_{j=1}^{\mu}\big{[}C(\mu)+B(j)\big{]}^{2}\Big{\\}}^{\frac{1}{2}}Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}.$

Using (3.7) again then gives the result. Note that we have used orthonormality
of $\\{\hat{q}_{j}\\}_{j=1}^{\mu}$ which will be proven as part of the
induction. ∎

###### Proof of Theorem 3.7:.

We begin with the initial step of the induction for (b) and (c). Note that (a)
trivially holds by construction with $A(m)=0$ for any $m<p_{1}$ where
$e_{p_{1}}=\hat{e}_{1}$ and this provides the initial step for (a).

By Propositions 3.2 and 3.4, there exists a unit eigenvector
$\hat{q}_{1}\in\mathrm{ran}\chi_{\omega}(T)$ such that

$\delta(\mathrm{span}\\{\hat{q}_{1}\\},\mathrm{span}\\{T^{k}\hat{e}_{1}\\})\leq
Z(T,\\{\hat{e}_{1}\\})r^{k}.$

Since
$\mathrm{span}\\{T^{k}\hat{e}_{1}\\}\subset\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{1}}$,
this implies that

$\delta(\mathrm{span}\\{\hat{q}_{1}\\},\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{1}})\leq
Z(T,\\{\hat{e}_{1}\\})r^{k}.$

Thus, it follows that

$\delta(\mathrm{span}\\{\hat{q}_{1}\\},\mathrm{span}\\{q_{k,i}\\}_{i=1}^{p_{1}})=\delta(\mathrm{span}\\{\hat{q}_{1}\\},\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{1}})\leq
Z(T,\\{\hat{e}_{1}\\})r^{k},$ (3.9)

from (2.6). Note that $\\{q_{k,i}\\}_{i=1}^{p_{1}}$ are orthonormal (recall
that $Q_{k}$ is unitary) and hence by (3.9) there exists some coefficients
$\alpha_{k,i}$ with $\sum_{i=1}^{p_{1}}|\alpha_{k,i}|^{2}\leq 1$ such that
defining $\tilde{\eta}_{k}=\sum_{i=1}^{p_{1}}\alpha_{k,i}q_{k,i}$ we have

$\left\|\hat{q}_{1}-\tilde{\eta}_{k}\right\|\leq Z(T,\\{\hat{e}_{1}\\})r^{k}.$
(3.10)

If $e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega},$ where $m<{p_{1}}$
then by Lemma 3.6 $\langle q_{k,m},\hat{q}_{1}\rangle=0$. It follows that we
must have

$\delta(\mathrm{span}\\{\hat{q}_{1}\\},\mathrm{span}\\{\hat{q}_{k,1}\\})\leq\left\|\hat{q}_{1}-\alpha_{k,p_{1}}\hat{q}_{k,1}\right\|\leq
Z(T,\\{\hat{e}_{1}\\})r^{k}.$

Hence we can take $B(1)=1$ and $C(1)=1$ in (b) and (c) respectively which
completes the initial step.

For the induction step we will argue simultaneously for (a), (b) and (c) using
induction on $\mu$. Suppose that (a) holds for $m<p_{\mu}$ with
$e_{p_{\mu}}=\hat{e}_{\mu}$ together with (b) and (c) for $j\leq\mu$ and some
$\mu<M$. Let $e_{p_{\mu+1}}=\hat{e}_{\mu+1}$ then we can use Lemma 3.8 to
extend (a) to all $m<p_{\mu+1}$ and this provides the step for (a). For (b),
we note that Propositions 3.2 and 3.4 imply that

$\delta(\mathrm{span}\\{\hat{q}_{i}\\}_{i=1}^{\mu}\oplus\mathrm{span}\\{\xi\\},\mathrm{span}\\{T^{k}\hat{e}_{i}\\}_{i=1}^{\mu+1},)\leq
Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k},\quad\xi\in\mathrm{ran}\chi_{\omega}(T),$
(3.11)

where $\xi$ is a unit eigenvector of $T.$ We may also assume without loss of
generality that $\xi$ is orthogonal to $\hat{q}_{j}$ for $j=1,...,\mu$. As
before, since
$\mathrm{span}\\{T^{k}\hat{e}_{i}\\}_{i=1}^{\mu+1}\subset\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{\mu+1}}$
we have

$\delta(\mathrm{span}\\{\hat{q}_{i}\\}_{i=1}^{\mu}\oplus\mathrm{span}\\{\xi\\},\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{\mu+1}})\leq
Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k},$

and hence by invertibility of $T$

$\begin{split}\delta(\mathrm{span}\\{\hat{q}_{i}\\}_{i=1}^{\mu}\oplus\mathrm{span}\\{\xi\\},\mathrm{span}\\{q_{k,i}\\}_{i=1}^{p_{\mu+1}})&=\delta(\mathrm{span}\\{\hat{q}_{i}\\}_{i=1}^{\mu}\oplus\mathrm{span}\\{\xi\\},\mathrm{span}\\{T^{k}e_{i}\\}_{i=1}^{p_{\mu+1}})\\\
&\leq Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}.\end{split}$ (3.12)

Again, using that$\\{q_{k,i}\\}_{i=1}^{p_{\mu+1}}$ are orthonormal, there
exists some coefficients $\alpha_{k,i}$ with
$\sum_{i=1}^{p_{\mu+1}}|\alpha_{k,i}|^{2}\leq 1$ such that defining
$\tilde{\eta}_{k}=\sum_{i=1}^{p_{\mu+1}}\alpha_{k,i}q_{k,i}$ we have

$\left\|\xi-\tilde{\eta}_{k}\right\|\leq
Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}.$ (3.13)

If $e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega},$ where $m<{p_{\mu+1}}$
then as shown above we have

$\left|\langle
q_{k,m},\xi\rangle\right|=\left|\langle\chi_{\omega}(T)q_{k,m},\xi\rangle\right|\leq
A(m)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}\leq
A(m)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}.$

Taking the inner product of $\xi-\tilde{\eta}_{k}$ with $q_{k,m}$ and using
(3.13) together with the orthonormality of the $q_{k,j}$s, it follows that
$\left|\alpha_{k,m}\right|\leq\big{(}A(m)+1\big{)}Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}$.
Similarly, if $j\leq\mu$ then for any $c\in\mathbb{C}$

$\left|\langle\hat{q}_{k,j},\xi\rangle\right|\leq\left|\langle
c\hat{q}_{j},\xi\rangle\right|+\left|c\hat{q}_{j}-\hat{q}_{k,j}\right|=\left|c\hat{q}_{j}-\hat{q}_{k,j}\right|,$

since $\xi$ is orthogonal to $\hat{q}_{j}$. Minimising over $c$, we can bound
this by $B(j)Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu})r^{k}$. In the same way, it
then follows that
$|\alpha_{k,p_{j}}|\leq\big{(}B(j)+1\big{)}Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}$
where $\hat{e}_{j}=e_{p_{j}}$. Together, these imply that

$\left\|\xi-\alpha_{k,p_{\mu+1}}\hat{q}_{k,\mu+1}\right\|\leq\Big{[}1+\Big{\\{}\sum_{m=1,e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega}}^{p_{\mu+1}}\big{[}A(m)+1\big{]}^{2}+\sum_{j=1}^{\mu}\big{[}B(j)+1\big{]}^{2}\Big{\\}}^{\frac{1}{2}}\Big{]}Z(T,\\{\hat{e}_{j}\\}_{j=1}^{\mu+1})r^{k}.$

To finish the inductive step, we define $\hat{q}_{\mu+1}=\xi$. Recall that
$\xi$ is orthogonal to any $\hat{q}_{l}$ with $l\leq\mu$. Hence it follows
that $\\{\hat{q}_{i}\\}_{i=1}^{\mu+1}$ are orthonormal and we can take

$B(\mu+1)=1+\Big{\\{}\sum_{m=1,e_{m}\in\Lambda_{\Psi}\cup\tilde{\Lambda}_{\omega}}^{p_{\mu+1}}\big{[}A(m)+1\big{]}^{2}+\sum_{j=1}^{\mu}\big{[}B(j)+1\big{]}^{2}\Big{\\}}^{\frac{1}{2}}$

in (b). For the induction step for (c), the fact that
$\\{\hat{q}_{k,i}\\}_{i=1}^{\mu+1}$ are orthonormal and (1.6) imply we can
take

$C(\mu+1)=\Big{(}\sum_{j=1}^{\mu+1}B(j)^{2}\Big{)}^{\frac{1}{2}}.$

Finally, if $M$ is finite we demonstrate that
$\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{M}=\mathrm{span}\\{\xi_{j}\\}_{j=1}^{M}.$
Since the $\\{\hat{q}_{i}\\}_{i=1}^{M}$ are orthogonal and are eigenvectors of
$\sum_{j=1}^{M}\lambda_{c_{j}}\,\xi_{j}\otimes\bar{\xi}_{j}$ it follows that
$\mathrm{span}\\{\hat{q}_{j}\\}_{j=1}^{M}=\mathrm{span}\\{\xi_{j}\\}_{j=1}^{M}=\mathrm{ran}\chi_{\omega}(T).$
∎

###  3.2 Main Results

Our first result generalises Theorem 3.1 to infinite dimensions and relies on
Theorem 3.7 (which concerns convergence to eigenvectors).

######  Theorem 3.9 (Convergence theorem for normal operators in infinite
dimensions).

Let $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ be an invertible normal operator with
$\sigma(T)=\omega\cup\Psi$ and $\omega=\\{\lambda_{i}\\}_{i=1}^{N},$ where the
$\lambda_{i}$’s are isolated eigenvalues with (possibly infinite) multiplicity
$m_{i}$ satisfying $|\lambda_{1}|>\ldots>|\lambda_{N}|.$ Suppose further that
$\sup\\{|\theta|:\theta\in\Psi\\}<|\lambda_{N}|,$ and let
$\\{e_{j}\\}_{j\in\mathbb{N}}$ be the canonical orthonormal basis. Let
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ and $\\{R_{n}\\}_{n\in\mathbb{N}}$ be $Q$\- and
$R$-sequences of $T$ with respect to $\\{e_{j}\\}_{j\in\mathbb{N}}.$ Let
$\\{\hat{e}_{j}\\}_{j=1}^{M}\subset\\{e_{j}\\}_{j\in\mathbb{N}}$, where
$M=m_{1}+\ldots+m_{N}$, be the subset described in Definition 3.5 and Theorem
3.7, i.e.
$\mathrm{span}\\{Q_{k}\hat{e}_{j}\\}\rightarrow\mathrm{span}\\{\hat{q}_{j}\\}$
where $\\{\hat{q}_{j}\\}_{j=1}^{M}\subset\mathrm{ran}\chi_{\omega}(T)$ is a
collection of orthonormal eigenvectors of $T$ and if
$e_{j}\notin\\{\hat{e}_{j}\\}_{j=1}^{M},$ then
$\chi_{\omega}(T)Q_{k}e_{j}\rightarrow 0.$ Then:

  * (i)

Every subsequence of $\\{Q_{n}^{*}TQ_{n}\\}_{n\in\mathbb{N}}$ has a convergent
subsequence $\\{Q_{n_{k}}^{*}TQ_{n_{k}}\\}_{k\in\mathbb{N}}$ such that

$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{WOT}}}{{\longrightarrow}}\left(\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right)\bigoplus\sum_{j\in\Theta}\xi_{j}\otimes
e_{j},$

as $k\rightarrow\infty,$ where

$\Theta=\\{j:e_{j}\notin\\{\hat{e}_{l}\\}_{l=1}^{M}\\},\quad\xi_{j}\in\overline{\mathrm{span}\\{e_{i}\\}_{i\in\Theta}}$

and only $\sum_{j\in\Theta}\xi_{j}\otimes e_{j}$ depends on the choice of
subsequence. Furthermore, if $T$ has only finitely many non-zero entries in
each column then we can replace $WOT$ convergence by $SOT$ convergence.

  * (ii)

We have the following convergence of sections:

$\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}\stackrel{{\scriptstyle\text{SOT}}}{{\longrightarrow}}\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j},\qquad\text{as
}n\rightarrow\infty,$

where $\widehat{P}_{M}$ denotes the orthogonal projection onto
$\overline{\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}}$. Furthermore, if we
define

$\rho=\mathrm{sup}\\{\left|z\right|:z\in\Psi\\},\quad
r=\max\\{\left|\lambda_{2}/\lambda_{1}\right|,...,\left|\lambda_{N}/\lambda_{N-1}\right|,\rho/\left|\lambda_{N}\right|\\}$

then $r<1$ and for any fixed $x\in\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}$ we
have the following rate of convergence

$\left\|\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}x-\left(\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right)x\right\|=O(r^{n}),\quad\text{as
}n\rightarrow\infty.$ (3.14)

If $M$ is finite then we can write (after possibly re-ordering)

$\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}=\bigoplus_{k=1}^{N}\left(\lambda_{k}\bigoplus_{j=1+\sum_{l<k}m_{l}}^{\sum_{l\leq
k}m_{l}}\hat{e}_{j}\otimes\hat{e}_{j}\right),$ (3.15)

and in part (ii) we have the rate of convergence

$\left\|\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}-\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right\|=O(r^{n}),\quad\text{as
}n\rightarrow\infty.$ (3.16)

If $\\{\chi_{\omega}(T)e_{l}\\}_{l=1}^{M}$ are linearly independent, then we
can take $\hat{e}_{j}=e_{j}$.

  * Remark 3.10

What Theorem 3.9 essentially says is that if we take the $n$-th iteration of
the IQR algorithm and truncate to an $m\times m$ matrix (i.e.
$P_{m}Q_{n}^{*}TQ_{n}P_{m}$) then, as $n$ grows, the eigenvalues of this
matrix will converge to the extremal parts of the spectrum of $T$. In
particular, the theorem suggests that the IQR algorithm can locate the
extremal parts of the spectrum.

###### Proof of Theorem 3.9:.

To prove (i), since a closed ball in $\mathcal{B}(l^{2}(\mathbb{N}))$ is
weakly sequentially compact, it follows that that any subsequence of
$\\{Q_{n}^{*}TQ_{n}\\}_{n\in\mathbb{N}}$ must have a weakly convergent
subsequence $\\{Q_{n_{k}}^{*}TQ_{n_{k}}\\}_{k\in\mathbb{N}}$. In particular,
there exists a $W\in\mathcal{B}(l^{2}(\mathbb{N}))$ such that

$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{\scriptsize
WOT}}}{{\longrightarrow}}W,\qquad k\rightarrow\infty.$

Let $\widehat{P}_{M}$ denote the projection onto
$\overline{\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}}$. Note that part (i) of
the theorem will follow if we can show that

$\widehat{P}_{M}W\widehat{P}_{M}=\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j},$ (3.17)

and

$\widehat{P}_{M}^{\perp}W\widehat{P}_{M}=0,\quad\widehat{P}_{M}W\widehat{P}_{M}^{\perp}=0.$

We will indeed show this, and we start by observing that, due to the weak
convergence and the standard functional calculus, we have that

$\langle W\hat{e}_{j},e_{i}\rangle=\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}\hat{e}_{j},\chi_{\omega}(T)Q_{n_{k}}e_{i}\rangle+\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}\hat{e}_{j},\chi_{\Psi}(T)Q_{n_{k}}e_{i}\rangle,$ (3.18) $\langle
We_{i},\hat{e}_{j}\rangle=\lim_{k\rightarrow\infty}\langle\chi_{\omega}(T)Q_{n_{k}}e_{i},T^{*}Q_{n_{k}}\hat{e}_{j}\rangle+\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}e_{i},\chi_{\Psi}(T)Q_{n_{k}}\hat{e}_{j}\rangle.$ (3.19)

We then have the following

$\begin{split}&\chi_{\omega}(T)Q_{n}e_{i}\rightarrow 0,\quad
n\rightarrow\infty,\quad i\in\Theta\\\
&\qquad\qquad\Longrightarrow\quad\begin{cases}\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}\hat{e}_{j},\chi_{\omega}(T)Q_{n_{k}}e_{i}\rangle=0,&i\in\Theta,\\\
\lim_{k\rightarrow\infty}\langle\chi_{\omega}(T)Q_{n_{k}}e_{i},T^{*}Q_{n_{k}}\hat{e}_{j}\rangle=0,&i\in\Theta,\end{cases}\end{split}$
(3.20)
$\begin{split}&\mathrm{span}\\{Q_{n}\hat{e}_{j}\\}\rightarrow\mathrm{span}\\{\hat{q}_{j}\\},\quad
n\rightarrow\infty,\quad
T\hat{q}_{j}=\lambda\hat{q}_{j},\,\lambda\in\omega,\\\
&\qquad\qquad\Longrightarrow\quad\begin{cases}\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}\hat{e}_{j},\chi_{\Psi}(T)Q_{n_{k}}e_{i}\rangle=0,&i\in\mathbb{N},\\\
\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}e_{i},\chi_{\Psi}(T)Q_{n_{k}}\hat{e}_{j}\rangle=0,&i\in\mathbb{N},\\\
\lim_{k\rightarrow\infty}\langle
TQ_{n_{k}}\hat{e}_{j},\chi_{\omega}(T)Q_{n_{k}}\hat{e}_{l}\rangle=\delta_{j,l}\lambda.\end{cases}\end{split}$
(3.21)

Thus, by (3.18), (3.20), (3.21) and Theorem 3.7 we get (3.17) and also that
$\widehat{P}_{M}^{\perp}W\widehat{P}_{M}=0$. Also, by (3.19), (3.20), (3.21)
and Theorem 3.7 we get that $\widehat{P}_{M}W\widehat{P}_{M}^{\perp}=0$. Note
that in all of these cases, Theorem 3.7 implies that the rate of convergence
is such that the difference between $\langle W\hat{e}_{j},e_{i}\rangle$,
$\langle We_{i},\hat{e}_{j}\rangle$ and their limiting values is
$O(r^{n_{k}})$ (however, not necessarily uniformly over the indices). Now
suppose that $T$ has finitely many non-zero entries in each column. This can
be described by a function $f:\mathbb{N}\rightarrow\mathbb{N}$ non-decreasing
with $f(n)\geq n$ such that $\langle Te_{j},e_{i}\rangle=0$ when $i>f(j)$ as
in Definition 4.1. Proposition 4.2 shows that this is preserved under the
iteration in the IQR algorithm, i.e. $Q_{n_{k}}^{*}TQ_{n_{k}}$ also has this
property. So let $x\in l^{2}(\mathbb{N})$ and $\epsilon>0$. Choose $y$ of
finite support such that $\|x-y\|\leq\epsilon$. It is then clear that
$\|Q_{n_{k}}^{*}TQ_{n_{k}}y-Wy\|\rightarrow 0$ as $n_{k}\rightarrow\infty$
(since we only require convergence in finitely many entries). Hence

$\limsup_{n_{k}\rightarrow\infty}\|Q_{n_{k}}^{*}TQ_{n_{k}}x-Wx\|\leq(\|T\|+\|W\|)\epsilon.$

Since $\epsilon>0$ and $x$ were arbitrary we have
$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{\scriptsize
SOT}}}{{\longrightarrow}}W$.

To prove (ii), suppose that $x\in\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}$,
then $x$ can be written as

$x=\sum_{j=1}^{M}x_{j}\hat{e}_{j},$

with at most finitely many $x_{j}$ non-zero. We have that
$\hat{\delta}(\mathrm{span}\\{Q_{n}\hat{e}_{j}\\},\mathrm{span}\\{\hat{q}_{j}\\})=O(r^{n})$
and hence there exists some $a_{n,j}$ of unit modulus such that
$\left\|Q_{n}\hat{e}_{j}-a_{n,j}\hat{q}_{j}\right\|=O(r^{n})$. Since $Q_{n}$
is unitary we then have

$\displaystyle\left\|\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}x-\left(\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right)x\right\|$
$\displaystyle\leq\left\|Q_{n}^{*}TQ_{n}\widehat{P}_{M}x-\left(\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right)Q_{n}^{*}Q_{n}x\right\|$
$\displaystyle=\left\|\sum_{j=1}^{M}x_{j}(T-\langle
T\hat{q}_{j},\hat{q}_{j}\rangle I)Q_{n}\hat{e}_{j}\right\|=O(r^{n}),$

where we have used the fact that $T$ is bounded in the last line. We therefore
have convergence on $\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}$, and, since the
operators are uniformly bounded, we must have convergence on
$\overline{\mathrm{span}\\{\hat{e}_{j}\\}_{j=1}^{M}}$ which implies that

$\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}\stackrel{{\scriptstyle\text{SOT}}}{{\longrightarrow}}\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j},\qquad\text{as
}n\rightarrow\infty.$

For the last parts, suppose that $M$ is finite. Theorem 3.7 then implies
(3.15) after a possible re-ordering. The rate of convergence in (3.14) also
implies that

$\left\|\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}-\bigoplus_{j=1}^{M}\langle
T\hat{q}_{j},\hat{q}_{j}\rangle\hat{e}_{j}\otimes\hat{e}_{j}\right\|=O(r^{n}).$

More generally, let $K\in\mathbb{N}\cup\\{\infty\\}$ be minimal such that
$\dim(\mathrm{span}\\{\chi_{\omega}(T)e_{j}\\}_{j=1}^{K})=M.$ Recall that we
defined

$\displaystyle\Lambda_{\omega}=\\{e_{j}:\chi_{\omega}(T)e_{j}\neq 0,j\leq
K\\},\quad\Lambda_{\Psi}=\\{e_{j}:\chi_{\omega}(T)e_{j}=0,j\leq K\\}$
$\displaystyle\text{and
}\tilde{\Lambda}_{\omega}=\\{e_{j}\in\Lambda_{\omega}:\chi_{\omega}(T)e_{j}\in\mathrm{span}\\{\chi_{\omega}(T)e_{i}\\}_{i=1}^{j-1}\\}.$

Recall also from the proof of Theorem 3.7 that
$\\{\hat{e}_{j}\\}_{j=1}^{M}=\Lambda_{\omega}\setminus\tilde{\Lambda}_{\omega}.$
If $\\{\chi_{\omega}(T)e_{j}\\}_{j=1}^{M}$ are linearly independent then
$\tilde{\Lambda}_{\omega}=\emptyset$, and therefore
$\\{\hat{e}_{j}\\}_{j=1}^{M}=\\{e_{j}\\}_{j=1}^{M},$ which yields that the
projection $\widehat{P}_{M}$ in (3.17) is the projection onto
$\overline{\mathrm{span}\\{e_{j}\\}_{j=1}^{M}}$. ∎

Theorems 3.9 and 3.7 also give us convergence to the eigenvectors. With the
use of (possibly countably many) shifts and rotations, the above theorem
allows us to find all eigenvalues, their multiplicities and eigenspaces
outside the convex hull of the essential spectrum, i.e. outside the essential
numerical range.

  * Example 3.11

It is possible in the case of infinite $M$ that the $\hat{q}_{j}$ do not form
an orthonormal basis of $\mathrm{ran}\chi_{\omega}(T)$ and we can even loose
part of $\omega$ in the convergence of
$\widehat{P}_{M}Q_{n}^{*}TQ_{n}\widehat{P}_{M}$ to a diagonal operator. This
is to be contrasted to the finite dimensional case. For example, suppose that
with respect to an initial orthonormal basis $\\{v_{j}\\}_{j\in\mathbb{N}}$,
$T$ is given by the diagonal matrix $\mathrm{Diag}(1/2,1,1,...)$. Now define
$f_{j}=v_{1}+(1/j)v_{j+1}$ and apply Gram-Schmidt to the sequence
$\\{f_{j}\\}_{j\in\mathbb{N}}$ to generate orthonormal vectors
$\\{e_{j}\\}_{j\in\mathbb{N}}$. It is easy to see that any $v_{j}$ can be
approximated to arbitrary accuracy using finite linear combinations of $e_{j}$
and hence $\\{e_{j}\\}_{j\in\mathbb{N}}$ is an orthonormal basis of our
Hilbert space. We also have that the $\chi_{1}(T)(f_{j})=(1/j)v_{j+1}$ are
linearly independent and hence so are $\chi_{1}(T)(e_{j})$. It follows that
the IQR iterates converge in the strong operator topology to the identity
operator. However, we could equally take $\omega=\\{1,1/2\\}$ in Theorem 3.9.
Hence we have the curious case that
$\overline{\mathrm{span}\\{\hat{q}_{j}\\}_{j\in\mathbb{N}}}\subset\overline{\mathrm{span}\\{\hat{v}_{j}\\}_{j>1}}$
and we loose the eigenvalue $1/2$.

The following corollary is entirely analogous to the finite dimensional case.

######  Corollary 3.12.

Suppose that the conditions of Theorem 3.9 hold with $M$ finite. Suppose also
that for $j=1,...,N$ the vectors
$\\{\chi_{\\{\lambda_{1},...,\lambda_{j}\\}}(T)e_{i}\\}_{i=1}^{\sum_{l\leq
j}m_{l}}$ are linearly independent. In the notation of Theorem 3.9, let
$\rho=\mathrm{sup}\\{\left|z\right|:z\in\Psi\\}$. For $j<N$ define
$r_{j}=\max\\{|\lambda_{k+1}/\lambda_{k}|:k\leq j\\}$ and for $j=N$ define
$r_{N}=\max\\{|\lambda_{k+1}/\lambda_{k}|,|\lambda_{N}/\rho|:k\leq j\\}$. We
then have the following rates of convergence to the diagonal operator for
$i,j\leq M$:

  1. 1.

$\left|\langle Q_{n}^{*}TQ_{n}e_{j},e_{i}\rangle\right|=O(r_{k}^{n})$ as
$n\rightarrow\infty$ if $i>j$ and $k$ is minimal such that $i\leq\sum_{l\leq
k}m_{l}$,

  2. 2.

$\left|\langle
Q_{n}^{*}TQ_{n}e_{i},e_{i}\rangle-\lambda_{k}\right|=O(r_{k}^{n})$ as
$n\rightarrow\infty$ if $k$ is minimal such that $i\leq\sum_{l\leq k}m_{l}$.

###### Proof.

The result follows from Theorem 3.9 applied successively to
$\omega_{1},\omega_{2},...,\omega_{N}$ where $\omega_{j}=\\{\lambda_{k}:k\leq
j\\}$. In general analogous results follows from Theorem 3.9 when $M$ is
infinite and with other linear independence conditions on
$\chi_{\omega^{\prime}}(T)e_{i}$ with $\omega^{\prime}\subset\omega$ but the
statements become less succinct. ∎

In the finite dimensional case and the case of distinct eigenvalues of the
same magnitude the QR algorithm applied to a normal matrix will ‘converge’ to
a block diagonal matrix (without necessarily converging in each block). This
can be extended to infinite dimensions by inductively using the following
theorem which also extends to non-normal operators.

######  Theorem 3.13 (Block convergence theorem in infinite dimensions).

Let $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ be an invertible operator (not
necessarily normal) and suppose that there exists an orthogonal projection $P$
of rank $M$ (possibly infinite) such that both the ranges of $P$ and of $I-P$
are invariant under $T$. Suppose also that there exists $\alpha>\beta>0$ such
that

  * •

$\|Tx\|\geq\alpha\|x\|\quad\forall x\in\mathrm{ran}(P)$,

  * •

$\|Tx\|\leq\beta\|x\|\quad\forall x\in\mathrm{ran}(I-P)$.

Let $\\{Q_{n}\\}_{n\in\mathbb{N}}$ and $\\{R_{n}\\}_{n\in\mathbb{N}}$ be $Q$\-
and $R$-sequences of $T$ with respect to $\\{e_{i}\\}.$ Then there exists a
subset $\\{\hat{e}_{j}\\}_{j=1}^{M}\subset\\{e_{i}\\}_{i\in\mathbb{N}}$ such
that

  * (i)

For any finite $\mu\leq M$ we have
$\delta(\mathrm{span}\\{Q_{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{ran}(P))=O(\beta^{n}/\alpha^{n})$
as $n\rightarrow\infty$. If $M$ is finite this implies full convergence
$\hat{\delta}(\mathrm{span}\\{Q_{n}\hat{e}_{j}\\}_{j=1}^{M},\mathrm{ran}(P))=O(\beta^{n}/\alpha^{n})$
as $n\rightarrow\infty$.

  * (ii)

Every subsequence of $\\{Q_{n}^{*}TQ_{n}\\}_{n\in\mathbb{N}}$ has a convergent
subsequence $\\{Q_{n_{k}}^{*}TQ_{n_{k}}\\}_{k\in\mathbb{N}}$ such that

$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{WOT}}}{{\longrightarrow}}\sum_{j=1}^{M}\xi_{j}\otimes\hat{e}_{j}\bigoplus\sum_{i\in\Theta}\zeta_{i}\otimes
e_{i},$

as $k\rightarrow\infty,$ where

$\Theta=\\{j:e_{j}\notin\\{\hat{e}_{l}\\}_{l=1}^{M}\\},\quad\xi_{j}\in\overline{\mathrm{span}\\{\hat{e}_{l}\\}_{l=1}^{M}},\quad\zeta_{i}\in\overline{\mathrm{span}\\{e_{l}\\}_{l\in\Theta}}.$

If $\\{Pe_{l}\\}_{l=1}^{M}$ are linearly independent then we can take
$\hat{e}_{j}=e_{j}$. Furthermore, if $T$ has only finitely many non-zero
entries in each column then we can replace $WOT$ convergence by $SOT$
convergence.

  * Remark 3.14

Theorem 3.13 essentially says that the IQR algorithm can compute the invariant
subspace $\mathrm{ran}(P)$ of such an operator if there is enough separation
between $T$ restricted to $\mathrm{ran}(P)$ and $\mathrm{ran}(I-P)$. In other
words, provided the existence of a dominant invariant subspace.

###### Proof of Theorem 3.13:.

The main ideas of the proof of Theorem 3.13 have already been presented so we
sketch the proof. We first define the vectors $\\{\hat{e}_{j}\\}_{j=1}^{M}$ in
a similar way to Definition 3.5 inductively by $\hat{e}_{j}=e_{p_{j}}$ where

$p_{j}=\min\\{i:Pe_{i}\notin\mathrm{span}\\{P\hat{e}_{k}\\}_{k=1}^{j-1}\\}.$

Let $r=\beta/\alpha<1$. We will prove inductively that

  * (a)

$\hat{\delta}(\mathrm{span}\\{Q_{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu})\leq
C_{1}(\mu)r^{n}$ for any finite $\mu\leq M$,

  * (b)

$\|PQ_{n}e_{j}\|\leq C_{2}(j)r^{n}$ for any $j\in\Theta$,

for some constants $C_{1}(\mu)$ and $C_{2}(j)$. Suppose that this has been
done. Part (i) of Theorem 3.13 now follows since
$\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu}\subset\mathrm{ran}(P)$. We
then argue as in the proof of Theorem 3.9 to gain

$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{\scriptsize
WOT}}}{{\longrightarrow}}W,\qquad k\rightarrow\infty.$

Then by studying the inner products $\langle
TQ_{n_{k}}e_{j},Q_{n_{k}}e_{i}\rangle$ using the invariance of
$\mathrm{ran}(P)$, $\mathrm{ran}(I-P)$ under $T$ and from (b), part (ii) of
Theorem 3.13 easily follows (note that (a) implies that
$\|(I-P)Q_{n}\hat{e}_{j}\|\leq C_{1}(j)r^{n}$). The final part of the theorem
then follows from the same arguments in the proof of Theorem 3.9. Hence we
only need to prove (a) and (b).

We first claim that

$\delta(\mathrm{span}\\{PT^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu})\leq
C_{3}(\mu)r^{n}.$ (3.22)

$P$ commutes with $T$ which is invertible and hence both of these spaces have
dimension $\mu$ by the construction of the $\hat{e}_{j}$. It follows that
(3.22) implies

$\hat{\delta}(\mathrm{span}\\{PT^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu})\leq\mu^{\frac{1}{2}}C_{3}(\mu)r^{n}=C_{4}(\mu)r^{n}.$
(3.23)

To show (3.22), let $x_{1}^{n},...,x_{\mu}^{n}$ be an orthonormal basis for
$\mathrm{span}\\{PT^{n}\hat{e}_{j}\\}_{j=1}^{\mu}$ and let
$\xi=\sum_{j=1}^{\mu}\alpha_{j}x_{j}^{n}$ have norm at most $1$. Now, we may
choose coefficients $\beta_{j,n}$ such that
$T^{n}\sum_{j=1}^{\mu}\beta_{j,n}x_{j}^{n}=\xi$ since $T|_{\mathrm{ran}(P)}$
is invertible when viewed as an operator acting on $\mathrm{ran}(P)$. By the
assumptions on $T$ we must have that

$\big{(}\sum_{j=1}^{m}\left|\beta_{j,n}\right|^{2}\big{)}^{1/2}\leq\frac{1}{\alpha^{n}}.$

We may change basis from $\\{\hat{e}_{j}\\}_{j=1}^{\mu}$ to
$\\{\tilde{e}_{j}\\}_{j=1}^{\mu}$ such that $P\tilde{e}_{j}=x_{j}^{n}$. Form
the vector

$\eta_{n}=T^{n}\big{(}\sum_{j=1}^{\mu}\beta_{j,n}\tilde{e}_{j}\big{)}\in\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu}.$

Then clearly by Hölder’s inequality

$\|\xi-\eta_{n}\|\leq\frac{\big{(}\sum_{j=1}^{\mu}\|T^{n}(I-P)\tilde{e}_{j}\|^{2}\big{)}^{1/2}}{\alpha^{n}}\leq
C_{3}(\mu)\frac{\beta^{n}}{\alpha^{n}},$

proving (3.22) and hence (3.23).

Note that the proof of Lemma 3.6 carries over (replacing the projection
$\chi_{\omega}(T)$ by $P$) to prove that

$\mathrm{span}\\{PQ_{n}e_{j}\\}_{j=1}^{m}=\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{s(m)}$
(3.24)

where $s(m)$ is maximal with
$\\{\hat{e}_{j}\\}_{j=1}^{s(m)}\subset\\{e_{j}\\}_{j=1}^{m}$. It follows that

$\displaystyle\delta(\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu})$
$\displaystyle=\delta(\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{PQ_{n}e_{j}\\}_{j=1}^{p_{\mu}})$
$\displaystyle=\delta(\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{PT^{n}e_{j}\\}_{j=1}^{p_{\mu}})$
$\displaystyle\leq\delta(\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{PT^{n}\hat{e}_{j}\\}_{j=1}^{\mu})\leq
C_{4}(\mu)r^{n},$

where we have used (2.6) to reach the second line and the fact that
$\mathrm{span}\\{PT^{n}\hat{e}_{j}\\}_{j=1}^{\mu}\subset\mathrm{span}\\{PT^{n}e_{j}\\}_{j=1}^{p_{\mu}}$
to reach the third line. Again, both spaces have dimension $\mu$ so we have

$\begin{split}\delta(\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{p_{\mu}})&=\delta(\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{T^{n}e_{j}\\}_{j=1}^{p_{\mu}})\\\
&\leq\delta(\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu},\mathrm{span}\\{T^{n}\hat{e}_{j}\\}_{j=1}^{\mu})\leq
C_{5}(\mu)r^{n}.\end{split}$ (3.25)

With these arguments out of the way (these are the analogue of Proposition
3.4) we can now form our inductive argument, similar to the proof of Theorem
3.7. Suppose first that (a) holds for $\mu$ (allowing $\mu=0$ for the initial
step) and let $j\in\Theta$ have $j<p_{\mu+1}$ (where $p_{\mu+1}=\infty$ if
$\mu=M$). From (a) for $\mu$ and (3.24) we have that

$PQ_{n}e_{j}=v_{n}+\sum_{i=1}^{\mu}a_{n,i}Q_{n}\hat{e}_{i}$

for some $v_{n}$ with $\|v_{n}\|\leq C_{1}(\mu)r^{n}$. Then we must have

$a_{n,i}+\langle v_{n},Q_{n}\hat{e}_{i}\rangle=\langle
PQ_{n}e_{j},Q_{n}\hat{e}_{i}\rangle=\langle
Q_{n}e_{j},PQ_{n}\hat{e}_{i}\rangle.$

Using (a) again, along with the fact that $Q_{n}e_{j}$ is orthogonal to
$\\{Q_{n}\hat{e}_{i}\\}_{i=1}^{\mu}$, we must have $\left|a_{n,i}\right|\leq
2C_{1}(\mu)r^{n}$. It follows that we can take
$C_{2}(j)=(2\sqrt{\mu}+1)C_{1}(\mu)$ for $j\in[p_{\mu}+1,...,p_{\mu+1})$ in
(b). Now we use (3.25). Let
$\xi\in\mathrm{span}\\{PQ_{n}\hat{e}_{j}\\}_{j=1}^{\mu+1}$ have unit norm and
assume that $p_{\mu+1}<\infty$ (else there is nothing to prove since then
$\mu=M$). Then there exists $b_{n,j}$ and $w_{n}$ such that

$\xi=\sum_{j=1}^{p_{\mu+1}}b_{n,j}Q_{n}e_{j}+w_{n}$

and $\|w_{n}\|\leq C_{5}(\mu+1)r^{n}$. Now let $j\in\Theta$ with $j<p_{\mu+1}$
then we must have

$\langle\xi,PQ_{n}e_{j}\rangle=\langle\xi,Q_{n}e_{j}\rangle=b_{n,j}+\langle
w_{n},Q_{n}e_{j}\rangle.$

We have proven (b) for such $j$ and hence we have
$\left|b_{n,j}\right|\leq\big{(}C_{2}(j)+C_{5}(\mu+1)\big{)}r^{n}$. It follows
that we can take

$C_{1}(\mu+1)=\mu^{\frac{1}{2}}\Big{[}C_{5}(\mu+1)+\Big{\\{}\sum_{j=1,j\in\Theta}^{p_{\mu+1}}[C_{2}(j)+C_{5}(\mu+1)]^{2}\Big{\\}}^{\frac{1}{2}}\Big{]},$

where the square root factor appears since the relevant spaces are
$\mu$-dimensional. This completes the inductive step (the initial step is
identical) and hence the proof of the theorem. ∎

Theorem 3.13 can be made sharper (under a slightly stricter assumption on the
linear independence of $\\{e_{j}\\}_{j=1}^{M}$) with the following theorem
which includes the case that $\mathrm{ran}(I-P)$ is not necessarily invariant.

######  Theorem 3.15 (Convergence to invariant subspace in infinite
dimensions).

Let $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ be an invertible operator (not
necessarily normal) and suppose that there exists an orthogonal projection $P$
of finite rank $M$ such that the range of $P$ is invariant under $T$. Suppose
also that there exists $\alpha>\beta>0$ such that

  * •

$\|Tx\|\geq\alpha\|x\|\quad\forall x\in\mathrm{ran}(P)$,

  * •

$\|(I-P)T(I-P)\|\leq\beta$.

Under these conditions, there exists a canonical $M$ dimensional
$T^{*}-$invariant subspace $S$ and we let $\tilde{P}$ denote the orthogonal
projection onto $S$ (in the special case that $\mathrm{ran}(I-P)$ is also
$T$-invariant such as in Theorems 3.9 and 3.13, then $S=\mathrm{ran}(P)$).
Suppose also that $\\{\tilde{P}e_{j}\\}_{j=1}^{M}$ are linearly independent.
Let $\\{Q_{n}\\}_{n\in\mathbb{N}}$ and $\\{R_{n}\\}_{n\in\mathbb{N}}$ be $Q$\-
and $R$-sequences of $T$ with respect to $\\{e_{i}\\}.$ Then

  * (i)

The subspace angle $\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)<\pi/2$ and we
have

$\hat{\delta}(\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))\leq\frac{\sin\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))\big{)}}{\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)\big{)}}\frac{\beta^{n}}{\alpha^{n}}\Big{(}1+\frac{\|PT(I-P)\|}{\alpha-\beta}\Big{)},$
(3.26)

  * (ii)

Every subsequence of $\\{Q_{n}^{*}TQ_{n}\\}_{n\in\mathbb{N}}$ has a convergent
subsequence $\\{Q_{n_{k}}^{*}TQ_{n_{k}}\\}_{k\in\mathbb{N}}$ such that

$Q_{n_{k}}^{*}TQ_{n_{k}}\stackrel{{\scriptstyle\text{WOT}}}{{\longrightarrow}}\sum_{j=1}^{M}\xi_{j}\otimes
e_{j}\bigoplus\sum_{i=M+1}^{\infty}\zeta_{i}\otimes e_{i},$

as $k\rightarrow\infty,$ where

$\xi_{j}\in\overline{\mathrm{span}\\{e_{l}\\}_{l=1}^{M}},\quad\zeta_{i}\in\mathcal{H}.$

Furthermore, if $T$ has only finitely many non-zero entries in each column
then we can replace $WOT$ convergence by $SOT$ convergence.

  * Remark 3.16

Theorem 3.15 says that the IQR algorithm can be used to approximate dominant
invariant subspaces. In particular, we shall use the bound (3.26) to build a
$\Delta_{1}$ algorithm in Section 5. Note in the normal case that Theorem 3.9
is more precise, both in giving convergence of individual vectors to
eigenvectors and in the less restrictive assumptions on spanning sets and $M$.
In the normal case (and that of Theorem 3.13) we also have that the limit
operator has a block diagonal form.

###  3.3 Proof of Theorem 3.15

In this section we will prove Theorem 3.15. The proof technique is different
to those used above and hence we have given it a separate section. Throughout,
we will denote the ratio $\beta/\alpha$ by $r$. Note that since $M$ is finite,
the bound $\alpha$ implies that
$T|_{\mathrm{ran}(P)}:\mathrm{ran}(P)\rightarrow\mathrm{ran}(P)$ is invertible
with $\|T|_{\mathrm{ran}(P)}^{-1}\|\leq 1/\alpha$. First, let $Q$ denote a
unitary change of basis matrix from $\\{e_{j}\\}$ to $\\{\tilde{e}_{j}\\}$
where $\\{\tilde{e}_{j}\\}_{j=1}^{M}$ is a basis for $\mathrm{ran}(P)$. Then
as matrices with respect to the original basis we can write

$Q=[P_{1},P_{2}],\quad Q^{*}TQ=\left(\begin{matrix}T_{11}&T_{12}\\\
0&T_{22}\end{matrix}\right),$

where $T_{11}\in\mathbb{C}^{M\times M}$ and $T_{12}$ has $M$ rows. Our
assumptions imply that $\|T_{11}^{-1}\|\leq 1/\alpha$ and
$\|T_{22}\|\leq\beta$. The next lemma shows that we can change the basis
further to eliminate the sub-block $T_{12}$. This is needed to apply a power
iteration type argument.

######  Lemma 3.17.

Define the linear function
$F:\mathcal{B}(l^{2}(\mathbb{N}),\mathbb{C}^{M})\rightarrow\mathcal{B}(l^{2}(\mathbb{N}),\mathbb{C}^{M})$
by

$F(A)=T_{11}^{-1}AT_{22},$

where we identify elements of $\mathcal{B}(l^{2}(\mathbb{N}),\mathbb{C}^{M})$
as matrices. Then we can define
$A\in\mathcal{B}(l^{2}(\mathbb{N}),\mathbb{C}^{M})$ by
$A-F(A)=-T_{11}^{-1}T_{12}$. Furthermore, if we define

$B(A)=\left(\begin{matrix}I&A\\\ 0&I\end{matrix}\right),$

then $B(A)$ has inverse $B(-A)$ and

$B(-A)\left(\begin{matrix}T_{11}&T_{12}\\\
0&T_{22}\end{matrix}\right)B(A)=\left(\begin{matrix}T_{11}&0\\\
0&T_{22}\end{matrix}\right).$ (3.27)

###### Proof.

Our assumptions on $T$ ensure that $F$ is a contraction with
$\left\|F\right\|\leq r<1$. Hence we can define $A$ via the series

$A=\sum_{k=0}^{\infty}F^{k}(-T_{11}^{-1}T_{12}).$

It is then straightforward to check $A-F(A)=-T_{11}^{-1}T_{12}$,
$B(A)B(-A)=B(-A)B(A)=I$ and the identity (3.27). ∎

Let

$Y=Q\left(\begin{matrix}I&0\\\ -A^{*}&I\end{matrix}\right)$

then we have the matrix identity

$Y^{-1}T^{*}Y=\left(\begin{matrix}T_{11}^{*}&0\\\
0&T_{22}^{*}\end{matrix}\right).$

The canonical $T^{*}-$invariant subspace alluded to in Theorem 3.15 is then
simply $S=\mathrm{span}\\{Ye_{j}\\}_{j=1}^{M}$. The space is canonical since
it is easily seen that it is unchanged if we use a different basis for
$\mathrm{ran}(P_{1})$ and $\mathrm{ran}(P_{2})$ in the definition of $Q$.

Now let
$P_{0}=\left(\begin{matrix}e_{1}&e_{2}&\ldots&e_{M}\end{matrix}\right)\in\mathcal{B}(\mathbb{C}^{M},l^{2}(\mathbb{N}))$
denote the matrix who’s columns are the first $M$ basis elements
$\\{e_{j}\\}_{j=1}^{M}$. Since the $\\{R_{i}\\}$ are upper triangular, it is
easy to see that

$T^{n}P_{0}=Q_{n}R_{n}P_{0}=Q_{n}P_{0}P_{0}^{*}R_{n}P_{0}.$

We will denote the (invertible) matrix
$P_{0}^{*}R_{n}P_{0}\in\mathbb{C}^{M\times M}$ by $Z_{n}$. Now define

$V^{1}_{n}=P_{1}^{*}Q_{n}P_{0}\in\mathcal{B}(\mathbb{C}^{M}),\quad
V^{2}_{n}=P_{2}^{*}Q_{n}P_{0}\in\mathcal{B}(\mathbb{C}^{M},l^{2}(\mathbb{N})),$

then we have the relation

$\left(\begin{matrix}T_{11}&T_{12}\\\
0&T_{22}\end{matrix}\right)^{n}\left(\begin{matrix}V^{1}_{0}\\\
V^{2}_{0}\end{matrix}\right)=\left(\begin{matrix}V^{1}_{n}\\\
V^{2}_{n}\end{matrix}\right)Z_{n}.$

But by Lemma 3.17 we have

$\left(\begin{matrix}T_{11}&T_{12}\\\
0&T_{22}\end{matrix}\right)^{n}=B(A)\left(\begin{matrix}T_{11}^{n}&0\\\
0&T_{22}^{n}\end{matrix}\right)B(-A).$

Unwinding the definitions, this implies the matrix identities

$\displaystyle T_{11}^{n}(V_{0}^{1}-AV_{0}^{2})$
$\displaystyle=(V_{n}^{1}-AV_{n}^{2})Z_{n},$ (3.28) $\displaystyle
T_{22}^{n}V_{0}^{2}$ $\displaystyle=V_{n}^{2}Z_{n}.$ (3.29)

######  Lemma 3.18.

The following identity holds

$\hat{\delta}(\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))=\|V_{n}^{2}\|.$
(3.30)

###### Proof.

Note that $\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{M}=\mathrm{ran}(Q_{n}P_{0})$
and $\mathrm{ran}(P)=\mathrm{ran}(P_{1})$. Since $P_{1}P_{1}^{*}$ and
$Q_{n}P_{0}P_{0}^{*}Q_{n}^{*}$ are orthogonal projections, it follows that

$\displaystyle\hat{\delta}(\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))$
$\displaystyle=\|Q_{n}P_{0}P_{0}^{*}Q_{n}^{*}-P_{1}P_{1}^{*}\|$
$\displaystyle=\|Q_{n}^{*}(Q_{n}P_{0}P_{0}^{*}Q_{n}^{*}-P_{1}P_{1}^{*})Q\|$
$\displaystyle=\left\|\left(\begin{matrix}0&P_{0}^{*}Q_{n}^{*}P_{2}\\\
-(I-P_{0})^{*}Q_{n}^{*}P_{1}&0\end{matrix}\right)\right\|.$

But we have that $\|P_{0}^{*}Q_{n}^{*}P_{2}\|=\|V_{n}^{2}\|$ and hence we are
done if we can show
$\|P_{0}^{*}Q_{n}^{*}P_{2}\|=\|(I-P_{0})^{*}Q_{n}^{*}P_{1}\|$. Consider the
unitary matrix

$U:=Q_{n}^{*}Q=\left(\begin{matrix}P_{0}^{*}Q_{n}^{*}P_{1}&P_{0}^{*}Q_{n}^{*}P_{2}\\\
(I-P_{0})^{*}Q_{n}^{*}P_{1}&(I-P_{0})^{*}Q_{n}^{*}P_{2}\end{matrix}\right)=\left(\begin{matrix}U_{11}&U_{12}\\\
U_{21}&U_{22}\end{matrix}\right).$

Now let $x\in\mathbb{C}^{M}$ be of unit norm, then
$\|U_{11}x\|^{2}+\|U_{21}x\|^{2}=1$. It follows that
$\|U_{21}\|^{2}=1-\sigma_{0}(U_{11})^{2}$, where $\sigma_{0}$ denotes the
smallest singular value. Applying the same argument to $U^{*}$ we see that
$\|U_{12}\|^{2}=1-\sigma_{0}(U_{11})^{2}=\|U_{21}\|^{2}$, completing the
proof. ∎

######  Lemma 3.19.

The matrix $(V_{0}^{1}-AV_{0}^{2})$ is invertible with

$\|(V_{0}^{1}-AV_{0}^{2})^{-1}\|\leq\frac{1}{\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)\big{)}}.$
(3.31)

###### Proof.

First note that since $\\{\tilde{P}e_{j}\\}_{j=1}^{M}$ are linearly
independent, we must have $\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)<\pi/2$
and hence the bound in (3.31) is finite. Let
$W=(P_{1}-P_{2}A^{*})(I+AA^{*})^{-1/2}\in\mathcal{B}(\mathbb{C}^{M},l^{2}(\mathbb{N}))$.
By considering $W^{*}W=I\in\mathbb{C}^{M\times M}$, we see that the columns of
$W$ are orthonormal. In fact, expanding $Y$ we have

$Y=[P_{1}-P_{2}A^{*}\quad P_{2}]$

and hence the columns of $W$ are a basis for the subspace $S$. Arguing as in
the proof of Lemma 3.18, we have that

$\hat{\delta}(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)=\sqrt{1-\sigma_{0}(W^{*}P_{0})^{2}}<1.$

This implies that $W^{*}P_{0}$ is invertible with

$\sigma_{0}(W^{*}P_{0})=\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S\big{)}\big{)}>0.$

We also have the identity

$V_{0}^{1}-AV_{0}^{2}=(I+AA^{*})^{1/2}(W^{*}P_{0}).$

Since $(I+AA^{*})^{-1/2}$ has norm at most $1$, we see that
$(V_{0}^{1}-AV_{0}^{2})$ is invertible and (3.31) holds. ∎

###### Proof of Theorem 3.15:.

Using Lemma 3.19 and the matrix identities (3.28) and (3.29), we can write

$V_{n}^{2}=T_{22}^{n}V_{0}^{2}(V_{0}^{1}-AV_{0}^{2})^{-1}T_{11}^{-n}(V_{n}^{1}-AV_{n}^{2}).$

Using (3.30) and (3.31), this implies

$\begin{split}\hat{\delta}(\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))&\leq\frac{\|V_{0}^{2}\|\|V_{n}^{1}-AV_{n}^{2}\|r^{n}}{\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)\big{)}}\\\
&=\frac{\sin\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))\big{)}\|V_{n}^{1}-AV_{n}^{2}\|r^{n}}{\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)\big{)}}.\end{split}$
(3.32)

It is clear by summing a geometric series that

$\|A\|\leq\frac{\|T_{12}\|}{\alpha(1-r)}=\frac{\|PT(I-P)\|}{\alpha-\beta}.$

It follows that $\|V_{n}^{1}-AV_{n}^{2}\|\leq 1+\|PT(I-P)\|/(\alpha-\beta)$.
Substituting this into (3.32) proves part (i) of the theorem.

Next we argue that if $i>M$ then $\|PQ_{n}e_{i}\|\rightarrow 0$ as
$n\rightarrow\infty$. We have that

$PQ_{n}e_{i}=\sum_{j=1}^{M}\alpha_{j,n}Q_{n}e_{j}+v_{n}$

with $\|v_{n}\|\rightarrow 0$ by part (i). Note that we then have

$\alpha_{j,n}=\langle PQ_{n}e_{i},Q_{n}e_{j}\rangle+\epsilon_{j,n}=\langle
Q_{n}e_{i},PQ_{n}e_{j}\rangle+\epsilon_{j,n}$

with $\\{\epsilon_{j,n}\\}$ null. But again by (i) we have that $PQ_{n}e_{j}$
approaches $\mathrm{span}\\{Q_{n}e_{k}\\}_{k=1}^{M}$ which is orthogonal to
$Q_{n}e_{i}$ and hence $\\{\alpha_{j,n}\\}$ is null. The proof of part (ii)
now follows the same argument as in the proof of part (i) of Theorem 3.9 and
of the final part of Theorem 3.13. The key property being that if $j\leq M$
and $i>M$ then $\langle Q_{n}^{*}TQ_{n}e_{j},e_{i}\rangle\rightarrow 0$ due to
the invariance of $\mathrm{ran}(P)$ under $T$. Note that it does not
necessarily follow (as is easily seen by considering upper triangular $T$)
that $\langle Q_{n}^{*}TQ_{n}e_{i},e_{j}\rangle\rightarrow 0$ for such $i,j$.
∎

##  4 The IQR algorithm can be computed

The previous section gives a theoretical justification for why the IQR
algorithm may work, but we are faced with the possibly unpleasant problem of
how to compute with infinite data structures on a computer. Fortunately there
is a way to overcome such a problem. The key is to impose some structural
requirements on the infinite matrix.

###  4.1 Quasi-banded subdiagonals

######  Definition 4.1.

Let $T$ be an infinite matrix acting as a bounded operator on
$l^{2}(\mathbb{N})$ with basis $\\{e_{j}\\}_{j\in\mathbb{N}}$. For
$f:\mathbb{N}\rightarrow\mathbb{N}$ non-decreasing with $f(n)\geq n$ we say
that $T$ has quasi-banded subdiagonals with respect to $f$ if $\langle
Te_{j},e_{i}\rangle=0$ when $i>f(j).$

This is the class of infinite matrices with a finite number of non-zero
elements in each column (and not necessarily in each row) which is captured by
the function $f$. It is for this class that the computation of the IQR
algorithm is feasible on a finite machine. For this class of operators one can
actually compute (without any approximation or any extra discretisation) the
matrix elements of the $n$-th iteration of the IQR algorithm as if it was done
on an infinite computer (meaning the computation collapses to a finite one).
The following result of independent interest is needed in the proof and
generalises the well known fact in finite dimensions that the QR algorithm
preserves bandwidth (see [61] for a good discussion of the tridiagonal case).

######  Proposition 4.2.

Let $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ and let $T_{n}$ be the $n$-th element
in the IQR iteration, such that $T_{n}=Q^{*}_{n}\cdots Q^{*}_{1}TQ_{1}\cdots
Q_{n},$ where

$Q_{j}=\underset{l\rightarrow\infty}{\text{SOT-lim \,}}U^{j}_{1}\cdots
U^{j}_{l}$

and $U^{j}_{l}$ is a Householder transformation. If T has quasi-banded
subdiagonals with respect to $f$ then so does $T_{n}$.

###### Proof.

By induction, it is enough to prove the result for $n=1$. From the
construction of the Householder reflections $U_{m}^{1}=P_{m-1}\oplus S_{m}$,
the chosen $\eta_{m}$ (see Theorem 2.2) have

$\langle\eta_{m},e_{j}\rangle=0,\quad j>f(m).$ (4.1)

Using the fact that $f$ is increasing, it follows that each $U^{1}_{m}$ has
quasi-banded subdiagonals with respect to $f$, as does the product
$U^{1}_{1}\cdots U^{1}_{m}$. It follows that $Q_{1}$ must have quasi-banded
subdiagonals with respect to $f$ and hence so does $T_{1}=R_{1}Q_{1}$ since
$R_{1}$ is upper triangular. ∎

######  Theorem 4.3.

Let $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ have quasi-banded subdiagonals with
respect to $f$ and let $T_{n}$ be the $n$-th element in the IQR iteration,
i.e. $T_{n}=Q^{*}_{n}\cdots Q^{*}_{1}TQ_{1}\cdots Q_{n},$ where

$Q_{j}=\underset{l\rightarrow\infty}{\text{SOT-lim \,}}U^{j}_{1}\cdots
U^{j}_{l}$

and $U^{j}_{l}$ is a Householder transformation (the superscript is not a
power, but an index). Let $P_{m}$ be the usual projection onto
$\mathrm{span}\\{e_{j}\\}_{j=1}^{m}$ and denote the $a$-fold iteration of $f$
by $\underbrace{f\circ{}f\circ{}...\circ{}f}_{a\text{ times}}=f_{a}$. Then

$\begin{split}P_{m}T_{n}P_{m}&=P_{m}U^{n}_{m}\cdots
U^{n}_{1}U^{n-1}_{f_{1}(m)}\cdots U^{n-1}_{1}\cdots U^{2}_{f_{(n-2)}(m)}\cdots
U^{2}_{1}U^{1}_{f_{(n-1)}(m)}\cdots U^{1}_{1}\\\ &\quad\cdot
P_{f_{n}(m)}TP_{f_{n}(m)}\\\ &\quad\cdot U^{1}_{1}\cdots
U^{1}_{f_{(n-1)}(m)}U^{2}_{1}\cdots U^{2}_{f_{(n-2)}(m)}\cdots
U^{n-1}_{1}\cdots U^{n-1}_{f_{1}(m)}U^{n}_{1}\cdots
U^{n}_{m}P_{m}.\end{split}$ (4.2)

  * Remark 4.4

What Theorem 4.3 says is that to compute the finite section of size $m$ of the
$n$-th iteration of the IQR algorithm (i.e. $P_{m}T_{n}P_{m}$), one only needs
information from the finite section of size $f_{n}(m)$ (i.e.
$P_{f_{n}(m)}TP_{f_{n}(m)}$) since the relevant Householder reflections can
also be computed from this information. In other words, the IQR algorithm can
be computed.

###### Proof of Theorem 4.3:.

By induction it is enough to prove that

$P_{m}T_{n}P_{m}=P_{m}U_{m}^{n}...U_{1}^{n}P_{f(m)}T_{n-1}P_{f(m)}U_{1}^{n}...U_{1}^{m}P_{m}$
(4.3)

To see why this is true, note that by the assumption that $T$ has quasi-banded
subdiagonals with respect to $f$, Proposition 4.2 shows that $T_{n}$ has
quasi-banded subdiagonals with respect to $f$ for all $n\in\mathbb{N}.$ Thus,
it follows from the construction in the proof of Theorem 2.2 that each
$U^{j}_{l}$ is of the form

$U^{j}_{l}=I_{l,j,1}\oplus\left(I_{l,j,2}-\frac{2}{\|\xi_{l,j}\|^{2}}\xi_{l,j}\otimes\bar{\xi}_{l,j}\right)\oplus
I_{l,j,3},$

where $I_{l,j,1}$ denotes the identity on $P_{l-1}\mathcal{H}$, $I_{l,j,2}$
denotes the identity on $\mathrm{span}\\{e_{k}:l\leq k\leq f(l)\\}$,
$I_{l,j,3}$ denotes the identity on $P_{f(l)}^{\perp}\mathcal{H}$ and
$\xi_{l,j}\in\mathrm{span}\\{e_{k}:l\leq k\leq f(l)\\}$. Since $P_{m}$ is
compact, it then follows that

$\begin{split}P_{m}T_{n}P_{m}&=(\underset{l\rightarrow\infty}{\text{SOT-lim}}\
P_{m}U_{l}^{n}...U_{1}^{n})P_{f(m)}T_{n-1}P_{f(m)}(\underset{l\rightarrow\infty}{\text{SOT-
lim}}\ U_{1}^{n}...U_{l}^{n}P_{m})\\\
&=P_{m}U_{m}^{n}...U_{1}^{n}P_{f(m)}T_{n-1}P_{f(m)}U_{1}^{n}...U_{1}^{m}P_{m}.\end{split}$
(4.4)

∎

  * Remark 4.5

This result allows us to implement the IQR algorithm because each $U^{j}_{l}$
only affects finitely many columns or rows of $A$ if multiplied either on the
left or the right. In computer science it is often referred to as “Lazy
evaluation” when one computes with infinite data structures, but defers the
use of the information until needed. A simple implementation is shown in the
appendix for the case that the matrix has $k$ subdiagonals (i.e. we have
$f(n)=n+k$).

The next question is how restrictive is the assumption in Definition 4.1? In
particular, suppose that $T\in\mathcal{B}(\mathcal{H})$ and that
$\xi\in\mathcal{H}$ is a cyclic vector for $T$ (i.e.
$\mathrm{span}\\{\xi,T\xi,T^{2}\xi,\ldots\\}$ is dense in $\mathcal{H}$). Then
by applying the Gram-Schmidt procedure to $\\{\xi,T\xi,T^{2}\xi,\ldots\\}$ we
obtain an orthonormal basis $\\{\eta_{1},\eta_{2},\eta_{3},\ldots\\}$ for
$\mathcal{H}$ such that the matrix representation of $T$ with respect to
$\\{\eta_{1},\eta_{2},\eta_{3},\ldots\\}$ is upper Hessenberg, and thus the
matrix representation has only one subdiagonal. The question is therefore
about the existence of a cyclic vector. Note that if $T$ does not have
invariant subspaces then every vector $\xi\in\mathcal{B}(\mathcal{H})$ is a
cyclic vector. Now what happens if $\xi$ is not cyclic for $T$? We may still
form $\\{\eta_{1},\eta_{2},\eta_{3},\ldots\\}$ as above however
$\mathcal{H}_{1}=\overline{\mathrm{span}\\{\eta_{1},\eta_{2},\eta_{3},\ldots\\}}$
is now an invariant subspace for $T$ and $\mathcal{H}_{1}\neq\mathcal{H}.$ We
may still form a matrix representation of $T$ with respect to
$\\{\eta_{1},\eta_{2},\eta_{3},\ldots\\}$, but this will now be a matrix
representation of $T|_{\mathcal{H}_{1}}.$ Obviously, we can have that
$\sigma(T|_{\mathcal{H}_{1}})\subsetneq\sigma(T)$.

However, the following example shows that the class of matrices for which we
can compute the IQR algorithm covers a wide number of applications. In
particular, it includes all finite interaction Hamiltonians on graphs. Such
operators play a prominent role in solid state physics [52, 55] describing
propagation of waves and spin waves as well as encompassing Jacobi operators
studied in many physical models and integrable lattices [75].

  * Example 4.6

Consider a connected, undirected graph $G$, such that each vertex degree is
finite and the set of vertices $V(G)$ is countably infinite. Consider the set
of all bounded operators $A$ on $l^{2}(V(G))\cong l^{2}(\mathbb{N})$ such that
the set $S(v):=\\{w\in V:\left\langle w,Av\right\rangle\neq 0\\}$ is finite
for any $v\in V$. Suppose our enumeration of the vertices obeys the following
pattern. $v_{1}$’s neighbours (including itself) are
$S_{1}=\\{v_{1},v_{2},...,v_{q_{1}}\\}$ for some finite $q_{1}$. The set of
neighbours of these vertices is $S_{2}=\\{e_{1},...,e_{q_{2}}\\}$ for some
finite $q_{2}$ where we continue the enumeration of $S_{1}$ and this process
continues inductively enumerating $S_{m}$. If we know $S(v)$ for all $v\in V$
then we can find an $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $A_{j,m}=0$
if $|j|>f(m)$. We simply choose $f(n)=q_{r_{n}}$ where $r_{n}$ is minimal such
that $\cup_{j\leq n}S(v_{j})\subset S_{r_{n}}$.

###  4.2 Invertible operators

More generally, given an invertible operator $T$ with information on how its
columns decay at infinity we can compute finite sections of the IQR iterates
with error control. For computing spectral properties, we can assume, by
shifting $T\rightarrow T+\lambda I$ then translating by $-\lambda$ back, that
the operator we are interested in is invertible, hence the invertibility
criterion is not that restrictive. Throughout we will use the following lemma
which says that for invertible operators, the QR decomposition is essentially
unique.

######  Lemma 4.7.

Let $T$ be an invertible operator (viewed as a matrix acting on
$l^{2}(\mathbb{N})$), then there exists a unique decomposition $T=QR$ with $Q$
unitary and $R$ invertible, upper triangular such that
$R_{ii}\in\mathbb{R}_{>0}$. Furthermore, any other “QR” decomposition
$T=Q^{\prime}R^{\prime}$ has a diagonal matrix
$D=\mathrm{Diag}(t_{1},t_{2},...)$ such that $\left|t_{i}\right|=1$ and
$Q=Q^{\prime}D$. In other words, the QR decomposition is unique up to phase
choices.

###### Proof.

Consider the QR decomposition already discussed in this paper,
$T=Q^{\prime\prime}R^{\prime\prime}$. $T$ is invertible and hence
$Q^{\prime\prime}$ is a surjective isometry so is unitary. Hence
$R^{\prime\prime}=Q^{\prime\prime*}T$ is invertible. Being upper triangular,
it follows that $R^{\prime\prime}_{ii}\neq 0$ for all $i$. Choose
$t_{i}\in\mathbb{T}$ such that $t_{i}R^{\prime\prime}_{ii}\in\mathbb{R}_{>0}$
and set $D=\mathrm{Diag}(t_{1},t_{2},...)$. Letting $Q=Q^{\prime\prime}D^{*}$
and $R=DR^{\prime\prime}$ we clearly have the decomposition as claimed.

Now suppose that $T=Q^{\prime}R^{\prime}$ then we can write
$Q=Q^{\prime}R^{\prime}R^{-1}$. It follows that $R^{\prime}R^{-1}$ is a
unitary upper triangular matrix and hence must be of the form
$D=\mathrm{Diag}(t_{1},t_{2},...)$ with $\left|t_{i}\right|=1$. ∎

Another way to see this result is to note that the columns of $Q$ are obtained
by applying the Gram-Schmidt procedure to the columns of $T$. The restriction
that $R_{ii}\in\mathbb{R}_{>0}$ can also be incorporated into Theorem 4.3.
Theorem 4.3 (in this subcase of invertibility) is then a consequence of the
fact that if $T$ has quasi-banded subdiagonals with respect to $f$ then

$P_{m}T^{n}P_{m}=P_{m}(P_{f_{n}(m)}TP_{f_{n}(m)})^{n}P_{m}$

and the relations (2.5) - we can apply Gram-Schmidt (or a more stable modified
version) to the columns of $P_{f_{n}(m)}TP_{f_{n}(m)}$ and truncate the
resulting matrix.

Assume that given $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ invertible (not
necessarily with quasi-banded subdiagonals), we can evaluate an increasing
family of increasing functions $g^{j}:\mathbb{N}\rightarrow\mathbb{N}$ such
that defining the matrix $T_{(j)}$ with columns $\\{P_{g^{j}(n)}Te_{n}\\}$ we
have that $T_{(j)}$ is invertible and

$\left\|(P_{g^{j}(n)}-I)Te_{n}\right\|\leq\frac{1}{j}.$ (4.5)

It is easy to see that such a sequence of functions must exist since any $S$
with $\left\|S-T\right\|\leq\left\|T^{-1}\right\|^{-1}$ is invertible. Given
this information, without loss of generality by increasing the $g^{j}$s
pointwise if necessary, applying Hölder’s inequality and taking subsequences,
we may assume that $\left\|T_{(j)}-T\right\|\leq 1/{j}.$ In other words, given
a sequence of functions satisfying (4.5) we can evaluate a sequence of
functions with this stronger condition. The following says that given such a
sequence of functions, we can compute the truncations $P_{m}T_{n}P_{m}$ to a
given precision.

######  Theorem 4.8.

Suppose $T\in\mathcal{B}(l^{2}(\mathbb{N}))$ is invertible and the family of
functions $\\{g^{j}\\}$ are as above. Suppose also that we are given a bound
$C$ such that $\left\|T\right\|\leq C$. Let $\epsilon>0$ and
$m,n\in\mathbb{N}$, then we can choose $j$ such that applying Theorem 4.3
(with the diagonal operators to ensure $R_{ii}>0$) to $T_{(j)}$ using the
function $g^{j}$ instead of $f$, we have the guaranteed bound

$\left\|P_{m}T_{n}P_{m}-P_{m}T_{(j),n}P_{m}\right\|\leq\epsilon,$

where $T_{(j),n}$ denotes the $n$-th IQR iterate of $T_{(j)}$.

###### Proof of Theorem 4.8:.

First consider the error when applying Theorem 4.3 to $T_{(j)}$ with $g^{j}$
for any fixed $j$. We will show that we can compute an error bound which
converges to zero as $j\rightarrow\infty$ and from this the theorem easily
follows by successively computing the bound and halting when this bound is
less than $\epsilon$.

Write the QR decompositions

$T^{n}=\hat{Q}_{n}\hat{R}_{n},\quad(T_{(j)})^{n}=\hat{Q}_{(j),n}\hat{R}_{(j),n}.$

We have $\left\|T-T_{(j)}\right\|\leq 1/j$ and hence, by writing
$T_{(j)}=T+(T_{(j)}-T)$, that

$\left\|T^{n}-(T_{(j)})^{n}\right\|\leq\sum_{k=1}^{n}{n\choose
k}\frac{1}{j^{k}}C^{n-k}\leq\frac{(C+1)^{n}}{j}=\frac{\tilde{C}}{j},$

where $\tilde{C}=(C+1)^{n}$. The columns of $\hat{Q}_{n}$ and
$\hat{Q}_{(j),n}$ are simply the columns of the matrices $T^{n}$ and
$(T_{(j)})^{n}$ after the application of Gram-Schmidt. Let the first $m$
columns of $T^{n}$ and $(T_{(j)})^{n}$ be denoted by $\\{t_{k}\\}_{k=1}^{m}$
and $\\{\tilde{t}_{k}^{j}\\}_{k=1}^{m}$ respectively and let
$\\{q_{k}\\}_{k=1}^{m}$ and $\\{\tilde{q}_{k}^{j}\\}_{k=1}^{m}$ be the vectors
obtained after applying Gram-Schmidt to these sequences of vectors. We then
have

$\begin{split}\|q_{1}-\tilde{q}_{1}^{j}\|&=\left\|\frac{t_{1}}{\|t_{1}\|}-\frac{\tilde{t}_{1}^{j}}{\|\tilde{t}_{1}^{j}\|}\right\|\\\
&=\left\|\frac{t_{1}(\|\tilde{t}_{1}^{j}\|-\|t_{1}\|)}{\|t_{1}\|\|\tilde{t}_{1}^{j}\|}-\frac{(\tilde{t}_{1}^{j}-t_{1})\|t_{1}\|}{\|t_{1}\|\|\tilde{t}_{1}^{j}\|}\right\|\leq\frac{2\|t_{1}-\tilde{t}_{1}^{j}\|}{\|\tilde{t}_{1}^{j}\|}\leq\frac{2\tilde{C}}{j\|\tilde{t}_{1}^{j}\|}.\end{split}$
(4.6)

For a vector $v$ of unit norm, let $P_{\perp v}$ denote the orthogonal
projection onto the space of vectors perpendicular to $v$. Note that for two
such vectors $v,w$, we have $\left\|P_{\perp v}-P_{\perp
w}\right\|\leq\left\|v-w\right\|$. Let

$v_{k}=P_{\perp q_{k-1}}\cdots P_{\perp
q_{1}}t_{k},\quad\tilde{v}_{k}^{j}=P_{\perp\tilde{q}_{k-1}^{j}}\cdots
P_{\perp\tilde{q}_{1}^{j}}\tilde{t}_{k}^{j},$ (4.7)

then $q_{k}$ are just the normalised version of $v_{k}$ and likewise
$\tilde{q}_{k}^{j}$ are just the normalised version of $\tilde{v}_{k}^{j}$.
Suppose that for $\mu<k$ we have $\|q_{\mu}-\tilde{q}_{\mu}^{j}\|\leq\delta$
for some $\delta>0$. Then applying the above products of projections we have

$\displaystyle\|v_{k}-\tilde{v}_{k}^{j}\|$ $\displaystyle\leq\|P_{\perp
q_{k-1}}\cdots P_{\perp q_{1}}(t_{k}-\tilde{t}_{k}^{j})\|+\|P_{\perp
q_{k-1}}\cdots P_{\perp q_{1}}\tilde{t}_{k}^{j}-\tilde{v}_{k}^{j}\|$
$\displaystyle\leq\|t_{k}-\tilde{t}_{k}^{j}\|+\|P_{\perp q_{k-1}}\cdots
P_{\perp q_{1}}-P_{\perp\tilde{q}^{j}_{k-1}}\cdots
P_{\perp\tilde{q}^{j}_{1}}\|\|\tilde{t}^{j}_{k}\|$
$\displaystyle\leq\|t_{k}-\tilde{t}_{k}^{j}\|+(k-1)\delta\|\tilde{t}_{k}^{j}\|.$

In the last line we have used the fact that if the operators
$\\{A_{l}\\}_{l=1}^{m}$ and $\\{B_{l}\\}_{l=1}^{m}$ have norm bounded by $1$,
then

$\left\|\prod_{l=1}^{m}A_{l}-\prod_{l=1}^{m}B_{l}\right\|\leq\sum_{l=1}^{m}\|A_{l}-B_{l}\|.$

Applying the same argument as in the inequalities (4.6) we see that

$\|q_{k}-\tilde{q}_{k}^{j}\|\leq\frac{2(\|t_{k}-\tilde{t}_{k}^{j}\|+(k-1)\delta\|\tilde{t}_{k}^{j}\|)}{\|\tilde{v}_{k}^{j}\|}\leq\frac{2({\tilde{C}}/{j}+2(k-1)\delta\tilde{C})}{\|\tilde{v}_{k}^{j}\|},$
(4.8)

since $\|\tilde{t}_{k}^{j}\|\leq C+\tilde{C}/j\leq 2\tilde{C}$. Now note that
we can compute the $\|\tilde{v}_{k}^{j}\|$ from the proof of Theorem 4.3. Set
$\delta_{1}(j)=\frac{2\tilde{C}}{j\|\tilde{t}_{1}^{j}\|}$ and for $1<k\leq m$
define iteratively

$\delta_{k}(j)=\max\Big{\\{}\delta_{k-1}(j),\frac{2({\tilde{C}}/{j}+2(k-1)\delta_{k-1}(j)\tilde{C})}{\|\tilde{v}_{k}^{j}\|}\Big{\\}}.$

We must have $\|q_{k}-\tilde{q}_{k}^{j}\|\leq\delta_{m}(j)$ for $1\leq k\leq
m$ where we have now shown the $j$ dependence as an argument.

It follows that
$\|(\hat{Q}_{n}-\hat{Q}_{(j),n})P_{m}\|\leq\sqrt{m}\delta_{m}(j)$ and hence
that

$\displaystyle\|P_{m}T_{n}P_{m}-P_{m}T_{(j),n}P_{m}\|$
$\displaystyle\leq\|P_{m}(\hat{Q}_{n}-\hat{Q}_{(j),n})^{*}T\hat{Q}_{n}P_{m}\|+\|P_{m}\hat{Q}_{(j),n}^{*}(T\hat{Q}_{n}-T_{(j)}\hat{Q}_{(j),n})P_{m}\|$
$\displaystyle\leq\sqrt{m}\delta_{m}(j)C+\|(T-T_{(j)})\hat{Q}_{(j),n}P_{m}\|+\|T(\hat{Q}_{n}-\hat{Q}_{(j),n})P_{m}\|$
$\displaystyle\leq 2\sqrt{m}\delta_{m}(j)C+\frac{1}{j}.$

So we need only show that $\delta_{m}(j)\rightarrow 0$ as
$j\rightarrow\infty$. Note that as $j\rightarrow\infty$, the columns of
$(T_{(j)})^{n}$ converge to that of $T^{n}$. It follows that
$\tilde{t}_{k}^{j}$ converge to $t_{k}$ and $\tilde{q}^{j}_{1}$ converges to
$q_{1}$. An easy inductive argument using (4.7) and (4.8) shows that the
vectors $\tilde{q}_{k}^{j}$ converge to $q_{k}$ and $\|\tilde{v}_{k}^{j}\|$
are bounded below. $\delta_{m}(j)\rightarrow 0$ now follows. ∎

##  5 SCI classification theorems

In this section we will apply the above results to prove three new
classification theorems in the SCI hierarchy. First, assume that
$T\in\mathcal{B}(l^{2}(\mathbb{N}))$ is an invertible normal operator with
$\sigma(T)=\omega\cup\Psi$, where $\omega\cap\Psi=\emptyset$,
$\omega=\\{\lambda_{i}\\}_{i=1}^{N},$ and the $\lambda_{i}$’s are isolated
eigenvalues with multiplicity $m_{i}$ satisfying
$|\lambda_{1}|>\ldots>|\lambda_{N}|.$ As usual, we also assume that
$\sup\\{|\theta|:\theta\in\Psi\\}<|\lambda_{N}|$ and set

$M:=m_{1}+\ldots+m_{N}\in\mathbb{N}\cup\\{\infty\\}.$ (5.1)

In this section we will assume for simplicity that all the $m_{i}$ except
possibly $m_{N}$ are finite. To be able to obtain the classification results
we need two key assumptions.

  * (I)

(Column decay): We assume a much weaker condition than bandedness of the
infinite matrix. Indeed, we suppose a known decay of the elements in the
columns of $T$ that is described through a family of increasing functions
$\\{g^{j}\\}_{j\in\mathbb{N}}$. In particular,
$g^{j}:\mathbb{N}\rightarrow\mathbb{N}$ is such that defining the infinite
matrix $T_{(j)}$ with columns $\\{P_{g^{j}(n)}Te_{n}\\}_{n\in\mathbb{N}}$ we
have that $T_{(j)}$ is invertible and

$\left\|(P_{g^{j}(n)}-I)Te_{n}\right\|\leq\frac{1}{j},\qquad n\in\mathbb{N}.$
(5.2)

  * (II)

(Distance to span of eigenvectors): In order to obtain error control
($\Delta_{1}$ classification) one needs to control the hidden constant in the
$O(r^{n})$ estimate in (3.16). This is done as follows, where
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ is a $Q$-sequence of $T$ with respect to
$\\{e_{j}\\}_{j\in\mathbb{N}}$. Given finite $k<M+1$ with
$m_{1}+...+m_{N-1}<k$, we will assume that if $l<N$ then
$\\{\chi_{\\{\lambda_{1},...,\lambda_{l}\\}}(T)e_{j}\\}_{j=1}^{m_{1}+...+m_{l}}$
are linearly independent. We also assume that
$\\{\chi_{\\{\lambda_{1},...,\lambda_{N}\\}}(T)e_{j}\\}_{j=1}^{k}$ are
linearly independent. This simply ensures that the IQR algorithm converges
with the expected ordering (largest eigenvalue in the first diagonal entry
then in descending order). It follows from Theorems 3.9 and 3.7, that there
exist eigenspaces $E_{1},...,E_{N}$ (with the last space depending on $k$ and
the vectors $\\{e_{j}\\}$) corresponding to the eigenvalues
$\lambda_{1},...,\lambda_{N}$ such that

    * –

$E_{i}=\mathrm{ker}(T-\lambda_{i}I)$ is the full eigenspace if $i<N$

    * –

$\hat{\delta}\Big{(}\bigoplus_{i=1}^{l}E_{i},\mathrm{span}\\{Q_{n}e_{j}\\}_{j=1}^{\min\\{m_{1}+...+m_{l},k\\}}\Big{)}\rightarrow
0$ as $n\rightarrow\infty$ for $l=1,...,N$.

We then define the initial supremum subspace angle by

$\Phi(T,\\{e_{j}\\}_{j=1}^{k}):=\sup_{l=1,...,N}\phi\Big{(}\bigoplus_{i=1}^{l}E_{i},\mathrm{span}\\{e_{j}\\}_{j=1}^{\min\\{m_{1}+...+m_{l},k\\}}\Big{)},$
(5.3)

where $\phi$, defined by (1.4), denotes the subspace angle. Our assumptions
and the proofs in Section 3 show that $\Phi(T,\\{e_{j}\\}_{j=1}^{k})<\pi/2$
and hence the key quantity $\tan\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}$
is finite.

  * Remark 5.1

The quantity $\tan\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}$ can be viewed
as a measure of how far $\\{e_{j}\\}_{j=1}^{k}$ is from
$\\{q_{j}\\}_{j=1}^{k}$, the $k$ eigenvectors of $T$ corresponding to the
first $k$ eigenvalues (including multiplicity and preserving order). Hence it
gives an estimate of how good the initial approximation
$\\{e_{j}\\}_{j=1}^{k}$ to $\\{q_{j}\\}_{j=1}^{k}$ is. Indeed, we know from
(3.16) that the convergence rate is $O(r^{n})$, and the hidden constant $C$
depends exactly on this behaviour. In particular, if $e_{j}=q_{j}$ for $j\leq
k$ then $C=0$.

Define also

$r(T)=\max\\{\left|\lambda_{2}/\lambda_{1}\right|,...,\left|\lambda_{N}/\lambda_{N-1}\right|,\rho(T)/\left|\lambda_{N}\right|\\},\qquad\rho(T)=\mathrm{sup}\\{\left|z\right|:z\in\Psi\\}.$

We can now define the class of operators $\Omega^{k}_{t,L}$ for the
classification theorem.

######  Definition 5.2.

Given $k\in\mathbb{N}$, $t\in(0,1)$ and $L>0$, let $\Omega^{k}_{t,L}$ denote
the class of invertible normal operators $T$ acting on $l^{2}(\mathbb{N})$
with $\left\|T\right\|\leq L$ such that:

  1. 1.

There exists the decomposition $\sigma(T)=\omega\cup\Psi$ as above with
$m_{1}+...+m_{N-1}<k\leq M$, where $M$ is defined in (5.1).

  2. 2.

If $m_{1}+...+m_{l}<k$ then
$\\{\chi_{\\{\lambda_{1},...,\lambda_{l}\\}}(T)e_{j}\\}_{j=1}^{m_{1}+...+m_{l}}$
are linearly independent. Also, the vectors
$\\{\chi_{\\{\lambda_{1},...,\lambda_{N}\\}}(T)e_{j}\\}_{j=1}^{k}$ are
linearly independent.

  3. 3.

We have access to functions $g^{j}:\mathbb{N}\rightarrow\mathbb{N}$ with
(5.2).

  4. 4.

It holds that $r(T)\leq t$ and
$\tan\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}\leq L$.

We can now define the computational problem that we want to classify in the
SCI hierarchy. Consider for any $T\in\Omega^{k}_{t,L}$, the problem of
computing the $k$-th largest eigenvalues (including multiplicity) and the
corresponding eigenspaces. In other words we consider the set valued mapping

$\Xi_{1}(T)=\mathcal{S}\subset\mathcal{M}=\mathbb{C}^{k}\times\big{(}l^{2}(\mathbb{N})\big{)}^{k}$

where we define

$\displaystyle\mathcal{S}$
$\displaystyle:=\Big{\\{}(\underbrace{\lambda_{1},...,\lambda_{1}}_{\text{$m_{1}$
times}},...,\underbrace{\lambda_{N},...,\lambda_{N}}_{\text{$k-(m_{1}+...+m_{N-1})$
times}})\times(\hat{q}_{1},...,\hat{q}_{k}):$ s.t.
$\\{\hat{q}_{j}\\}_{j=m_{1}+...+m_{l-1}+1}^{m_{1}+...+m_{l}}$ is an
orthonormal basis of $\mathrm{ran}(\chi_{\lambda_{l}}(T))$ for $l<N$
$\displaystyle\text{and $\\{\hat{q}_{j}\\}_{j=m_{1}+...+m_{N-1}+1}^{k}$ is an
orthonormal basis for a subspace of
$\mathrm{ran}(\chi_{\lambda_{N}}(T))$}\Big{\\}}.$

As discussed in Remark A.2 in §A.2, where we review the SCI hierarchy, when we
speak of convergence of $\mathcal{M}\ni\Gamma_{n}(T)$ to $\Xi_{1}(T)$, we
define, with a slight abuse of notation,

$\mathrm{dist}(\Gamma_{n}(T),\Xi_{1}(T)):=\inf_{y\in\Xi_{1}(T)}d_{\mathcal{M}}(\Gamma_{n}(T),y)\rightarrow
0.$

Having established the basic definition we can now present the classification
theorem.

######  Theorem 5.3 ($\Delta_{1}$ classification for the extremal part of the
spectrum).

Given the above setup we have $\\{\Xi_{1},\Omega^{k}_{t,L}\\}\in\Delta_{1}.$
In other words, for all $n\in\mathbb{N}$, there exists a general tower using
radicals, $\Gamma_{n}(T)$, such that for all $T\in\Omega^{k}_{t,L}$,

$\mathrm{dist}(\Gamma_{n}(T),\Xi_{1}(T))\leq 2^{-n}.$

  * Remark 5.4

Note that this means that we converge to the $k$ largest magnitude eigenvalues
in order with error control, and not just arbitrary points of the spectrum.
This is in contrast to most $\Sigma_{1}$ classifications in the SCI hierarchy
where the best we can hope for is to bound $\mathrm{dist}(z,\sigma(T))$ for
$z\in\mathbb{C}$.

###### Proof of Theorem 5.3:.

Let $T\in\Omega_{t,L}^{k}$ then by the definition of $\Omega_{t,L}^{k}$, we
may take $\hat{e}_{j}=e_{j}$ for $j=1,...,k$ in the arguments in Section 3.1.
The first step is to bound $Z(T,\\{e_{j}\\}_{j=1}^{k})$ in terms of
$\Phi(T,\\{e_{j}\\}_{j=1}^{k})$. Let $\\{\tilde{e}_{j}\\}_{j=1}^{k}$ denote
the basis described in Section 3.1. In our case:

  * •

For any $1\leq i\leq k$,
$\mathrm{span}\\{\tilde{e}_{j}\\}_{j=1}^{i}=\mathrm{span}\\{e_{j}\\}_{j=1}^{i}$.

  * •

If $j>m_{1}+...+m_{l}$ then $\chi_{\lambda_{l}}(T)\tilde{e}_{j}=0$.

  * •

The vectors
$\\{\chi_{\lambda_{l}}(T)\tilde{e}_{j}\\}_{j=m_{1}+...+m_{l-1}+1}^{\min\\{m_{1}+...+m_{l},k\\}}$
are orthonormal.

Let $\delta_{j}=\|\tilde{e}_{j}\|$ then we must have that if
$m_{1}+...m_{l-1}<j\leq m_{1}+...+m_{l}$ then

$\displaystyle\frac{\delta_{j}^{2}-1}{\delta_{j}^{2}}$
$\displaystyle\leq\delta\Big{(}\mathrm{span}\\{\tilde{e}_{j}\\},\bigoplus_{i=1}^{l}\mathrm{span}\\{\chi_{\\{\lambda_{i}\\}}(T)\tilde{e}_{j}\\}_{j=m_{1}+...m_{i-1}+1}^{\min\\{m_{1}+...+m_{i},k\\}}\Big{)}^{2}$
$\displaystyle\leq\delta\Big{(}\mathrm{span}\\{\tilde{e}_{j}\\}_{j=1}^{\min\\{m_{1}+...+m_{l},k\\}},\bigoplus_{i=1}^{l}\mathrm{span}\\{\chi_{\\{\lambda_{i}\\}}(T)\tilde{e}_{j}\\}_{j=m_{1}+...m_{i-1}+1}^{\min\\{m_{1}+...+m_{i},k\\}}\Big{)}^{2}$
$\displaystyle=\delta\Big{(}\mathrm{span}\\{e_{j}\\}_{j=1}^{\min\\{m_{1}+...+m_{l},k\\}},\bigoplus_{i=1}^{l}E_{i}\Big{)}^{2}$
$\displaystyle\leq\sin^{2}\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}$

Where the first line holds since the nearest point to $\tilde{e}_{j}$ in
$\bigoplus_{i=1}^{l}\mathrm{span}\\{\chi_{\\{\lambda_{i}\\}}(T)\tilde{e}_{j}\\}_{j=m_{1}+...m_{i-1}+1}^{\min\\{m_{1}+...+m_{i},k\\}}$
is simply $\chi_{\lambda_{l}}(T)\tilde{e}_{j}$ and the $E_{i}$ are defined as
above and in (3.1). Rearranging, this implies that

$\delta_{j}^{2}\leq\frac{1}{1-\sin^{2}\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}}=\frac{1}{\cos^{2}\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})}.$

Hence it follows that

$Z(T,\\{e_{j}\\}_{j=1}^{k})=\Big{(}\sum_{j=1}^{k}\delta_{j}^{2}-1\Big{)}^{\frac{1}{2}}\leq\Big{(}\sum_{j=1}^{k}\tan^{2}\big{(}\Phi(T,\\{e_{j}\\}_{j=1}^{k})\big{)}\Big{)}^{\frac{1}{2}}\leq\sqrt{k}L.$

In particular, Theorem 3.7 and its proof now implies that

$\hat{\delta}(\mathrm{span}\\{\hat{q}_{j}\\},\mathrm{span}\\{Q_{m}e_{j}\\})\leq
B(j)\sqrt{k}Lt^{m},$

where $\\{\hat{q}_{j}\\}_{j=1}^{k}$ are orthonormal eigenvectors of $T$ and
$Q_{m}$ is a $Q-$sequence of $T$. In particular, $\\{B(j)\\}_{j=1}^{k}$ can be
computed in finitely many arithmetic operations from the induction proof of
Theorem 3.7. It follows that there exists $z_{j,m}\in\mathbb{C}$ of unit
modulus such that defining $\beta=\max\\{B(1),...,B(k)\\}\sqrt{k}L$, we have

$\left\|Q_{m}e_{j}-z_{j,m}\hat{q}_{j}\right\|\leq\beta t^{m}.$

Note that we do not need to assume knowledge of $N$ for this bound (trivially
$N\leq k$). Using that $Q_{m}$ is an isometry, this implies that

$\left|\langle Q_{m}^{*}TQ_{m}e_{j},e_{j}\rangle-\lambda_{a_{j}}\right|\leq
2\left\|T\right\|\beta t^{m}\leq 2L\beta t^{m},$

where $T\hat{q}_{j}=\lambda_{a_{j}}$. Note that we must have
$\\{\lambda_{a_{j}}\\}_{j=m_{1}+...+m_{l-1}+1}^{m_{1}+...+m_{l}}=\lambda_{l}$
and $\\{\lambda_{a_{j}}\\}_{j=m_{1}+...+m_{N-1}+1}^{k}=\lambda_{N}$ by 3. in
the definition of $\Omega_{t,L}^{k}$.

Given any $\epsilon>0$, choose $m$ large enough so that $2L\beta
t^{m}\leq\epsilon$ and $\beta t^{m}\leq\epsilon$. The fact that
$\left\|T\right\|\leq L$ and (5.2) holds implies that we can compute $\langle
Q_{m}^{*}TQ_{m}e_{j},e_{j}\rangle$ to accuracy $\epsilon$ using finitely many
arithmetical and square root operations using Theorem 4.8. Call these
approximations
$\tilde{\lambda}_{1},\tilde{\lambda}_{2},...,\tilde{\lambda}_{k}$.
Furthermore, the proof of Theorem 4.8 also makes clear that we can compute
$Q_{m}e_{j}\in l^{2}(\mathbb{N})$ to accuracy $\epsilon$ using finitely many
arithmetical and square root operations (the approximations have finite
support). Call these approximations
$\tilde{q}_{1},\tilde{q}_{2},...,\tilde{q}_{k}$. Then set

$\Gamma^{\epsilon}(T)=(\tilde{\lambda}_{1},\tilde{\lambda}_{2},...,\tilde{\lambda}_{k})\times(\tilde{q}_{1},\tilde{q}_{2},...,\tilde{q}_{k}).$

The above estimates show that
$\mathrm{dist}(\Gamma^{\epsilon}(T),\Xi_{1}(T))\leq 4k\epsilon$. The proof is
completed by setting $\Gamma_{n}(T)=\Gamma^{2^{-(n+2)}/k}(T)$. ∎

Next suppose we have a continuous increasing function function
$g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ diverging at $\infty$
such that $g(0)=0$ and $g(x)\leq x$. Let $\Omega_{\mathrm{IQR}}^{g}$ be the
set of all operators $T$ acting on $l^{2}(\mathbb{N})$ (i.e. we fix the
representation w.r.t. the canonical basis) for which the IQR algorithm
converges in the weak operator topology to a diagonal matrix with the same
spectrum as $T$ and such that

$\left\|(T-zI)^{-1}\right\|^{-1}\geq
g\big{(}\mathrm{dist}(z,\sigma(T))\big{)}.$

Note that by Theorem 3.9 this includes all normal compact operators, $T$, such
that $\\{z\in\sigma(T):\left|z\right|=s\\}$ has size at most $1$ for all $s>0$
(where we can take $g(x)=x$).333A simple compactness argument says that for
any bounded operator $T$ there is a corresponding function $g$ that works. We
will allow evaluations of $g$ in our algorithms and also assume that we are
given functions that satisfy (5.2) and have an upper bound for $\|T\|$. We
consider computing $\Xi_{2}(T)=\sigma(T)$ in the space of compact non-empty
subsets of $\mathbb{C}$ with the Hausdorff metric.

######  Theorem 5.5 ($\Sigma_{1}$ classification for spectrum).

Given the above setup we have
$\\{\Xi_{2},\Omega_{\mathrm{IQR}}^{g}\\}\in\Sigma_{1}.$ In other words, there
is a convergent sequence of general towers using radicals, $\Gamma_{n}(T)$,
such that $\Gamma_{n}(T)\rightarrow\Xi_{2}(T)=\sigma(T)$ for any
$T\in\Omega_{\mathrm{IQR}}^{g}$ and for all $n$ we have

$\Gamma_{n}(T)\subset\sigma(T)+B_{2^{-n}}(0).$

###### Proof of Theorem 5.5:.

Let $T\in\Omega_{\mathrm{IQR}}^{g}$ and $Q_{m}$ be a $Q-$sequence of $T$. Fix
$n\in\mathbb{N}$. Then Theorem 4.8 shows that we can compute any finite number
of the diagonal entries of $Q_{m}^{*}TQ_{m}$ to any given accuracy using
finitely many arithmetical and square root operations. Similarly, the proof
shows that we can compute $TQ_{m}e_{j}$ and $Q_{m}e_{j}$ to any given accuracy
in $l^{2}(\mathbb{N})$ (the approximations have finite support). Now let
$\alpha_{j,m}$ be the computed approximations of $\langle
Q_{m}^{*}TQ_{m}e_{j},e_{j}\rangle$ to accuracy $1/m$, then since
$T\in\Omega_{\mathrm{IQR}}^{g}$ we have that
$\lim_{m\rightarrow\infty}\alpha_{j,m}=\alpha_{j}\in\sigma(T)$. Furthermore,
$\\{\alpha_{j}:{j\in\mathbb{N}}\\}$ is dense in $\sigma(T)$. We have that

$\left\|(T-\alpha_{j,m}I)^{-1}\right\|^{-1}\leq\left\|TQ_{m}e_{j}-\alpha_{j,m}Q_{m}e_{j}\right\|$

and hence that

$\mathrm{dist}(\alpha_{j,m},\sigma(T))\leq
g^{-1}(\left\|TQ_{m}e_{j}-\alpha_{j,m}Q_{m}e_{j}\right\|).$ (5.4)

Given $m,j$, we can compute an upper bound $h_{j,m}$ for the right hand side
of (5.4) by approximating the norm
$\left\|TQ_{m}e_{j}-\alpha_{j,m}Q_{m}e_{j}\right\|$ from above to accuracy
$1/m$ and finitely many evaluations of $g$. Namely, let $x_{j,m}$ be the
approximation of $\left\|TQ_{m}e_{j}-\alpha_{j,m}Q_{m}e_{j}\right\|$ and set

$h_{j,m}=\frac{\min\\{l\in\mathbb{N}:g(l/m)\geq x_{j,m}\\}}{m}.$

It is then clear that $\lim_{m\rightarrow\infty}h_{j,m}=0$ and $h_{j,m}\geq
g^{-1}(\left\|TQ_{m}e_{j}-\alpha_{j,m}Q_{m}e_{j}\right\|)$.

We set $\Gamma_{n}(T)=\\{\alpha_{j,m(n,T)}:j=1,...,n\\}$ where $m(n,T)$ is
minimal such that $h_{j,m}\leq 2^{-n}$ for $j=1,...,n$. By (5.4), we must have
that

$\Gamma_{n}(T)\subset\sigma(T)+B_{2^{-n}}(0).$

It is also clear that $\Gamma_{n}(T)\rightarrow\sigma(T)$ in the Hausdorff
metric. ∎

The final result considers dominant invariant subspaces discussed in Theorem
3.15. Let $M\in\mathbb{N}$, $t\in(0,1)$ and $L>0$. We let
$\tilde{\Omega}^{M}_{t,L}$ denote the class of operators such that the
assumptions of Theorem 3.15 hold (same $M$) and such that:

  1. 1.

$\beta/\alpha<t$

  2. 2.

$\max\Big{\\{}\|T\|,\frac{\sin\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))\big{)}}{\cos\big{(}\phi(\mathrm{span}\\{e_{j}\\}_{j=1}^{M},S)\big{)}}\Big{(}1+\frac{\|PT(I-P)\|}{\alpha-\beta}\Big{)}\Big{\\}}\leq
L$

We also assume that we are given functions that satisfy (5.2) and consider
computing the dominant invariant subspace $\Xi_{3}(T)=\mathrm{ran}(P)$ in the
space of $M$-dimensional subspaces of $l^{2}(\mathbb{N})$ equipped with the
metric $\hat{\delta}$.

######  Theorem 5.6 ($\Delta_{1}$ classification for dominant invariant
subspace).

Given the above setup we have
$\\{\Xi_{3},\tilde{\Omega}^{M}_{t,L}\\}\in\Delta_{1}.$ In other words, for all
$n\in\mathbb{N}$, there exists a general tower using radicals,
$\Gamma_{n}(T)$, each an $M$-dimensional subspace of $l^{2}(\mathbb{N})$, such
that for all $T\in\tilde{\Omega}^{M}_{t,L}$,

$\hat{\delta}(\Gamma_{n}(T),\Xi_{3}(T))\leq 2^{-n}.$

###### Proof of Theorem 5.6:.

Let $n\in\mathbb{N}$ and $T\in\tilde{\Omega}^{M}_{t,L}$. Then from Theorem
3.15, we can choose $m$ large so that $t^{m}L<2^{-(n+1)}$, and hence

$\hat{\delta}(\mathrm{span}\\{Q_{m}e_{j}\\}_{j=1}^{M},\mathrm{ran}(P))<2^{-(n+1)}.$

Using Theorem 4.8 and its proof, given $\epsilon$ we can compute in finitely
many arithmetical and square root operations, approximations
$v_{m,j}(\epsilon)$ (of finite support) such that

$\|v_{m,j}(\epsilon)-Q_{m}e_{j}\|\leq\epsilon.$

The vectors $\\{Q_{m}e_{j}\\}_{j=1}^{M}$ are orthonormal, as are the
approximations $\\{v_{m,j}(\epsilon)\\}_{j=1}^{M}$. A simple application of
Hölder’s inequality then yields

$\hat{\delta}(\mathrm{span}\\{v_{m,j}(\epsilon)\\}_{j=1}^{M},\mathrm{span}\\{Q_{m}e_{j}\\}_{j=1}^{M})\leq\sqrt{M}\epsilon.$

By the triangle inequality, the proof of the theorem is complete by choosing
$\epsilon$ such that $\sqrt{M}\epsilon\leq 2^{-(n+1)}$ and then setting
$\Gamma_{n}(T)=\mathrm{span}\\{v_{m,j}(\epsilon)\\}_{j=1}^{M}$. ∎

##  6 Examples and numerical simulations

The aim of the is section is threefold:

  1. 1.

To demonstrate the convergence and implementation results of Section 3–5 on
practical examples.

  2. 2.

To demonstrate that, as well as the proven results, the IQR algorithm performs
better than theoretically expected in many cases. In particular we conjecture
that for normal operators whose essential spectrum has exactly one extremal
point, the IQR algorithm will also converge to this point. We also demonstrate
cases where this seems to hold even if there are multiple extreme points of
the essential spectrum and even in non-normal cases.

  3. 3.

To compare the IQR algorithm to the finite section method and show that in
some cases it considerably outperforms it. In general one can view
$\sigma(P_{m}Q_{n}^{*}TQ_{n}|_{P_{m}\mathcal{H}})$ as a generalised version of
the finite section method, now with two parameters ($m$ and $n$) that can be
varied with $n$ controlling the number of IQR iterates. In some cases we find
this avoids spectral pollution whilst still converging to the entire spectrum.

Before embarking with some numerical examples, two remarks are in order.
First, extra care has been taken in the case of non self-adjoint operators
whose finite truncations can be non-normal and hence the computation of their
spectra can be numerically unstable. Unless stated otherwise, all calculations
were performed in double precision (in MATLAB) and have been checked against
extended precision [36] to ensure that none of the results are due to
numerical artefacts. Second, when dealing with operators acting on
$l^{2}(\mathbb{Z})$ we use $\mathbb{N}$ as an index set by listing the
canonical basis as $e_{0},e_{1},e_{-1},e_{2},e_{-2},...$, allowing us to apply
the IQR algorithm on $l^{2}(\mathbb{N})$. Of course different indexing is
possible and in general this would lead to different implementations of the
IQR algorithm,444A discussion of this is beyond the scope of this paper. In
effect, for invertible operators, this corresponds to choosing the order of
columns on which to perform a Gram-Schmidt type procedure. but we stick with
this ordering throughout.

###  6.1 The finite section method

We first briefly say a few words on the finite section method, the standard
means to discretise infinite matrices, since comparisons will be made later.
If $\\{P_{m}\\}_{m\in\mathbb{N}}$ is a sequence of finite-rank projections
such that $P_{m+1}\geq P_{m}$ and $P_{m}\rightarrow I$ strongly, where $I$ is
the identity, then the idea is to replace $T$ by the finite square matrix
$P_{m}T|_{P_{m}\mathcal{H}}$ (typically, one takes $P_{m}$ to be the
orthogonal projection onto $\mathrm{span}\\{e_{1},\ldots,e_{m}\\}$). Thus, to
find $\sigma(T)$, we instead compute $\sigma(P_{m}T|_{P_{m}\mathcal{H}})$.
However, there can be significant issues when using the finite section method.
In general, there is no guarantee that the computed spectra
$\sigma(P_{m}T|_{P_{m}\mathcal{H}})$ need converge to $\sigma(T)$.

For example, consider the shift operator $Se_{j}=e_{j+1}$ on
$l^{2}(\mathbb{N})$. If $P_{m}$ projects onto
$\mathrm{span}\\{e_{1},\ldots,e_{m}\\},$ we would get that
$\sigma((P_{m}S|_{P_{m}\mathcal{H}})=\\{0\\}$ for all $m$, whereas $\sigma(S)$
is the closed unit disc. We can also have that
$\sigma(P_{m}T|_{P_{m}\mathcal{H}})\nsubseteq\sigma(T).$ For example, let

$A=\left(\begin{matrix}a_{1}&i&&&\\\ 1&a_{2}&i&&\\\ &1&a_{3}&i&\\\
&&1&a_{4}&\ddots\\\ &&&\ddots&\ddots\\\ \end{matrix}\right),$ (6.1)

where $a_{j}=5\cos(j)/4+2i\sin(j)$. To gain an accurate picture of the
spectrum, note that $A$ is banded and hence we can compute approximates to the
pseudospectrum [42]. In order to approximate the spectrum in the best possible
way we must take $\epsilon$ as small as possible. Unfortunately, there is a
restriction to how small $\epsilon$ can be depending on
$\epsilon_{\mathrm{mach}}$ (machine precision) of the software used. To
illustrate this, observe that the approximates are given by (a discrete
version of)

$\begin{split}\Gamma_{m}(A)&=\\{z\in\mathbb{C}:\min\\{\sqrt{\lambda}:\lambda\in\sigma_{0}(P_{m}(A-z)^{*}(A-z)|_{P_{m}\mathcal{H}})\\}\leq\epsilon\\}\\\
&\qquad\quad\cup\\{z\in\mathbb{C}:\min\\{\sqrt{\lambda}:\lambda\in\sigma_{0}(P_{m}(A-z)(A-z)^{*}|_{P_{m}\mathcal{H}})\\}\leq\epsilon\\}.\end{split}$
(6.2)

Thus, ignoring the additional error in computing the smallest singular values
(denoted by $\sigma_{0}$) and assuming $A$ to have matrix entries of order
$1$, computing $\Gamma_{m}(A)$ will have the same challenges as if one squares
a real number and then takes its square root. In particular, due to the
floating point arithmetic used in the software and (6.2) we must at least have
that

$\epsilon\gtrsim\sqrt{\epsilon_{\mathrm{mach}}},$

and this puts a serious restriction on our computation, particularly for the
non-normal case where the distance $d_{H}(\sigma(T),\sigma_{\epsilon}(T))$ may
be large (though we always have $\sigma(T)\subset\sigma_{\epsilon}(T)$).
However, it is possible to detect spectral pollution outside of
$\sigma_{\epsilon}(T)$ if we can approximate it well.

The phenomenon of “spectral pollution” occurs for $A$: namely, the computed
spectrum $\sigma(P_{m}A|_{P_{m}\mathcal{H}})$ contains elements that have
nothing to do with $\sigma(A).$ This is visualised in Fig. 1, an example with
spectral pollution $z\notin\sigma_{1/10}(A)$ where the same phenomenon occurs
for larger $m$. The spectral pollution phenomenon is well known. As the
following theorem suggests, such pollution can be arbitrarily bad.

Figure 1: Left: $\sigma_{\epsilon}(A)$ plotted as contours of the resolvent
norm, as well as $\sigma(P_{m}A|_{P_{m}\mathcal{H}})$ for $m=300$ with the
false eigenvalue (recall that $\sigma(A)\subseteq\sigma_{\epsilon}(A)$).
Right: $\sigma_{\epsilon}(T)$, $\sigma(T)$ and
$\sigma(P_{m}T|_{P_{m}\mathcal{H}})$ for $m=100$.

######  Theorem 6.1 (Pokrzywa [62]).

Let $A\in\mathcal{B}(\mathcal{H})$ and $\\{P_{m}\\}$ be a sequence of finite-
dimensional projections converging strongly to the identity. Suppose that
$S\subset W_{e}(A).$ Then there exists a sequence $\\{\tilde{P}_{m}\\}$ of
finite-dimensional projections such that $P_{m}<\tilde{P}_{m}$ (so
$\tilde{P}_{m}\rightarrow I$ strongly) and

$d_{H}(\sigma(A_{m})\cup S,\sigma(\tilde{A}_{m}))\rightarrow 0,\quad\text{as
}m\rightarrow\infty,$

where

$A_{m}=P_{m}A|_{P_{m}\mathcal{H}},\qquad\tilde{A}_{m}=\tilde{P}_{m}A|_{\tilde{P}_{m}\mathcal{H}}$

and $d_{H}$ denotes the Hausdorff metric.

Despite this result, the finite section can perform quite well. This is the
case for self adjoint operators [6, 21, 40] and it is also well suited for the
computation of pseudospectra of Toeplitz operators [14, 18]. Moreover, in
general, we have the following (recall that $W_{e}(T)$ is the convex hull of
the essential spectrum for $T$ normal):

######  Theorem 6.2 (Pokrzywa [62]).

Let $T\in\mathcal{B}(\mathcal{H})$ and $\\{P_{m}\\}$ be a sequence of finite-
dimensional projections converging strongly to the identity. If $\lambda\notin
W_{e}(T)$ then $\lambda\in\sigma(T)$ if and only if

$\mathrm{dist}(\lambda,\sigma(P_{m}T|_{P_{m}\mathcal{H}}))\longrightarrow
0,\qquad\text{as }m\rightarrow\infty.$

However, if we want to use the finite section method and rely on Theorem 6.2
we must know $W_{e}(T),$ and that may be unpleasant to compute. Alternatively,
we could hope that $\sigma_{\mathrm{ess}}(T)$ is close to $W_{e}(T)$. For
example if $T$ is hypo-normal ($T^{*}T-TT^{*}\geq 0$) then

$\mathrm{conv}(\sigma_{\mathrm{ess}}(T))=W_{e}(T),$

where $\mathrm{conv}(\sigma_{\mathrm{ess}}(T))$ denotes the convex hull of
$\sigma_{\mathrm{ess}}(T).$ But what if we have a “very non-normal” operator?

Another problem we may encounter using the finite section method is that even
though $\sigma_{d}(T)$ may be recovered, one may get a very misleading picture
of the rest of the spectrum. Such problems are illustrated in the following
simple example. Let

$T=\left(\begin{array}[]{cccc|cccc}2.5+0.5i&0&0&0&0&0&0&\cdots\\\
1&3-0.5i&0&0&0&0&0&\cdots\\\ 0&1&1.7&0.05&0&0&0&\cdots\\\
0&0&0.05&t_{4}&0&0&0&\cdots\\\ \hline\cr 0&0&0&0&t_{5}&0&0&\cdots\\\
0&0&0&0&1&t_{6}&0&\cdots\\\ 0&0&0&0&0&1&t_{7}&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\ddots\\\
\end{array}\right),$ (6.3)

where $t_{j}=1+0.5(\sin(j)+i\cos(j))$ for $j\geq 4.$ This operator decomposes
into an upper $4\times 4$ block and an operator acting on the perpendicular
subspace. It is also possible to compute the spectrum analytically (it
consists of a disc of radius $1$ centred at $1$ together with two isolated
eigenvalues). Again, we can compute the pseudospectrum of $T$ (Fig. 1) to
reveal that whilst the eigenvalues produced by the finite section method are
correct, they do not capture the entire spectrum. It is straightforward to
adapt this example (e.g. by changing basis) to have the same phenomena without
an obvious decomposition of the operator into a finite part and triangular