Givens rotation

from Wikipedia, the free encyclopedia

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

The application as a method in numerical linear algebra, for example for the determination of eigenvalues ​​and QR decomposition, dates back to the 1950s, when Givens was at the Oak Ridge National Laboratory . Such rotations are already used in the older Jacobi method (1846), but they only became practical with the advent of computers.

description

The transformation can be done through an orthogonal matrix of form

describe, where and appear in the -th and -th row and column. Such a matrix is ​​called the Givens matrix. In more formal terms:

The matrix-vector product represents a rotation of the vector through an angle in the -plane, this is called the Givens rotation.

The main application of the Givens rotation is in numerical linear algebra to generate zero entries in vectors and matrices. This effect can be used, for example, when calculating the QR decomposition of a matrix. Such rotary dies are also used in the Jacobi method .

QR decomposition using Givens rotations

  • The process is stable. Pivoting is not required.
  • Flexible consideration of already existing 0 entries in structured (especially sparse ) matrices.
  • The idea is to successively set the elements below the main diagonal to zero by multiplying the matrix from the left with Givens rotations. First you edit the first column from top to bottom and then one after the other the other columns also from top to bottom.
  • So you have to perform matrix multiplications . Since a maximum of 2n values ​​change per multiplication, the overall effort for a QR decomposition of a fully populated m × n matrix is . For thinly populated matrices, however, the effort is considerably lower.
  • If you want to transform the entry at the matrix position to zero, you put and , where .

example

With

,

You finally get the QR decomposition:

algorithm

To calculate a QR decomposition of a matrix , proceed as follows.

Rotate the first column of the matrix to a vector with a zero as the last entry:

where you have to choose as described above:

Now proceed in the same way with the next entries in the first column and save all the transformation matrices in the matrix :

A distinction must be necessarily taken to the individual items that the template is no longer on the original matrix relate, but to the already-formed matrix: .

Now you have to edit the following columns in the same way and thus find transformation matrices , which transform the -th column of the matrix to a vector with zero entries below the -th element.

Finally, the QR decomposition results from :

literature

  • Gene H. Golub, Charles F. van Loan: Matrix Computations . 2nd edition. The Johns Hopkins University Press, 1989.
  • Martin Hermann: Numerical Mathematics , 2nd, revised and expanded edition, Oldenbourg Verlag, Munich and Vienna 2006, ISBN 3-486-57935-5 , pp. 155-159
  • W. Dahmen, A. Reusken: Numerics for engineers and natural scientists . Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3