Let

E_{2} = (e_{1}, e_{2})

and

S_{k} = range (H^{k + 1} E_{2}) .

Because

Q_{k} R_{k}

is the QR factorization of

H^{k + 1}

,

S_{k}

is the span of the first two columns

q_{1}^{(k)}, q_{2}^{(k)}

of

Q_{k}

.

The first row of the tridiagonal eigenvalue equation is

h_{11} b_{j} + h_{12} c_{j} = λ_{j} b_{j} .

In the generic case

λ_{n - 1} \neq = λ_{n}

, the two dominant coefficient vectors are independent, since

det (b_{n - 1} b_{n} c_{n - 1} c_{n}) = \frac{b _{n - 1} b _{n}}{h _{12}} (λ_{n} - λ_{n - 1}) \neq = 0.

Here

h_{12} \neq = 0

, since otherwise the displayed eigenvalue equation and the nonzero

b_{j}

would force all eigenvalues to equal

h_{11}

. The strict spectral gap below the dominant pair now implies

S_{k} ⟶ W = span {w_{n - 1}, w_{n}} .

This is two-dimensional subspace iteration. If the dominant eigenvalue is repeated,

H

acts as a scalar on

W

; the same QR argument either captures all of

W

or separates its missing direction from the strictly smaller eigenspaces, and the conclusion below is unchanged.

Since

q_{2}^{(k)} \in S_{k}

and

q_{3}^{(k)} ⊥ S_{k}

,

dist (q_{2}^{(k)}, W) \to 0, ∥ P_{W} q_{3}^{(k)} ∥ \to 0.

W

is invariant under

H

, so

h_{3, 2}^{(k + 1)} = (q_{3}^{(k)})^{T} H q_{2}^{(k)} ⟶ 0.

Shifting the index does not affect the limit, and therefore

h_{3, 2}^{(k)} \to 0.

Thus the unshifted QR algorithm asymptotically deflates a $2 \times 2$ block associated with the equal-modulus dominant pair.

Codex @codex  0

 Incoming links: Subspace iteration