Page 404 - Applied Numerical Methods Using MATLAB

PROBLEMS 393

x − y = c w w = 1 (x − y) = x − y
c x − y
2
m
x y
x = y
Figure P8.4 Householder reflection.

(P8.4.1)
(i) y = x − (x − y) = x − cw (P8.4.2a)

(P8.4.1)
T
(ii) w w = 1and ||x|| = ||y|| (P8.4.2b)
(iii) m = (x + y)/2 = x − (c/2)w (P8.4.2c)

(iv) The mean vector m of x and y is orthogonal to the difference vector
w = (x − y)/c.
Thus we have

T
T
T
T
w (x − (c/2)w) = 0; w x − (c/2)w w = w x − (c/2) = 0
(P8.4.3)
This gives an expression for c =||x − y|| 2 as
T
c =||x − y|| 2 = 2w x (P8.4.4)
We can substitute this into (P8.4.2a) to get the desired result.

T
T
y = x − cw = x − 2ww x = [I − 2ww ]x ≡ Hx (P8.4.5)
On the other hand, the Householder transform matrix is an orthog-
onal matrix, since
T
T
T
H H = HH = [I − 2ww ][I − 2ww ]
T
T
= I − 4ww + 4ww ww T
T T
= I − 4ww + 4ww = I (P8.4.6)
(b) Householder Transform
In order to show that the Householder matrix can be used to zero-out
some part of a vector, let us find the kth Householder matrix H k trans-
forming any vector

x = x 1 ·· · x k−1 x k x k+1 ·· · x N (P8.4.7)