Page 356 - Matrix Analysis & Applied Linear Algebra

352 Chapter 5 Norms, Inner Products, and Orthogonality

T
T
T
T
T
Note: If A is a symmetric matrix, then H =(P AP) = P A P = H,
so H is symmetric. But as illustrated below for n =5, a symmetric Hessenberg
form is a tridiagonal matrix,
 
∗∗ 000
 ∗∗∗ 00 
T
H = P AP =  0 ∗∗∗ 0  ,


00 ∗∗∗
 
000 ∗∗
so the following useful corollary is obtained.
• Every real-symmetric matrix is orthogonally similar to a tridiagonal matrix,
and Householder reduction can be used to compute this tridiagonal matrix.
However, the Lanczos technique discussed on p. 651 can be much more effi-
cient.
Example 5.7.5
Problem: Compute the QR factors of a nonsingular upper-Hessenberg matrix
n×n
H ∈ .
Solution: Due to its smaller multiplication count, Householder reduction is
generally preferred over Givens reduction. The exception is for matrices that
have a zero pattern that can be exploited by the Givens method but not by
the Householder method. A Hessenberg matrix H is such an example. The
first step of Householder reduction completely destroys most of the zeros in
H, but applying plane rotations does not. This is illustrated below for a 5 × 5
Hessenberg form—remember that the action of P k,k+1 affects only the k th and
(k +1) st rows.

     
∗∗∗∗∗ ∗∗∗∗∗ ∗∗∗∗∗
 0  0
 ∗∗∗∗∗  ∗∗∗∗  ∗∗∗∗ 
  P 12   P 23  
 0 ∗∗∗∗  −−−→  0 ∗∗∗∗  −−−→  00 ∗∗∗ 
00 ∗∗∗ 00 ∗∗∗ 00 ∗∗∗
     
000 ∗∗ 000 ∗∗ 000 ∗∗
   
∗∗∗∗∗ ∗∗∗∗∗
 0 ∗∗∗∗   0 ∗∗∗∗ 
 P 45 
P 34 
−−−→  00 ∗∗∗  −−−→  00 ∗∗∗  .

000 ∗∗ 000 ∗∗
   
000 ∗∗ 0000 ∗
In general, P n−1,n ··· P 23 P 12 H = R is upper triangular in which all diagonal
entries, except possibly the last, are positive—the last diagonal can be made pos-
itive by the technique illustrated in Example 5.7.2. Thus we obtain an orthogonal
T
matrix P such that PH = R, or H = QR in which Q = P .