Editing Householder transformation (section)

====QR decomposition====

{{main|QR decomposition#Using Householder reflections}}

Householder transformations can be used to calculate a [[QR decomposition]].  Consider a matrix tridiangularized up to column <math>i</math>, then our goal is to construct such Householder matrices that act upon the principal submatrices of a given matrix

<math>
\begin{bmatrix}
a_{11} & a_{12} & \cdots & & & a_{1n} \\
0 & a_{22} & \cdots & & & a_{1n} \\
\vdots & & \ddots & & & \vdots \\
0 & \cdots & 0 & x_{1}=a_{ii} & \cdots & a_{in} \\
0 & \cdots & 0 & \vdots &  & \vdots \\
0 & \cdots & 0 & x_{n}=a_{ni} & \cdots & a_{nn}
\end{bmatrix}
</math>

via the matrix

<math>
\begin{bmatrix}
I_{i-1}&0\\
0&P_v
\end{bmatrix}
</math>.

(note that we already established before that Householder transformations are unitary matrices, and since the multiplication of unitary matrices is itself a unitary matrix, this gives us the unitary matrix of the QR decomposition)

If we can find a <math>\vec v</math> so that

<math>P_v \vec x = \vec e_1</math>

we could accomplish this. Thinking geometrically, we are looking for a plane so that the reflection about this plane happens to land directly on the basis vector.  In other words,

{{NumBlk|:|<math>\vec x-2\langle\vec x,\vec v\rangle \vec v = \alpha \vec e_1</math>|{{EquationRef|1}}}}

for some constant <math>\alpha</math>.  However, for this to happen, we must have

<math>\vec v\propto\vec x-\alpha\vec e_1</math>.

And since <math>\vec v</math> is a unit vector, this means that we must have

{{NumBlk|:|<math>\vec v=\pm\frac{\vec x-\alpha\vec e_1}{\|\vec x-\alpha\vec e_1\|_2}</math>|{{EquationRef|2}}}}

Now if we apply equation ({{EquationNote|2}}) back into equation ({{EquationNote|1}}), we get

<math display="block">\vec x-\alpha\vec e_1 = 2(\langle \vec x,\frac{\vec x-\alpha\vec e_1}{\|\vec x-\alpha\vec e_1\|_2}\rangle\frac{\vec x-\alpha\vec e_1}{\|\vec x-\alpha\vec e_1\|_2}</math>

Or, in other words, by comparing the scalars in front of the vector <math>\vec x - \alpha\vec e_1</math> we must have

<math>\|\vec x-\alpha\vec e_1\|_2^2=2\langle\vec x,\vec x-\alpha e_1\rangle</math>.

Or

<math>2(\| \vec x\|_2^2-\alpha x_1)=\|\vec x\|_2^2-2\alpha x_1+\alpha^2</math>

Which means that we can solve for <math>\alpha</math> as

<math>\alpha=\pm\|\vec x\|_2</math>

This completes the construction; however, in practice we want to avoid [[catastrophic cancellation]] in equation ({{EquationNote|2}}).  To do so, we choose the sign of <math>\alpha</math> as

<math>\alpha=-sign(Re(x_1))\|\vec x\|_2</math>
<ref>{{cite book |last1=Saad |first1=Yousef |author-link1=Yousef Saad |title=Iterative methods for sparse linear systems |publisher=Society for Industrial and Applied Mathematics |date=2003 |pages=11–13 }}</ref>