Linear Systems of Algebraic Equations

This page presents some topics from Linear Algebra needed for construction of solutions to systems of linear algebraic equations and some applications. We use matrices and vectors as essential elements in obtaining and expressing the solutions.

Givens rotation

In numerical linear algebra, a Givens rotation is a rotation in the plane spanned by two coordinates axes. Givens rotations are named after James Wallace Givens, Jr. (1910--1993), who introduced them to numerical analysis in the 1950s while he was working at Argonne National Laboratory. A Givens rotation is represented by a matrix of the form

\[ G(i,j,\theta ) = \begin{bmatrix} 1& \cdots & 0 &\cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots && \vdots && \vdots \\ 0 & \cdots & c & \cdots & -s & \cdots & 0 \\ \vdots && \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & s & \cdots & c & \cdots & 0 \\ \vdots && \vdots && \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end{bmatrix} , \]

where \( c= \cos\theta \quad\mbox{and} \quad s= \sin \theta \) appear at the intersections ith and jth rows and columns. The product \( G(i,j, \theta ){\bf x} \) represents a counterclockwise rotation of the vector x in the (i,j) plane of θ radians, hence the name Givens rotation. It requires \( 3mn^2 - n^3 \) flop operations (or about 50% more than Householder QR).

The main use of Givens rotations in numerical linear algebra is to introduce zeroes in vectors or matrices. This effect can, for example, be employed for computing the QR decomposition of a matrix. One advantage over Householder transformations is that they can easily be parallelised, and another is that often for very sparse matrices they have a lower operation count.

When a Givens rotation matrix, \( G(i,j, \theta ) , \) multiplies another matrix, A, from the left, \( G(i,j, \theta )\, {\bf A} , \) only rows i and j of A are affected. Thus we restrict attention to the following counterclockwise problem. Given a and b, find \( c = \cos\theta \quad \mbox{and} \quad s = \sin\theta \) such that

\[ \begin{bmatrix} c&-s \\ s&c \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix} , \]

where \( r = \sqrt{a^2 + b^2} \) is the length of the vector [a, b]. Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek c and s. An obvious solution would be

\[ c \,\leftarrow \,\frac{a}{r} , \qquad s \,\leftarrow \,-\frac{b}{r} . \]

However, the computation for r may overflow or underflow. An alternative formulation avoiding this problem is implemented as the hypot function in many programming languages. The standard matrix for a counterclockwise rotation through an angle θ about an axis in \( \mathbb{R}^3 , \) which is determined by an arbitrary unit vector \( {\bf u} = (a,b,c), \quad a^2 + b^2 + c^2 =1 , \) that has its initial point at the origin is

\[ \begin{bmatrix} a^2 \left( 1-\cos\theta \right) + \cos\theta & ab \left( 1-\cos\theta \right) -c\cos\theta & ac \left( 1-\cos\theta \right) + b\sin\theta \\ ab \left( 1-\cos\theta \right) + c\sin \theta & b^2 \left( 1-\cos\theta \right) + \cos\theta & bc \left( 1-\cos\theta \right) -a\sin\theta \\ ac\left( 1-\cos\theta \right) -b \sin\theta & bc \left( 1-\cos\theta \right) + a\sin\theta & c^2 \left( 1-\cos\theta \right) + \cos\theta \end{bmatrix} . \]

Example. Consider some simple examples of rotations in 3D space:

Operator	Rotation Equations	Standard Matrix
Counterclockwise rotation about the posotive x-axis through an angle θ	\( \begin{split} u_1 &=x \\ u_2 &= y\cos\theta -z\sin \theta \\ u_3 &= y\sin\theta +z\cos\theta \end{split} \)	\( \begin{bmatrix} 1&0&0 \\ 0&\cos\theta & -\sin\theta \\ 0&\sin\theta & \cos\theta \end{bmatrix} \)
Counterclockwise rotation about the posotive y-axis through an angle θ	\( \begin{split} u_1 &=x\cos\theta +z\sin \theta \\ u_2 &= y \\ u_3 &= -x\sin\theta +z\cos\theta \end{split} \)	\( \begin{bmatrix} \cos\theta&0&\sin\theta \\ 0&1&0 \\ -\sin\theta &0&\cos\theta \end{bmatrix} \)
Counterclockwise rotation about the posotive z-axis through an angle θ	\( \begin{split} u_1 &=x\cos\theta -y\sin\theta \\ u_2 &= x\sin\theta +y\cos \theta \\ u_3 &= z \end{split} \)	\( \begin{bmatrix} \cos\theta & -\sin\theta &0 \\ \sin\theta & \cos\theta&0 \\0&0&1 \end{bmatrix} \)