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

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

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

Любая n  ×  n- матрица 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}}}$

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

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

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

Решение системы Теплица [ править ]

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

${\displaystyle Ax=b}$

называется теплицевой системой, если A - теплицева матрица. Если A - тёплицева матрица n  ×  n , то система имеет только 2 n - 1 степени свободы , а не n ² . Поэтому можно ожидать, что решение системы Теплица будет проще, и это действительно так.

Системы Теплица могут быть решены алгоритмом Левинсона за время O ( n ² ) . ^[1] Было показано, что варианты этого алгоритма слабо устойчивы (т. Е. Демонстрируют численную устойчивость для хорошо обусловленных линейных систем). ^[2] Алгоритм также может быть использован для нахождения определителя матрицы Теплица за время O ( n ² ) . ^[3]

Матрица Теплица также может быть разложена (т. Е. Разложена на множители) за время O ( n ² ) . ^[4] Алгоритм Барейсса для разложения LU устойчив. ^[5] LU-разложение дает быстрый метод решения системы Теплица, а также для вычисления определителя.

Алгоритмы, которые асимптотически быстрее алгоритмов Барейса и Левинсона, описаны в литературе, но на их точность нельзя положиться. ^{[6] [7] [8] [9]}

Общие свойства [ править ]

• Матрица Теплица n  ×  n может быть определена как матрица A, где A _{i ,  j} = c _{i - j} , для констант c _{1 - n} , ..., c _{n - 1} . Набор из п  ×  п матриц Теплицы является подпространством в векторном пространстве из п  ×  п матриц (под матрицей сложения и умножения).
• Две матрицы Теплица могут быть добавлены за время O ( n ) (сохраняя только одно значение каждой диагонали) и умножены за время O ( n ² ).
• Матрицы Теплица персимметричны . Симметричные матрицы Теплица бывают центросимметричными и бисимметричными .
• Матрицы Теплица также тесно связаны с рядами Фурье , потому что оператор умножения на тригонометрический полином , сжатый до конечномерного пространства, может быть представлен такой матрицей. Точно так же можно представить линейную свертку как умножение на матрицу Теплица.
• Матрицы Теплица коммутируют асимптотически . Это означает, что они диагонализируются на одном и том же основании, когда размер строки и столбца стремится к бесконечности.
• Положительно полуопределенная п  ×  п матрица Теплица из ранга г < п может быть однозначно факторизовать${\displaystyle A}$

${\displaystyle A=\sum _{k=1}^{r}d_{i}v(f_{k})v(f_{k})^{\operatorname {H} }=VDV^{\operatorname {H} }}$

где приведен г  ×  г положительно определенную диагональную матрицу , является п  ×  г Вандермонда матрицы таким образом, что столбцы . Здесь и нормализуется частота, и это эрмитова транспонированная из . Если ранг r = n , то разложение Вандермонда не единственно. ^[10]${\displaystyle D=\mathrm {diag} (d_{1},\ldots ,d_{r})}$ ${\displaystyle V=[v(f_{1}),\ldots ,v(f_{r})]}$ ${\displaystyle v(f)=[1,e^{i2\pi f},\ldots ,e^{i2\pi (n-1)f}]^{\operatorname {T} }}$${\displaystyle i^{2}=-1}$${\displaystyle f_{k}\in [0,1]}$${\displaystyle V^{\operatorname {H} }}$${\displaystyle V}$

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

${\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} })}$

где и - нижнетреугольные теплицевы матрицы, а - строго нижнетреугольная матрица. ^[11]${\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 в ссылке на книгу Google: ^[12]${\displaystyle f}$${\displaystyle A}$${\displaystyle A}$${\displaystyle L^{\infty }}$

См. Также [ править ]

• Циркулянт матрица , матрица Теплица с дополнительным свойством, что${\displaystyle a_{i}=a_{i+n}}$
• Матрица Ганкеля , "перевернутая" (т.е. перевернутая по строкам) матрица Теплица

Заметки [ править ]

Ссылки [ править ]

• Боянчик, А.В.; Brent, RP; де Хуг, Франция; Свит, Д.Р. (1995), "Об устойчивости алгоритмов факторизации Барейса и связанных с ним Теплица", SIAM Journal on Matrix Analysis and Applications , 16 : 40–57, arXiv : 1004.5510 , doi : 10.1137 / S0895479891221563
• Бёттчер, Альбрехт; Грудский, Сергей М. (2012), Теплицевые матрицы, асимптотическая линейная алгебра и функциональный анализ , Биркхойзер, ISBN 978-3-0348-8395-5
• Брент, Р.П. (1999), "Устойчивость быстрых алгоритмов для структурированных линейных систем", в Kailath, T .; Сайед, AH (ред.), Быстрые надежные алгоритмы для матриц со структурой , SIAM , стр. 103–116
• Чан, RH-F .; Джин, X.-Q. (2007), Введение в итерационные решатели Теплица , SIAM
• Chandrasekeran, S .; Камедь.; Солнце, X .; Xia, J .; Чжу, Дж. (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
• Кришна, Х .; Ван, Y. (1993), "Разделенный Левинсона Алгоритм слабо стабильный" , SIAM журнал по численному анализу , 30 (5): 1498-1508, DOI : 10,1137 / 0730078
• Монахан, Дж. Ф. (2011), Численные методы статистики , Cambridge University Press
• Мукерджи, Бишва Натх; Маити, Sadhan Самар (1988), "О некоторых свойствах положительно определенных матриц Теплица и их возможные применения" (PDF) , Линейная алгебра и ее применения , 102 : 211-240, DOI : 10,1016 / 0024-3795 (88) 90326- 6
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), Численные рецепты: Искусство научных вычислений (третье изд.), Cambridge University Press , ISBN 978-0-521-88068-8
• Стюарт, М. (2003), «Сверхбыстрый решатель Теплица с улучшенной числовой стабильностью» , Журнал SIAM по матричному анализу и приложениям , 25 (3): 669–693, doi : 10.1137 / S089547980241791X
• Ян, Зай; Се, Лихуа; Стойка, Петре (2016), «Разложение Вандермонда многоуровневых матриц Теплица с применением к многомерному сверхразрешению», IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi : 10.1109 / TIT.2016.2553041

Дальнейшее чтение [ править ]

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