Слабосвязанная матрица с диагональным преобладанием - Weakly chained diagonally dominant matrix

Диаграмма Венна, показывающая сдерживание матриц со слабой диагональной доминантой (WCDD) относительно матриц со слабой диагональной доминантой (WDD) и строго диагональной доминантой (SDD).

В математике слабосвязанные матрицы с диагональным преобладанием семья невырожденные матрицы которые включают строго матрицы с диагональным преобладанием.

Определение

Предварительные мероприятия

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

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

Определение

Комплексная квадратная матрица ${\displaystyle A}$ как говорят слабо сцепленный по диагонали (WCDD), если

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

Пример

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

В ${\displaystyle m\times m}$ матрица

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

это WCDD.

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

Неособенность

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

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

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

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

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

${\displaystyle \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|,}$

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

Напоминая, что несводимый Матрица - это матрица, чей связанный ориентированный граф сильно связанный, тривиальным следствием вышеизложенного является то, что неприводимо диагонально доминирующая матрица (т.е. неприводимая матрица WDD хотя бы с одной строкой SDD) невырождена.^[3]

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

Следующие варианты эквивалентны:^[4]

• ${\displaystyle A}$ неособый WDD М-матрица.
• ${\displaystyle A}$ неособый WDD L-матрица;
• ${\displaystyle A}$ является WCDD L-матрица;

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

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

${\displaystyle \left\Vert A^{-1}\right\Vert _{\infty }\leq \sum _{i}\left[a_{ii}\prod _{j=1}^{i}(1-u_{j})\right]^{-1}}$ куда ${\displaystyle u_{i}={\frac {1}{\left|a_{ii}\right|}}\sum _{j=i+1}^{n}\left|a_{ij}\right|.}$

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

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

Приложения

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

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

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

Например, рассмотрим одномерный Проблема Пуассона

${\displaystyle u^{\prime \prime }(x)+g(x)=0}$ за ${\displaystyle x\in (0,1)}$

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

${\displaystyle -{\frac {1}{h^{2}}}A{\vec {u}}+{\vec {g}}=0}$ куда ${\displaystyle [{\vec {g}}]_{j}=g(jh)}$

и

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

Обратите внимание, что ${\displaystyle A}$ является L-матрицей WCDD.

Рекомендации

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