Матрица Хессенберга

Вид квадратной матрицы в линейной алгебре

В линейной алгебре матрица Хессенберга — это особый вид квадратной матрицы , которая является «почти» треугольной . Если быть точным, верхняя матрица Хессенберга имеет нулевые элементы ниже первой поддиагонали , а нижняя матрица Хессенберга имеет нулевые элементы выше первой наддиагонали . ^[1] Они названы в честь Карла Хессенберга . ^[2]

Разложение Хессенберга — это матричное разложение матрицы на унитарную матрицу и матрицу Хессенберга, такое что , где обозначает сопряженное транспонирование . ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle H}$ $${\displaystyle PHP^{*}=A}$$ ${\displaystyle P^{*}}$

Определения

Верхняя матрица Хессенберга

Говорят, что квадратная матрица находится в верхней форме Гессенберга или является верхней матрицей Гессенберга, если для всех с . ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle a_{i,j}=0}$ ${\displaystyle i,j}$ ${\displaystyle i>j+1}$

Верхняя матрица Хессенберга называется нередуцированной , если все элементы поддиагонали отличны от нуля, т.е. если для всех . ^[3] ${\displaystyle a_{i+1,i}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Нижняя матрица Хессенберга

Говорят, что квадратная матрица находится в нижней форме Гессенберга или является нижней матрицей Гессенберга , если ее транспонированная матрица является верхней матрицей Гессенберга или, что эквивалентно, если для всех с . ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle }$ ${\displaystyle a_{i,j}=0}$ ${\displaystyle i,j}$ ${\displaystyle j>i+1}$

