Слабоцепная диагонально-доминантная матрица

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

Определение

Предварительные сведения

Мы говорим ряд $i$ сложной матрицы $A=(a_{ij})$ является строго диагонально доминирующим (SDD), если $|a_{ii}|>\textstyle {\sum _{j\neq i}}|a_{ij}|$ . Мы говорим $A$ является SDD, если все его строки являются SDD. Слабо диагональное доминирование (WDD) определяется как $\geq$ вместо.

связанный Ориентированный граф, с $m\times m$ комплексная матрица $A=(a_{ij})$ задается вершинами $\{1,\ldots ,m\}$ и ребра определяются следующим образом: существует ребро из $i\rightarrow j$ тогда и только тогда, когда $a_{ij}\neq 0$ .

Определение

Сложная квадратная матрица $A$ называется слабоцепным диагонально-доминантным (WCDD), если

$A$ в рамках WDD и
для каждой строки $i_{1}$ это не SDD, там прогулка существует $i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{k}$ в ориентированном графе $A$ заканчивается строкой SDD $i_{k}$ .

Пример

{\displaystyle я} — Ориентированный граф, связанный с матрицей WCDD в примере. Выделена первая строка, SDD. Обратите внимание, что независимо от того, какой узел $i$ мы начинаем, мы можем найти прогулку $i\rightarrow (i-1)\rightarrow (i-2)\rightarrow \cdots \rightarrow 1$ .

The $m\times m$ матрица

{\begin{pmatrix}1\\-1&1\\&-1&1\\&&\ddots &\ddots \\&&&-1&1\end{pmatrix}}

под WCDD.

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

Несингулярность

Матрица WCDD невырождена. ^{[ 1 ]}

Доказательство : ^{[ 2 ]} Позволять $A=(a_{ij})$ быть матрицей WCDD. Предположим, существует ненулевое $x$ в нулевом пространстве $A$ . Не ограничивая общности, пусть $i_{1}$ быть таким, что $|x_{i_{1}}|=1\geq |x_{j}|$ для всех $j$ . С $A$ это WCDD, мы можем прогуляться $i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{k}$ заканчивается строкой SDD $i_{k}$ .

Взяв модули с обеих сторон

-a_{i_{1}i_{1}}x_{i_{1}}=\sum _{j\neq i_{1}}a_{i_{1}j}x_{j}

и применение неравенства треугольника дает

\left|a_{i_{1}i_{1}}\right|\leq \sum _{j\neq i_{1}}\left|a_{i_{1}j}\right|\left|x_{j}\right|\leq \sum _{j\neq i_{1}}\left|a_{i_{1}j}\right|,

и, следовательно, ряд $i_{1}$ это не СДД. Более того, поскольку $A$ является WDD, приведенная выше цепочка неравенств выполняется с равенством, так что $|x_{j}|=1$ в любое время $a_{i_{1}j}\neq 0$ . Поэтому, $|x_{i_{2}}|=1$ . Повторяя этот аргумент с $i_{2}$ , $i_{3}$ и т. д., мы находим, что $i_{k}$ это не SDD, противоречие. $\square$

Вспоминая, что неприводимая матрица — это матрица, связанный с ней ориентированный граф сильно связен , тривиальным следствием вышесказанного является то, что неприводимо доминантная по диагонали матрица (т. е. неприводимая матрица WDD с хотя бы одной строкой SDD) невырождена. ^{[ 3 ]}

Связь с неособыми M-матрицами

Следующие действия эквивалентны: ^{[ 4 ]}

$A$ является неособой WDD M-матрицей .
$A$ – неособая WDD L-матрица ;
$A$ суб- и L-матрица WCDD ;

Фактически, L-матрицы WCDD были изучены ( Джеймсом Х. Брэмблом и Б.Э. Хаббардом) еще в 1964 году в журнальной статье. ^{[ 5 ]} в котором они фигурируют под альтернативным названием матриц положительного типа .

Более того, если $A$ это $n\times n$ WCDD L-матрицу, мы можем оценить ее обратную величину следующим образом: ^{[ 6 ]}

