Поворот Гивенса

Поворот Гивенса — в линейной алгебре линейный оператор поворота вектора на некоторый заданный угол.

Матрица Гивенса[1][2][3]

Матрица Гивенса имеет следующий вид:

Данная матрица отличается от единичной матрицы только подматрицей

расположенной на строках и столбцах с номерами и . Является ортогональной.

Если дан вектор , , то выбрав

можно обнулить -ую компоненту вектора :

С помощью поворотов Гивенса можно вычислять QR-разложение матриц и проводить эрмитовы матрицы к трёхдиагональной форме.

Использование матриц Гивенса для трёхдиагонализации

Пусть хотим привести к трёхдиагональному виду симметричную матрицу:

Где . Тогда домножим её на матрицу вращения Гивенса: . — транспонированная матрица. При этом изменятся только элементы , и

Здесь штрих обозначает элемент возникающий после вращения. Выберем коэффициенты и так, чтобы обнулить недиагональный элемент и сохранить связь и с и

Тогда:

Такое вращение применяют последовательно, чтобы обнулить все элементы первой строки, кроме двух первых. То есть (1,2), (1,3), (1,4)...(1,n) Потом ко-второй строке (2,3),(2, 4)...(2,n)

Код на C++:

for (unsigned int i=0; i<N-1; ++i) 
    {
    for (unsigned int j=i+2; j<N; ++j)               
        {
            t = 2*matr[i][j]/(matr[i][i] - matr[j][j]);
            phi = 0.5 * atan(t);
            c = cos(phi);
            s = sin(phi);
 
            bii = c*c*matr[i][i] + 2*c*s*matr[i][j] + s*s*matr[j][j];
            bij = s*c*(matr[j][j] - matr[i][i]) + matr[i][j] * (c*c - s*s);
            bjj = s*s*matr[i][i] + c*c*matr[j][j] - 2*c*s*matr[i][j];
            bji = bij;
 
            matr[i][i] = bii;
            matr[i][j] = bij;
            matr[j][i] = bji;
            matr[j][j] = bjj;
        }
    }

Примечания

  1. Тыртышников Е. Е. Методы численного анализа. М., 2006. — С. 73-74.
  2. Björck, Åke, 1934-. Numerical methods for least squares problems. — Philadelphia: SIAM, 1996. — С. 121-123. — xvii, 408 pages с. — ISBN 0-89871-360-9, 978-0-89871-360-2.
  3. Demmel, James W. Applied numerical linear algebra. — Philadelphia: Society for Industrial and Applied Mathematics, 1997. — С. 53-56. — xi, 419 pages с. — ISBN 0-89871-389-7, 978-0-89871-389-3, 0-89871-361-7, 978-0-89871-361-9.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.