2^a Questão (2,0 pontos). Seja A in R^n times n. A é dita diagonalmente dominante se
sumsubstackj=1 j neq i^n|ai j|<|ai i|, forall i=1, cdots, n
Mostre que se A é diagonalmente dominante então todo método de ponto fixo converge para a solução do sistema linear A x=b, onde b in R^n é um vetor arbitrário.

Passo 1

O enunciado diz que A=(aij)inR^ntimes n é estritamente diagonalmente dominante se, para todo i=1,dots,n,
sumsubstackj=1 jneq i^nl|aijr|<l|aiir|
Queremos mostrar que, para qualquer decomposição A=M-N com M invertível, a iteração de ponto fixo
x^k+1=H,x^k + c, H=M^-1N,;c=M^-1b,
converge para a solução de Ax=b.

Passo 2

Aplicamos o Teorema do Ponto Fixo de Banach: se phi:R^ntoR^n satisfaz
|phi(x)-phi(y)|<= q,|x-y|forall x,y, q<1
numa norma qualquer, então phi tem único ponto fixo x^* e a iteração x^k+1=phi(x^k) converge para x^*.

Passo 3

Escrevemos o sistema Ax=b na forma de ponto fixo: dado A=M-N com M inversível,
Ax=b ;Long<=ftrightarrow; Mx=Nx+b ;Long<=ftrightarrow; x=M^-1N,x + M^-1b
Logo o operador de iteração é phi(x)=H,x+c, onde H=M^-1N.

Passo 4

Escolhemos a norma infinito em R^n e a matriz associada:
|H|infty = |M^-1N|infty <= |M^-1|infty,|N|infty
No caso clássico de Jacobi, M=D (a matriz diagonal de A) e N=L+U. Então
|H|infty =l|D^-1(L+U)r|infty =max1<= i<= nsumjneq i|aij||aii| <1
pela estrita diagonalmente dominância de A.

Passo 5

Como |H|infty<1, phi(x)=H,x+c é contração e, pelo Teorema de Banach, a sequência x^k+1=phi(x^k) converge para o único ponto fixo, que é a solução de Ax=b. O mesmo raciocínio vale para qualquer outra divisão A=M-N que preserve a diagonalmente dominância de modo a garantir |M^-1N|infty<1.

Resposta

Uma vez que em norma infinito |H|infty<1, toda iteração de ponto fixo x^k+1=H,x^k+c converge linearmente para a solução de Ax=b.

Exercícios relacionados