Método de Gauss-Seidel (II)
Critérios de convergência
Vamos lá?
Em uma aula anterior vimos o método de Gauss-Seidel, uma variação inteligente do método de Jacobi. Porém não ficou claro quando ele era convergente nem por quê. Nesta aula, vamos usar o resultado da aula geral sobre convergência de métodos iterativos para tentar entender o que acontece no caso do método de Gauss-Seidel.
- 1
- 2
O spliting da matriz foi usado para...
Para o sistema linear é correto afirmar que...
Para poder usar o resultado de convergência que deduzimos duas aulas atrás é preciso escrever o método de Gauss-Seidel (GS) no formato do método iterativo geral apresentado naquela aula. Vamos relembrar como é a iteração de GS usando um exemplo.
Considere o sistema linear a seguir
O fato de
Lembrando do resultado de convergência para métodos iterativos estacionários para sistemas lineares, para garantir a convergência do método de GS, basta pedir que
Para o método de Gauss-Jacobi foi simples relacionar o valor de
Critério de Sassenfeld: Seja
Este critério sai de analisar a norma infinito de
Um corolário deste resultado é que sistemas lineares com matrizes diagonalmente dominantes por linha também têm a convergência assegurada para as sequências geradas pelo método de Gauss-Seidel.
Considere um exemplo no Octave.
A = [5 2 -1; 4 6 3; 0 -2 4]; b = [-10; 4; 6];
A matriz
n = rows(A); beta(1,1) = sum(abs(A(1,2:n))) / abs(A(1,1)); for i=2:n; beta(i,1) = (abs(A(i,1:i-1))*beta(1:i-1) + sum(abs(A(i,i+1:n))))/abs(A(i,i)); endfor beta beta = 0.60000 0.90000 0.45000
Como o valor máximo do vetor
D = diag(diag(A)) # Diagonal de A D = Diagonal Matrix 5 0 0 0 6 0 0 0 4 L = tril(A)-D; # Porção triangular inferior de A U = triu(A)-D; # Porção triangular superior de A BJ = -inv(D)*(L+U); # Matriz de iteração do método de Jacobi BGS = -inv(L+D)*U; # Matriz de iteração do método de Gauss-Seidel
Acima, construímos as matrizes de iteração do método de Jacobi e do método de Gauss-Seidel. Estamos fazendo isto apenas para fins didáticos. Como comentamos acima, a construção explícita dessas matrizes não é necessária para a aplicação desses métodos.
norm(BJ,inf) ans = 1.1667 norm(BGS,inf) ans = 0.90000
No bloco acima, vemos que
Itere o método de Gauss-Seidel partindo do vetor nulo.
x = [0;0;0]; x1 = inv(D+L) * (b-U*x); # 1ª iteração de Gauss-Seidel norm(x1-x,inf) # norma do passo ans = 2.5000 x = x1; x1 = inv(D+L) * (b-U*x); # 2ª iteração de Gauss-Seidel norm(x1-x,inf) # norma do passo ans = 1.0500 x = x1; x1 = inv(D+L) * (b-U*x); # 3ª iteração de Gauss-Seidel norm(x1-x,inf) # norma do passo ans = 0.31500 x = x1; x1 = inv(D+L) * (b-U*x); # 4ª iteração de Gauss-Seidel norm(x1-x,inf) # norma do passo ans = 0.015750 x1 # Aproximação corrente x1 = -2.0008 0.9999 1.9999
Neste exemplo, após o cálculo de cada novo iterando foi sendo computado
1. Escreva um algoritmo para o método de Gauss-Seidel e conte o número de operações realizadas em cada iteração do método (não esqueça de computar as operações necessárias para a verificação do critério de parada). Implemente seu algoritmo em Octave.
2. Prove que se uma matriz é diagonalmente dominante por linhas, então ela também satisfaz o critério de Sassenfeld.