Slabě zřetězená úhlopříčně dominantní matice - Weakly chained diagonally dominant matrix - Wikipedia

Vennův diagram ukazující zadržení slabě zřetězených diagonálně dominantních (WCDD) matic ve srovnání se slabě diagonálně dominantními (WDD) a přísně diagonálně dominantními (SDD) maticemi.

V matematice je slabě zřetězené úhlopříčně dominantní matice jsou rodina nesingulární matice které zahrnují přísně diagonálně dominantní matice.

Definice

Předkola

Říkáme řádek ${ displaystyle i}$ komplexní matice ${ displaystyle A = (a_ {ij})}$ je striktně diagonálně dominantní (SDD), pokud ${ displaystyle | a_ {ii} |> textový styl { sum _ {j neq i}} | a_ {ij} |}$. Říkáme ${ displaystyle A}$ je SDD, pokud jsou všechny jeho řádky SDD. Slabě úhlopříčně dominantní (WDD) je definován pomocí ${ displaystyle geq}$ namísto.

The řízený graf spojené s ${ displaystyle m krát m}$ komplexní matice ${ displaystyle A = (a_ {ij})}$ je dáno vrcholy ${ displaystyle {1, ldots, m }}$ a hrany definované následovně: existuje hrana z ${ displaystyle i rightarrow j}$ kdyby a jen kdyby ${ displaystyle a_ {ij} neq 0}$.

Definice

Složitá čtvercová matice ${ displaystyle A}$ se říká, že je slabě zřetězený diagonálně dominantní (WCDD), pokud

• ${ displaystyle A}$ je WDD a
• pro každý řádek ${ displaystyle i_ {1}}$ to je ne SDD, existuje a Procházka ${ displaystyle i_ {1} rightarrow i_ {2} rightarrow cdots rightarrow i_ {k}}$ v orientovaném grafu ${ displaystyle A}$ končící na řádku SDD ${ displaystyle i_ {k}}$.

Příklad

Směrovaný graf spojený s maticí WCDD v příkladu. První řádek, který je SDD, je zvýrazněn. Všimněte si, že bez ohledu na to, který uzel ${ displaystyle i}$ začneme v, můžeme najít procházku ${ Displaystyle i rightarrow (i-1) rightarrow (i-2) rightarrow cdots rightarrow 1}$.

The ${ displaystyle m krát m}$ matice

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

je WCDD.

Vlastnosti

Nesmyslnost

Matice WCDD je nesmyslná.^[1]

Důkaz:^[2]Nechat ${ displaystyle A = (a_ {ij})}$ být maticí WCDD. Předpokládejme, že existuje nenulová hodnota ${ displaystyle x}$ v nulovém prostoru ${ displaystyle A}$.Ztráta obecnosti, ať ${ displaystyle i_ {1}}$ být takový, že ${ displaystyle | x_ {i_ {1}} | = 1 geq | x_ {j} |}$ pro všechny ${ displaystyle j}$.Od té doby ${ displaystyle A}$ je WCDD, můžeme si vybrat procházku ${ displaystyle i_ {1} rightarrow i_ {2} rightarrow cdots rightarrow i_ {k}}$ končící na řádku SDD ${ displaystyle i_ {k}}$.

Užívání modulů na obou stranách

${ displaystyle -a_ {i_ {1} i_ {1}} x_ {i_ {1}} = součet _ {j neq i_ {1}} a_ {i_ {1} j} x_ {j}}$

a použití výnosů nerovnosti trojúhelníku

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

a tedy řádek ${ displaystyle i_ {1}}$ není SDD. Kromě toho od ${ displaystyle A}$ je WDD, výše uvedený řetězec nerovností platí s rovností tak ${ displaystyle | x_ {j} | = 1}$ kdykoli ${ displaystyle a_ {i_ {1} j} neq 0}$.Proto, ${ displaystyle | x_ {i_ {2}} | = 1}$.Opakování tohoto argumentu s ${ displaystyle i_ {2}}$, ${ displaystyle i_ {3}}$, atd., zjistíme, že ${ displaystyle i_ {k}}$ není SDD, rozpor. ${ displaystyle square}$

Připomínaje, že neredukovatelné matice je ta, jejíž přidružený směrovaný graf je silně propojený, triviální důsledkem výše uvedeného je, že ireducibilně diagonálně dominantní matice (tj. neredukovatelná matice WDD s alespoň jedním řádkem SDD) je nesmyslná.^[3]

Vztah k nesingulárním M-maticím

Následující jsou ekvivalentní:^[4]

• ${ displaystyle A}$ je nesmyslný WDD M-matice.
• ${ displaystyle A}$ je nesmyslný WDD L-matice;
• ${ displaystyle A}$ je WCDD L-matice;

Ve skutečnosti byly WCDD L-matice studovány (autorem) James H. Bramble a B. E. Hubbard) již v roce 1964 v časopiseckém článku^[5] ve kterém se objevují pod alternativním názvem matice pozitivního typu.

Navíc pokud ${ displaystyle A}$ je ${ displaystyle n krát n}$ WCDD L-matice, můžeme její inverzní vazbu svázat takto:^[6]

${ displaystyle left Vert A ^ {- 1} right Vert _ { infty} leq sum _ {i} left [a_ {ii} prod _ {j = 1} ^ {i} ( 1-u_ {j}) right] ^ {- 1}}$ kde ${ displaystyle u_ {i} = { frac {1} { vlevo | a_ {ii} vpravo |}} součet _ {j = i + 1} ^ {n} vlevo | a_ {ij} vpravo |.}$

Všimněte si, že ${ displaystyle u_ {n}}$ je vždy nula a že pravá strana výše uvedeného je ${ displaystyle infty}$ kdykoli jedna nebo více konstant ${ displaystyle u_ {i}}$ je jedna.

Jsou známy přísnější hranice pro inverzi WCDD L-matice.^{[7][8][9][10]}

Aplikace

Kvůli jejich vztahu s M-matice (vidět výše ), Matice WCDD se často objevují v praktických aplikacích. Příklad je uveden níže.

Monotónní numerická schémata

WCDD L-matice vznikají přirozeně z monotónních aproximačních schémat pro parciální diferenciální rovnice.

Zvažte například jednorozměrný Poissonův problém

${ displaystyle u ^ { prime prime} (x) + g (x) = 0}$ pro ${ displaystyle x v (0,1)}$

s Dirichletovy okrajové podmínky ${ displaystyle u (0) = u (1) = 0}$.Letting ${ displaystyle {0, h, 2 h, ldots, 1 }}$ být číselná mřížka (pro některé pozitivní ${ displaystyle h}$ , který rozděluje jednotu), monotónní schéma konečných rozdílů pro Poissonův problém má podobu

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

a

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

Všimněte si, že ${ displaystyle A}$ je WCDD L-matice.

Reference