Матрица Теплица

Матрица с равными значениями по диагоналям

В линейной алгебре матрица Теплица или диагонально-постоянная матрица , названная в честь Отто Теплица , представляет собой матрицу , в которой каждая нисходящая диагональ слева направо является постоянной. Например, следующая матрица является матрицей Теплица:

${\displaystyle \qquad {\begin{bmatrix}a&b&c&d&e\\f&a&b&c&d\\g&f&a&b&c\\h&g&f&a&b\\i&h&g&f&a\end{bmatrix}}.}$

Любая матрица вида ${\displaystyle n\times n}$ ${\displaystyle A}$

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\cdots &\cdots &a_{-(n-1)}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{-1}&a_{-2}\\\vdots &&\ddots &a_{1}&a_{0}&a_{-1}\\a_{n-1}&\cdots &\cdots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}$

является матрицей Теплица . Если элемент обозначен, то мы имеем ${\displaystyle i,j}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}}$

${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}.}$

Матрица Теплица не обязательно является квадратной .

Решение системы Теплица

Матричное уравнение вида

${\displaystyle Ax=b}$

называется системой Теплица, если является матрицей Теплица. Если матрица Теплица, то система имеет не более чем уникальные значения, а не . Поэтому мы могли бы ожидать, что решение системы Теплица будет проще, и это действительно так. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle 2n-1}$ ${\displaystyle n^{2}}$

Системы Теплица можно решать с помощью таких алгоритмов, как алгоритм Шура или алгоритм Левинсона по времени. ^{[1] [2]} Было показано, что варианты последних слабо устойчивы (т.е. они демонстрируют численную устойчивость для хорошо обусловленных линейных систем ). ^[3] Алгоритмы также можно использовать для нахождения определителя матрицы Теплица во времени. ^[4] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

Матрица Теплица также может быть разложена (т.е. факторизована) по времени . ^[5] Алгоритм Барейсса для LU-разложения стабилен. ^[6] LU-разложение дает быстрый метод решения системы Теплица, а также вычисления определителя. ${\displaystyle O(n^{2})}$

Общие свойства

• Матрица Теплица может быть определена как матрица где для констант . Множество теплицевых матриц является подпространством векторного пространства матриц (при сложении матриц и скалярном умножении ). ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}=c_{i-j}}$ ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$
• Две матрицы Теплица можно складывать во времени (путем сохранения только одного значения каждой диагонали) и умножать во времени. ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$
• Матрицы Теплица персимметричны . Симметричные матрицы Теплица одновременно центросимметричны и бисимметричны .
• Матрицы Теплица также тесно связаны с рядами Фурье , поскольку оператор умножения на тригонометрический многочлен , сжатый до конечномерного пространства, может быть представлен такой матрицей. Точно так же линейную свертку можно представить как умножение на матрицу Теплица.
• Матрицы Теплица коммутируют асимптотически . Это означает, что они диагонализуются по одному и тому же базису , когда размерность строки и столбца стремится к бесконечности.

• Для симметричных матриц Теплица существует разложение

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$

где – нижняя треугольная часть . ${\displaystyle G}$ ${\displaystyle {\frac {1}{a_{0}}}A}$

• Обратная невырожденная симметричная матрица Теплица имеет представление

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

где и – нижние треугольные матрицы Теплица, а – строго нижнетреугольная матрица. ^[7] ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C}$

Дискретная свертка

Операцию свертки можно построить как умножение матрицы, при которой один из входных данных преобразуется в матрицу Теплица. Например, свертка и может быть сформулирована как: ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\cdots &0&0\\h_{2}&h_{1}&&\vdots &\vdots \\h_{3}&h_{2}&\cdots &0&0\\\vdots &h_{3}&\cdots &h_{1}&0\\h_{m-1}&\vdots &\ddots &h_{2}&h_{1}\\h_{m}&h_{m-1}&&\vdots &h_{2}\\0&h_{m}&\ddots &h_{m-2}&\vdots \\0&0&\cdots &h_{m-1}&h_{m-2}\\\vdots &\vdots &&h_{m}&h_{m-1}\\0&0&0&\cdots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}}$

${\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\cdots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&0&\cdots &0\\0&x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&\cdots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\cdots &0\\\vdots &&\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\cdots &0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}&0\\0&\cdots &0&0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}.}$

Этот подход можно расширить для вычисления автокорреляции , взаимной корреляции , скользящего среднего и т. д.

Бесконечная матрица Теплица

Двубесконечная матрица Теплица (т.е. элементы, индексированные ) индуцирует линейный оператор на . ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle A}$ ${\displaystyle \ell ^{2}}$

${\displaystyle A={\begin{bmatrix}&\vdots &\vdots &\vdots &\vdots \\\cdots &a_{0}&a_{-1}&a_{-2}&a_{-3}&\cdots \\\cdots &a_{1}&a_{0}&a_{-1}&a_{-2}&\cdots \\\cdots &a_{2}&a_{1}&a_{0}&a_{-1}&\cdots \\\cdots &a_{3}&a_{2}&a_{1}&a_{0}&\cdots \\&\vdots &\vdots &\vdots &\vdots \end{bmatrix}}.}$

Индуцированный оператор ограничен тогда и только тогда, когда коэффициенты матрицы Теплица являются коэффициентами Фурье некоторой существенно ограниченной функции . ${\displaystyle A}$ ${\displaystyle f}$

В таких случаях называется символом матрицы Теплица , а спектральная норма матрицы Теплица совпадает с нормой ее символа. Доказательство легко установить и можно найти в теореме 1.1 . ^[8] ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle L^{\infty }}$

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

