Konvergentní matice - Convergent matrix

v numerická lineární algebra, a konvergentní matice je matice, která konverguje k nulová matice pod maticová umocňování.

Pozadí

Když postupné pravomoci a matice T se stanou malými (tj. když všechny položky z T přiblížit se nule, po navýšení T matice) T konverguje k nulové matici. A pravidelné rozdělení a ne singulární matice A má za následek konvergentní matici T. Semi-konvergentní rozdělení matice A vede k semi-konvergentní matici T. Generál iterační metoda konverguje pro každý počáteční vektor, pokud T je konvergentní a za určitých podmínek, pokud T je semi-konvergentní.

Definice

Říkáme n × n matice T A konvergentní matice -li

${ displaystyle lim _ {k to infty} ( mathbf {T} ^ {k}) _ {ij} = 0,}$

(1)

pro každého i = 1, 2, ..., n a j = 1, 2, ..., n.^[1][2][3]

Příklad

Nechat

${ displaystyle { begin {aligned} & mathbf {T} = { begin {pmatrix} { frac {1} {4}} & { frac {1} {2}} [4pt] 0 & { frac {1} {4}} end {pmatrix}}. end {zarovnáno}}}$

Výpočet postupných pravomocí T, získáváme

${ displaystyle { begin {aligned} & mathbf {T} ^ {2} = { begin {pmatrix} { frac {1} {16}} & { frac {1} {4}} [ 4pt] 0 & { frac {1} {16}} end {pmatrix}}, quad mathbf {T} ^ {3} = { begin {pmatrix} { frac {1} {64}} & { frac {3} {32}} [4pt] 0 & { frac {1} {64}} end {pmatrix}}, quad mathbf {T} ^ {4} = { begin {pmatrix} { frac {1} {256}} & { frac {1} {32}} [4pt] 0 & { frac {1} {256}} end {pmatrix}}, quad mathbf {T } ^ {5} = { begin {pmatrix} { frac {1} {1024}} & { frac {5} {512}} [4pt] 0 & { frac {1} {1024}} konec {pmatrix}}, end {zarovnáno}}}$

${ displaystyle { begin {aligned} mathbf {T} ^ {6} = { begin {pmatrix} { frac {1} {4096}} & { frac {3} {1024}} [4 b. ] 0 & { frac {1} {4096}} end {pmatrix}}, end {zarovnáno}}}$

a obecně

${ displaystyle { begin {aligned} mathbf {T} ^ {k} = { begin {pmatrix} ({ frac {1} {4}}) ^ {k} & { frac {k} {2 ^ {2k-1}}} [4pt] 0 & ({ frac {1} {4}}) ^ {k} end {pmatrix}}. End {zarovnáno}}}$

Od té doby

${ displaystyle lim _ {k to infty} left ({ frac {1} {4}} right) ^ {k} = 0}$

a

${ displaystyle lim _ {k to infty} { frac {k} {2 ^ {2k-1}}} = 0,}$

T je konvergentní matice. Všimněte si, že ρ(T) = 1/4, kde ρ(T) představuje spektrální poloměr z T, od té doby 1/4 je jediný vlastní číslo z T.

Charakterizace

Nechat T být n × n matice. Následující vlastnosti jsou ekvivalentní k T být konvergentní maticí:

1. ${ displaystyle lim _ {k to infty} | mathbf {T} ^ {k} | = 0,}$ pro nějakou přirozenou normu;
2. ${ displaystyle lim _ {k to infty} | mathbf {T} ^ {k} | = 0,}$ pro všechny přirozené normy;
3. ${ displaystyle rho ( mathbf {T}) <1}$;
4. ${ displaystyle lim _ {k to infty} mathbf {T} ^ {k} mathbf {x} = mathbf {0},}$ pro každého X.^[4][5][6][7]

Iterační metody

Generál iterační metoda zahrnuje proces, který převádí soustava lineárních rovnic

${ displaystyle mathbf {Axe} = mathbf {b}}$

(2)

do ekvivalentního systému formuláře

${ displaystyle mathbf {x} = mathbf {Tx} + mathbf {c}}$

(3)

pro nějakou matici T a vektor C. Po počátečním vektoru X⁽⁰⁾ je vybrána, sekvence přibližných vektorů řešení je generována výpočtem

${ displaystyle mathbf {x} ^ {(k + 1)} = mathbf {Tx} ^ {(k)} + mathbf {c}}$

(4)

pro každého k ≥ 0.^[8][9] Pro libovolný počáteční vektor X⁽⁰⁾ ∈ ${ displaystyle mathbb {R} ^ {n}}$, sekvence ${ displaystyle lbrace mathbf {x} ^ { vlevo (k vpravo)} rbrace _ {k = 0} ^ { infty}}$ definován (4), pro každého k ≥ 0 a C ≠ 0, konverguje k jedinečnému řešení (3) právě tehdy ρ(T) <1, to znamená, T je konvergentní matice.^[10][11]

Pravidelné rozdělení

A rozdělení matice je výraz, který představuje danou matici jako součet nebo rozdíl matic. V soustavě lineárních rovnic (2) výše, s A ne singulární matice A lze rozdělit, tj. zapsat jako rozdíl

${ displaystyle mathbf {A} = mathbf {B} - mathbf {C}}$

(5)

aby (2) lze přepsat jako (4) výše. Výraz (5) je pravidelné rozdělení A kdyby a jen kdyby B⁻¹ ≥ 0 a C ≥ 0, to znamená, B⁻¹ a C mít pouze nezáporné položky. Pokud rozdělení5) je pravidelné rozdělení matice A a A⁻¹ ≥ 0, pak ρ(T) <1 a T je konvergentní matice. Proto metoda (4) konverguje.^[12][13]

Semi-konvergentní matice

Říkáme n × n matice T A semi-konvergentní matice pokud je limit

${ displaystyle lim _ {k to infty} mathbf {T} ^ {k}}$

(6)

existuje.^[14] Li A je možná singulární, ale (2) je konzistentní, to znamená, b je v rozmezí A, pak posloupnost definovaná (4) konverguje k řešení (2) pro každého X⁽⁰⁾ ∈ ${ displaystyle mathbb {R} ^ {n}}$ kdyby a jen kdyby T je semi-konvergentní. V tomto případě je rozdělení (5) se nazývá a semi-konvergentní rozdělení z A.^[15]

Viz také

• Gauss – Seidelova metoda
• Jacobiho metoda
• Seznam matic
• Nilpotentní matice
• Postupná nadměrná relaxace

Poznámky

Reference

• Burden, Richard L .; Faires, J. Douglas (1993), Numerická analýza (5. vydání), Boston: Prindle, Weber a Schmidt, ISBN  0-534-93219-3.
• Isaacson, Eugene; Keller, Herbert Bishop (1994), Analýza numerických metod, New York: Doveru, ISBN  0-486-68029-0.
• Carl D. Meyer, Jr.; R. J. Plemmons (září 1977). „Konvergentní síly matice s aplikacemi iteračních metod pro singulární lineární systémy“. Časopis SIAM o numerické analýze. 14 (4): 699–705. doi:10.1137/0714047.
• Varga, Richard S. (1960). "Faktorizace a normalizované iterační metody". V Langer, Rudolph E. (ed.). Hraniční problémy v diferenciálních rovnicích. Madison: University of Wisconsin Press. s. 121–142. LCCN  60-60003.
• Varga, Richard S. (1962), Iterativní analýza matice, New Jersey: Prentice – Hall, LCCN  62-21277.