13 Sistemas Lineares Parte3

Prévia do material em texto

CÁLCULO NUMÉRICO 
Profa. Dra. Yara de Souza Tadano yaratadano@utfpr.edu.br 
Aula 13 
Sistemas de Equações Lineares – Parte 3 04/2014 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 3/44 
MÉTODOS 
ITERATIVOS 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 4/44 
MOTIVAÇÃO 
¨  Os métodos iterativos ou de aproximação fornecem uma 
alternativa aos métodos de eliminação vistos. 
¨  Eles utilizam menos memória dos computadores; 
¨  Podem reduzir os erros de arredondamento na solução 
obtida por métodos exatos; 
¨  Em alguns casos, podem ser aplicados para resolver 
conjuntos de equações não-lineares; 
¨  No caso da matriz dos coeficientes ser esparsa, darão boas 
aproximações. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 5/44 
¨  Os método iterativos são semelhantes às técnicas de 
obtenção de raízes de uma única equação. 
¨  Consistem em escolher um valor e, então, usar um método 
sistemático para obter uma estimativa refinada da raiz. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 6/44 
MÉTODO DE 
GAUSS-SEIDEL 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 7/44 
MÉTODO DE GAUSS-SEIDEL 
¨  Este é o método iterativo mais comumente usado. 
¨  Vamos supor, por simplicidade, um sistema de 3 equações e 
3 incógnitas: 
E1 : a11x1 + a12x2 + a13x3 = b1
E2 : a21x1 + a22x2 + a23x3 = b2
E3 : a31x1 + a32x2 + a33x3 = b3
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 8/44 
MÉTODO DE GAUSS-SEIDEL 
¨  Se os elementos da diagonal forem todos não-nulos, é 
possível isolar x1 em E1; x2 em E2 e x3 em E3; 
x1 =
b1 − a12x2 − a13x3
a11
x2 =
b2 − a21x1 − a23x3
a22
x3 =
b3 − a31x1 − a32x2
a33
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 9/44 
MÉTODO DE GAUSS-SEIDEL 
¨  Podemos, então, escolher aproximações iniciais para os x’s 
e resolver estas equações. 
¨  Uma forma simples é supor que os valores de x são todos 
nulos. 
¨  Estes zeros são usados para calcular um novo valor para: 
 
 
 
¨  Então, substitui-se este novo x1 junto com x3 = 0, para obter 
um novo x2, e repete-se o processo para calcular uma nova 
estimativa para x3. 
x1 =
b1
a11
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 10/44 
MÉTODO DE GAUSS-SEIDEL 
¨  Em seguida, volta-se para a primeira equação e todo o 
processo é repetido até que a solução convirja para valores 
suficientemente próximos dos valores verdadeiros. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 11/44 
Critério de Parada 
¨  Como saber se os valores estão próximos dos valores 
verdadeiros? 
Para todo i, onde j e j – 1 representam a iteração atual e a 
anterior. 
εa,i =
xij − xij−1
xij
⋅100%< εs
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 12/44 
Exemplo 1 
¨  Considere o sistema: 
¨  A solução verdadeira é: 
¨  Use o Método de Gauss-Seidel para obter a solução 
aproximada com 
3x1 − 0,1x2 − 0,2x3 = 7,85
0,1x1 + 7x2 − 0,3x3 = −19,3
0,3x1 − 0,2x2 +10x3 = 71, 4
"
#
$$
%
$
$
x1 = 3, x2 = −2,5, x3 = 7
εs = 0,01%
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 13/44 
Exemplo 1 
Iteração (j) x1(j) x2(j) x3(j) 
1 2,616667 -2,794524 7,005610 
2 2,990557 -2,499625 7,000291 
3 3,166674 -2,502369 6,994952 
4 3,166409 -2,502594 6,994956 
|εt| iteração 4 5,55% 0,10% 0,007% 
|εa| iteração 4 0,008% 0,009% 0,00006% 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 14/44 
Algoritmo do método de Gauss-Seidel 
ENTRADA: A (matriz n×n com ajj ≠ 0, j = 1, ..., n), b, aproximação 
inicial x(0), precisão ε, número máximo de iterações N. 
SAÍDA: solução aproximada x(m) = [xj(m)] ou mensagem de falha. 
Passo 1: Para m = 0, ..., N – 1, faça: 
 Passo 2: Para j = 1, ..., n, faça: 
 
 
 
 
 FIM Passo 2 
 