\left\Vert A^{-1}\right\Vert _{\infty }\leq \sum _{i}\left[a_{ii}\prod _{j=1}^{i}(1-u_{j})\right]^{-1}

где

u_{i}={\frac {1}{\left|a_{ii}\right|}}\sum _{j=i+1}^{n}\left|a_{ij}\right|.

Обратите внимание, что $u_{n}$ всегда равна нулю и что правая часть приведенной выше оценки равна $\infty$ всякий раз, когда одна или несколько констант $u_{i}$ один.

Известны более точные оценки обратной L-матрицы WCDD. ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}

Приложения

Благодаря своей связи с M-матрицами (см. выше ), матрицы WCDD часто встречаются в практических приложениях. Пример приведен ниже.

Монотонные численные схемы

L-матрицы WCDD естественным образом возникают из монотонных схем аппроксимации уравнений в частных производных .

Например, рассмотрим одномерную задачу Пуассона

u^{\prime \prime }(x)+g(x)=0

для

x\in (0,1)

с граничными условиями Дирихле $u(0)=u(1)=0$ . Сдача в аренду $\{0,h,2h,\ldots ,1\}$ быть числовой сеткой (для некоторых положительных $h$ делящий единицу), монотонная разностная схема для задачи Пуассона принимает вид

-{\frac {1}{h^{2}}}A{\vec {u}}+{\vec {g}}=0

где

[{\vec {g}}]_{j}=g(jh)

и

A={\begin{pmatrix}2&-1\\-1&2&-1\\&-1&2&-1\\&&\ddots &\ddots &\ddots \\&&&-1&2&-1\\&&&&-1&2\end{pmatrix}}.

Обратите внимание, что $A$ нижняя и WCDD L-матрица.

Ссылки

^ Шивакумар, Пенсильвания; Чу, Ким Хо (1974). «Достаточное условие необращения в нуль определителей» (PDF) . Труды Американского математического общества . 43 (1): 63. doi : 10.1090/S0002-9939-1974-0332820-0 . ISSN 0002-9939 .
^ Азимзаде, Парсиад; Форсайт, Питер А. (2016). «Слабо связанные матрицы, итерация политики и импульсное управление». SIAM Journal по численному анализу . 54 (3): 1341–1364. arXiv : 1510.03928 . дои : 10.1137/15M1043431 . ISSN 0036-1429 . S2CID 29143430 .
^ Хорн, Роджер А.; Джонсон, Чарльз Р. (1990). Матричный анализ . Издательство Кембриджского университета, Кембридж.
^ Азимзаде, Парсиад (2019). «Быстрый и стабильный тест для проверки того, является ли слабо доминантная по диагонали матрица неособой M-матрицей». Математика вычислений . 88 (316): 783–800. arXiv : 1701.06951 . Бибкод : 2017arXiv170106951A . дои : 10.1090/mcom/3347 . S2CID 3356041 .
^ Брамбл, Джеймс Х.; Хаббард, Бельгия (1964). «О конечно-разностном аналоге эллиптической задачи, которая не является ни диагонально доминирующей, ни неотрицательного типа». Журнал математической физики . 43 : 117–132. дои : 10.1002/sapm1964431117 .
^ Шивакумар, Пенсильвания; Уильямс, Джозеф Дж.; Йе, Цян; Маринов, Корнелиу А. (1996). «О двусторонних границах, связанных со слабо доминантными по диагонали M-матрицами, с применением к динамике цифровых цепей». Журнал SIAM по матричному анализу и приложениям . 17 (2): 298–312. дои : 10.1137/S0895479894276370 . ISSN 0895-4798 .
^ Ченг, Гуан-Хуэй; Хуан, Тин-Чжу (2007). «Верхняя граница для $\Vert A^{-1}\Vert _{\infty }$ строго диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 426 (2–3): 667–673. doi : 10.1016/j.laa.2007.06.001 . ISSN 0024-3795 .
^ Ли, Вэнь (2008). «Норма бесконечности, обратная несингулярным диагональным доминирующим матрицам» . Письма по прикладной математике . 21 (3): 258–263. дои : 10.1016/j.aml.2007.03.018 . ISSN 0893-9659 .
^ Ван, Пин (2009). «Верхняя граница для $\Vert A^{-1}\Vert _{\infty }$ строго диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 431 (5–7): 511–517. doi : 10.1016/j.laa.2009.02.037 . ISSN 0024-3795 .
^ Хуан, Тин-Чжу; Чжу, Ян (2010). «Оценка $\Vert A^{-1}\Vert _{\infty }$ для слабоцепных диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 432 (2–3): 670–677. doi : 10.1016/j.laa.2009.09.012 . ISSN 0024-3795 .

