View
6
Download
0
Category
Preview:
Citation preview
Sistemas de Equações
Métodos Iterativos
Computação – 2º Semestre 2016/2017
Sistemas de Equações Lineares
Forma geral:
em que x1,…, xn são as incógnitas,
a11,…, ann são os coeficientes (constantes)
b1,…, bn são constantes
n é o número de equações e incógnitas
Forma matricial:
em que
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
2211
22222121
11212111
bAx
nnnn
n
n
aaa
aaa
aaa
A
21
22221
11211
nx
x
x
x2
1
nb
b
b
b2
1
24 Abril 2017 Sistemas de Equações - Métodos Iterativos
Métodos Numéricos
Métodos Directos:
Exemplos: Regra de Cramer, Eliminação de Gauss
Teoricamente permitem calcular soluções exactas usando um
número finito de operações aritméticas elementares.
Na prática, devido aos erros de arredondamento, cancelamento subtractivo,…, calculam apenas soluções aproximadas.
Métodos Iterativos:
Exemplos: Método de Gauss-Seidel, Método de Jacobi
A solução é definida como um limite de uma sucessão (infinita) de vectores
Na prática, calcula-se apenas um número finito de vectores da sucessão, isto é, calcula-se um número finito de iterações.
3Sistemas de Equações - Métodos Iterativos4 Abril 2017
Métodos Iterativos
Os Métodos Directos estão sujeitos a erros de
arredondamento
Os Métodos Iterativos permitem controlar os erros das
aproximações
Em determinados problemas de ciência e engenharia o
conhecimento do domínio permite boas estimativa iniciais
4Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método das Substituições Sucessivas
Rescrever a equação f(x)=0 de modo a que x esteja no lado
esquerdo da equação:
x=g(x)
é sempre possível!
se não se conseguir resolver f(x)=0 em ordem a x, então basta
somar x a ambos os lados da equação obtendo-se x=g(x)=f(x)+x
Usar a nova função g para estimar o novo valor de x:
xi+1=g(xi)
O erro aproximado é dado por:
5Raízes de Equações não Lineares - Métodos Abertos
%100 1
1
i
iia
x
xx
21 Março 2017
Método de Gauss-Seidel
É o método iterativo mais utilizado para a resolução de
sistemas de equações lineares [A]{x}={b}.
Resolve cada equação em ordem a uma variável, e usa esse
valor nas equações seguintes.
Exemplo de um sistema de 3x3 com os coeficientes da
diagonal diferentes de zero:
x1j b1 a12x2
j1 a13x3j1
a11
x2j b2 a21x1
j a23x3j1
a22
x3j b3 a31x1
j a32x2j
a33
6Sistemas de Equações - Métodos Iterativos
3333232131
2323222121
1313212111
bxaxaxa
bxaxaxa
bxaxaxa
4 Abril 2017
Método de Gauss-Seidel
É o método iterativo mais utilizado para a resolução de
sistemas de equações lineares [A]{x}={b}.
Começa com estimativas iniciais:
(podem ser todos zero)
Itera:
Termina quando para todo i:
7Sistemas de Equações - Métodos Iterativos
nn xxxxxx ~,,~,~ 0
2
0
21
0
1
tolx
xxj
i
j
i
j
iia
%1001
,
ij
k
jij
ij
k
jiji
ii
k
i xaxaba
x )()1()1( 1
4 Abril 2017
Método de Gauss-Seidel
Exemplo:
Início:
Primeira iteração: Erro aproximado: 100%
10
2.03.04.717
3.01.03.193
2.01.085.7
213
1
312
1
3
1
21
jjj
jjj
jjj
xxx
xxx
xxx
8Sistemas de Equações - Métodos Iterativos
4.7101 .20 3.0
3.19.30 7 1.0
85.7.20 .10 3
321
321
321
xxx
xxx
xxx
0,0,0 0
3
0
2
0
1 xxx
616667.23
)0(2.0)0(1.085.71
1
x
794524.27
)0(3.0)616667.2(1.03.191
2
x
005610.710
)794524.2(2.0)616667.2(3.04.711
3
x
%100616667.2
0616667.21,
a
%100794524.2
0794524.22,
a
%100005610.7
0005610.73,
a
4 Abril 2017
Método de Gauss-Seidel
Exemplo:
Segunda iteração: Erro aproximado:
10
2.03.04.717
3.01.03.193
2.01.085.7
213
1
312
1
3
1
21
jjj
jjj
jjj
xxx
xxx
xxx
9Sistemas de Equações - Métodos Iterativos
4.7101 .20 3.0
3.19.30 7 1.0
85.7.20 .10 3
321
321
321
xxx
xxx
xxx
005610.7,794524.2,616667.2 1
3
1
2
1
1 xxx
990557.23
)005610.7(2.0)794524.2(1.085.72
1
x
499625.27
)005610.7(3.0)990557.2(1.03.192
2
x
000291.710
)499625.2(2.0)990557.2(3.04.712
3
x
990557.2
616667.2990557.21,
a
%8.112, a
%076.03, a
%5.121, a
4 Abril 2017
Método de Jacobi
Semelhante ao Método de Gauss-Seidel, excepto que os
valores da iteração j1 são usados para actualizar todas as
variáveis da iteração j:
33
1
232
1
13133
22
1
323
1
12122
11
1
313
1
21211
a
xaxabx
a
xaxabx
a
xaxabx
jjj
jjj
jjj
10Sistemas de Equações - Métodos Iterativos
3333232131
232222121
1313212111
bxaxaxa
bxaxaxa
bxaxaxa
n
n
ijj
k
jiji
ii
k
i xaba
x,1
)()1( 1
4 Abril 2017
Método de Jacobi
a) Gauss-Seidel
b) Jacobi
Gauss-Seidel converge mais rapidamente que Jacobi!
11Sistemas de Equações - Métodos Iterativos4 Abril 2017
Convergência
O Método de Gauss-Seidel (e o de Jacobi) podem divergir
Se o sistema é estritamente diagonal dominante, é garantida
a convergência:
A condição anterior é suficiente mas não necessária:
Pode convergir não sendo diagonal dominante
aii aijj1ji
n
12Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Gauss-Seidel
Dado o sistema de equações:
15312 321 x- x x
2835 321 x x x
761373 321 x x x
1
0
1
3
2
1
x
x
x
Com a estimativa inicial:
A matriz de coeficientes é:
1373
351
5312
A
O Método de Gauss-Siedel converge?
Exemplo:
13Sistemas de Equações - Métodos Iterativos4 Abril 2017
Verificar se a matriz de coeficientes é estritamente diagonal
dominante:
O Método de Gauss-Seidel converge!
Método de Gauss-Seidel
1373
351
5312
A 43155 232122 aaa
10731313 323133 aaa
8531212 131211 aaa
14Sistemas de Equações - Métodos Iterativos4 Abril 2017
Problema: Estimativa inicial:
Iterações: Primeira iteração:
Método de Gauss-Seidel
76281
13733515312
3
2
1
x
x
x
12
531 1
3
1
21
jjj xx
x
5
328 1
312
jjj xx
x
13
7376 213
jjj xx
x
101
0
3
0
2
0
1
x
x
x
50000.0
12
15031x1
1
9000.4
5
135.028x1
2
0923.3
13
9000.4750000.0376x1
3
15Sistemas de Equações - Métodos Iterativos4 Abril 2017
Problema: Estimativa inicial:
Iterações:
Método de Gauss-Seidel
76281
13733515312
3
2
1
x
x
x
101
0
3
0
2
0
1
x
x
x
16Sistemas de Equações - Métodos Iterativos
Iteração x1 x2 x3
1
2
3
4
5
6
0.50000
0.14679
0.74275
0.94675
0.99177
0.99919
100.00
240.61
80.236
21.546
4.5391
0.74307
4.9000
3.7153
3.1644
3.0281
3.0034
3.0001
100.00
31.889
17.408
4.4996
0.82499
0.10856
3.0923
3.8118
3.9708
3.9971
4.0001
4.0001
67.662
18.876
4.0042
0.65772
0.074383
0.00101
%1,a %2,a %3,a
4
3
1
3
2
1
x
x
x
0001.4
0001.3
99919.0
3
2
1
x
x
x
A solução aproximada é perto da solução exacta: .
4 Abril 2017
Método de Gauss-Seidel
Dado o sistema de equações:
1
0
1
3
2
1
x
x
x
Com a estimativa inicial:
A matriz de coeficientes é:
5312351
1373A
O Método de Gauss-Siedel converge?
Exemplo:
17Sistemas de Equações - Métodos Iterativos
761373 321 xxx
2835 321 xxx
15312 321 xxx
4 Abril 2017
Verificar se a matriz de coeficientes é estritamente diagonal
dominante:
Não sabemos se o Método de Gauss-Seidel converge!
Método de Gauss-Seidel
43155 232122 aaa
1531255 323133 aaa
2013733 131211 aaa
18Sistemas de Equações - Métodos Iterativos
5312351
1373A
4 Abril 2017
Problema: Estimativa inicial:
Iterações: Primeira iteração:
Método de Gauss-Seidel
12876
5312
3511373
3
2
1
x
x
x
3
13776 1
3
1
21
jjj xx
x
5
328 1
312
jjj xx
x
5
3121 213
jjj xx
x
101
0
3
0
2
0
1
x
x
x
19Sistemas de Equações - Métodos Iterativos
213
)1(13)0(7761
1
x
8.05
)1(321281
2
x
680.505
)8.0(3)21(1211
3
x
4 Abril 2017
Problema: Estimativa inicial:
Iterações:
Método de Gauss-Seidel
101
0
3
0
2
0
1
x
x
x
20Sistemas de Equações - Métodos Iterativos
%1,a %2,a %3,a
Não converge!
12876
5312
3511373
3
2
1
x
x
x
Iteração x1 x2 x3
1
2
3
4
5
6
21.000
−196.15
−1995.0
−20149
2.0364×105
−2.0579×105
95.238
110.71
109.83
109.90
109.89
109.89
0.80000
14.421
−116.02
1204.6
−12140
1.2272×105
100.00
94.453
112.43
109.63
109.92
109.89
50.680
−462.30
4718.1
−47636
4.8144×105
−4.8653×106
98.027
110.96
109.80
109.90
109.89
109.89
4 Abril 2017
Mas o Método de Gauss-Seidel pode ser usado:
Se o sistema não é diagonal dominante tentar rearranjar as
equações de modo a garantir a convergência!
Nem sempre é possível:
Método de Gauss-Seidel
21Sistemas de Equações - Métodos Iterativos
A matriz de coeficientes
não é diagonal dominante
5312
351
1373
A
Mas é o mesmo conjunto de
equações que convergiu no
exemplo anterior
1373
351
5312
A
3321 xxx
9432 321 xxx
97 321 xxx
4 Abril 2017
Método de Gauss-Seidelfunction x = GaussSeidel(A,b,es,maxit)
% GaussSeidel: Gauss Seidel method
% x = GaussSeidel(A,b): Gauss Seidel without relaxation
% input:
% A = coefficient matrix
% b = right hand side vector
% es = stop criterion (default = 0.00001%)
% maxit = max iterations (default = 50)
% output:
% x = solution vector
if nargin<2,error('at least 2 input arguments required'),end
if nargin<4|isempty(maxit),maxit=50;end
if nargin<3|isempty(es),es=0.00001;end
[m,n] = size(A);
if m~=n, error('Matrix A must be square'); end
C = A;
for i = 1:n
C(i,i) = 0;
x(i) = 0;
end
22Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Gauss-Seidelx = x';
for i = 1:n
C(i,1:n) = C(i,1:n)/A(i,i);
end
for i = 1:n
d(i) = b(i)/A(i,i);
end
iter = 0;
while (1)
xold = x;
for i = 1:n
x(i) = d(i)-C(i,:)*x;
if x(i) ~= 0
ea(i) = abs((x(i) - xold(i))/x(i)) * 100;
end
end
iter = iter+1;
if max(ea)<=es | iter >= maxit, break, end
end
23Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Gauss-Seidel
Exemplo:>> A = [12 3 -5; 1 5 3; 3 7 13]; b = [1; 28; 76];
>> x = GaussSeidel(A,b)
x =
1.0000
3.0000
4.0000
>> A = [ 3 7 13; 1 5 3; 12 3 -5]; b = [76; 28; 1];
>> x = GaussSeidel(A,b)
x =
1.0e+050 *
-3.9953
0.2382
-9.4457
24Sistemas de Equações - Métodos Iterativos4 Abril 2017
Relaxação
Para melhorar a convergência um método iterativo pode utilizar uma técnica de relaxação
Após o cálculo de cada valor, este é modificado por uma média pesada dos resultados da iteração presente com a anterior:
em que é um factor de peso que varia entre 0 e 2.
Se =1 então (1- )= 0 e o valor não se modifica
Se 0<<1 (sub-relaxação):
Utilizado para “obrigar” um sistema que não converge a convergir ou
para aumentar a convergência reduzindo oscilações
Se 1<≤2 (sobre-relaxação):
Peso extra na nova solução para aumentar a velocidade de convergência
xinew xi
new 1 xiold
25Sistemas de Equações - Métodos Iterativos4 Abril 2017
Relaxação
Exemplo: Calcular o sistema seguinte com o Método de Gauss-Seidel usando sobre-relaxação =1.2
Rearranjar o sistema de modo a ficar diagonal dominante e resolver as equações em ordem a x1 e x2 respectivamente:
Primeira iteração (com estimativas iniciais x1=0 e x2=0)
26Sistemas de Equações - Métodos Iterativos
=1.2
=1.2
4 Abril 2017
Sistemas de Equações Não Lineares
De um modo geral, um sistema de equações não lineares
pode ser representado na forma:
em que o objectivo é calcular os valores de x1,…, xn que
satisfazem simultaneamente todas as equações.
27Sistemas de Equações - Métodos Iterativos
0, , ,
0, , ,
0, , ,
21
212
211
nm
n
n
xxxf
xxxf
xxxf
4 Abril 2017
Sistemas de Equações Não Lineares
Exemplo:
28Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx
4 Abril 2017
Método das Substituições Sucessivas
Os sistemas não lineares também podem ser resolvidos
por uma estratégia identica à do método de Gauss-Seidel
Resolver cada equação em ordem a uma variável, e
usar esse valor nas equações seguintes.
29Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método das Substituições Sucessivas
Exemplo:
30Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx5.3
5.10
2
0
1
x
x
4 Abril 2017
Método das Substituições Sucessivas
Exemplo:
Resolver a equações em ordem a x1 e x2:
Iterar:
Diverge!31Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx5.3
5.10
2
0
1
x
x
2
2
11
10
x
xx
2
212 357 xxx
21429.25.3
)5.1(10 2
1
x 37516.24)5.3)(21429.2(357 2
2 x
20910.037516.24
)21429.2(10 2
1
x 709.429)37516.24)(20910.0(357 2
2 x
4 Abril 2017
Método das Substituições Sucessivas
Exemplo:
Resolver de outra forma a equações em ordem a x1 e x2:
Iterar:
Converge!32Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx5.3
5.10
2
0
1
x
x
211 10 xxx 1
22
3
57
x
xx
17945.2)5.3(5.1101 x 86051.2)17945.2(3
5.3572
x
94053.1)86051.2(17945.2101 x 04955.3)94053.1(3
86051.2572
x
4 Abril 2017
Método de Newton-Raphson
Os sistemas não lineares também podem ser
resolvidos pelo método de Newton-Raphson.
Para uma variável, a aproximação pela série de Taylor
e a respectiva equação de Newton-Raphson é:
33Sistemas de Equações - Métodos Iterativos
)()()()( 11 iiiii xfxxxfxf )(
)(1
i
iii
xf
xfxx
4 Abril 2017
Método de Newton-Raphson
Os sistemas não lineares também podem ser
resolvidos pelo método de Newton-Raphson.
Para 2 variáveis, a aproximação pela série de Taylor e
as respectivas equações de Newton-Raphson são:
1
,2
2
,1
2
,2
1
,1
1
,2
,1
1
,1
,2
,21,2
2
,2
,21,2
1
,2
,11,1,21,2
1
,2
2
,1
2
,2
1
,1
2
,1
,2
2
,2
,1
,11,1
2
,1
,21,2
1
,1
,11,1,11,1
x
f
x
f
x
f
x
f
x
ff
x
ff
xxx
fxx
x
fxxff
x
f
x
f
x
f
x
f
x
ff
x
ff
xxx
fxx
x
fxxff
iiii
i
i
i
i
ii
i
ii
i
iiii
iiii
i
i
i
i
ii
i
ii
i
iiii
34Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Newton-Raphson
Exemplo:
Calcular as derivada parciais:
Calcular os valores das funções:
35Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx5.3
5.10
2
0
1
x
x
4 Abril 2017
Método de Newton-Raphson
Exemplo:
Calcular:
Converge!
36Sistemas de Equações - Métodos Iterativos
573
102
212
21
2
1
xxx
xxx
5.3
5.10
2
0
1
x
x
5.20,1 f
625.10,2 f
5.61
0,1 x
f
5.12
0,1 x
f
75.361
0,2 x
f
5.322
0,2 x
f
125.156)75.36(5.1)5.32(5.61
0,2
2
0,1
2
0,2
1
0,1 x
f
x
f
x
f
x
f
03603.2125.156
)5.1(625.1)5.32(5.25.1
1
0,2
2
0,1
2
0,2
1
0,1
2
0,1
0,2
2
0,2
0,1
0,11,1
x
f
x
f
x
f
x
f
x
ff
x
ff
xx
84388.2125.156
)75.36)(5.2()5.6(625.15.3
1
0,2
2
0,1
2
0,2
1
0,1
1
0,2
0,1
1
0,1
0,2
0,21,2
x
f
x
f
x
f
x
f
x
ff
x
ff
xx
4 Abril 2017
Método de Newton-Raphson
Para n variáveis, o Método de Newton-Raphson tem a
forma:
Em que J(x) é a matriz Jacobiana de f:
Na prática não se calcula a inversa do Jacobiano J-1(xi),
resolve-se o sistema linear:
para o passo de Newton si, e calcula-se a estimativa:
37Sistemas de Equações - Métodos Iterativos
)()(1
1 iiii fJ xxxx
j
iij
x
fJ
)()(
xx
)()( iii fJ xsx
iii sxx 1
4 Abril 2017
Método de Newton-Raphsonfunction [x,f,ea,iter]=newtmult(func,x0,es,maxit,varargin)
% newtmult: Newton-Raphson root zeroes nonlinear systems
% [x,f,ea,iter]=newtmult(func,x0,es,maxit,p1,p2,...):
% uses the Newton-Raphson method to find the roots of
% a system of nonlinear equations
% input:
% func = name of function that returns f and J
% x0 = initial guess
% es = desired percent relative error (default = 0.0001%)
% maxit = maximum allowable iterations (default = 50)
% p1,p2,... = additional parameters used by function
% output:
% x = vector of roots
% f = vector of functions evaluated at roots
% ea = approximate percent relative error (%)
% iter = number of iterations
38Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Newton-Raphsonif nargin<2,error('at least 2 input arguments required'),end
if nargin<3|isempty(es),es=0.0001;end
if nargin<4|isempty(maxit),maxit=50;end
iter = 0;
x=x0;
while (1)
[J,f]=func(x,varargin{:});
dx=J\f;
x=x-dx;
iter = iter + 1;
ea=100*max(abs(dx./x));
if iter>=maxit|ea<=es, break, end
end
39Sistemas de Equações - Métodos Iterativos4 Abril 2017
Método de Newton-Raphson
Exemplo:function [J,f]=System(x)
J=[2*x(1)+x(2) x(1); 3*x(2)^2 1+6*x(1)*x(2)];
f=[x(1)^2+x(1)*x(2)-10; x(2)+3*x(1)*x(2)^2-57];
end
>> x0=[1.5;3.5];
>> [x,f,ea,iter]=newtmult(@System,x0)
x =
2.0000
3.0000
f =
1.0e-004 *
-0.0129
-0.2214
ea =
1.9554e-005
iter =
4
40Sistemas de Equações - Métodos Iterativos4 Abril 2017
Recommended