Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант): различия между версиями
| [досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) м (→Литература) |
ASA (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 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> хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса) | ||
| Строка 13: | Строка 13: | ||
[[Категория:Законченные статьи без перевода на английский язык]] | [[Категория:Законченные статьи без перевода на английский язык]] | ||
[[Категория:Законченные статьи]] | [[Категория:Законченные статьи]] | ||
| + | |||
| + | [[en:Givens (rotations) method for the QR decomposition of a (real) Hessenberg matrix]] | ||
Текущая версия на 08:48, 9 июля 2022
Метод Гивенса (в отечественной математической литературе называется также методом вращений) используется для разложения матриц в виде [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].
