Page 358 - Matrix Analysis & Applied Linear Algebra

354 Chapter 5 Norms, Inner Products, and Orthogonality

2
2
2
2
5.6.9) to produce the conclusion b + b 2 = a +2a + a . Now use the fact
ii jj ii ij jj
that b kk = a kk for all k = i, j together with B = A to write
F F
2 2 2 2 2 2 2
B = B − b = B − b − b + b
F F kk F kk ii jj
k k
=i,j
2 2 2 2 2 2 2 2
= A − a − a +2a + a = A − a − 2a
F kk ii ij jj F kk ij
k
=i,j k
2 2
= A − 2a .
F ij
Furthermore, since a 2 pq ≤ a 2 ij for all p = q,
2

2 2 2 2 2 2 A F
A = a ≤ a =(n − n)a =⇒−a ≤− ,
F pq ij ij ij n − n
2
p=q p=q

so
2
2 2 2 2 A F 2 2
B = A − 2a ≤ A − 2 = 1 − A .
F F ij F n − n n − n F
2
2
Jacobi’s Diagonalization Algorithm. Start with A 0 = A, and produce a
T
sequence of matrices A k = P A k−1 P k , where at the k th step P k is a plane
k
rotation constructed to annihilate the maximal off-diagonal entry in A k−1 . In
particular, if a ij is the entry of maximal magnitude in A k−1 , then P k is the
rotator in the (i, j)-plane defined by setting
1 σ (a ii − a jj )
2
s = √ and c = √ = 1 − s , where σ = .
1+ σ 2 1+ σ 2 2a ij
For n> 2we have
k
2 2 2

A ≤ 1 − A → 0as k →∞.
k F 2 F
n − n
Therefore, if P (k) is the orthogonal matrix defined by P (k) = P 1 P 2 ··· P k , then
T (k)
(k)
lim P AP = lim A k = D
k→∞ k→∞
is a diagonal matrix.
Exercises for section 5.7
5.7.1. (a) Using Householder reduction, compute the QR factors of
 
1 19 −34
A =  −2 −5 20  .
2 8 37
(b) Repeat part (a) using Givens reduction.