Просмотр кода страницы Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме

{{algorithm
| name              = Разложение в произведение хессенберговой и двух ортогональных матриц методом Хаусхолдера (отражений)
| serial_complexity = <math>O(n^3)</math>
| pf_height         = <math>O(n^2)</math>
| pf_width          = <math>O(n^2)</math>
| input_data        = <math>n^2</math>
| output_data       = <math>n(n + 2)</math>
}}
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

'''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения  матриц в виде <math>A=QDV</math> (<math>Q, V</math> - унитарные, <math>D</math> — правая двухдиагональная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрицы <math>Q, V</math> хранятся и используются не в своём явном виде, а в виде произведения матриц отражения<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием двух одномерных дополнительных массивов. 

В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.

=== Математическое описание алгоритма ===

В методе Хаусхолдера для выполнения разложения матрицы в произведение хессенберговой и двух ортогональных используются попеременные умножения слева и справа её текущих модификаций на матрицы Хаусхолдера (отражений). 

{{Шаблон:Матрица отражений}}

На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные элементы в <math>i</math>-м столбце, а потом (кроме шага с номером <math>i=n-1</math>) с помощью преобразования отражения "убираются" ненулевые наддиагональные элементы в <math>i</math>-м столбце, кроме самого левого из них. Таким образом, после <math>n-1</math> шагов преобразований получается хессенбергова <math>D</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<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>U=E-\frac{1}{\gamma}vv^*</math> <math>v</math> находится через координаты текущей <math>i</math>-й строки так:

<math>s</math> - вектор размерности <math>n-i</math>, составленный из элементов <math>i</math>-й строки, начиная с <math>i+1</math>-го элемента.

Если <math>(s,s)=0</math>, то <math>v=e_{i+1}</math>, <math>\gamma = \frac{1}{2}</math>.

В остальных случаях по алгоритму вычисляется <math>u = \frac{1}{\sqrt{(s,s)}}s</math>, и далее <math>v_{j}=0</math> при <math>j<i+1</math>, <math>v_{j}=u_{j-i+2}</math> при <math>j>i+1</math>, а <math>v_{i+1}=1</math>, если <math>u_{1}=0</math> и <math>v_{i+1}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)</math> для остальных значений. При этом <math>\gamma = 1+|u_{1}|</math>.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления на каждом шагу скалярных произведений <math>(s,s)</math> и <math>(x,v)</math> для всех подстолбцов <math>x</math>справа от текущего, а также векторные операции <math>x'=x-\frac{(x,v)}{\gamma}v</math>, и затем вычисления на каждом шагу (кроме шага с номером <math>i=n-1</math>) скалярных произведений <math>(s,s)</math> и <math>(x,v)</math> для всех подстрок <math>x</math>снизу от текущей, а также векторные операции <math>x'=x-\frac{(x,v)}{\gamma}v</math>. Это используется при программировании метода во многих библиотеках для его конструирования из стандартных подпрограмм (например, из BLAS).

=== Макроструктура алгоритма ===

=== Схема реализации последовательного алгоритма ===

=== Последовательная сложность алгоритма ===

При классификации по последовательной сложности, таким образом, метод Хаусхолдера относится к алгоритмам ''с кубической сложностью''.

=== Информационный граф ===

=== Ресурс параллелизма алгоритма ===

=== Входные и выходные данные алгоритма ===

'''Входные данные''': плотная квадратная матрица <math>A</math> (элементы <math>a_{ij}</math>).

'''Объём входных данных''': <math>n^2</math>.

'''Объём выходных данных''': <math>n^2+2n</math>.

=== Свойства алгоритма ===

Вычислительная погрешность в методе отражений (Хаусхолдера) растет ''линейно'', как и в методе Гивенса (вращений).

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===


== Литература ==
<references />

[[Категория:Начатые статьи]]
[[Категория:Разложения матриц]]