Matriz convergente - Convergent matrix

Na álgebra linear numérica , uma matriz convergente é uma matriz que converge para a matriz zero sob a exponenciação da matriz .

Fundo

Quando as potências sucessivas de uma matriz T tornam-se pequenas (isto é, quando todas as entradas de T se aproximam de zero, ao elevar T a potências sucessivas), a matriz T converge para a matriz zero. Uma divisão normal de um não-singulares matriz A resulta em uma matriz convergente T . Uma divisão semi-convergente de uma matriz de um resultado em uma matriz semi-convergente T . Um método iterativo geral converge para cada vetor inicial se T for convergente, e sob certas condições se T for semi-convergente.

Definição

Chamamos um n × n matriz T uma convergente matriz se

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

( 1 )

para cada i = 1, 2, ..., n e j = 1, 2, ..., n .

Exemplo

Deixar

${\ displaystyle {\ begin {align} & \ mathbf {T} = {\ begin {pmatrix} {\ frac {1} {4}} & {\ frac {1} {2}} \\ [4pt] 0 & { \ frac {1} {4}} \ end {pmatriz}}. \ end {alinhado}}}$

Calculando potências sucessivas de T , obtemos

${\ displaystyle {\ begin {align} & \ 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}} \ end {pmatrix}}, \ end {alinhado}}}$

${\ displaystyle {\ begin {align} \ mathbf {T} ^ {6} = {\ begin {pmatrix} {\ frac {1} {4096}} & {\ frac {3} {1024}} \\ [4pt ] 0 & {\ frac {1} {4096}} \ end {pmatrix}}, \ end {alinhado}}}$

e, em geral,

${\ displaystyle {\ begin {alinhados} \ mathbf {T} ^ {k} = {\ begin {pmatrix} ({\ frac {1} {4}}) ^ {k} & {\ frac {k} {2 ^ {2k-1}}} \\ [4pt] 0 & ({\ frac {1} {4}}) ^ {k} \ end {pmatriz}}. \ End {alinhado}}}$

Desde a

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

e

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

T é uma matriz convergente. Observe que ρ ( T ) = 1/4, onde ρ ( T ) representa o raio espectral de T , uma vez que1/4é o único autovalor de T .

Caracterizações

Deixe- T ser um n × n matriz. As seguintes propriedades são equivalentes a T sendo uma matriz convergente:

1. ${\ displaystyle \ lim _ {k \ to \ infty} \ | \ mathbf {T} ^ {k} \ | = 0,}$ por alguma norma natural;
2. ${\ displaystyle \ lim _ {k \ to \ infty} \ | \ mathbf {T} ^ {k} \ | = 0,}$ para todas as normas naturais;
3. ${\ displaystyle \ rho (\ mathbf {T}) <1}$;
4. ${\ displaystyle \ lim _ {k \ to \ infty} \ mathbf {T} ^ {k} \ mathbf {x} = \ mathbf {0},}$para cada x .

Métodos iterativos

Um método iterativo geral envolve um processo que converte o sistema de equações lineares

${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$

( 2 )

em um sistema equivalente do formulário

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

( 3 )

para alguma matriz T e vetor c . Depois que o vetor inicial x ⁽⁰⁾ é selecionado, a sequência de vetores de solução aproximados é gerada pela computação

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

( 4 )

para cada k ≥ 0. Para qualquer vetor inicial x ⁽⁰⁾ ∈ , a sequência definida por ( 4 ), para cada k ≥ 0 e c ≠ 0, converge para a solução única de ( 3 ) se e somente se ρ ( T ) <1, ou seja, T é uma matriz convergente. ${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle \ lbrace \ mathbf {x} ^ {\ left (k \ right)} \ rbrace _ {k = 0} ^ {\ infty}}$

Divisão regular

Uma divisão de matriz é uma expressão que representa uma dada matriz como uma soma ou diferença de matrizes. No sistema de equações lineares ( 2 ) acima, com A não singular, a matriz A pode ser dividida, ou seja, escrita como uma diferença

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

( 5 )

de modo que ( 2 ) pode ser reescrito como ( 4 ) acima. A expressão ( 5 ) é uma divisão regular de A se e somente se B ⁻¹ ≥ 0 e C ≥ 0 , ou seja, B ⁻¹ e C têm apenas entradas não negativas. Se a divisão ( 5 ) é uma divisão regular da matriz A e A ⁻¹ ≥ 0 , então ρ ( T ) <1 e T é uma matriz convergente. Portanto, o método ( 4 ) converge.

Matriz semi-convergente

Chamamos um n × n matriz T uma matriz semi-convergente se o limite

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

( 6 )

existe. Se A é possivelmente singular, mas ( 2 ) é consistente, ou seja, b está na faixa de A , então a sequência definida por ( 4 ) converge para uma solução para ( 2 ) para cada x ⁽⁰⁾ ∈ se e somente se T é semi-convergente. Neste caso, o corte ( 5 ) é chamado uma divisão semi-convergente de Uma . ${\ displaystyle \ mathbb {R} ^ {n}}$

Veja também

• Método Gauss-Seidel
• Método Jacobi
• Lista de matrizes
• Matriz nilpotente
• Super-relaxamento sucessivo

Notas

Referências

• Burden, Richard L .; Faires, J. Douglas (1993), Numerical Analysis (5ª ed.), Boston: Prindle, Weber e Schmidt , ISBN 0-534-93219-3.
• Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods , Nova York: Dover , ISBN 0-486-68029-0.
• Carl D. Meyer, Jr .; RJ Plemmons (setembro de 1977). "Poderes convergentes de uma matriz com aplicações a métodos iterativos para sistemas lineares singulares". SIAM Journal on Numerical Analysis . 14 (4): 699–705. doi : 10.1137 / 0714047 .
• Varga, Richard S. (1960). "Fatoração e Métodos Iterativos Normalizados". Em Langer, Rudolph E. (ed.). Problemas de limite em equações diferenciais . Madison: University of Wisconsin Press . pp. 121–142. LCCN  60-60003 .
• Varga, Richard S. (1962), Matrix Iterative Analysis , New Jersey: Prentice – Hall , LCCN  62-21277.