x jm+1( ) =
1
ajj
bj − ajkxkm+1( )
k=1
j−1
∑ − ajkxkm( )
k= j+1
n
∑
#
$
%%
&
'
((
novos antigos 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 15/44 
Algoritmo do método de Gauss-Seidel 
 
 Passo 3: Se , então: 
 
 SAÍDA: x(m+1) 
 PARE (Procedimento concluído com sucesso). 
FIM Passo 1 
 
SAÍDA: 
. 
PARE (Procedimento concluído sem sucesso). 
 
máx
j
x jm+1( ) − x jm( ) < ε
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 16/44 
¨  À medida que cada novo valor de x é calculado pelo método 
de Gauss-Seidel, ele é imediatamente usado na próxima 
equação. 
¨  Assim, se a solução estiver convergindo, a melhor estimativa 
disponível será empregada. 
Uma abordagem alternativa é dada pelo 
 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 17/44 
MÉTODO DE 
GAUSS-JACOBI 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 18/44 
Método de Gauss-Jacobi 
¨  Neste método, em vez de usar os últimos x’s disponíveis, 
esta técnica usa as equações: 
x1 =
b1 − a12x2 − a13x3
a11
x2 =
b2 − a21x1 − a23x3
a22
x3 =
b3 − a31x1 − a32x2
a33
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 19/44 
Método de Gauss-Jacobi 
¨  Para calcular um conjunto de novos x’s com base no 
conjunto de antigos x’s. 
Método de 
Gauss-Seidel 
Método de 
Gauss-Jacobi 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 20/44 
CRITÉRIOS DE 
CONVERGÊNCIA 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 21/44 
Critérios de convergência 
¨  Nos métodos iterativos são necessários os critérios que 
garantam a convergência: 
¤  Critério das linhas; 
¤  Critério de Sassenfeld. 
¨  Estes critérios são suficientes, mas não necessários para a 
convergência. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 22/44 
Critério das Linhas 
¨  Dado o sistema Ax = b, seja: 
¨  Se , então os métodos de 
geram uma sequência {x(k)} 
convergente para a solução do sistema, independente da 
escolha de x(0). 
αk = akj
j=1
j≠k
n
∑
#
$
%
%
%
&
'
(
(
(
akk
α =máx
1≤k≤n
αk <1
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 23/44 
Exemplo 2 
¨  Considere o sistema do Exemplo 1: 
¨  Vamos aplicar o critério das linhas para verificar a 
convergência. 
3x1 − 0,1x2 − 0,2x3 = 7,85
0,1x1 + 7x2 − 0,3x3 = −19,3
0,3x1 − 0,2x2 +10x3 = 71, 4
"
#
$$
%
$
$
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 24/44 
Critério de Sassenfeld 
¨  Sejam: 
e 
β1 =
a1 j
a11j=2
n
∑
βi =
aij β j
j=1
i−1
∑ + aij
j=i+1
n
∑
#
$
%
%
&
'
(
(
aii
,
=
ai1 β1 + ai2 β2 +!+ aii−1 βi−1 + aii+1 +!+ ain
aii
=
a12 + a13 +!+ a1n
a11
i = 2,3,!,n
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 25/44 
Critério de Sassenfeld 
¨  Seja: 
¨  Se β < 1, o gera uma 
sequência convergente para qualquer x (0). 
¨  Quanto menor β, mais rápida a convergência. 
β =máx
1≤i≤n
βi{ }
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 26/44 
Exemplo 3 
¨  Seja o sistema: 
¨  Verifique se este sistema convergirá ao aplicarmos o Método 
de Gauss-Seidel. 
3x1 + x3 = 3
x1 − x2 =1
3x1 + x2 + 2x3 = 9
"
#
$$
%
$
$
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 27/44 
Exemplo 4 
¨  Para o sistema linear: 
O Método de Gauss-Jacobi gera uma sequência convergente 
para a soluçãoexata: 
 
 
 
 VERIFIQUE!!!!!! 
x1 + x2 = 3
x1 −3x2 = −3
"
#
$
x =
32
32
!
"
#
#
#
$
%
&
&
&
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 28/44 
Exemplo 4 
¨  Aplique o critério das linhas para verificar se ele é satisfeito 
para este sistema. 
¨  Vimos que α1 = 1. Isto mostra que, o critério das linhas é 
uma condução , mas para a 
convergência dos Métodos de Gauss-Seidel e Gauss Jacobi. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 29/44 
Exemplo 5 
¨  Para o sistema linear: 
¨  Veremos que o critério das linhas não é satisfeito, porém 
uma permutação de equações faz com que o critério seja 
satisfeito. 
x1 +3x2 + x3 = −2
5x1 + 2x2 + 2x3 = 3
6x2 +8x3 = −6
"
#
$$
%
$
$
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 30/44 
Exemplo 5 
¨  Como o critério das linhas é satisfeito quando fazemos a 
permutação entre as equações 1 e 2, é conveniente 
aplicarmos o a esta nova 
disposição do sistema, pois desta forma a convergência está 
assegurada. 
¨  Podemos, então, concluir que sempre que o critério das 
linhas não for satisfeito, devemos tentar uma permutação 
de linhas e/ou colunas de forma a obtermos uma disposição 
para a qual a matriz dos coeficientes satisfaça o critério das 
linhas. 
¨  No entanto, nem sempre é possível obter tal disposição. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 31/44 
¨  Em relação ao , podemos 
fazer permutações nas linhas e colunas para encontrar uma 
disposição que satisfaça o critério das linhas ou o critério 
de Sassenfeld. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 32/44 
Exemplo 6 
¨  Seja o sistema linear: 
¨  Verifique se o critério de Sassenfeld pode ser aplicado à este 
sistema. Se não, faça as permutações necessárias para que o 
critério seja satisfeito. 
2x1 + x2 +3x3 = 9
−x2 + x3 =1
x1 + 3x3 = 3
"
#
$$
%
$
$
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 33/44 
COMPARAÇÃO 
ENTRE OS MÉTODOS 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 34/44 
Convergência 
¨  Métodos Diretos 
¨  Métodos Iterativos 
Convergência assegurada 
apenas sob determinadas 
condições. 
Convergência garantida para 
qualquer sistema não-singular 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 35/44 
Esparsidade 
¨  Métodos Diretos 
¨  Métodos Iterativos 
Principal vantagem é não 
alterar a estrutura da matriz 
A dos coeficientes, então, 
neste caso é muitas vezes 
preferível 
Durante o processo de 
eliminação podem surgir 
elementos não-nulos em 
posições aij que originalmente 
eram nulas. 
Aula 12 – Sistemas de Equações Lineares – Parte 3 
Cálculo Numérico 36/44 
Erros de Arredondamento 
 
¨  Métodos Diretos 
 
¨  Métodos Iterativos 
Somente os erros cometidos 
na última iteração afetam a 
solução. 
Sérios problemas com erros de 
arredondamento, para amenizar 
usamos técnicas de pivoteamento 
Erros cometidos nas iterações anteriores não 
levarão à divergência do processo, nem à 
convergência a um outro vetor que não a solução