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

редактировать

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

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

Любая матрица A размера n × n вида

A = [a a - 1 a - 2 ⋯ ⋯ a - (n - 1) a 1 a 0 a - 1 ⋱ ⋮ a 2 a 1 ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ a - 1 a - 2 ⋮ ⋱ a 1 a 0 a - 1 an - 1 ⋯ ⋯ a 2 a 1 a 0] {\ 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 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, то мы имеем

A i, j = A i + 1, j + 1 = a i - j. {\ displaystyle A_ {i, j} = A_ {i + 1, j + 1} = a_ {ij}. \}A_ {i, j} = A_ {i + 1, j + 1} = a_ {ij}. \

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

Содержание

  • 1 Решение система Теплица
  • 2 Общие свойства
  • 3 Дискретная свертка
  • 4 Бесконечная матрица Теплица
  • 5 См. также
  • 6 Примечания
  • 7 Ссылки
  • 8 Дополнительная литература

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

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

A x = b {\ displaystyle Ax = b \}Ax = b \

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

Системы Теплица могут быть решены с помощью алгоритма Левинсона за O (n) времени. Было показано, что варианты этого алгоритма слабо устойчивы (т.е. они демонстрируют числовую стабильность для хорошо обусловленных линейных систем). Алгоритм также может использоваться для нахождения детерминанта матрицы Теплица за O(n) time.

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

Алгоритмы, которые асимптотически быстрее алгоритмов Барейсса и Левинсона, описаны в литературе, но на их точность нельзя полагаться.

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

A = ∑ k = 1 rdiv (fk) v (fk) H = VDVH {\ displaystyle A = \ sum _ {k = 1} ^ {r} d_ {i} v (f_ {k}) v (f_ {k}) ^ {\ operatorname {H}} = VDV ^ {\ operatorname {H}}}{\ displaystyle A = \ sum _ {k = 1} ^ {r} d_ {i} v (f_ {k}) v (f_ {k}) ^ {\ operatorname {H} } = VDV ^ {\ operatorname {H}}}
где D = diag (d 1,…, Dr) {\ displaystyle D = \ mathrm {diag} (d_ {1}, \ ldots, d_ {r})}{\ displaystyle D = \ mathrm {diag} (d_ {1}, \ ldots, d_ {r}))} - положительно определенная диагональная матрица размером r × r, V = [v (f 1),…, v (fr)] {\ displaystyle V = [v (f_ {1}), \ ldots, v (f_ {r})]}{\ displaystyle V = [v (f_ {1}), \ ldots, v (f_ {r})]} является n × r матрица Вандермонда такая, что столбцы имеют вид v (f) = [1, ei 2 π f,…, ei 2 π (n - 1) f] T {\ displaystyle v (f) = [1, e ^ {i2 \ pi f}, \ ldots, e ^ {i2 \ pi (n-1) f}] ^ {\ operatorname {T}}}{\ displaystyle v (f) = [1, e ^ {i2 \ pi f}, \ ldots, e ^ {i2 \ pi (n-1) f}] ^ {\ operatorname {T} }} . Здесь i = - 1 {\ displaystyle i = {\ sqrt {-1}}}i = {\ sqrt {-1}} и fk ∈ [0, 1] {\ displaystyle f_ {k} \ in [0, 1]}{\ displaystyle f_ {k} \ in [0,1]} - нормализованная частота, а VH {\ displaystyle V ^ {\ operatorname {H}}}{\ displaystyle V ^ {\ operatorname {H}}} - эрмитовское транспонирование для В {\ Displaystyle V}V . Если ранг r = n, то разложение Вандермонда не единственно.
  • Для симметричных тёплицевых матриц существует разложение
1 a 0 A = GGT - (G - I) (G - I) T {\ displaystyle {\ frac {1} {a_ {0}}} A = GG ^ {\ operatorname {T}} - (GI) (GI) ^ {\ operatorname {T}}}{\ displaystyle {\ frac {1} {a_ {0}}} A = GG ^ {\ operatorname {T}} - (GI) (GI) ^ {\ operatorname {T}} }
где G { \ displaystyle G}G - это нижняя треугольная часть 1 a 0 A {\ displaystyle {\ frac {1} {a_ {0}}} A}{\ displaystyle {\ frac {1} {a_ {0}}} A} .
  • Инверсия неособой симметричной Матрица Теплица имеет представление
A - 1 = 1 α 0 (BBT - CCT) {\ displaystyle A ^ {- 1} = {\ frac {1} {\ alpha _ {0}}} (BB ^ {\ имя оператора {T}} -CC ^ {\ operatorname {T}})}{\ displaystyle A ^ {- 1} = {\ frac {1} {\ alpha _ {0}}} (BB ^ {\ operatorname {T}} -CC ^ {\ operatorname {T}})}
где B {\ displaystyle B}B и C {\ displaystyle C}C - это нижнетреугольные матрицы Теплица, а C {\ displaystyle C}C - строго нижнетреугольная матрица.

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

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

y = h ∗ x = [h 1 0 ⋯ 0 0 h 2 h 1 ⋮ ⋮ h 3 h 2 ⋯ 0 0 h 3 ⋯ h 1 0 hm - 1 ⋮ ⋱ h 2 h 1 hmhm - 1 ⋮ h 2 0 hm hm - 2 ⋮ 0 0 ⋯ hm - 1 hm - 2 ⋮ ⋮ hmhm - 1 0 0 0 ⋯ hm] [x 1 x 2 x 3 ⋮ xn] {\ 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 = 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}}}
y T = [h 1 h 2 h 3 ⋯ hm - 1 hm] [x 1 x 2 x 3 ⋯ xn 0 0 0 ⋯ 0 0 x 1 x 2 x 3 ⋯ xn 0 0 ⋯ 0 0 0 x 1 x 2 x 3… xn 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 ⋯ 0 0 x 1 ⋯ xn - 2 xn - 1 xn 0 0 ⋯ 0 0 0 x 1 xn - 2 xn - 1 xn]. {\ 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 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}}.}

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

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

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

A = [⋮ ⋮ ⋮ ⋮ ⋯ a 0 a - 1 a - 2 a - 3 ⋯ ⋯ a 1 a 0 a - 1 a - 2 ⋯ ⋯ a 2 a 1 a 0 a - 1 ⋯ ⋯ a 3 a 2 a 1 a 0 ⋯ ⋮ ⋮ ⋮ ⋮]. {\ 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 = {\ 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}}.}

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

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

См. Также

Примечания

Список литературы

Дополнительная литература

Последняя правка сделана 2021-06-11 05:16:04
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте