Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)
Метод Гивенса (в отечественной математической литературе называется также методом вращений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса)
номера столбцов: [math]\begin{matrix} \ _{i-1}\quad _i\quad _{i+1} & \ & _{j-1}\ \ _j\quad _{j+1}\end{matrix}[/math]
[math]T_{ij} = \begin{bmatrix} 1 & \cdots & 0\quad 0\quad 0 & \cdots & 0\quad 0\quad 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 1\quad 0\quad 0 & \cdots & 0\quad 0\quad 0 & \cdots & 0 \\ 0 & \cdots & 0\quad c\quad 0 & \cdots & 0\ -s\ 0 & \cdots & 0 \\ 0 & \cdots & 0\quad 0\quad 1 & \cdots & 0\quad 0\quad 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0\quad 0\quad 0 & \cdots & 1\quad 0\quad 0 & \cdots & 0 \\ 0 & \cdots & 0\quad s\quad 0 & \cdots & 0\quad c\quad 0 & \cdots & 0 \\ 0 & \cdots & 0\quad 0\quad 0 & \cdots & 0\quad 0\quad 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0\quad 0\quad 0 & \cdots & 0\quad 0\quad 0 & \cdots & 1 \\ \end{bmatrix} [/math]
может быть определена парой индексов и одним параметром. Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от стандартной реализации метода Гивенса для плотной квадратной матрицы, для него нужно выполнить всего [math]n-1[/math] операций вращения, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь алгоритма, как и в случае плотных матриц, линеен.
Алгоритм, однако, в своём чистом виде практически не используется. Дело в том, что в QR-алгоритме, где QR-разложения хессенберговых матриц формально используются, для экономии ресурсов они давно применяются в неявном виде, а именно в составе QR-итераций с неявным одинарным сдвигом[2].
