\magnification=1200

\input coursemacro.defs
\input coursepages
\input font.defs

\def\sign{{\rm sign}}

\def\runningtitle{QR}

{\bigbold QR}

{\bold Tridiagonal reduction}

We start with the matrix $M$ of size $n \times 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, \dots ,1,0, \dots , 0]$.
We choose the reflection vector to be
$u + \beta e_{i+1}$, where 
%
$$ \beta =\sign(u[i+1]) \, \Vert u \Vert  $$
%
to avoid cancellation.
This reflects $u$ to $-\beta e_{i+1}$.
So we set
%
$$ w = (u + \beta e_{i+1}) $$
%
and reflect perpendicularly to $w$.

Then we apply conjugation by $R_{w}$ to $M_{i+1}$.
All in all:
%
$$ \eqalign {
\nu &= u \Dot u \cr
\beta &= \sign(u[i+1]) \sqrt{\nu} \cr
w &= u + \beta e_{i+1} \cr
\mu &= w \Dot w \cr
	&= \Vert u \Vert^{2} + 2 u_{i+1} \beta + \beta^{2} \cr
	&= 2 \beta^{2} + 2 u_{i+1} \beta \cr
	&= 2 \beta(\beta + u_{i+1}) \cr
	&= 2 ( \nu + u_{i+1} \beta )\cr
\gamma &= 2/\mu \cr
p &= M_{i+1} w \cr
q &= \gamma \left( p - \gamma \, { w \Dot p \over 2 } \, w \right ) \cr
M_{i+1} &= M_{i+1} - w \otimes q - q \otimes w \cr
} $$
%
and $u$ is replaced by $-\beta e_{i+1}$.

{\bold QR for a tridiagonal matrix}

Suppose now that $M$ is tridiagonal.  We wish to diagonalize it.


\bye