В линейной алгебре - матрица Теплица или матрица диагональных констант, названный в честь Отто Теплица, представляет собой матрицу , в которой каждая нисходящая диагональ слева направо постоянна. Например, следующая матрица является матрицей Теплица:
Любая матрица A размера n × n вида
- это матрица Теплица . Если элемент i, j в A обозначен A i, j, то мы имеем
Матрица Теплица не обязательно является квадратной.
Содержание
- 1 Решение система Теплица
- 2 Общие свойства
- 3 Дискретная свертка
- 4 Бесконечная матрица Теплица
- 5 См. также
- 6 Примечания
- 7 Ссылки
- 8 Дополнительная литература
Решение Теплица система
Матричное уравнение вида
называется системой Теплица, если A является матрицей Теплица. Если A является матрицей Тёплица , то система имеет только 2n − 1 степеней свободы, а не n. Поэтому можно ожидать, что решение системы Теплица будет проще, и это действительно так.
Системы Теплица могут быть решены с помощью алгоритма Левинсона за O (n) времени. Было показано, что варианты этого алгоритма слабо устойчивы (т.е. они демонстрируют числовую стабильность для хорошо обусловленных линейных систем). Алгоритм также может использоваться для нахождения детерминанта матрицы Теплица за O(n) time.
Матрица Теплица также может быть разложена (т.е. разложена на множители) в O (n) раз. Алгоритм Барейса для разложения LU является стабильным. LU-разложение дает быстрый метод решения системы Теплица, а также для вычисления определителя.
Алгоритмы, которые асимптотически быстрее алгоритмов Барейсса и Левинсона, описаны в литературе, но на их точность нельзя полагаться.
Общие свойства
- Матрица Теплица n × n может определяется как матрица A, где A i, j = c i − j, для констант c 1 − n … c n − 1. Набор матриц Теплица размера n × n является подпространством векторного пространства матриц размера n × n при матричном сложении и скалярном умножении.
- Две матрицы Теплица могут быть добавлено за O (n) раз (путем сохранения только одного значения каждой диагонали) и умножено на за O (n) раз.
- Матрицы Теплица - это персимметричный. Симметричные матрицы Теплица являются центросимметричными и бисимметричными.
- матрицами Теплица также тесно связаны с рядами Фурье, потому что оператор умножения на тригонометрический полином, сжатый до конечномерного пространства, может быть представлен такой матрицей. Точно так же можно представить линейную свертку как умножение на матрицу Теплица.
- Матрицы Теплица коммутируют асимптотически. Это означает, что они диагонализируют в одном и том же базисе, когда размерность строки и столбца стремится к бесконечности.
- A положительная полуопределенная матрица Теплица n × n ранга r < n can be uniquely factored as
- где - положительно определенная диагональная матрица размером r × r, является n × r матрица Вандермонда такая, что столбцы имеют вид . Здесь и - нормализованная частота, а - эрмитовское транспонирование для . Если ранг r = n, то разложение Вандермонда не единственно.
- Для симметричных тёплицевых матриц существует разложение
- где - это нижняя треугольная часть .
- Инверсия неособой симметричной Матрица Теплица имеет представление
- где и - это нижнетреугольные матрицы Теплица, а - строго нижнетреугольная матрица.
Дискретная свертка
Операция свертка может быть построен как матричное умножение, где один из входов преобразуется в матрицу Теплица. Например, свертка и может быть сформулирована как:
Этот подход можно расширить для вычисления автокорреляции, взаимной корреляции, скользящего среднего и т. д.
Бесконечная матрица Теплица
Двубесконечная матрица Теплица (т. Е. Элементы, индексированные ) индуцирует линейный оператор на .
Индуцированный оператор ограничен тогда и только тогда, когда коэффициенты матрицы Теплица являются коэффициентами Фурье некоторой существенно ограниченной функции .
В таких случаях называется символом матрицы Теплица , а спектральная норма матрицы Теплица совпадает с норма его символа. Доказательство легко установить, и его можно найти в виде теоремы 1.1 в ссылке на книгу Google:
См. Также
- Циркулянтная матрица, матрица Теплица с дополнительным свойством, которое
- Матрица Ганкеля, «перевернутая» (т.е. перевернутая по строкам) матрица Теплица
Примечания
Список литературы
- Боянчик А.В.; Brent, R.P.; de Hoog, F. R.; Свит, Д.Р. (1995), «Об устойчивости алгоритмов факторизации Барейса и связанных с ним Теплица», Журнал SIAM по матричному анализу и приложениям, 16: 40–57, arXiv : 1004.5510, doi : 10.1137 / S0895479891221563
- Böttcher, Albrecht; Грудский, Сергей М. (2012), Матрицы Теплица, асимптотическая линейная алгебра и функциональный анализ, Birkhäuser, ISBN 978-3-0348-8395-5
- Brent, RP (1999), «Устойчивость быстрых алгоритмов для структурированных линейных систем», в Kailath, T.; Сайед А. Х. (ред.), Быстрые надежные алгоритмы для матриц со структурой, SIAM, стр. 103–116
- Чан, Р. Х.-Ф.; Джин, X.-Q. (2007), Введение в итерационные решатели Теплица, SIAM
- Chandrasekeran, S.; Жвачка.; Солнце, X.; Xia, J.; Чжу, Дж. (2007), «Сверхбыстрый алгоритм для систем линейных уравнений Теплица», Журнал SIAM по матричному анализу и приложениям, 29(4): 1247–1266, CiteSeerX 10.1.1.116.3297, doi : 10.1137 / 040617200
- Чен, WW; Hurvich, C.M.; Лу, Ю. (2006), «О корреляционной матрице дискретного преобразования Фурье и быстром решении больших систем Теплица для временных рядов с длинной памятью», Журнал Американской статистической ассоциации, 101 (474): 812–822, CiteSeerX 10.1.1.574.4394, doi : 10.1198 / 016214505000001069
- Кришна, ЧАС.; Ван, Ю. (1993), «Алгоритм разделения Левинсона слабо устойчив», Журнал SIAM по численному анализу, 30(5): 1498–1508, doi : 10.1137 / 0730078
- Монахан, Дж. Ф. (2011), Численные методы статистики, Cambridge University Press
- Мукерджи, Бишва Нат; Маити, Садхан Самар (1988), «О некоторых свойствах положительно определенных матриц Теплица и их возможных приложениях» (PDF), Линейная алгебра и ее приложения, 102 : 211–240, doi : 10.1016 / 0024-3795 (88) 90326-6
- Нажмите, WH; Теукольский, С. А.; Vetterling, W. T.; Фланнери, Б.П. (2007), Численные рецепты: Искусство научных вычислений (Третье изд.), Cambridge University Press, ISBN 978-0 -521-88068-8
- Стюарт, М. (2003), «Сверхбыстрый решатель Теплица с улучшенной числовой стабильностью», Журнал SIAM по матричному анализу и приложениям, 25(3) : 669–693, doi : 10.1137 / S089547980241791X
- Ян, Зай; Се, Лихуа; Стойка, Петре (2016), «Разложение Вандермонда многоуровневых матриц Теплица с применением к многомерному сверхразрешению», Транзакции IEEE по теории информации, 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. ; Tal, A. (2018), «Матричная жесткость случайных тёплицевых матриц», Computational Complexity, 27 (2): 305–350, doi : 10.1007 / s00037- 016-0144-9
- Голуб Г.Х., van Loan CF (1996), Matrix Computations (Johns Hopkins University Press ) §4.7 - Теплиц и родственные системы
- Gray RM, Теплица и циркулянтные матрицы: обзор (Now Publishers )
- Noor, F.; Morgera, SD (1992), «Построение эрмитовой матрицы Теплица из произвольный набор собственных значений ", Транзакции IEEE по обработке сигналов, 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