Principles of Mathematics in Operations Research

88 6 Computational Aspects

Remark 6.2.3 (QR Algorithm) Start with Ao. Factor it using the Gram-

Schmidt process into QQRQ, then reverse factors A\ = RQQO- A\ is similar to

Ao: Q 0 AoQo — QQ (QORO)QO — A\. So, Ak = QkRk =^ Ak+i = RkQk- Ak

approaches to a triangular form in which we can read the eigen values from

the main diagonal. There are some modifications to speed up this procedure as

well.

Definition 6.2.4 // a matrix is less than a triangular form, one nonzero di-

agonal below the main diagonal, it is called in Hessenberg form. Furthermore,

if it is symmetric then it is said to be in tridiagonal form.

Definition 6.2.5 A Householder transformation (or an elementary reflector)

is a matrix of the form

T

H = I-2- |2 "

Remark 6.2.6 Often v is normalized to become a unit vector u = jr^r, then

H — I — 2uuT. In either case, H is symmetric and orthogonal:

HTH =(I- 2uuT)T{I - 2uuT) = 1- AuuT + AuuTuuT = I.

In the complex case, H is both Hermitian and unitary.

H is sometimes called elementary reflector since

Proposition 6.2.7 Let z = e\ — (1,0, ,0)r, and a — \x\, andv = x+crz.
Then, Hx = -az = {-a, 0, • • • , 0)T.

Proof.

Hx

VV X T

(x + az)-

2(x + az)Tx

IHI' v (x + az)T(x + az)

Hx = x — (x + az) — —az. D

Remark 6.2.8 Assume that we are going to transform A into a tridiagonal
or Hessenberg form U~^1 AU. Let

Hx =

a-21

031

_0.nl _

, z =

"1"

0

0

Ui

10 0 00

0

0 H

0

0

[/f\ andU~lAUi =

an * * * *

—a * * * *

0 * * * *

0 * * * *

0 * * * *