Трехдиагональная матрица

В линейной алгебре трехдиагональная матрица — это ленточная матрица , которая имеет ненулевые элементы только на главной диагонали , субдиагональной/нижней диагонали (первая диагональ ниже этой) и супрадиагональной/верхней диагонали (первая диагональ выше главной диагонали). Например, следующая матрица является трехдиагональной :

{\begin{pmatrix}1&4&0&0\\3&4&1&0\\0&2&3&4\\0&0&1&3\\\end{pmatrix}}.

Определителем трехдиагональной матрицы является континуант ее элементов. ^[1]

Ортогональное преобразование симметричной (или эрмитовой) матрицы в трехдиагональную форму можно выполнить с помощью алгоритма Ланцоша .

Характеристики

Трехдиагональная матрица — это матрица, которая является одновременно верхней и нижней матрицей Хессенберга . ^[2] В частности, трехдиагональная матрица представляет собой прямую сумму матриц p 1 на 1 и q 2 на 2 таких, что p + q /2 = n — размерность трехдиагонали. Хотя общая трехдиагональная матрица не обязательно является симметричной или эрмитовой , многие из тех, которые возникают при решении задач линейной алгебры, обладают одним из этих свойств. Более того, если действительная трехдиагональная матрица A удовлетворяет условиям a _{k , k +1} a _{k +1, k} > 0 для всех k , так что знаки ее элементов симметричны, то она аналогична эрмитовой матрице путем диагональной замены базовой матрицы. Следовательно, его собственные значения действительны. Если мы заменим строгое неравенство на a _{k , k +1} a _{k +1, k} ≥ 0, то в силу непрерывности собственные значения по-прежнему гарантированно будут действительными, но матрица больше не обязательно будет похожа на эрмитову матрицу. ^[3]

Набор трехдиагональных матриц размера всех n × n образует 3n-2- мерное векторное пространство .

линейной алгебры Многие алгоритмы требуют значительно меньше вычислительных усилий при применении к диагональным матрицам, и это улучшение часто распространяется и на трехдиагональные матрицы.

Определитель

Определитель A трехдиагональной матрицы порядка n можно вычислить из трехчленного рекуррентного соотношения . ^[4] Напишите f ₁ = | 1 _| = a ₁ (т. е. f ₁ является определителем матрицы 1 на 1, состоящей только из a ₁ ), и пусть

f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}.

Последовательность ( f _i ) называется континуантом и удовлетворяет рекуррентному соотношению

f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}

с начальными значениями f ₀ = 1 и f ₋₁ = 0. Стоимость вычисления определителя трехдиагональной матрицы с использованием этой формулы линейна по n , а для общей матрицы стоимость является кубической.

Инверсия

Обратная T неособая трехдиагональная матрица

T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}

дается

(T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i<j\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}

где θ _i удовлетворяют рекуррентному соотношению

\theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n

с начальными условиями θ ₀ = 1, θ ₁ = a ₁ и φ _i удовлетворяют

\phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\qquad i=n-1,\ldots ,1

с начальными условиями φ _{n +1} = 1 и φ _n = a _n . ^[5]^[6]

Решения в замкнутой форме могут быть вычислены для особых случаев, таких как симметричные матрицы, в которых все диагональные и недиагональные элементы равны. ^[7] или матрицы Теплица ^[8] и для общего случая тоже. ^[9]^[10]

В общем, обратная трехдиагональная матрица является полуразделимой матрицей , и наоборот. ^[11] Обратная симметричная трехдиагональная матрица может быть записана как однопарная матрица (также известная как представимая генератором полуразделимая матрица ) вида ^[12]^[13]

${\begin{pmatrix}\alpha _{1}&-\beta _{1}\\-\beta _{1}&\alpha _{2}&-\beta _{2}\\&\ddots &\ddots &\ddots &\\&&\ddots &\ddots &-\beta _{n-1}\\&&&-\beta _{n-1}&\alpha _{n}\end{pmatrix}}^{-1}={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{1}b_{2}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{1}b_{n}&a_{2}b_{n}&\cdots &a_{n}b_{n}\end{pmatrix}}=\left(a_{\min(i,j)}b_{\max(i,j)}\right)$