[ShivakumarChew1974-1] Шивакумар, Пенсильвания; Чу, Ким Хо (1974). «Достаточное условие необращения в нуль определителей» (PDF) . Труды Американского математического общества . 43 (1): 63. doi : 10.1090/S0002-9939-1974-0332820-0 . ISSN 0002-9939 .

[AzimzadehForsyth2016-2] Азимзаде, Парсиад; Форсайт, Питер А. (2016). «Слабо связанные матрицы, итерация политики и импульсное управление». SIAM Journal по численному анализу . 54 (3): 1341–1364. arXiv : 1510.03928 . дои : 10.1137/15M1043431 . ISSN 0036-1429 . S2CID 29143430 .

[HornJohnson1990-3] Хорн, Роджер А.; Джонсон, Чарльз Р. (1990). Матричный анализ . Издательство Кембриджского университета, Кембридж.

[Azimzadeh2017-4] Азимзаде, Парсиад (2019). «Быстрый и стабильный тест для проверки того, является ли слабо доминантная по диагонали матрица неособой M-матрицей». Математика вычислений . 88 (316): 783–800. arXiv : 1701.06951 . Бибкод : 2017arXiv170106951A . дои : 10.1090/mcom/3347 . S2CID 3356041 .

[BrambleHubbard1964-5] Брамбл, Джеймс Х.; Хаббард, Бельгия (1964). «О конечно-разностном аналоге эллиптической задачи, которая не является ни диагонально доминирующей, ни неотрицательного типа». Журнал математической физики . 43 : 117–132. дои : 10.1002/sapm1964431117 .

[ShivakumarWilliams1996-6] Шивакумар, Пенсильвания; Уильямс, Джозеф Дж.; Йе, Цян; Маринов, Корнелиу А. (1996). «О двусторонних границах, связанных со слабо доминантными по диагонали M-матрицами, с применением к динамике цифровых цепей». Журнал SIAM по матричному анализу и приложениям . 17 (2): 298–312. дои : 10.1137/S0895479894276370 . ISSN 0895-4798 .

[ChengHuang2007-7] Ченг, Гуан-Хуэй; Хуан, Тин-Чжу (2007). «Верхняя граница для $\Vert A^{-1}\Vert _{\infty }$ строго диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 426 (2–3): 667–673. doi : 10.1016/j.laa.2007.06.001 . ISSN 0024-3795 .

[Li2008-8] Ли, Вэнь (2008). «Норма бесконечности, обратная несингулярным диагональным доминирующим матрицам» . Письма по прикладной математике . 21 (3): 258–263. дои : 10.1016/j.aml.2007.03.018 . ISSN 0893-9659 .

[Wang2009-9] Ван, Пин (2009). «Верхняя граница для $\Vert A^{-1}\Vert _{\infty }$ строго диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 431 (5–7): 511–517. doi : 10.1016/j.laa.2009.02.037 . ISSN 0024-3795 .

[HuangZhu2010-10] Хуан, Тин-Чжу; Чжу, Ян (2010). «Оценка $\Vert A^{-1}\Vert _{\infty }$ для слабоцепных диагонально доминирующих М-матриц» . Линейная алгебра и ее приложения . 432 (2–3): 670–677. doi : 10.1016/j.laa.2009.09.012 . ISSN 0024-3795 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]