The Factorization

A Givens rotation can zero out one element in a row, using some other row. The rotation can be seen as:

$$A(:,[i,j]) \gets \left( \begin{array}{rr} c & s \\ -s & c \end{array} \right)^T A(:,[i,k])$$ (2.1)

where $c=cos(\theta)$ and $s=sin(\theta)$, for some $\theta$, which clearly guarantees orthogonality.

Contrary to eg. the simple Gauss elimination, we will not only introduce non-zeros (called fill-ins) in the row holding the element we are eliminating, but also in the eliminating row. The orthogonality of the transform should hopefully make up for this, by not requiring us to pivot rows in order to guarantee numerical stability.

An example where ``$x$'' is used to represent some arbitrary non-zero, and ``0'' is used to represent the zero elements, could be:

$$\left( \begin{array}{rrrr} x & x & x & 0 \\ x & x & 0 ... ...& 0 \\ 0 & 0 & x & x \\ 0 & x & x & x \end{array}\right)$$

The ``$f$'' denotes a ``fill-in''. In order to completely factorize the system, we will ofcourse have to apply more Givens Rotations. But the above example should demonstrate how one Givens Rotation affects the system.

Whenever a fill-in is introduced below the diagonal, it will require one extra Givens rotation in order to eliminate it. A fill-in above the diagonal, will require more work in the final back-substitution.