ECT1303-2013.2-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; 
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
xx
Erro relativo ⇒ 
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: 
 
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. 
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 ∈= 0,5 e depois calcule o resíduo 
 
� �� − 0,25�� − 0,25�� = 0−0,25�� + �� − 0,25�� = 0−0,25�� + �� − 0,25�� = 0,25−0,25�� + �� = 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,2 
 �2�� − �� = 1�� + 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 
*xSeja 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
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 
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 
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,01 <=B
B
∞
=max
1≤ i≤n
aij
j=1
n
∑ B 1 =max1≤ j≤n aij
i=1
n
∑
Convergência do Método de Jacobi 
O método de Jacobi pode ser descrito sob a forma 
matricial: 
Para isto, decompomos a matriz A na forma: 
A = L + D + R 
 onde 
L = 
D = 
R = 
gxBx kk += − )1()( 
Convergência do Método de Jacobi 
Assim, o sistema Ax = b, se torna: 
(D+L+R)x = b 
ou ainda: 
Dx = -(L+R)x + b 
e finalmente : 
x = -D-1(L+R)x + D-1b 
que está na forma do processo iterativo com: 
B = -D-1(L+R) e g = D-1b. 
Logo, o método de Jacobi pode ser escrito como: 
x(k+1) = −D−1(L + R)x(k ) + D−1b
Convergência do Método de Jacobi 
Supondo det(D) ≠ 0, temos aii ≠ 0 para i=1,...n. 
Podemos, então, antes de decompor a matriz A, dividir 
cada equação pelo elemento correspondente da 
diagonal principal, resultando assim: 
A* = L* + I + R* 
Assim, o método de Jacobi pode ser descrito como: 
x(k+1) = −(L*+R*)x(k ) + b*
Critérios de Convergência 
Fazendo B = -(L*+R*) e 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! 
Convergência do Método de Gauss-Seidel 
Como para o método de Jacobi, suponha que o sistema 
linear Ax = b seja escrito na forma: 
(L* + I + R*) x = b* 
Transformamos esse sistema como segue: 
(L* + I)x = -R*x + b* 
x = -(L* + I)-1R*x + (L* + I)-1b* 
 que está na forma do processo iterativo definido 
anteriormente com: 
B = -(L*+I) -1R* e g = (L*+I) -1b. 
 
Convergência do Método de Gauss-Seidel 
O método de Gauss-Seidel é definido pelo seguinte 
processo iterativo: 
 
Multiplicando ambos os lados por (L* + I), segue que: 
x
(k+1)
= −(L *+I)−1R* x(k ) + (L *+I)−1b*
(L *+I)x(k+1) = −R* x(k ) + b*
x(k+1) = −L* x(k+1) − R* x(k ) + b*
Critérios de Convergência 
Fazendo B = -(L*+I)-1R* 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
β1 = aij*
j= 2
n
∑
βi = aij*
j=1
i−1
∑ β j + aij*
j= i+1
n
∑ , i = 2,...,n
Critérios de Convergência 
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 e em seguida resolva o 
seguinte sistema utilizando Gauss-Seidel 
 
� �� + 4�� + �� = 10−6�� + 2�� + �� = −3−�� − �� + 3��= −6 
 
Atividade 
Solução 
– Teste do critério das linhas 
• Para a primeira linha: 1 > 4+1 ? Não. Falhou! 
– Sassenfeld 
• Para a prmeira linha: 1 > 4+1 ? Não. Falhou! 
– Podemos tentar rearranjar as linhas do sistema: 
�−6�� + 2�� + �� = −3�� + 4�� + �� = 10−�� − �� + 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 Gauss-Seidel 
 
 
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