The QR process

Tridiagonal reduction We start with the matrix M of size n × n. Suppose we are looking at the lower submatrix M_{i} at corner M[i][i], for i = 0 to n − 2. Set m = n − i − 1. Let u be the m-dimensional column vector M[i + 1][i] to M[n − 1][i]. Then we apply an m-dimensional reflection to u to get a multiple of e_{i+1} = [0, …, 1, 0, …, 0]. We choose the reflection vector to be u + βe_{i+1}, where

β = sign(u[i + 1]) ∥u∥

to avoid cancellation. This reflects u to −βe_{i+1}. So we set

w = (u + βe_{i+1})

and reflect perpendicularly to w. Then we apply conjugation by R_{w} to M_{i+1}. All in all:

ν = u^{•} u
β = sign(u[i + 1])\sqrt{ν}
w = u + βe_{i+1}
μ = w^{•} w
= ∥u∥^{2} + 2u_{i+1}β + β^{2}
= 2β^{2} + 2u_{i+1}β
= 2β(β + u_{i+1})
= 2(ν + u_{i+1}β)
γ = 2/μ
p = M_{i+1}w
q = γ (p − γ \frac{w^{•} p}{2} w)
M_{i+1} = M_{i+1} − w ⊗ q − q ⊗ w

and u is replaced by −βe_{i+1}. QR for a tridiagonal matrix