где ${\begin{cases}\displaystyle a_{i}={\frac {\beta _{i}\cdots \beta _{n-1}}{\delta _{i}\cdots \delta _{n}\,b_{n}}}\\\displaystyle b_{i}={\frac {\beta _{1}\cdots \beta _{i-1}}{d_{1}\cdots d_{i}}}\end{cases}}$ с ${\begin{cases}d_{n}=\alpha _{n},\quad d_{i-1}=\alpha _{i-1}-{\frac {\beta _{i-1}^{2}}{d_{i}}},&i=n,n-1,\cdots ,2,\\\delta _{1}=\alpha _{1},\quad \delta _{i+1}=\alpha _{i+1}-{\frac {\beta _{i}^{2}}{\delta _{i}}},&i=1,2,\cdots ,n-1.\end{cases}}$

Решение линейной системы

Система уравнений Ax = b для $b\in \mathbb {R} ^{n}$ может быть решена с помощью эффективной формы исключения Гаусса, когда A является трехдиагональным, называемым трехдиагональным матричным алгоритмом , требующим O ( n ) операций. ^[14]

Собственные значения

Когда трехдиагональная матрица также является теплицевой , существует простое решение в замкнутой форме для ее собственных значений, а именно: ^[15]^[16]

a-2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.

Действительная симметричная трехдиагональная матрица имеет действительные собственные значения, и все собственные значения различны (просты), если все недиагональные элементы не равны нулю. ^[17] Существуют многочисленные методы численного вычисления собственных значений действительной симметричной трехдиагональной матрицы с произвольной конечной точностью, обычно требующие $O(n^{2})$ операции над матрицей размера $n\times n$ , хотя существуют быстрые алгоритмы, которые (без параллельных вычислений) требуют всего лишь $O(n\log n)$ . ^[18]

В качестве примечания: нередуцированная симметричная трехдиагональная матрица - это матрица, содержащая ненулевые недиагональные элементы трехдиагонали, где собственные значения различны, а собственные векторы уникальны с точностью до масштабного коэффициента и взаимно ортогональны. ^[19]

Сходство с симметричной трехдиагональной матрицей

Для несимметричных или несимметричных трехдиагональных матриц можно вычислить собственное разложение, используя преобразование подобия.Учитывая действительную трехдиагональную несимметричную матрицу

T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}

где $b_{i}\neq c_{i}$ .Предположим, что каждое произведение недиагональных элементов строго положительно. $b_{i}c_{i}>0$ и определим матрицу преобразования $D$ к ^[20]

D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}

Преобразование подобия $D^{-1}TD$ дает симметричную трехдиагональную матрицу $J$ к: ^[21]^[20]

J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.

Обратите внимание, что $T$ и $J$ имеют одинаковые собственные значения.

Компьютерное программирование

Преобразование, приводящее общую матрицу к форме Хессенберга, приведет эрмитову матрицу к трехдиагональной форме. Таким образом, многие алгоритмы собственных значений при применении к эрмитовой матрице в качестве первого шага сводят входную эрмитову матрицу к (симметричной вещественной) трехдиагональной форме. ^[22]

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

Приложения

Дискретизация в пространстве одномерного уравнения диффузии или теплопроводности

{\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}

второго порядка использование центральных конечных разностей приводит к

{\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x^{2}}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}

с константой дискретизации $\Delta x$ . Матрица трехдиагональная с $a_{i}=-2$ и $b_{i}=c_{i}=1$ . Примечание: здесь не используются граничные условия.

См. также

Примечания