• Циркулянтная матрица — квадратная матрица Теплица с дополнительным свойством: ${\displaystyle a_{i}=a_{i+n}}$
• Матрица Ханкеля , «перевернутая» (т. е. перевернутая по строкам) матрица Теплица.
• Предельные теоремы Сегё

Примечания

1. Пресс и др. 2007, §2.8.2 — Матрицы Теплица
2. Хейс 1996, Глава 5.2.6
3. Кришна и Ван 1993
4. Монахан 2011, §4.5 - Системы Теплица
5. Брент 1999
6. Боянчик и др. 1995 год
7. Мукерджи и Маити, 1988 г.
8. Бетчер и Грудский, 2012 г.

Рекомендации

• Боянчик, А.В.; Брент, РП; де Хоог, Франция; Свит, Д. Р. (1995), «О стабильности алгоритмов факторизации Барейса и родственных ему Теплица», SIAM Journal on Matrix Analysis and Applications , 16 : 40–57, arXiv : 1004.5510 , doi : 10.1137/S0895479891221563, S2CID  367586
• Бетчер, Альбрехт; Грудский, Сергей М. (2012), Матрицы Теплица, асимптотическая линейная алгебра и функциональный анализ, Биркхойзер, ISBN 978-3-0348-8395-5
• Брент, Р.П. (1999), «Стабильность быстрых алгоритмов для структурированных линейных систем», Кайлат, Т.; Сайед, А.Х. (ред.), Быстрые надежные алгоритмы для матриц со структурой , SIAM , стр. 103–116, doi : 10.1137/1.9781611971354.ch4, hdl : 1885/40746 , S2CID  13905858
• Чан, Р.Х.-Ф.; Джин, X.-Q. (2007), Введение в итеративные решатели Теплица , SIAM , doi : 10.1137/1.9780898718850, ISBN 978-0-89871-636-8
• Чандрасекеран, С.; Жвачка.; Солнце, Х.; Ся, Дж.; Чжу, Дж. (2007), «Сверхбыстрый алгоритм для систем линейных уравнений Теплица», SIAM Journal on Matrix Analysis and Applications , 29 (4): 1247–1266, CiteSeerX  10.1.1.116.3297 , doi : 10.1137/040617200
• Чен, WW; Гурвич, СМ; Лу, Ю. (2006), «О корреляционной матрице дискретного преобразования Фурье и быстром решении больших систем Теплица для временных рядов с длинной памятью», Журнал Американской статистической ассоциации , 101 (474): 812–822, CiteSeerX  10.1.1.574.4394 , номер doi : 10.1198/016214505000001069, S2CID  55893963
• Хейс, Монсон Х. (1996), Статистическая цифровая обработка сигналов и моделирование , John Wiley & Son, ISBN 0-471-59431-8
• Кришна, Х.; Ван, Ю. (1993), «Алгоритм Сплит-Левинсона слабо устойчив» , SIAM Journal on Numerical Analysis , 30 (5): 1498–1508, doi : 10.1137/0730078
• Монахан, Дж. Ф. (2011), Численные методы статистики , Издательство Кембриджского университета
• Мукерджи, Бишва Натх; Маити, Садхан Самар (1988), «О некоторых свойствах положительно определенных матриц Теплица и их возможных применениях» (PDF) , Линейная алгебра и ее приложения , 102 : 211–240, doi : 10.1016/0024-3795(88)90326- 6
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), Численные рецепты: искусство научных вычислений (Третье изд.), Cambridge University Press , ISBN 978-0-521-88068-8
• Стюарт, М. (2003), «Сверхбыстрый решатель Теплица с улучшенной числовой стабильностью», SIAM Journal on Matrix Analysis and Applications , 25 (3): 669–693, doi : 10.1137/S089547980241791X, S2CID  15717371
• Ян, Зай; Се, Лихуа; Стойка, Петре (2016), «Разложение Вандермонда многоуровневых теплицевых матриц с применением к многомерному сверхразрешению», IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi : 10.1109/TIT.2016.2553041, S2CID  6291005

дальнейшее чтение

• Барейсс, Э.Х. (1969), «Численное решение линейных уравнений с теплицевыми и векторными теплицевыми матрицами», Numerische Mathematik , 13 (5): 404–424, doi : 10.1007/BF02163269, S2CID  121761517
• Гольдрейх, О. ; Таль, А. (2018), «Матричная жесткость случайных матриц Теплица», Computational Complexity , 27 (2): 305–350, doi : 10.1007/s00037-016-0144-9, S2CID  253641700
• Голуб Г.Х. , ван Лоан К.Ф. (1996), Матричные вычисления ( издательство Университета Джонса Хопкинса ) §4.7 — Теплиц и родственные системы
• Грей Р.М., Теплиц и циркулянтные матрицы: обзор (теперь издатели) doi : 10.1561/0100000006
• Нур, Ф.; Моргера, С.Д. (1992), «Построение эрмитовой матрицы Теплица из произвольного набора собственных значений», IEEE Transactions on Signal Processing , 40 (8): 2093–2094, Bibcode : 1992ITSP...40.2093N, doi : 10.1109/ 78.149978
• Пан, Виктор Ю. (2001), Структурированные матрицы и полиномы: унифицированные сверхбыстрые алгоритмы , Биркхойзер , ISBN 978-0817642402
• Да, Ке; Лим, Лек-Хенг (2016), «Каждая матрица является произведением матриц Теплица», Foundations of Computational Mathematics , 16 (3): 577–598, arXiv : 1307.5132 , doi : 10.1007/s10208-015-9254-z, S2CID  254166943