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