Матрица Теплица - Toeplitz matrix

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

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

это Матрица Теплица. Если я,j элемент А обозначается А_я,j, то имеем

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

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

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

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

${\displaystyle Ax=b\ }$

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

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

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

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

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

• An п×п Матрица Теплица может быть определена как матрица А где А_{я, j} = c_{i − j}, для констант c_1−п ... c_п−1. Набор п×п Матрицы Теплица - это подпространство из векторное пространство из п×п матрицы при сложении матриц и скалярном умножении.
• Две матрицы Теплица могут быть добавлены в О(п) время (сохраняя только одно значение каждой диагонали) и умноженный в О(п²) время.
• Матрицы Теплица персимметричный. Симметричные матрицы Теплица обе являются центросимметричный и бисимметричный.
• Матрицы Теплица также тесно связаны с Ряд Фурье, поскольку оператор умножения по тригонометрический полином, сжатый в конечномерное пространство, может быть представлена ​​такой матрицей. Точно так же можно представить линейную свертку как умножение на матрицу Теплица.
• Матрицы Теплица ездить асимптотически. Это означает, что они диагонализировать В то же самое основа когда размер строки и столбца стремится к бесконечности.
• А положительный полуопределенный п×п Матрица Теплица ${\displaystyle A}$ ранга р < п может быть однозначно учитывается как

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

где ${\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={\sqrt {-1}}}$ и ${\displaystyle f_{k}\in [0,1]}$ - нормализованная частота, а ${\displaystyle V^{\operatorname {H} }}$ это Эрмитово транспонирование из ${\displaystyle V}$. Если ранг р = п, то разложение Вандермонда не единственно.^[10]

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

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

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

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

В свертка Операция может быть построена как матричное умножение, где один из входных данных преобразуется в матрицу Теплица. Например, свертка ${\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}$.

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

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

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

Заметки

1. Press et al. 2007 г., §2.8.2 - Матрицы Теплица
2. Кришна и Ван 1993
3. Монахан 2011, §4.5 - Теплицевые системы
4. Брент 1999
5. Боянчик и др. 1995 г. Ошибка harvnb: цель отсутствует: CITEREFBojanczykBrentHoogSweet1995 (Помогите)
6. Стюарт 2003
7. Чен, Гурвич и Лу 2006
8. Чан и Джин 2007
9. Chandrasekeran et al. 2007 г.
10. Ян, Се и Стойка, 2016
11. Мукерджи и Мэйти 1988
12. Böttcher & Grudsky 2012

использованная литература

• Bojanczyk, A. W .; Brent, R.P .; de Hoog, F. R .; Свит, Д. Р. (1995), "Об устойчивости алгоритмов факторизации Барейса и связанных с ним алгоритмов Теплица", Журнал SIAM по матричному анализу и приложениям, 16: 40–57, arXiv:1004.5510, Дои:10.1137 / S0895479891221563
• Бёттчер, Альбрехт; Грудский, Сергей М. (2012), Матрицы Теплица, асимптотическая линейная алгебра и функциональный анализ, Биркхойзер, ISBN  978-3-0348-8395-5
• Брент, Р. П. (1999), "Устойчивость быстрых алгоритмов для структурированных линейных систем", в Kailath, T .; Сайед, А. Х. (ред.), Быстрые надежные алгоритмы для матриц со структурой, СИАМ, стр. 103–116
• Chan, R.H.-F .; Джин, X.-Q. (2007), Введение в итерационные решатели Теплица, СИАМ
• Chandrasekeran, S .; Жвачка.; Солнце, X .; Xia, J .; Чжу, Дж. (2007), "Сверхбыстрый алгоритм для системы линейных уравнений Теплица", Журнал SIAM по матричному анализу и приложениям, 29 (4): 1247–1266, CiteSeerX  10.1.1.116.3297, Дои:10.1137/040617200
• Chen, W. W .; Hurvich, C.M .; Лу, Ю. (2006), "О корреляционной матрице дискретного преобразования Фурье и быстром решении больших систем Теплица для временных рядов с длинной памятью", Журнал Американской статистической ассоциации, 101 (474): 812–822, CiteSeerX  10.1.1.574.4394, Дои:10.1198/016214505000001069
• Кришна, Х .; Ван, Ю. (1993), «Сплит-алгоритм Левинсона слабо устойчив», Журнал SIAM по численному анализу, 30 (5): 1498–1508, Дои:10.1137/0730078
• Монахан, Дж. Ф. (2011), Численные методы статистики, Издательство Кембриджского университета
• Мукерджи, Бишва Натх; Маити, Садхан Самар (1988), «О некоторых свойствах положительно определенных теплицевых матриц и их возможных приложениях» (PDF), Линейная алгебра и ее приложения, 102: 211–240, Дои:10.1016/0024-3795(88)90326-6
• Press, W. H .; Теукольский, С. А .; Vetterling, W. T .; Фланнери, Б. П. (2007), Числовые рецепты: искусство научных вычислений (Третье изд.), Издательство Кембриджского университета, ISBN  978-0-521-88068-8
• Стюарт, М. (2003), «Сверхбыстрый решатель Теплица с улучшенной числовой стабильностью», Журнал SIAM по матричному анализу и приложениям, 25 (3): 669–693, Дои:10.1137 / S089547980241791X
• Ян, Зай; Се, Лихуа; Стойка, Петре (2016), "Разложение Вандермонда многоуровневых тёплицевых матриц с применением к многомерному сверхразрешению", IEEE Transactions по теории информации, 62 (6): 3685–3701, arXiv:1505.02510, Дои:10.1109 / TIT.2016.2553041

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

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