Слабо связанная диагонально доминирующая матрица

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

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

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

Говорят, что сложная квадратная матрица имеет слабую цепочку диагонально доминирующих матриц (WCDD), если${\displaystyle А}$

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

Матрица​${\displaystyle m\times m}$

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

это WCDD.

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

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

и, следовательно, row не является SDD. Более того, поскольку является WDD, приведенная выше цепочка неравенств выполняется с равенством, так что всякий раз , когда . Следовательно, . Повторяя этот аргумент с , , и т. д., мы обнаруживаем, что не является SDD, противоречие.${\displaystyle i_{1}}$${\displaystyle А}$${\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}}$${\displaystyle \квадрат}$

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

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

• ${\displaystyle А}$является неособой WDD M-матрицей .
• ${\displaystyle А}$– неособая WDD L-матрица ;
• ${\displaystyle А}$представляет собой L-матрицу WCDD ;

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

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

${\displaystyle \left\Верт A^{-1}\right\Верт _{\infty }\leq \сумма _{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 и(0)=и(1)=0}$${\displaystyle \{0,h,2h,\ldots ,1\}}$${\displaystyle ч}$

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

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