Introduction to Computational Linear Algebra

120 Introduction to Computational Linear Algebra

Theorem 5.10 (Convergence of the QR Algorithm) Let H ∈ C

n×n

an

unreduced upper Hessenberg matrix of which eigenvalues satisfy

|λ

1

| > |λ

2

| > ··· > |λ

n

| > 0. (5.16)

Under the assumption (5.16), when applied on H, the QR algorithm builds

a sequence of upper-Hessenberg matrices that are unitarily similar to H and

such that the sequence converges (modulo a unitary diagonal matrix) to an

upper-triangular matrix T . The diagonal of T is diag(λ

1

, ··· , λ

n

).

Proof. See reference [18]. A simpler proof for the real symmetric case is also

given in reference [20].

Acceleration of the Convergence

Introduction of shifts ...