¬

9. £

W"U

W"U

10. EndDo

In exact arithmetic, this algorithm and Algorithm 6.1 are mathematically equivalent. In

the presence of round-off the above formulation is much more reliable. However, there

are cases where cancellations are so severe in the orthogonalization steps that even the

Modi¬ed Gram-Schmidt option is inadequate. In this case, two further improvements can

be utilized.

The ¬rst improvement resorts to double orthogonalization. Whenever the ¬nal vector

u¥ obtained at the end of the main loop in the above algorithm has been computed, a

³ tC

yq

„ 5|

9

¡ © B ¦£

§

1B

§ £u©

u¥

test is performed to compare its norm with the norm of the initial (which is ). ¦

If the reduction falls below a certain threshold, indicating severe cancellation might have

occurred, a second orthogonalization is made. It is known from a result by Kahan that

additional orthogonalizations are super¬‚uous (see, for example, Parlett [160]).

The second improvement is to use a different technique altogether. From the numerical

point of view, one of the most reliable orthogonalization techniques is the Householder

algorithm. Recall from Chapter 1 that the Householder orthogonalization uses re¬‚ection

² ¬H¥

matrices of the form to transform a matrix into upper triangular form. ¤

¥ ¥@

˜

H H

In the Arnoldi algorithm, the column vectors of the matrix to be orthonormalized are ¤

§

u© u¦

not available ahead of time. Instead, the next vector is obtained as , where is the ¦

R¦

current basis vector. In the Householder algorithm an orthogonal column is obtained as

R ¡ R £ R (

¥W ¥ ¥ ¥ ¥

where are the previous Householder matrices. This vector is then

(

W

§

multiplied by and the previous Householder transforms are applied to it. Then, the next

Householder transform is determined from the resulting vector. This procedure is described

in the following algorithm, which was originally proposed by Walker [221].

g

˜h¤ v ¢

¡¦ ¦

84C¥ P7 5 £¡ D R¥¤A P¥ P76 8

5BD Q BD

0 (%&$

'#

) 2

1 3

¢

¬ W

1. Select a nonzero vector ; Set ¦

¦

v

¬

2. For Do: w

#( #(V(

! !

yT y u¥

3. Compute the Householder unit vector such that

V(w( y vrE¡Y R ¬ X Ru X u u ¥ T

¬(

²

4. and V

u

y (

¤rV( y vEe`u¬ u ¥ u

¬ (Y

² ¬ u¥ ¥u ¥˜

5. , where

¢¬ W

¥

6. £

u u ¥ £ ¥ ¦¬ “ u ¦

¥

7. ¡

W! 3

u ¥ u ¦¬

u ¦§§ ¥ u

¥ "U

8. If compute

W“ W

W

9. EndDo

u¥

For details regarding the determination of the Householder vector in the third to ¬fth

u

¥

lines and on its use in the sixth to eight lines, see Chapter 1. Recall that the matrices need

u u

not be formed explicitly. To obtain from in line 6, zero out all the components from £

uW“

¤ ¤

position through of the -vector and change its -th component, leaving all others

w

y ¥¤

unchanged. Thus, the matrix will have the same structure as the ( £ $ & ¢ £ (

(

! £

W

matrix of equation (1.22) in Chapter 1. By comparison with the Householder algorithm

¤ ¢

¢

seen in Chapter 1, we can infer that the above process computes the factorization of ¤

W§ ’§ W ’§ W§

© ( § ( £ © ( © ¦

the matrix . De¬ne¦(

¦

¦

¦ ( ¢

R a± q ®

i

¥ ¦¬

¥ ¥

u uu

¤

W“ W

u

The de¬nition of in line 8 of the algorithm yields the relation,

"U

W

¡¬ u ©§ u

¦ u

¤

"U

W

u¥ u

After the next Householder transformation is applied in line 6, satis¬es the rela-

£