Givens Rotation - Triangularization

Triangularization

Given the following 3x3 Matrix, perform two iterations of the Given's Rotation to bring the matrix to an upper Triangular matrix in order to compute the QR decomposition.

$A = \begin{bmatrix} 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end{bmatrix}$

In order to form the desired matrix, we must zero elements (2,1) and (3,2). We first select element (2,1) to zero. Using a rotation matrix of:

$G_{1} = \begin{bmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$

We have the following matrix multiplication:

$\begin{bmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end{bmatrix}$

Where:

$\begin{align} r &{}= \sqrt{6^2 + 5^2} = 7.8102 \\ c &{}= 6 / r = 0.7682\\ s &{}= -5 / r = -0.6402 \end{align}$

Plugging in these values for c and s and performing the matrix multiplication above yields a new A of:

$A =\begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end{bmatrix}$

We now want to zero element (3,2) to finish off the process. Using the same idea as before, we have a rotation matrix of:

$G_{2} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end{bmatrix}$

We are presented with the following matrix multiplication:

$\begin{bmatrix} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end{bmatrix} \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end{bmatrix}$

Where:

$\begin{align} r &{}= \sqrt{(-2.4327)^2 + 4^2} = 4.6817 \\ c &{}= -2.4327 / r = -0.5196 \\ s &{}= -4 / r = -0.8544 \end{align}$

Plugging in these values for c and s and performing the multiplications gives us a new matrix of:

$R = \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & 4.6817 & 0.9664 \\ 0 & 0 & -4.1843 \\ \end{bmatrix}$

This new matrix R is the upper triangular matrix needed to perform an iteration of the QR decomposition. Q is now formed using the transpose of the rotation matrices in the following manner:

$Q = G_{1}^T * G_{2}^T$

Performing this matrix multiplication yields:

$Q = \begin{bmatrix} 0.7682 & 0.3327 & 0.5470 \\ 0.6402 & -0.3992 & -0.6564 \\ 0 & 0.8544 & -0.5196 \\ \end{bmatrix}$

This completes two iterations of the Givens Rotation and calculating the QR decomposition can now be done.

Read more about this topic: Givens Rotation