Introduction to Computational Linear Algebra

140 Introduction to Computational Linear Algebra

arithmetic (machine precision parameter: ). We assume that

A

˜

V

k

=

˜

V

k

˜

T

k

+

˜

β

k+1

˜v

k+1

e

T

k

+ E

k

where kE

k

k

2

= O(kAk

2

). For any eigenpair (λ, z) of

˜

T

k

and x =

˜

V

k

z its

corresponding Ritz vector, prove that







kAx − λxk

2

−

˜

β

k+1

|e

T

k

z|







= O(kAk

2

). (5.47)

This bound allows to consider that the pair (λ, x) is an eigenpair when

˜

β

k+1

|e

T

k

z| = O(kAk

2

).

2. An algorithm to compute Λ(A) ∩[a, b], where a and b are given. Justify the

following algorithm:

(i) Perform Lanczos without reorthogonalization to build

˜

V

m

and

˜

T

m

for a

large m (e.g., m = n or m = 2n). The basis

˜

V

m

is not stored.

(ii) Determine Λ

1

= Λ(

˜

T

m

) ∩ [a, b] = {λ

1

, ··· , λ

q

} and the corresponding

eigenvectors Z

1

= [z

1

, ··· , z

q

].

(iii) Eliminate some spurious eigen