Difference between revisions of "Givens (rotations) method for the QR decomposition of a (real) Hessenberg matrix"
Line 1: | Line 1: | ||
− | {{level- | + | {{level-m}} |
'''Метод Гивенса''' (в отечественной математической литературе называется также '''методом вращений''') используется для разложения матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса) | '''Метод Гивенса''' (в отечественной математической литературе называется также '''методом вращений''') используется для разложения матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса) |
Revision as of 08:49, 9 July 2022
Метод Гивенса (в отечественной математической литературе называется также методом вращений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса)
colomn numbers: [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].