Нижняя матрица Хессенберга называется неприведенной , если все наддиагональные элементы отличны от нуля, т.е. если для всех . ${\displaystyle a_{i,i+1}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Примеры

Рассмотрим следующие матрицы. $${\displaystyle A={\begin{bmatrix}1&4&2&3\\3&4&1&7\\0&2&3&4\\0&0&1&3\\\end{bmatrix}}}$$ $${\displaystyle B={\begin{bmatrix}1&2&0&0\\5&2&3&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$$ $${\displaystyle C={\begin{bmatrix}1&2&0&0\\5&2&0&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$$

Матрица является верхней нередуцированной матрицей Гессенберга, является нижней нередуцированной матрицей Гессенберга и является нижней матрицей Гессенберга, но не является нередуцированной. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

Компьютерное программирование

Многие алгоритмы линейной алгебры требуют значительно меньших вычислительных усилий при применении к треугольным матрицам , и это улучшение часто переносится и на матрицы Хессенберга. Если ограничения задачи линейной алгебры не позволяют удобно свести общую матрицу к треугольной, сведение к форме Хессенберга часто является следующим лучшим решением. Фактически, сведение любой матрицы к форме Хессенберга может быть достигнуто за конечное число шагов (например, с помощью преобразования Хаусхолдера унитарных преобразований подобия). Последующее сведение матрицы Хессенберга к треугольной матрице может быть достигнуто с помощью итерационных процедур, таких как сдвинутая QR -факторизация. В алгоритмах собственных значений матрица Хессенберга может быть дополнительно сведена к треугольной матрице с помощью сдвинутой QR-факторизации в сочетании с шагами дефляции. Сведение общей матрицы к матрице Хессенберга и последующее сведение к треугольной матрице, вместо прямого сведения общей матрицы к треугольной, часто позволяет сэкономить арифметические операции, используемые в алгоритме QR для задач на собственные значения.

Сведение к матрице Хессенберга

Трансформации домохозяев

Любая матрица может быть преобразована в матрицу Хессенберга с помощью преобразования подобия с использованием преобразований Хаусхолдера . Следующая процедура для такого преобразования адаптирована из A Second Course In Linear Algebra Гарсии и Роджера . ^[4] ${\displaystyle n\times n}$

Пусть будет любой действительной или комплексной матрицей, тогда пусть будет подматрицей , построенной путем удаления первой строки в , и пусть будет первым столбцом . Построим матрицу Хауссорера , где ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle A^{\prime }}$ ${\displaystyle (n-1)\times n}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \mathbf {a} _{1}^{\prime }}$ ${\displaystyle A'}$ ${\displaystyle (n-1)\times (n-1)}$ ${\displaystyle V_{1}=I_{(n-1)}-2{\frac {ww^{*}}{\|w\|^{2}}}}$ $${\displaystyle w={\begin{cases}\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}-\mathbf {a} _{1}^{\prime }\;\;\;\;\;\;\;\;,\;\;\;a_{11}^{\prime }=0\\\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}+{\frac {\overline {a_{11}^{\prime }}}{|a_{11}^{\prime }|}}\mathbf {a} _{1}^{\prime }\;\;\;,\;\;\;a_{11}^{\prime }\neq 0\\\end{cases}}}$$

Эта матрица хаусаузер будет отображаться в и как таковая, блочная матрица будет отображать матрицу в матрицу , которая имеет только нули ниже второго элемента первого столбца. Теперь постройте матрицу хаусаузер аналогичным образом, как таковую, которая отображает первый столбец в , где — подматрица из , построенная путем удаления первой строки и первого столбца из , затем пусть которая отображается в матрицу , которая имеет только нули ниже первого и второго элемента поддиагонали. Теперь постройте и затем аналогичным образом, но для матрицы, построенной путем удаления первой строки и первого столбца из и продолжайте, как в предыдущих шагах. Продолжайте таким образом в общей сложности шагов . ${\displaystyle \mathbf {a} _{1}^{\prime }}$ ${\displaystyle \|\mathbf {a} _{1}^{\prime }\|\mathbf {e} _{1}}$ ${\displaystyle U_{1}={\begin{bmatrix}1&\mathbf {0} \\\mathbf {0} &V_{1}\end{bmatrix}}}$ ${\displaystyle A}$ ${\displaystyle U_{1}A}$ ${\displaystyle (n-2)\times (n-2)}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle \|\mathbf {a} _{1}^{\prime \prime }\|\mathbf {e} _{1}}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle A^{\prime }}$ ${\displaystyle A^{\prime }}$ ${\displaystyle U_{2}={\begin{bmatrix}1&0&0\\0&1&0\\0&0&V_{2}\end{bmatrix}}}$ ${\displaystyle U_{1}A}$ ${\displaystyle U_{2}U_{1}A}$ ${\displaystyle V_{3}}$ ${\displaystyle U_{3}}$ ${\displaystyle A^{\prime \prime \prime }}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle n-2}$

По построению , первые столбцы любой матрицы инвариантны относительно умножения на справа. Следовательно, любая матрица может быть преобразована в верхнюю матрицу Хессенберга с помощью преобразования подобия вида . ${\displaystyle U_{k}}$ ${\displaystyle k}$ ${\displaystyle n\times n}$ ${\displaystyle U_{k}^{*}}$ ${\displaystyle U_{(n-2)}(\dots (U_{2}(U_{1}AU_{1}^{*})U_{2}^{*})\dots )U_{(n-2)}^{*}=U_{(n-2)}\dots U_{2}U_{1}A(U_{(n-2)}\dots U_{2}U_{1})^{*}=UAU^{*}}$

вращения Якоби (Гивенса)

Вращение Якоби (также называемое вращением Гивенса) — это ортогональное матричное преобразование в виде

${\displaystyle A\to A'=J(p,q,\theta )^{T}AJ(p,q,\theta )\;,}$

где , , — матрица вращения Якоби, все элементы которой равны нулю, за исключением ${\displaystyle J(p,q,\theta )}$ ${\displaystyle p<q}$

${\displaystyle \left\{{\begin{aligned}J(p,q,\theta )_{ii}&{}=1\;\forall i\neq p,q\\J(p,q,\theta )_{pp}&{}=\cos(\theta )\\J(p,q,\theta )_{qq}&{}=\cos(\theta )\\J(p,q,\theta )_{pq}&{}=\sin(\theta )\\J(p,q,\theta )_{qp}&{}=-\sin(\theta )\;.\end{aligned}}\right.}$

Можно обнулить элемент матрицы , выбрав угол поворота , удовлетворяющий уравнению ${\displaystyle A'_{p-1,q}}$ ${\displaystyle \theta }$

${\displaystyle A_{p-1,p}\sin \theta +A_{p-1,q}\cos \theta =0\;,}$

Теперь последовательность таких вращений Якоби со следующей ${\displaystyle (p,q)}$

${\displaystyle (p,q)=(2,3),(2,4),\dots ,(2,n),(3,4),\dots ,(3,n),\dots ,(n-1,n)}$

приводит матрицу к нижней форме Хессенберга. ^[5] ${\displaystyle A}$

Характеристики

Для , совершенно верно , что каждая матрица является как верхней, так и нижней матрицей Гессенберга. ^[6] ${\displaystyle n\in \{1,2\}}$ ${\displaystyle n\times n}$

Произведение матрицы Хессенберга с треугольной матрицей снова является Хессенбергом. Точнее, если является верхним Хессенбергом и является верхним треугольным, то и являются верхними Хессенбергом. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle AT}$ ${\displaystyle TA}$

Матрица, которая является как верхней, так и нижней матрицей Гессенберга, является трехдиагональной матрицей , важным примером которой является матрица Якоби . Она включает симметричные или эрмитовые матрицы Гессенберга. Эрмитову матрицу можно свести к трехдиагональным действительным симметричным матрицам. ^[7]

Оператор Хессенберга

Оператор Хессенберга — это бесконечномерная матрица Хессенберга. Обычно он встречается как обобщение оператора Якоби на систему ортогональных полиномов для пространства квадратично-интегрируемых голоморфных функций над некоторой областью — то есть, пространством Бергмана . В этом случае оператор Хессенберга — это оператор правого сдвига , заданный как ${\displaystyle S}$ $${\displaystyle [Sf](z)=zf(z).}$$

Собственные значения каждой главной подматрицы оператора Хессенберга задаются характеристическим полиномом для этой подматрицы. Эти полиномы называются полиномами Бергмана и обеспечивают ортогональный полиномиальный базис для пространства Бергмана.

Смотрите также

• сорт Хессенберг

Примечания

1. Хорн и Джонсон (1985), стр. 28; Стер и Булирш (2002), стр. 251.
2. Бисва Нат Датта (2010) Численная линейная алгебра и ее приложения, 2-е изд., Общество промышленной и прикладной математики (SIAM) ISBN  978-0-89871-685-6 , стр. 307
3. Хорн и Джонсон 1985, стр. 35
4. Рамон Гарсия, Стефан; Хорн, Роджер (2017). Второй курс линейной алгебры . Cambridge University Press. ISBN 9781107103818.
5. Бини, Дарио А.; Роболь, Леонардо (2016). «Квазиразделимое сокращение Гессенберга вещественных диагональных матриц плюс матриц низкого ранга и приложения». Линейная алгебра и ее приложения . 502 : 186–213. arXiv : 1501.07812 . doi : 10.1016/j.laa.2015.08.026.
6. Заметки лекций. Заметки на 2016-10-21 Корнелльский университет
7. "Вычислительные процедуры (собственные значения) в LAPACK". sites.science.oregonstate.edu . Получено 24.05.2020 .

Ссылки

• Хорн, Роджер А.; Джонсон, Чарльз Р. (1985), Матричный анализ , Cambridge University Press , ISBN 978-0-521-38632-6.
• Стер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-95452-3.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 11.6.2. Приведение к форме Гессенберга», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, заархивировано из оригинала 2011-08-11 , извлечено 2011-08-13

Внешние ссылки

• Матрица Хессенберга в MathWorld .
• Матрица Хессенберга на PlanetMath .
• Высокопроизводительные алгоритмы приведения к сжатой (Гессенберга, трехдиагональной, двухдиагональной) форме
• Обзор алгоритма