Métodos iterativos para solução de sistemas lineares

Segundo Trabalho de Cálculo Numérico I – SME-200

“Métodos Iterativos para solução de Sistemas Lineares”
Gauss-Siedel SOR Gradientes Conjugados

Prof. Luis Gustavo Nonato Alunos: Rubens Abranches Filho Laura Blanco 5713752 4458450

USP-2012

Neste trabalho serão apresentados e implementados computacionalmente, utilizando o programa Matlab, três métodos iterativos para solução de sistemas lineares: método SOR, método de Gauss-Seidel e método dos Gradientes Conjugados. Com base nos resultados obtidos o método dos Gradientes Conjugados mostrou melhor convergência dentre os três analisados. 1. Introdução Um sistema de equações lineares Ax = b pode ser resolvido por um processo onde, a partir de um vetor inicial x0, uma seqüência de vetores {x1, x2, x3, ..., xk, …} é gerada de modo a convergir para a solução x do sistema. Nesse processo é realizada uma série de operações repetidas, e por isso tal processo é denominado iterativo. Dado o sistema linear: Ax = b; n bi =

∑ Ajjxj j=1 i = 1, 2, 3, …, m;

(1.1)

Onde, b é um vetor de constantes de ordem m, A é a matriz de coeficientes de tamanho mXn e x é o vetor solução de ordem n. Sendo A uma matriz quadrada nXn, isolando-se o i-ésimo valor de x para cada linha i do sistema, obtém-se: n Aiixi = bi - ∑ Ajjxj j=1 e j≠i n

i = 1, 2, 3, …, m; i = 1, 2, 3, …, m;

(1.2) (1.3)

xi = bi - 1 ∑ Ajjxj Aii Aii j=1 e j≠i

No processo iterativo a eq. (1.3) pode ser representada conforme eq. (1.4). Xk-1 = Mxk + c; (1.4) Onde, M é a matriz de iteração e c é um vetor constante. O processo iterativo é dito estacionário se M não for alterada durante o processo. 2. Condição de Convergência A sequência de vetores solução {x1, x2, x3, ..., xk, …} converge para a solução do sistema linear Ax = b, quando satisfeito o seguinte teorema: Teorema 1.1: O método iterativo da eq. (1.4) converge com qualquer valor inicial x 0 se e somente se, ρ(M) ∑ |aij|; j=1 e j≠i

i = 1, 2, 3, …, n;

(2.1)

Pelos Teoremas