Difference between revisions of "Householder (reflections) method for the QR decomposition of a (real) Hessenberg matrix"
[unchecked revision] | [quality revision] |
(Created page with "{{level-a}} '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом...") |
|||
Line 3: | Line 3: | ||
'''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A=QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. | '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A=QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. | ||
− | {{ | + | {{Template:Reflection matrix}} |
Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от [[Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант|стандартной реализации метода Хаусхолдера для плотной квадратной матрицы]], для него нужно выполнять операции отражения с базой на приведении двумерных векторов к одному из ортов, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь этого алгоритма, как и в случае метода Гивенса, от которого метод Хаусхолдера отличается только коэффициентами в матрицах, линеен. | Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от [[Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант|стандартной реализации метода Хаусхолдера для плотной квадратной матрицы]], для него нужно выполнять операции отражения с базой на приведении двумерных векторов к одному из ортов, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь этого алгоритма, как и в случае метода Гивенса, от которого метод Хаусхолдера отличается только коэффициентами в матрицах, линеен. |
Revision as of 13:43, 2 March 2018
Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для разложения матриц в виде [math]A=QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц отражения[2].
A reflection (or a Householder) matrix is a matrix of the form [math]U=E-2ww^*[/math], where the vector [math]w[/math] is normalized: [math]w^{*}w=1[/math]. Such a matrix is unitary ([math]U^{*}U=E[/math]) and Hermitian ([math]U^{*}=U[/math]) at the same time; consequently, this matrix is its own inverse ([math]U^{-1}=U[/math]).
Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от стандартной реализации метода Хаусхолдера для плотной квадратной матрицы, для него нужно выполнять операции отражения с базой на приведении двумерных векторов к одному из ортов, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь этого алгоритма, как и в случае метода Гивенса, от которого метод Хаусхолдера отличается только коэффициентами в матрицах, линеен.
Алгоритм, однако, в своём чистом виде практически не используется. Дело в том, что в QR-алгоритме, где QR-разложения хессенберговых матриц формально используются, для экономии ресурсов они давно применяются в неявном виде, а именно в составе QR-итераций с неявным двойным сдвигом[3].