ECT1303-2015.1-Aula12-Solucao_Sistemas_LinearesIII

Prévia do material em texto

UFRN 
Universidade Federal do Rio Grande do Norte 
Escola de Ciências e Tecnologia 
Solução de Sistemas de 
Equações Lineares 
Parte III: Métodos Iterativos 
ECT1303 – Computação Numérica 
• Manter o telefone celular sempre 
desligado/silencioso quando estiver em 
sala de aula; 
• Nunca atender o celular na sala de aula. 
Objetivos 
Discutir os métodos iterativos de resolução de 
sistemas lineares; 
Saber em que casos eles são melhores que os 
métodos exatos; 
Saber quais suas vantagens e desvantagens. 
Introdução 
Métodos como: 
método de eliminação de Gauss 
método de decomposição LU 
são ditos exatos: obtêm a solução final após um 
número exatos de passos. 
Processos Estacionários 
Um método é iterativo quando fornece uma 
sequência de estimativas da solução, cada uma das 
quais obtida das anteriores pela repetição do mesmo 
tipo de processo. 
Um método iterativo é estacionário se cada 
estimativa é obtida do anterior sempre pelo mesmo 
processo. 
Precisamos sempre saber se a sequência que 
estamos obtendo está convergindo ou não para a 
solução desejada. 
Introdução 
Vantagens dos métodos iterativos: 
São melhores que os exatos em casos onde a matriz 
dos coeficientes é esparsa (muitos elementos iguais a 
zero); 
Utilizam menos memória do computador; 
Podem ser usados para reduzir erros de 
arredondamento proveniente dos métodos exatos, 
ou seja, são mais imunes a erros de arredondamento 
Sob certas condições, podem ser usados para 
resolver um conjunto de equações não-lineares. 
Introdução 
Porém, há também desvantagens: 
Contrariamente aos métodos exatos, não é 
sempre que um método iterativo tem sucesso. 
A convergência dos métodos iterativos acontece 
somente na presença de certas condições. 
Métodos iterativos: como funcionam? 
As equações são escritas na forma explícita: 
 
 
O processo de solução começa com a escolha de valores 
iniciais para as incógnitas. 
Na 1ª iteração, a primeira solução é substituída no lado 
direito das equações, obtendo-se a segunda solução. 
Na 2ª iteração, a segunda solução é substituída de volta 
nas equações, gerando a terceira solução. 
As iterações continuam da mesma forma até convergir 
para a solução real (nem sempre converge!) 
3323213113
2232312122
1131321211
)]([
)]([
)]([
axaxabx
axaxabx
axaxabx



3333232131
2323222121
1313212111
bxaxaxa
bxaxaxa
bxaxaxa



Convergência 
Definição 
Dados uma sequência de vetores x(k) E e uma 
norma sobre E, onde E é um espaço vetorial, 
dizemos que a sequência {x(k)} converge para x  E 
se || x(k) – x || → 0, quando k → ∞. 
i
ni
xx


1
max
Para obtermos a solução com uma determinada precisão 
devemos, durante o processo iterativo, efetuar o seguinte 
teste: 
 
 onde  é uma precisão pré-fixada; x(k) e x(k+1) são duas 
aproximações consecutivas para x. 
Se a condição é satisfeita, então x(k+1) é a solução 
procurada, isto é, tomamos 
Processo de parada 






)1(
)()1(
k
kk
x
xxErro relativo  
Também é possível utilizar o erro absoluto como critério 
de parada: 
 
 
Ou até mesmo utilizar outra norma vetorial qualquer, por 
exemplo, a norma euclidiana: 
 
 
Processo de parada 


 )()1( kk xx
Erro absoluto  

2
)()1( kk xx
Método de Jacobi 
Métodos Iterativos 
Dado o sistema Ax = b, o método de Jacobi consiste na 
determinação de uma sequência de aproximações na 
(k+1)-ésima iteração a partir da k-ésima estimativa 
usando: 
 
 
 
Inicia-se com os valores iniciais quaisquer: 
 
Pode-se assumir que o valor inicial de todas as incógnitas 
seja igual a zero. 
 
 
Método de Jacobi 
nixab
a
x
nj
ij
j
k
jiji
ii
k
i ,...,2,1 
1
1
)(1 




















 




Os valores das incógnitas são atualizados todos de 
uma vez no final de cada iteração. 
É fácil ver que, no método de Jacobi, as equações 
são mudadas simultaneamente usando-se o valor 
mais recente do vetor x, por causa disso esse 
método também é conhecido por Método dos 
Deslocamentos Simultâneos. 
Método de Jacobi 
Resolver o sistema: 
 
 
 
Pelo Método de Jacobi com 
x(0) = (0.7, -1.6, 0.6)t e ε < 10-2. 
 
Obs: neste caso escolhemos 𝑥 0 𝑖 = 𝑏(𝑖)/𝑎(𝑖, 𝑖) 
Qual a diferença de comçar 𝑥 0 = [0 0 … 0]? 
Exemplo 1 
Solução 
Dividindo cada equação pelo correspondente da 
diagonal principal, temos: 
 
 
 
Temos que as iterações são definidas por: 
Solução 
A partir de x(0), obtemos os seguinte valores para x(1) : 
 
 
 
Continuando as iterações, obtemos a tabela: 
Solução 
Desde que: 
 
 
Temos: 
 
 
 
Segue que a solução do sistema com ε < 10-2 é: 
• Exercício: Resolva o seguinte sistema, utilizando 
Jacobi, com erro absoluto ∈= 0,5 e depois calcule o 
resíduo 
 
 
𝑥1 − 0,25𝑥2 − 0,25𝑥3 = 0
−0,25𝑥1 + 𝑥2 − 0,25𝑥4 = 0
−0,25𝑥1 + 𝑥3 − 0,25𝑥4 = 0,25
−0,25𝑥2 + 𝑥4 = 0,25
 
Exercício 
Método de Gauss-Seidel 
Métodos Iterativos 
No método de Gauss-Seidel, valores iniciais também são 
assumidos para as incógnitas: 
 
Pode-se assumir que o valor inicial de todas as incógnitas 
seja igual a zero. 
O método de Gauss-Seidel é fundamentado na simples 
constatação de que o cálculo de necessita dos 
valores de calculados na iteração 
precedente. 
Ora, na iteração k+1, nós já temos em mãos uma melhor 
aproximação de , i.e., 
 
Método de Gauss-Seidel 
1
2
kx
k
n
kk xxx ,...,, 31
1x
1
1
kx
Da mesma forma, no momento cálculo de 
podemos utilizar e que já foram 
calculados. 
De forma geral, para o cálculo de , podemos 
utilizar já calculados na iteração 
atual e da iteração precedente. 
 
Método de Gauss-Seidel 
1
3
kx
1
1
kx 12
kx
1k
ix
1
1
1
2
1
1 ,...,,


 k
i
kk xxx
k
n
k
i
k
i xxx ,...,, 21 
A aplicação do método de Gauss-Seidel, leva à 
fórmula iterativa: 
Método de Gauss-Seidel 


































































1
1
)1(1
1
)(
1
1
)1(1
2
)(
11
11
1
1
1
1,...,2 
1
1
nj
j
k
jnjn
nn
k
n
nj
ij
k
jij
ij
j
k
jiji
ii
k
i
nj
j
k
jj
k
xab
a
x
nixaxab
a
x
xab
a
x
Esse método difere do processo de Jacobi por utilizar 
para o cálculo de uma componente de x(k+1) o valor 
mais recente das demais componentes. 
Por esse motivo, o método de Gauss Seidel é 
conhecido por Método dos Deslocamentos 
Sucessivos. 
Método de Gauss-Seidel 
Exemplo 2 
 Resolver o sistema: 
 
 
 
 pelo método de Gauss-Seidel com ε < 10-2. 
Solução 
Temos que as iterações são definidas por: 
 
 
E a partir de x(0) = (0, 0, 0)t , obtemos para x(1) os 
seguintes valores: 
Solução 
Continuando as iterações obtemos a tabela: 
 
 
 
Temos: 
Solução 
E, portanto, temos: 
 
 
Segue que a solução do sistema para ε < 10-2, é: 
Exercício 
• Resolva o sistema pelo método de Gauss-Seidel com 
∈= 0,22𝑥1 − 𝑥2 = 1
𝑥1 + 2𝑥2 = 3
 
 
Para determinar a solução de um sistema linear por 
métodos iterativos, é preciso transformar o sistema dado 
em um outro sistema onde possa ser definido um processo 
iterativo. 
Seja um sistema linear Ax = b determinado, onde A é uma 
matriz n x n; x e b são vetores n x 1. 
Suponha então que o sistema Ax = b tenha sido 
transformado num sistema equivalente da forma: 
x = Bx + g, 
 de maneira que a solução desse sistema seja também 
solução de Ax = b. 
 
 
Convergência 
*x
Seja uma aproximação inicial para . 
Obtemos as aproximações sucessivas , usando o 
processo iterativo estacionário definido por: 
 
Se a sequência converge para , então coincide 
com a solução . 
Passando-se ao limite ambos os membros da equação 
anterior, obtém-se: 
 
Pela equivalência, é também solução de . 
 
 
 
Convergência 

x(0) *x

x(k )
gxBx kk   )1()( 

x(k) 
*x

Ax  b
gxBx  * *

Ax  b
*x
*x
Prova do Critério Geral da Convergência 
Seja o vetor erro . 
Subtraindo de , obtemos: 
 
 e portanto: 
 
Podemos escrever 
 
E por aplicações sucessivas, temos que: 
 
 
 
 
)()( * kk xxe 

e(k)  B e(k1)

x(k)  B x(k1)  g gxBx  * *
 )1()( * *  kk xxBxx

e(k1)  B e(k2)  e(k)  B2 e(k2)

e(k)  Bk e(0)
erro inicial 
Corolário – Critério Geral da Convergência 
O processo iterativo definido anteriormente é 
convergente se, para alguma norma de matrizes, 
Convergência 

B 1
Prova do Critério Geral da Convergência 
Pelas propriedades de normas de matrizes , segue que: 
 
Portanto: 
 
Vemos, que se então tende a zero. 
 
 
 
 

Bke(0)  B
k
 e(0)

e(k )  B
k
 e(0)

B 1

e(k )
Se para alguma norma, então o processo 
iterativo definido por converge. 

B 1

x(k)  B x(k1)  g
Exemplo 3 
Seja 
 
 
 
Verificar se um sistema Ax = b que tenha a matriz B 
acima como matriz de iteração convergirá para a 
solução. 
 
Solução 
Calculando , obtemos e nada podemos 
concluir. 
Calculando , obtemos e podemos 
agora afirmar que o processo iterativo com essa 
matriz é convergente. 

B
 2,1

B

B
1 19,0
1
B

B

 max
1in
aij
j1
n


B
1
 max
1 jn
aij
i1
n

Critérios de Convergência Jacobi 
Escolhendo as normas e , obtemos condições 
suficientes de convergência para o método de Jacobi. 
O método converge se: 
O critério das linhas for satisfeito: 
 
Ou o critério das colunas for satisfeito: 
onde 
max
1 in
aij
*
j1
j i
n
 1

max
1 jn
aij
*
i1
i j
n
 1

aij
* 
aij
aii
Matrizes de diagonais estritamente dominantes 
Definição 
Uma matriz A tem diagonal estritamente 
dominante se: 

aij
j1
j i
n
  aii , i 1,2,...n
Critérios de Convergência 
Dada a definição anterior, podemos observar que, se a 
matriz for estritamente diagonalmente dominante, 
então o critério das linhas é satisfeito. 
Se dividirmos cada equação pelo correspondente 
elemento da diagonal principal segue que: 
 
Portanto, podemos também verificar a convergência do 
método de Jacobi testando se a matriz dos coeficientes 
tem diagonal estritamente dominante. 
Exemplo 4: Teste de convergência 
Voltemos ao sistema: 
 
 
 
Antes de aplicar o método de Jacobi, devemos testar se temos 
garantia de convergência. 
Nesse caso, verificamos que a matriz dos coeficientes tem 
diagonal estritamente dominante, pois: 
convergência garantida! 
Critérios de Convergência Gauss-Seidel 
No critério geral de convergência, o método de Gauss-
Seidel converge se: 
1. O critério de Sassenfeld for satisfeito: 
 
 onde 

max
1in
i 1
niaa
a
n
ij
ijj
i
j
iji
n
j
j
,...,2 ,
1
*
1
1
*
2
*
11










Critérios de Convergência Gauss-Seidel 
2. O critério das linhas for satisfeito: 
 
 
 ou a matriz dos coeficientes tiver diagonal 
estritamente dominante: 

aij
j1
j i
n
  aii , i 1,2,...n

max
1 in
aij
*
j1
j i
n
 1
Exemplo 5: Teste de convergência 
Voltemos ao sistema: 
 
 
 
Antes de aplicar o método de Gauss-Seidel, devemos testar se 
temos garantia de convergência. 
Como a matriz não tem diagonal estritamente dominante, por 
esse critério nada podemos concluir em relação à convergência 
do processo de Gauss-Seidel. 
Exemplo 5: Teste de convergência 
Dividindo cada equação pelo correspondente elemento da 
diagonal principal obtemos: 
 
 
Vimos que, se a matriz dos coeficientes não tiver diagonal 
estritamente dominante, então o critério das linhas também 
não será satisfeito, como mostrado a seguir: 
Exemplo 5: Teste de convergência 
E portanto, nada podemos concluir em relação à convergência. 
Aplicando o critério de Sassenfeld, temos: 
 
 
 
 
 
Logo, como o critério de Sassenfeld foi satisfeito e o mesmo é 
condição suficiente para convergência, podemos garantir que o 
processo de Gauss-Seidel converge. 
Observações 
1. Para um dado sistema linear, o método de Jacobi 
pode convergir enquanto que o de Gauss-Seidel 
diverge e vice-versa. 
2. Se não for muito menor que 1, a convergência 
pode ser bastante lenta. 
3. A convergência para ambos os métodos não depende 
da solução inicial x(0). 
4. Normalmente, tomamos x(0)=0 para o método de 
Gauss-Seidel e x(0)=b* para o método de Jacobi. 
B
• Verifique a convergência para Jacobi e em seguida 
resolva o seguinte sistema: 
 
 
𝑥1 + 4𝑥2 + 𝑥3 = 10
−6𝑥1 + 2𝑥2 + 𝑥3 = −3
−𝑥1 − 𝑥2 + 3𝑥3= −6
 
 
Atividade 
Solução 
– Teste do critério das linhas 
• Para a primeira linha: 1 > 4+1 ? Não. Falhou! 
– Teste do critério das colunas 
• Para a primeira coluna: 1 > 6/2 + 1/3 ? Não. Falhou! 
– Podemos tentar rearranjar as linhas do sistema: 
 
−6𝑥1 + 2𝑥2 + 𝑥3 = −3
𝑥1 + 4𝑥2 + 𝑥3 = 10
−𝑥1 − 𝑥2 + 3𝑥3= −6
 
– Teste do critério das linhas 
• Para a primeira linha: 6 > 2+1 ? Sim! 
• Para a segunda linha: 4 > 1+1 ? Sim! 
• Para a terceira linha: 3 > 1+1 ? Sim! Passou! 
– Resolver normalmente por Jacobi 
 
 
Atividade 
Usando o método de Jacobi, obter a solução do sistema 
abaixo, com precisão de 3 casas decimais. 
Atividade 
Dado o sistema: 
 
 
 
 
Resolvê-lo pelo método de Gauss-Seidel com ε < 10-2 
 
Atividade 
Comparação entre os métodos 
diretos e iterativos 
• Métodos diretos 
• Recomendados para sistemas de pequeno porte com 
matrizes de coeficiente densas 
• Métodos Iterativos 
• Bastante vatajosos para sistemas de grande porte cuja 
matriz de coeficiente seja esparsa. 
• Necessário verificar condições de convergencia