^ Томас Мьюир (1960). Трактат по теории определителей . Дуврские публикации . стр. 516–525 .
^ Хорн, Роджер А.; Джонсон, Чарльз Р. (1985). Матричный анализ . Издательство Кембриджского университета. п. 28. ISBN 0521386322 .
^ Хорн и Джонсон, стр. 174.
^ Эль-Миккави, МЭА (2004 г.). «Об обратной общей трехдиагональной матрице». Прикладная математика и вычислительная техника . 150 (3): 669–679. дои : 10.1016/S0096-3003(03)00298-4 .
^ Да Фонсека, CM (2007). «О собственных значениях некоторых трехдиагональных матриц» . Журнал вычислительной и прикладной математики . 200 : 283–286. дои : 10.1016/j.cam.2005.08.047 .
^ Усмани, РА (1994). «Обращение трехдиагональной матрицы Якоби» . Линейная алгебра и ее приложения . 212–213: 413–414. дои : 10.1016/0024-3795(94)90414-6 .
^ Ху, ГЯ; О'Коннелл, РФ (1996). «Аналитическое обращение симметричных трехдиагональных матриц». Журнал физики A: Математический и общий . 29 (7): 1511. doi : 10.1088/0305-4470/29/7/020 .
^ Хуанг, Ю.; Макколл, ВФ (1997). «Аналитическое обращение общих трехдиагональных матриц». Журнал физики A: Математический и общий . 30 (22): 7919. doi : 10.1088/0305-4470/30/22/026 .
^ Маллик, РК (2001). «Обратная трехдиагональная матрица» . Линейная алгебра и ее приложения . 325 : 109–139. дои : 10.1016/S0024-3795(00)00262-7 .
^ Кылич, Э. (2008). «Явная формула обращения трехдиагональной матрицы цепными дробями назад». Прикладная математика и вычислительная техника . 197 : 345–357. дои : 10.1016/j.amc.2007.07.046 .
^ Раф Вандебриль; Марк Ван Барель; Никола Мастронарди (2008). Матричные вычисления и полуразделимые матрицы. Том I: Линейные системы . Джу Пресс. Теорема 1.38, с. 41. ИСБН 978-0-8018-8714-7 .
^ Меран, Жерар (1992). «Обзор обратной симметричной трехдиагональной и блочной трехдиагональной матриц» . Журнал SIAM по матричному анализу и его приложениям . 13 (3): 707–728. дои : 10.1137/0613045 .
^ Боссу, Себастьян (2024). «Трёхдиагональные и однопарные матрицы и обратная сумма двух однопарных матриц» . Линейная алгебра и ее приложения . 699 : 129–158. arXiv : 2304.06100 . дои : 10.1016/j.laa.2024.06.018 .
^ Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Издательство Университета Джонса Хопкинса. ISBN 0-8018-5414-8 .
^ Ношезе, С.; Пасквини, Л.; Райхель, Л. (2013). «Трёхдиагональные матрицы Теплица: свойства и новые приложения». Численная линейная алгебра с приложениями . 20 (2): 302. doi : 10.1002/nla.1811 .
^ Это также можно записать как $a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})$ потому что $\cos(x)=-\cos(\pi -x)$ , как это сделано в: Кулкарни, Д.; Шмидт, Д.; Цуй, СК (1999). «Собственные значения трехдиагональных псевдотеплицевых матриц» (PDF) . Линейная алгебра и ее приложения . 297 :63. дои : 10.1016/S0024-3795(99)00114-7 .
^ Парлетт, Б.Н. (1980). Симметричная проблема собственных значений . Прентис Холл, Инк.
^ Коакли, ES; Рохлин, В. (2012). «Быстрый алгоритм «разделяй и властвуй» для вычисления спектров действительных симметричных трехдиагональных матриц» . Прикладной и вычислительный гармонический анализ . 34 (3): 379–414. дои : 10.1016/j.acha.2012.06.003 .
^ Диллон, Индерджит Сингх. Новый алгоритм O(n 2 ) для симметричной трехдиагональной задачи о собственных значениях/собственных векторах (PDF) . п. 8.
^ Jump up to: ^а ^б Крир, М. (1994). «Аналитические процессы рождения-смерти: подход гильбертова пространства». Стохастические процессы и их приложения . 49 (1): 65–74. дои : 10.1016/0304-4149(94)90112-0 .
^ «www.math.hkbu.edu.hk лекция по математике» (PDF) .
^ Эйдельман, Юлий; Гохберг, Израиль; Джеминьяни, Лука (1 января 2007 г.). «О быстром приведении квазиразделимой матрицы к гессенберговской и трехдиагональной формам» . Линейная алгебра и ее приложения . 420 (1): 86–101. дои : 10.1016/j.laa.2006.06.028 . ISSN 0024-3795 .

