Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме
| Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ \frac{8 n^3}{3}+O(n^2) }[/math] |
| Объём входных данных | [math]\displaystyle{ n^2 }[/math] |
| Объём выходных данных | [math]\displaystyle{ n(n + 2) }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ 2n^2+O(n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ n^2 }[/math] |
Свойства и структура алгоритма
Общее описание алгоритма
Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для приведения симметричных вещественных матриц к двухдиагональному виду, или, что то же самое, для разложения [math]\displaystyle{ A=QDU^T }[/math] ([math]\displaystyle{ Q, U }[/math] - ортогональные, [math]\displaystyle{ D }[/math] — нижняя двухдиагональная матрица)[1]. При этом матрицы [math]\displaystyle{ Q, U }[/math] хранятся и используются не в своём явном виде, а в виде произведения матриц отражения[2]. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием двух одномерных дополнительных массивов.
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.