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

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

Например, следующая матрица трехдиагональная:

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

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

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

Свойства [ править ]

Трехдиагональная матрица - это матрица, которая является как верхней, так и нижней матрицей Хессенберга . ^[2] В частности, трехдиагональная матрица представляет собой прямую сумму из р 1-на-1 и Q 2-на-2 матрицы таким образом, что р + д / 2 = п - размерность Трехдиагональная. Хотя общая трехдиагональная матрица не обязательно является симметричной или эрмитовой , многие из тех, которые возникают при решении задач линейной алгебры, обладают одним из этих свойств. Кроме того, если вещественная трехдиагональная матрица 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 мерное векторное пространство .

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

Определитель [ править ]

Определитель трехдиагональной матрицы А порядка п может быть вычислен из трехчленного в рекуррентном соотношении . ^[4] Напишите f ₁ = | а ₁ | = 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={\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]

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

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

Собственные значения [ править ]

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

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

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

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

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

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

Учитывая действительную трехдиагональную несимметричную матрицу

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$

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}}

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

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$

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

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

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

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

Пятидиагональная матрица

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

↑ Томас Мьюир (1960). Трактат по теории детерминант . Dover Publications . С. 516–525 .
^ Хорн, Роджер А .; Джонсон, Чарльз Р. (1985). Матричный анализ . Издательство Кембриджского университета. п. 28. ISBN 0521386322.
↑ Хорн и Джонсон, стр.174
^ Эль-Mikkawy, MEA (2004). «Об инверсии общей трехдиагональной матрицы». Прикладная математика и вычисления . 150 (3): 669–679. DOI : 10.1016 / S0096-3003 (03) 00298-4 .
^ Da Fonseca, CM (2007). «О собственных значениях некоторых трехдиагональных матриц» . Журнал вычислительной и прикладной математики . 200 : 283–286. DOI : 10.1016 / j.cam.2005.08.047 .
^ Усмани, RA (1994). «Обращение трехдиагональной матрицы Якоби» . Линейная алгебра и ее приложения . 212–213: 413–414. DOI : 10.1016 / 0024-3795 (94) 90414-6 .
^ Ху, GY; О'Коннелл, РФ (1996). «Аналитическое обращение симметричных трехдиагональных матриц». Журнал физики A: математический и общий . 29 (7): 1511. DOI : 10.1088 / 0305-4470 / 29/7/020 .
^ Хуанг, Y .; Макколл, У.Ф. (1997). «Аналитическое обращение общих трехдиагональных матриц». Журнал физики A: математический и общий . 30 (22): 7919. DOI : 10,1088 / 0305-4470 / 30/22/026 .
^ Mallik, РК (2001). «Обращение к трехдиагональной матрице» . Линейная алгебра и ее приложения . 325 : 109–139. DOI : 10.1016 / S0024-3795 (00) 00262-7 .
^ Kılıç, E. (2008). «Явная формула обращения трехдиагональной матрицы обратными цепными дробями». Прикладная математика и вычисления . 197 : 345–357. DOI : 10.1016 / j.amc.2007.07.046 .
^ Раф Вандебрил; Марк Ван Барел; Никола Мастронарди (2008). Матричные вычисления и полусепарабельные матрицы. Том I: Линейные системы . JHU Press. Теорема 1.38, с. 41. ISBN 978-0-8018-8714-7.
^ Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Издательство Университета Джона Хопкинса. ISBN 0-8018-5414-8.
^ Noschese, S .; Pasquini, L .; Райхель, Л. (2013). «Трехдиагональные матрицы Теплица: свойства и новые приложения». Численная линейная алгебра с приложениями . 20 (2): 302. DOI : 10.1002 / nla.1811 .
^ Это также можно записать какпотому, как это сделано в: Kulkarni, D .; Schmidt, D .; Цуй, СК (1999). «Собственные значения трехдиагональных псевдотёплицевых матриц» (PDF) . Линейная алгебра и ее приложения . 297 : 63. DOI : 10.1016 / S0024-3795 (99) 00114-7 . $a-2{\sqrt {bc}}\cos(k\pi /{(n+1)})$ $\cos(x)=-\cos(\pi -x)$
^ Парлетт, Б. (1980). Симметричная проблема собственных значений . Prentice Hall, Inc.
^ Coakley, ES; Рохлин В. (2012). «Быстрый алгоритм« разделяй и властвуй »для вычисления спектров реальных симметричных трехдиагональных матриц» . Прикладной и вычислительный гармонический анализ . 34 (3): 379–414. DOI : 10.1016 / j.acha.2012.06.003 .
^ Диллон, Индерджит Сингх. Новый O (n 2) алгоритм для симметричной трехдиагональной проблемы собственных значений / собственных векторов (PDF) . п. 8.
^ "www.math.hkbu.edu.hk лекция по математике" (PDF) .

Внешние ссылки [ править ]

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

[1] Томас Мьюир (1960). Трактат по теории детерминант . Dover Publications . С. 516–525 .

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

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

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

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

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

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

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

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

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

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

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

[13] Noschese, S .; Pasquini, L .; Райхель, Л. (2013). «Трехдиагональные матрицы Теплица: свойства и новые приложения». Численная линейная алгебра с приложениями . 20 (2): 302. DOI : 10.1002 / nla.1811 .

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

[15] Парлетт, Б. (1980). Симметричная проблема собственных значений . Prentice Hall, Inc.

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

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

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

[1]