Внешние ссылки

Трехдиагональные и двудиагональные матрицы в руководстве LAPACK.
Моаввад Эль-Миккави, Абдельрахман Каравиа (2006). «Обращение общих трехдиагональных матриц» (PDF) . Письма по прикладной математике . 19 (8): 712–720. дои : 10.1016/j.aml.2005.11.012 . Архивировано из оригинала (PDF) 20 июля 2011 г.
Высокопроизводительные алгоритмы приведения к сжатой (Гессенберговой, трехдиагональной, двудиагональной) форме.
Решатель трехдиагональной линейной системы на C++

[1] Томас Мьюир (1960). Трактат по теории определителей . Дуврские публикации . стр. 516–525 .

[2] Хорн, Роджер А.; Джонсон, Чарльз Р. (1985). Матричный анализ . Издательство Кембриджского университета. п. 28. ISBN 0521386322 .

[3] Хорн и Джонсон, стр. 174.

[4] Эль-Миккави, МЭА (2004 г.). «Об обратной общей трехдиагональной матрице». Прикладная математика и вычислительная техника . 150 (3): 669–679. дои : 10.1016/S0096-3003(03)00298-4 .

[5] Да Фонсека, CM (2007). «О собственных значениях некоторых трехдиагональных матриц» . Журнал вычислительной и прикладной математики . 200 : 283–286. дои : 10.1016/j.cam.2005.08.047 .

[6] Усмани, РА (1994). «Обращение трехдиагональной матрицы Якоби» . Линейная алгебра и ее приложения . 212–213: 413–414. дои : 10.1016/0024-3795(94)90414-6 .

[7] Ху, ГЯ; О'Коннелл, РФ (1996). «Аналитическое обращение симметричных трехдиагональных матриц». Журнал физики A: Математический и общий . 29 (7): 1511. doi : 10.1088/0305-4470/29/7/020 .

[8] Хуанг, Ю.; Макколл, ВФ (1997). «Аналитическое обращение общих трехдиагональных матриц». Журнал физики A: Математический и общий . 30 (22): 7919. doi : 10.1088/0305-4470/30/22/026 .

[9] Маллик, РК (2001). «Обратная трехдиагональная матрица» . Линейная алгебра и ее приложения . 325 : 109–139. дои : 10.1016/S0024-3795(00)00262-7 .

[10] Кылич, Э. (2008). «Явная формула обращения трехдиагональной матрицы цепными дробями назад». Прикладная математика и вычислительная техника . 197 : 345–357. дои : 10.1016/j.amc.2007.07.046 .

[VandebrilBarel2008-11] Раф Вандебриль; Марк Ван Барель; Никола Мастронарди (2008). Матричные вычисления и полуразделимые матрицы. Том I: Линейные системы . Джу Пресс. Теорема 1.38, с. 41. ИСБН 978-0-8018-8714-7 .

[Meurant1992-12] Меран, Жерар (1992). «Обзор обратной симметричной трехдиагональной и блочной трехдиагональной матриц» . Журнал SIAM по матричному анализу и его приложениям . 13 (3): 707–728. дои : 10.1137/0613045 .

[13] Боссу, Себастьян (2024). «Трёхдиагональные и однопарные матрицы и обратная сумма двух однопарных матриц» . Линейная алгебра и ее приложения . 699 : 129–158. arXiv : 2304.06100 . дои : 10.1016/j.laa.2024.06.018 .

[14] Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Издательство Университета Джонса Хопкинса. ISBN 0-8018-5414-8 .

[15] Ношезе, С.; Пасквини, Л.; Райхель, Л. (2013). «Трёхдиагональные матрицы Теплица: свойства и новые приложения». Численная линейная алгебра с приложениями . 20 (2): 302. doi : 10.1002/nla.1811 .

[16] Это также можно записать как $a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})$ потому что $\cos(x)=-\cos(\pi -x)$ , как это сделано в: Кулкарни, Д.; Шмидт, Д.; Цуй, СК (1999). «Собственные значения трехдиагональных псевдотеплицевых матриц» (PDF) . Линейная алгебра и ее приложения . 297 :63. дои : 10.1016/S0024-3795(99)00114-7 .

