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

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

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

Определения

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

Квадрат $n\times n$ матрица $A$ называется верхней матрицей Хессенберга или верхней матрицей Хессенберга, если $a_{i,j}=0$ для всех $i,j$ с $i>j+1$.

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

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

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

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

Примеры

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

Матрица $A$ — верхняя неприводимая матрица Хессенберга, $B$ — нижняя нередуцированная матрица Хессенберга и $C$ является нижней матрицей Хессенберга, но не является нередуцированной.

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

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

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

Преобразования домохозяев

Любой $n\times n$ Матрица может быть преобразована в матрицу Хессенберга путем преобразования подобия с использованием преобразований Хаусхолдера . Следующая процедура такого преобразования адаптирована из «Второго курса линейной алгебры» Гарсиа и Роджера .

Позволять $A$ быть любым реальным или сложным $n\times n$ матрица, то пусть $A^{\prime }$ быть $(n-1)\times n$ подматрица $A$ построенный путем удаления первой строки в $A$ и пусть $\mathbf {a} _{1}^{\prime }$ быть первым столбцом $A'$. Постройте $(n-1)\times (n-1)$ матрица домохозяина $V_{1}=I_{(n-1)}-2{\frac {ww^{*}}{\|w\|^{2}}}$ где $$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}}$$

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

По конструкции $U_{k}$, первый $k$ столбцы какие-то $n\times n$ матрицы инвариантны относительно умножения на $U_{k}^{*}$ справа. Следовательно, любая матрица может быть преобразована в верхнюю матрицу Хессенберга преобразованием подобия вида $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^{*}$.

Ротации Якоби (Гивенса)

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

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

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

$\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.$

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

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

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

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

уменьшает матрицу $A$ к нижней форме Гессенберга.

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

Для $n\in \{1,2\}$, это пустая правда , что каждый $n\times n$ матрица является одновременно верхним Хессенбергом и нижним Хессенбергом.

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

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

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

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

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

См. также

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

Ссылки

• Хорн, Роджер А.; Джонсон, Чарльз Р. (1985), Матричный анализ , Издательство Кембриджского университета , ISBN  978-0-521-38632-6 .
• Стер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-0-387-95452-3 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 11.6.2. Приведение к форме Хессенберга» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 13 августа 2011 г.

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

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