Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме: различия между версиями
Frolov (обсуждение | вклад) (Новая страница: «{{algorithm | name = Разложение в произведение хессенберговой и двух ортогональных матри…») |
ASA (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 2 участников) | |||
| Строка 13: | Строка 13: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A= | + | '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A=QRQ^T</math> (<math>Q</math> - ортогональная, <math>R</math> — правая почти треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием одномерного дополнительного массива. |
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | ||
| Строка 23: | Строка 23: | ||
{{Шаблон:Матрица отражений}} | {{Шаблон:Матрица отражений}} | ||
| − | На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные элементы в <math>i</math>-м столбце, а потом | + | На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные (кроме первой поддиагонали) элементы в <math>i</math>-м столбце, а потом выполняется преобразование того же отражения, но справа. Таким образом, после <math>n-2</math> шагов преобразований получается хессенбергова <math>R</math> из разложения матрицы в произведение хессенберговой и двух ортогональных. |
На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде <math>U=E-\frac{1}{\gamma}vv^*</math>, где <math>v</math> находится для левых матриц отражения через координаты текущего <math>i</math>-го столбца так: | На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде <math>U=E-\frac{1}{\gamma}vv^*</math>, где <math>v</math> находится для левых матриц отражения через координаты текущего <math>i</math>-го столбца так: | ||
| Строка 31: | Строка 31: | ||
Если <math>(s,s)=0</math>, то <math>v=e_{i}</math>, <math>\gamma = \frac{1}{2}</math>. | Если <math>(s,s)=0</math>, то <math>v=e_{i}</math>, <math>\gamma = \frac{1}{2}</math>. | ||
| − | В остальных случаях по алгоритму вычисляется <math>u = \frac{1}{\sqrt{(s,s)}}s</math>, и далее <math>v_{j}=0</math> при <math>j<i</math>, <math>v_{j}=u_{j-i+1}</math> при <math>j>i</math>, а <math>v_{i}=1</math>, если <math>u_{1}=0</math> и <math>v_{i}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)</math> для остальных значений. При этом <math>\gamma = 1+|u_{1}|</math>. | + | В остальных случаях по алгоритму вычисляется <math>u = \frac{1}{\sqrt{(s,s)}}s</math>, и далее <math>v_{j}=0</math> при <math>j < i</math>, <math>v_{j}=u_{j-i+1}</math> при <math>j > i</math>, а <math>v_{i}=1</math>, если <math>u_{1}=0</math> и <math>v_{i}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)</math> для остальных значений. При этом <math>\gamma = 1+|u_{1}|</math>. |
После вычисления вектора <math>v</math> подстолбцы справа от ведущего модифицируются по формулам <math>x'=x-\frac{(x,v)}{\gamma}v</math>. | После вычисления вектора <math>v</math> подстолбцы справа от ведущего модифицируются по формулам <math>x'=x-\frac{(x,v)}{\gamma}v</math>. | ||
| − | + | Затем с помощью вычисленных параметров отражения выполняется умножение на матрицу Хаусхолдера справа. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | |||
| − | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 65: | Строка 57: | ||
'''Объём входных данных''': <math>n^2</math>. | '''Объём входных данных''': <math>n^2</math>. | ||
| − | '''Объём выходных данных''': <math>n^2+ | + | '''Объём выходных данных''': <math>n^2+n</math>. |
=== Свойства алгоритма === | === Свойства алгоритма === | ||
| Строка 73: | Строка 65: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| − | === | + | === Результаты прогонов === |
| − | |||
| − | |||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
== Литература == | == Литература == | ||
| + | |||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
[[Категория:Разложения матриц]] | [[Категория:Разложения матриц]] | ||
| + | |||
| + | [[en:Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form]] | ||
Текущая версия на 10:38, 7 июля 2022
| Разложение в произведение хессенберговой и двух ортогональных матриц методом Хаусхолдера (отражений) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n^3)[/math] |
| Объём входных данных | [math]n^2[/math] |
| Объём выходных данных | [math]n(n + 2)[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(n^2)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n^2)[/math] |
Основные авторы описания: А.В.Фролов
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для разложения матриц в виде [math]A=QRQ^T[/math] ([math]Q[/math] - ортогональная, [math]R[/math] — правая почти треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц отражения[2]. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием одномерного дополнительного массива.
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.
1.2 Математическое описание алгоритма
В методе Хаусхолдера для выполнения разложения матрицы в произведение хессенберговой и двух ортогональных используются попеременные умножения слева и справа её текущих модификаций на матрицы Хаусхолдера (отражений).
Матрица отражений (Хаусхолдера) - матрица вида [math]U=E-2ww^*[/math], где [math]w[/math] - вектор, удовлетворяющий равенству [math]w^{*}w=1[/math]. Является одновременно унитарной ([math]U^{*}U=E[/math]) и эрмитовой ([math]U^{*}=U[/math]), поэтому обратна самой себе ([math]U^{-1}=U[/math]).
На [math]i[/math]-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные (кроме первой поддиагонали) элементы в [math]i[/math]-м столбце, а потом выполняется преобразование того же отражения, но справа. Таким образом, после [math]n-2[/math] шагов преобразований получается хессенбергова [math]R[/math] из разложения матрицы в произведение хессенберговой и двух ортогональных.
На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде [math]U=E-\frac{1}{\gamma}vv^*[/math], где [math]v[/math] находится для левых матриц отражения через координаты текущего [math]i[/math]-го столбца так:
[math]s[/math] - вектор размерности [math]n+1-i[/math], составленный из элементов [math]i[/math]-го столбца, начиная с [math]i[/math]-го.
Если [math](s,s)=0[/math], то [math]v=e_{i}[/math], [math]\gamma = \frac{1}{2}[/math].
В остальных случаях по алгоритму вычисляется [math]u = \frac{1}{\sqrt{(s,s)}}s[/math], и далее [math]v_{j}=0[/math] при [math]j \lt i[/math], [math]v_{j}=u_{j-i+1}[/math] при [math]j \gt i[/math], а [math]v_{i}=1[/math], если [math]u_{1}=0[/math] и [math]v_{i}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)[/math] для остальных значений. При этом [math]\gamma = 1+|u_{1}|[/math].
После вычисления вектора [math]v[/math] подстолбцы справа от ведущего модифицируются по формулам [math]x'=x-\frac{(x,v)}{\gamma}v[/math].
Затем с помощью вычисленных параметров отражения выполняется умножение на матрицу Хаусхолдера справа.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
При классификации по последовательной сложности, таким образом, метод Хаусхолдера относится к алгоритмам с кубической сложностью.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: плотная квадратная матрица [math]A[/math] (элементы [math]a_{ij}[/math]).
Объём входных данных: [math]n^2[/math].
Объём выходных данных: [math]n^2+n[/math].
1.10 Свойства алгоритма
Вычислительная погрешность в методе отражений (Хаусхолдера) растет линейно, как и в методе Гивенса (вращений).