[17] Парлетт, Б.Н. (1980). Симметричная проблема собственных значений . Прентис Холл, Инк.

[18] Коакли, ES; Рохлин, В. (2012). «Быстрый алгоритм «разделяй и властвуй» для вычисления спектров действительных симметричных трехдиагональных матриц» . Прикладной и вычислительный гармонический анализ . 34 (3): 379–414. дои : 10.1016/j.acha.2012.06.003 .

[19] Диллон, Индерджит Сингх. Новый алгоритм O(n 2 ) для симметричной трехдиагональной задачи о собственных значениях/собственных векторах (PDF) . п. 8.

[kreer_operator-20] Jump up to: ^а ^б Крир, М. (1994). «Аналитические процессы рождения-смерти: подход гильбертова пространства». Стохастические процессы и их приложения . 49 (1): 65–74. дои : 10.1016/0304-4149(94)90112-0 .

[21] «www.math.hkbu.edu.hk лекция по математике» (PDF) .

[22] Эйдельман, Юлий; Гохберг, Израиль; Джеминьяни, Лука (1 января 2007 г.). «О быстром приведении квазиразделимой матрицы к гессенберговской и трехдиагональной формам» . Линейная алгебра и ее приложения . 420 (1): 86–101. дои : 10.1016/j.laa.2006.06.028 . ISSN 0024-3795 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

v т и Матричные классы
Явно ограниченные записи	Чередование Антидиагональ антиэрмитовский Антисимметричный наконечник стрелы Группа двуугольный Бисимметричный Блок-диагональ Блокировать Блок трехдиагональный логическое значение Коши Центросимметричный Конференция Комплекс Адамара Сопозитивный Диагональная доминанта Диагональ Дискретное преобразование Фурье элементарный Эквивалент Фробениус Обобщенная перестановка Адамар Приобретение эрмитовский Хессенберг Пустой Целое число Логический Матричный блок Мецлер Мур Неотрицательный Пятиугольный перестановка Персимметричный Полиномиальный кватернионный Подпись косо-эрмитовский Кососимметричный Горизонт Редкий Сильвестр Симметричный Тёплиц Треугольный Трехдиагональный Вандермонде Уолш С
Постоянный	Обмен Гильберт Личность Лемер Из них Паскаль Паули Редхеффер Сдвиг Ноль
Условия на собственные значения или собственные векторы	Компаньон Конвергентный Дефектный Определенный Диагонализуемый Гурвиц Положительно-определенный Стилтьес
Выполнение условий на изделия или инверсы	Конгруэнтный Идемпотент или проекция Обратимый Инволютивный Нильпотентный Нормальный Ортогональный Унимодульный Одномогущий Унитарный Полностью унимодульный Взвешивание
С конкретными приложениями	Адъюгат знак чередования Дополненный Безу Карл Великий Картан циркулирующий Кофактор коммутация Путаница Коксетер Расстояние Дублирование и устранение Евклидово расстояние Фундаментальное (линейное дифференциальное уравнение) Генератор Грамм Гессен Домохозяин якобиан Момент Расплачиваться Выбирать Случайный Вращение Зейферт сдвиг Сходство симплектический Полностью позитивный Трансформация
Используется в статистике	Центрирование Корреляция Ковариация Дизайн Двойной стохастический Информация о Фишере Имеет Точность Стохастический Переход
Используется в теории графов	Смежность Бисмежность Степень Эдмондс Заболеваемость лапласиан Соседство Зайделя Все
Используется в науке и технике	Кабиббо – Кобаяши – Маскава Плотность Фундаментальный (компьютерное зрение) Нечеткая ассоциативность Гамма Гелл-Манн гамильтониан Нерегулярный Перекрывать С Государственный переход Замена З (химия)
Связанные термины	Джордан в нормальной форме Линейная независимость Матричная экспонента Матричное представление конических сечений Идеальная матрица Псевдообратный Форма эшелона строк Вронскиан
Математический портал Список матриц Категория:Матрицы