§

u¦

At each step, the algorithm multiplies the previous Arnoldi vector by and then or-

u¥ R¦

thonormalizes the resulting vector against all previous ™s by a standard Gram-Schmidt

u¥

procedure. It will stop if the vector computed in line 4 vanishes. This case will be ex-

amined shortly. Now a few simple properties of the algorithm are proved.

h¤ ¡ v A£

£¦ vA

9

' ' ©' )$ )

§

Assume that Algorithm 6.1 does not stop before the -th step. !

¢ ¦ (( £ ¦ (

Then the vectors form an orthonormal basis of the Krylov subspace

¦

W

§’(( W ©W§( W ¦ § H ¬ ¢

£¡

¢

C

¦ © ¦ W “

¢

W

yq

„ 5|

tC

9

¡ © B ¦£

§

1B

£ 6 A T

£

}( u ¦

¬

The vectors , are orthonormal by construction. That they span $V˜ (

!((

V

X

y §

¢ ¢

u¦ u u

follows from the fact that each vector is of the form where is a ¦

¢

W “ W“

T T W

²z

polynomial of degree . This can be shown by induction on as follows. The result is

! ¢

X X

y

¢

¬ ¬ §

¢

clearly true for , since with . Assume that the result is true ¦ ¦

u¦ W W

y y

for all integers and consider . We have

W"U u T T

u

a±a q ®

i

f f

² W ¦X § X

² u ¦§§ ¬ §T ¬ R ¦ u R §

¢ ¢

u u¦ u R uvR ¦

£ £ £

W“ W“

’U W"U

W W

R R

W W

X

§

¢ ¢

u¦ u u

which shows that can be expressed as where is of degree and completes

¦

W"U W

the proof.

Q¤ ¡$ v A£

£¦ ´A

' ' T©' 2 )

§)

(¤

¥

Denote by , the matrix with column vectors , , ¦

¢ ! $

¡ ¥ X ¡y W

vR

u

, by , the Hessenberg matrix whose nonzero entries are de¬ned by

w!

¦ ¢ ¢ ! £

¡

Algorithm 6.1, and by the matrix obtained from by deleting its last row. Then the

¢ ¢

following relations hold:

± ¯ q ®i

$¢ ¡

§ ¬ ¥w

¢ ¢ ¢¡ ¢

a±— q ®

i

¡

¬ (¢

¢

a± q ®

i

¡ "U

W

§ ¬ ¢

¢

¢

£ 6 A

£

The relation (6.5) follows from the following equality which is readily derived

from lines 4, 5, and 7 of Algorithm 6.1,

u

a± q ®

i

"U f

W

¬ u ©§ }

¬

( R ¦ uR

¦ $Q˜ (

!((

£

y

£R

W

Relation (6.4) is a matrix reformulation of (6.7). Relation (6.6) follows by multiplying both

sides of (6.4) by and making use of the orthonormality of . ¦§ © ¢ ¦ V(

(

¢

W