Sistemas de Equações Métodos Iterativoscomp.ssdi.di.fct.unl.pt/aulas/teoricas/aulaT5.pdfMétodos Iterativos Os Métodos Directos estão sujeitos a erros de arredondamento Os Métodos

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


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


É 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:


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


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


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


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


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


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!


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



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:


Verificar se a matriz de coeficientes é estritamente diagonal

dominante:

O Método de Gauss-Seidel converge!


1373

351

5312

A 43155 232122 aaa

10731313 323133 aaa

8531212 131211 aaa


Problema: Estimativa inicial:

Iterações: Primeira iteração:


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



Iterações:


76281

13733515312

3

2

1

x

x

x

101

0

3

0

2

0

1

x

x

x


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


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:


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!


43155 232122 aaa

1531255 323133 aaa

2013733 131211 aaa


5312351

1373A

4 Abril 2017


Iterações: Primeira iteração:


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


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


Iterações:


101

0

3

0

2

0

1

x

x

x


%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:



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


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



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


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


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)


=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.


0, , ,

0, , ,

0, , ,

21

212

211

nm

n

n

xxxf

xxxf

xxxf

4 Abril 2017

Sistemas de Equações Não Lineares

Exemplo:


573

102

212

21

2

1

xxx

xxx

4 Abril 2017


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.



Exemplo:


573

102

212

21

2

1

xxx

xxx5.3

5.10

2

0

1

x

x

4 Abril 2017


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


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 é:


)()()()( 11 iiiii xfxxxfxf )(

)(1

i

iii

xf

xfxx

4 Abril 2017


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



Exemplo:

Calcular as derivada parciais:

Calcular os valores das funções:


573

102

212

21

2

1

xxx

xxx5.3

5.10

2

0

1

x

x

4 Abril 2017


Exemplo:

Calcular:

Converge!


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


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:


)()(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


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



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


Documents

Sistemas de Equações Métodos Iterativoscomp.ssdi.di.fct.unl.pt/aulas/teoricas/aulaT5.pdfMétodos Iterativos Os Métodos Directos estão sujeitos a erros de arredondamento Os Métodos