Givens-Rotation

In linear algebra, a Givens rotation is ( Wallace Givens ) a rotation in a plane that is defined by two coordinate axes. Sometimes this is also called Jacobi rotation referred to ( according to Carl Gustav Jacobi ).

Description

The transformation can be achieved by a matrix of the form

Describe, where c = cos = sin appear ( θ ) and s ( θ ) in the i-th and k -th row and column. Such a matrix is called Givens matrix. Formal words:

The matrix-vector product is a rotation of the vector x at an angle θ in the (i, k) is plane, this is known as the Givens rotation.

The main application of the Givens rotation is numerical linear algebra to generate zero entries in vectors and matrices. This effect can be exploited, for example in the calculation of the QR decomposition of a matrix. In addition, such rotation matrices in the Jacobi method can be used.

QR decomposition by means of Givens rotations

• The process is very stable. Pivoting is not required.
• Flexible consideration of existing 0 - entries in structured (particularly sparse ) matrices.
• The idea is to successively set the elements below the main diagonal to zero by multiplying the matrix on the left by Givens rotations. First you edit the first column from top to bottom and then successively the other columns also from the top down.
• So you have to perform matrix multiplication. As per multiplication change most 2n values ​​, respectively, of the cost of a QR decomposition of a crowded mx total n- matrix. For sparse matrices, the effort is, however, considerably lower.
• If you want to achieve, so it is and where.

Example ( QR decomposition ):

With

Finally obtained the QR decomposition: