Sistemas de Equações Lineares Métodos Directoscomp.ssdi.di.fct.unl.pt/aulas/teoricas/aulaT4.pdf · Sistemas de Equações Muitos princípios fundamentais em problemas de ciência

Sistemas de Equações Lineares

Métodos Directos

Computação – 2º Semestre 2016/2017

Sistemas de Equações

Muitos princípios fundamentais em problemas de ciência e engenharia podem ser expressos em termos de equações:

Em problemas de raízes temos apenas uma equação e o objectivo é calcular os valores dos parâmetros que a satisfazem

Quando o que pretendemos modelar é constituído por várias componentes obtemos um sistema de equações:

e o objectivo é calcular os valores de x1,…, xn que satisfazem simultaneamente todas as equações.

228 Março 2017 Sistemas de Equações Lineares - Métodos Directos

externasfunções

,parâmetros ,tesindependen

variáveisdependente

variávelf

0, , ,

0, , ,

0, , ,

21

212

211

nm

n

n

xxxf

xxxf

xxxf

Sistemas de Equações

Exemplos:

3Sistemas de Equações Lineares - Métodos Directos

equilíbrio de massa:

massa: inputs - outputs

equilíbrio de forças:

forças horizontais = 0

forças verticais = 0

equilíbrio de corrente:

corrente (i) = 0

equilíbrio de voltagem:

iR = 0

28 Março 2017


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

28 Março 2017


Forma matricial:

em que

Um sistema de equações lineares é determinado se tem

uma única solução.

Um sistema de equações lineares é determinado se e

só se verificar qualquer das duas condições equivalentes:

1) A-1 existir

2) det A 0


bAx

nnnn

n

n

aaa

aaa

aaa

A

21

22221

11211

nx

x

x

x2

1

nb

b

b

b2

1

28 Março 2017

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.

6Sistemas de Equações Lineares - Métodos Directos28 Março 2017

Matrizes

Uma matriz é um conjunto de elementos organizado em

linhas e colunas e representado por um símbolo (ex: [A]).

Uma entrada de uma matriz é um elemento (ex: a23)


Matrizes

Uma sequência horizontal de elementos é uma linha e

uma sequência vertical de elementos é uma coluna.

O primeiro índice de um elemento indica a linha

enquanto que o segundo indica a coluna.

O tamanho de uma matriz é indicado como m linhas

por n colunas, ou simplesmente m por n (ou m n).

matrizes 1 n são vectores linha.

matrizes m 1 são vectores coluna.


Matrizes Especiais

Matrizes com m=n são denominadas matrizes quadradas.

Existem várias matrizes quadradas especiais:

Symmetric

A

5 1 2

1 3 7

2 7 8

Diagonal

A

a11

a22

a33

Identity

A

1

1

1

Upper Triangular

A

a11 a12 a13

a22 a23

a33

Lower Triangular

A

a11

a21 a22

a31 a32 a33

Banded

A

a11 a12

a21 a22 a23

a32 a33 a34

a43 a44


Operações com Matrizes

Duas matrizes são iguais se e só se:

São do mesmo tamanho

Todos os elementos correspondentes são iguais

A adição e subtracção de matrizes são efectuadas por

adição e subtracção dos elementos correspondentes.

(as matrizes têm que ter o mesmo tamanho)

A multiplicação de uma matriz por um escalar é obtida

por multiplicação de cada elemento pelo escalar.


Multiplicação de Matrizes

Os elementos da matriz [C] que resulta da

multiplicação de [A] e [B] são:

cij aikbk jk1

n


Matriz Inversa e Transposta

A inversa de uma matriz quadrada [A] é a matriz [A]-1 que,

quando multiplicada por [A], resulta na matriz identidade [I]:

[A][A]-1=[A]-1[A]=[I]

A transposta de uma matriz corresponde a trocar as linhas

pelas colunas:

(aij)T=aji


Representação de Álgebra Linear

As matrizes permitem uma notação concisa para a

representação e resolução de sistemas de equações lineares:

a11x1 a12x2 a13x3 b1

a21x1 a22x2 a23x3 b2

a31x1 a32x2 a33x3 b3

a11 a12 a13

a21 a22 a23

a31 a32 a33

x1

x2

x3

b1

b2

b3

[A]{x}{b}


Resolução com o MATLAB

O MATLAB oferece duas formas directas de resolver sistemas de equações lineares [A]{x}={b}:

Divisão-à-esquerdax = A\b

Matriz inversa x = inv(A)*b

A matriz inversa é menos eficiente que a divisão-à-esquerda


Método Gráfico

Para duas equações:

resolver ambas em ordem a x2:

obtendo-se rectas:

desenhar as rectas e localizar

a sua intersecção


2222121

1212111

bxaxa

bxaxa

intercept(slope) 12 xx

22

21

22

212

12

11

12

112

a

bx

a

ax

a

bx

a

ax

28 Março 2017

Método Gráfico

Pode ajudar a detectar casos em que:

a) Não existem soluções

b) Existem infinitas soluções

c) O problema é mal condicionado


Determinantes

O determinante D=|A| de uma matriz A é calculado a partir dos

seus elementos:

Determinantes de matrizes maiores que 3 x 3 podem ser muito

complicados de calcular.

3231

222113

3331

232112

3332

232211

333231

232221

131211

211222112221

1211

1111

33

22

11

aa

aaa

aa

aaa

aa

aaa

aaa

aaa

aaa

aaaaaa

aa

aa


Determinantes

Exemplos:


812232123

D

28 Março 2017

Determinantes

Exemplos:


12

1

12

1

D

21

12

1

D

04.05

3.211

2

1

0

2

111

2

1

0112

2

1

15

3.2

12

1

D

28 Março 2017

Regra de Cramer

Se Ax=b é a forma matricial de um sistema de equações

lineares onde a matriz A é invertível, então:

onde Ai é a matriz que se obtém de A substituindo a

coluna i pelo vector b

A Regra de Cramer exige o cálculo de n+1 determinantes

de ordem n, o que conduz a uma complexidade O(n!)

É impraticável para sistemas com mais que 3 equações.


niD

D

A

Ax ii

i ,,2,1,det

det

28 Março 2017

Regra de Cramer

Usar a Regra de Cramer para resolver:

Calcular o determinante D

0.3x1 0.52x2 x3 0.01

0.5x1 x2 1.9x3 0.67

0.1x1 0.3x2 0.5x3 0.44

D

0.3 0.52 1

0.5 1 1.9

0.1 0.3 0.5

0.31 1.9

0.3 0.50.52

0.5 1.9

0.1 0.51

0.5 1

0.1 0.4 0.0022


Regra de Cramer


Calcular os determinantes Di substituindo a i-ésima coluna por b

0.3x1 0.52x2 x3 0.01

0.5x1 x2 1.9x3 0.67

0.1x1 0.3x2 0.5x3 0.44

03278.03.044.0

167.01

5.044.09.167.0

52.05.03.09.11

01.05.03.044.09.1167.0

152.001.0

1

D


D2

0.3 0.01 1

0.5 0.67 1.9

0.1 0.44 0.5

0.30.67 1.9

0.44 0.50.01

0.5 1.9

0.1 0.51

0.5 0.67

0.1 0.44 0.0649

04356.03.01.0

15.001.0

44.01.067.05.0

52.044.03.0

67.013.0

44.03.01.067.015.001.052.03.0

3

D

28 Março 2017

Regra de Cramer


Calcular a solução:

0.3x1 0.52x2 x3 0.01

0.5x1 x2 1.9x3 0.67

0.1x1 0.3x2 0.5x3 0.44

9.140022.0

03278.011

D

Dx


x2 D2

D

0.0649

0.0022 29.5

8.190022.0

04356.033

D

Dx

28 Março 2017

Regra de Cramer

Exemplo MATLAB:>> A=[0.3 0.52 1;0.5 1 1.9;0.1 0.3 0.5];

>> D=det(A)

D =

-0.0022

>> A1=A; A1(:,1)=[-0.01;0.67;-0.44], x1=det(A1)/D

A1 =

-0.0100 0.5200 1.0000

0.6700 1.0000 1.9000

-0.4400 0.3000 0.5000

x1 = -14.9000

>> A2=A; A2(:,2)=[-0.01;0.67;-0.44]; x2=det(A2)/D

x2 = -29.5000

>> A3=A; A3(:,3)=[-0.01;0.67;-0.44]; x3=det(A3)/D

x3 = 19.8000

0.3x1 0.52x2 x3 0.01

0.5x1 x2 1.9x3 0.67

0.1x1 0.3x2 0.5x3 0.44


Método de Eliminação de Gauss

Transformar o sistema original Ax=b num sistema equivalente, mas cuja matriz seja triangular (de fácil resolução)

Dois sistemas de equações lineares dizem-se equivalentes se possuírem o mesmo conjunto de soluções.

Cada sistema de equações lineares Ax=b tem associada a sua matriz ampliada:

A matriz triangular é obtida por uma sequência de operações elementares sobre A’ que preservam a equivalência:

permutação de duas linhas

multiplicação de uma linha por um escalar não nulo

soma a uma linha do produto de outra linha por um escalar.25Sistemas de Equações Lineares - Métodos Directos

nnnnn

n

n

b

b

b

aaa

aaa

aaa

A

2

1

21

22221

11211

28 Março 2017

Método de Eliminação de Gauss Naïve

“Naïve” significa que não são considerados

os problemas resultantes da divisão por zero

Eliminação

Começando na 1ª linha, adicionar ou subtrair

múltiplos dessa linha para eliminar o 1º

coeficiente das linhas seguintes.

Continuar o processo na 2ª linha para

remover o 2º coeficiente das linhas seguintes.

Parar quando se obtiver uma matriz triangular.

Substituição

Começando na última linha, resolver a

incógnita, e introduzir o resultado obtido na

linha imediatamente superior.

Porque a matriz é triangular, ao continuar o

processo para cada linha superior podem ser

resolvidas todas as incógnitas.



Exemplo:

Eliminação:

multiplicar a 1ª linha por 0.1/3 e subtrair o resultado à 2ªlinha

multiplicar a 1ª linha por 0.3/3 e subtrair o resultado à 3ªlinha:

multiplicar a 2ª linha por -0.19/7.00333 e subtrair o resultado à 3ªlinha:



Exemplo:

Substituição:

resolver a 3ª equação:




Método de Eliminação de Gauss Naïvefunction x = GaussNaive(A,b)

% GaussNaive: naive Gauss elimination

% x = GaussNaive(A,b): Gauss elimination without pivoting.

% input:

% A = coefficient matrix

% b = right hand side vector

% output:

% x = solution vector

[m,n] = size(A);

if m~=n, error('Matrix A must be square'); end

nb = n+1;

Aug = [A b];


Método de Eliminação de Gauss Naïve% forward elimination

for k = 1:n-1

for i = k+1:n

factor = Aug(i,k)/Aug(k,k);

Aug(i,k:nb) = Aug(i,k:nb)-factor*Aug(k,k:nb);

end

end

% back substitution

x = zeros(n,1);

x(n) = Aug(n,nb)/Aug(n,n);

for i = n-1:-1:1

x(i) = (Aug(i,nb)-Aug(i,i+1:n)*x(i+1:n))/Aug(i,i);

end



Número de operações de vírgula-flutuante (flops) num sistema nxn

Eliminação:


)(3

2)2)(()1)(( 2

31

1

1

1

nOn

knknknknn

k

n

k

Adições/Subtracções Multiplicações/Divisões

28 Março 2017


Número de operações de vírgula-flutuante (flops) num sistema nxn

O tempo de execução aumenta muito com o tamanho do sistema.

A eliminação é a componente computacional mais crítica



No entanto é muito mais eficiente que a regra de Cramer!

Comparação do tempo de execução na resolução de um sistema

de equações lineares nxn, num supercomputador Cray J90:



Com o método naïve surgem problemas se um coeficiente na diagonal (pivot) é 0 (problema: divisão por 0) ou próximo de 0 (problema: erros de arredondamento)

Evitam-se estes problemas com técnicas de selecção de pivot: Determinação da linha com o coeficiente de maior valor

absoluto abaixo do elemento pivot

Troca das respectivas linhas

A técnica que introduz esta troca de linhas denomina-se pivotação parcial.

Se também for permitido troca de colunas denomina-se pivotação total.



Exemplo:

Versão naïve: (solução → x1=1/3, x2 = 2/3)

multiplicar a 1ª linha por 1/0.0003 e subtrair o resultado à 2ªlinha:

resolver as equações: x2 = 2/3

sensível aos erros de arredondamento:



Exemplo:

Versão com pivotagem: (solução → x1=1/3, x2 = 2/3)

trocar a 1ª linha com a 2ªlinha:

eliminar e resolver as equações: x2 = 2/3

pouco sensível aos erros de arredondamento:


Método de Eliminação de Gaussfunction x = GaussPivot(A,b)

% GaussPivot: Gauss elimination pivoting

% x = GaussPivot(A,b): Gauss elimination with pivoting.

% input:

% A = coefficient matrix

% b = right hand side vector

% output:

% x = solution vector

[m,n]=size(A);

if m~=n, error('Matrix A must be square'); end

nb=n+1;

Aug=[A b];


Método de Eliminação de Gauss% forward elimination

for k = 1:n-1

% partial pivoting

[big,i]=max(abs(Aug(k:n,k)));

ipr=i+k-1;

if ipr~=k

Aug([k,ipr],:)=Aug([ipr,k],:);

end

for i = k+1:n

factor=Aug(i,k)/Aug(k,k);

Aug(i,k:nb)=Aug(i,k:nb)-factor*Aug(k,k:nb);

end

end

% back substitution

x=zeros(n,1);

x(n)=Aug(n,nb)/Aug(n,n);

for i = n-1:-1:1

x(i)=(Aug(i,nb)-Aug(i,i+1:n)*x(i+1:n))/Aug(i,i);

end


Documents

Sistemas de Equações Lineares Métodos Directoscomp.ssdi.di.fct.unl.pt/aulas/teoricas/aulaT4.pdf · Sistemas de Equações Muitos princípios fundamentais em problemas de ciência