Resolução Numérica de Sistemas Lineares Parte Ijorge.cavalcanti/6CN_Sistemas_Parte1.pdf · 2 Sistemas Lineares Muitos problemas de matemática numérica são modelados em termos

Cálculo Numérico

Resolução Numérica de

Sistemas Lineares –Parte I

Prof. Jorge Cavalcanti – [email protected]

MATERIAL ADAPTADO DOS SLIDES DA DISCIPLINA CÁLCULO NUMÉRICO DA UFCG - www.dsc.ufcg.edu.br/~cnum/

2

Sistemas Lineares

Muitos problemas de matemática numérica são modelados em termos de um sistema de equações lineares.

Essa representação é vantajosa, pois separa o problema em partes menores e possui vários métodos de resolução

Exemplos de aplicações de sistemas lineares são encontrados em várias áreas da engenharia, como por exemplo:

Análise de circuitos elétricos;

Análise de vibrações em um sistema mecânico;

Distribuição da força-peso na estrutura de um edifício.

3

Sistemas Lineares

Forma Geral

onde:

aij coeficientes

xi variáveis

4

Exemplo 01

2, 4, -5, 4, 1, -5, 2, 4 e 5 coeficientes

x1, x2 e x3 variáveis

Sistemas Lineares

5

Sistemas Lineares

Forma Matricial

onde:

Ax = b

6

Sistemas Lineares

Exemplo 02

Forma Geral

Forma Matricial

7

Sistemas Lineares

Classificação I

Impossível Não possui solução

Exemplo 03

8

Sistemas Lineares

Classificação II

Possível Possui 1 ou mais soluções

Determinado Solução única

Exemplo 04

9

Classificação III


Indeterminado Mais de uma solução

Exemplo 05

Sistemas Lineares

10

Sistemas Lineares

Classificação IV


Homogêneo Vetor b=0

Exemplo 06

11

Sistemas Lineares

Sistemas Triangulares:

Possibilidade de resolução de forma Retroativa Inferior (aij = 0, se j >i; i, j = 1,2,…n)

12

Sistemas Lineares

nn

n33 3

n22 32 2

n11 31 21 1

a000

aa00aaa0aaaa

A

Sistemas Triangulares:

Possibilidade de resolução de forma Retroativa

Superior (aij = 0, se j<i; i, j = 1,2,…n)

13

Solução Retroativa

Exemplo 7:

Dado o sistema:

Primeiro passo para sua resolução:

2x2

3x5x41x2xx

10xx5x4x3

4

43

432

4321

12

2x 4

14


Exemplo 7:

Segundo passo:

Terceiro passo:

15


Exemplo 7:

Último passo:

16

Métodos Numéricos

Diretos

Solução pode ser encontrada através de um número finito de passos

Método de Gauss

Método da Eliminação de Jordan

Fatoração LU

17

Métodos Numéricos

Iterativos

Solução a partir de uma seqüência de aproximações para o valor do vetor solução x, até que seja obtido um valor que satisfaça à precisão pré-estabelecida

Método de Jacobi

Método de Gauss – Siedel

18

Método de Gauss

Propósito

Transformação do sistema linear a ser resolvido em um sistema linear triangular;

Resolução do sistema linear triangular de forma retroativa

19

Método de Gauss

Transformação do Sistema Linear

Troca da ordem das linhas;

Multiplicação de uma das equações por um número real não nulo;

Substituição de uma das equações por uma combinação linear dela mesma com outra equação.

20

Método de Gauss

Passos do Método de Gauss

Construção da matriz aumentada Ab

21

Método de Gauss


Passo 1:

Eliminar os coeficientes de x1 presentes nas linhas 2,3,...,n - sendo a21 = a31, = ... = an1 = 0, sendo a11 chamado de pivô da coluna

Substituir a linha 2, L2, pela combinação linear

1 1

2 12 112 122 :,

a

amondeLmLL

22

Método de Gauss


Substituir a linha 3, L3, pela combinação linear:

23

Método de Gauss


Deve-se continuar a substituição até a linha n;

Caso algum elemento app=0, achar outra

linha k onde akp≠ 0 e trocar tais linhas. Caso a linha k não exista, o sistema linear não possui solução.

24

Método de Gauss


Eliminar os coeficientes de x2 nas linhas 3, 4, ..., n (fazer a32=a42=...=an2 = 0);

Eliminar os coeficientes de x3 nas linhas 4, 5, ..., n (fazer a43=a53=...=an3 = 0) e assim sucessivamente.

25

Método de Gauss

Exemplo 8:

Resolver o sistema:

Matriz aumentada Ab

Pivô

26

Método de Gauss

Exemplo 8:

Faz-se:

Assim:

27

Método de Gauss

Exemplo 8:

Faz-se:

Assim:

28

Método de Gauss

Exemplo 8:

Obtém-se a matriz:

Novo Pivô

29

Método de Gauss

Exemplo 8:

Substituindo a linha 3 por:

Têm-se:

30

Método de Gauss

Exemplo 8:

A matriz [Ab] fica assim com os seguintes valores:

31

Método de Gauss

Exemplo 8:

Usa-se a solução retroativa:

32

Método de Gauss

Exemplo 9:

Resolver o sistema.

Representando o sistema pela matriz aumentada:

M21 = a21/a11 = 1/3

M31 = a31/a11 = 4/3

33

Método de Gauss

Exemplo 9:

Escolhendo a primeira linha como pivô, obtém-se:

34

Método de Gauss

Exemplo 9:

Representando o sistema pela matriz aumentada:

M32 = a32/a22 = (1/3)/(1/3) = 1

35

Exemplo 9:

Escolhendo agora a segunda linha como pivô, têm-se:

Obtêm-se a seguinte matriz ampliada:

Método de Gauss

36

Método de Gauss

Exemplo 9:

O que termina com a triangulação:

08003

5

3

2

3

10

1423

321

321

321

xxx

xxx

xxx

37

Método de Gauss

Exemplo 9:

Com a solução:

x3 = 0

x2 = 5/3 * 3 = 5

x1 = -9/3 = -3

38

Método do Pivoteamento Parcial

Semelhante ao método de Gauss;

Usado quando o pivô é nulo ou próximo de zero.

Minimiza a amplificação de erros de arredondamento durante as eliminações;

Consiste em escolher o elemento de maior módulo em cada coluna para ser o pivô.

39


Exemplo 10:

Resolver o sistema abaixo:

3x4x3

4x0xx3

3x3x2x

32

321

321

3430

4013

3321

Ab][

40


Exemplo 10:

Matriz aumentada original deve ser ajustada: O maior coeficiente (módulo) na primeira coluna é o

elemento a21=3. Esse coeficiente será considerado o pivô e deverá

ocupar a posição diagonal na primeira coluna. Portanto, devemos trocar a 2ª linha pela 1ª linha,

fazendo a21 ocupar a posição (1,1).

3430

4013

3321

Ab][

3430

3321

4013

Ab][

41


Exemplo 10:

Aplicando o Método de Gauss no pivô a11=3:

Encontrar a nova linha:

]//[

]/[][

][)/(][

353350L

403113321L

4013313321LmLL

2

2

12122

M21 = a21/a11 = 1/3

3430

353350

4013

Ab //][

O maior coeficiente (módulo) na segunda coluna é o elemento a32=3;Esse elemento ocupará a posição diagonal, então troca-se a 3ª linha pela 2ª linha.

.

42


Exemplo 10:

A matriz ajustada será:

Aplicando o Método de Gauss no pivô a22=3

Encontrar a nova linha:

]/[

]///[]//[

][)/(]//[

09700L

9159209150353350L

3430953533502LmLL

3

3

3233

M32 = a32/a22 = 5/9

353350

3430

4013

Ab

//

][

.

43


Exemplo 10:

A matriz ampliada resultante fica:

Resolvendo o sistema triangular superior:

09700

3430

4013

Ab

/

][

x3 = 0

3x2 + 4x3 = 3; 3x2=3; x2=1

3x1 + 1x2 = 4; 3x1 = 3; x1 = 1

44

Método de Jordan

Consiste em efetuar operações sobre as equações do sistema, com a finalidade de obter um sistema diagonal equivalente;

Um sistema diagonal é aquele em que os elementos aij da matriz coeficiente [A] são iguais a zero, para i≠j,

i, j = 1,2,...,n.

45

Método de Jordan

Sistema diagonal equivalente:

nn

n33 3

n22 2

n11 1

a000

aa00a0a0a00a

]A[

M21 = a21/a11

M31 = a31/a11

M23 = ?

M12 = ?

Mnm = ?

46

Método de Jordan

Exemplo 11:

A partir do sistema:

Com matriz aumentada:

1

02

42

321

321

321

xxx

xxx

xxx

1111

0112

4211

Ab

M21 = a21/a11=2/1 = 2

M31 = a31/a11=1/1 = 1

47

Método de Jordan

Exemplo 11:


Substituindo a linha 3 por :

8530

,4211)2(0112

2

12122

L

LmLL

5320

,4211)1(1111

3

13133

L

LmLL

48

Método de Jordan

Exemplo 11:

A matriz ampliada resulta em:


5320

8530

4211

Ab

M32 = a32/a22=-2/-3=2/3

3/13/100

3/163/10205320

8530)3/2(5320

3

3

23233

L

L

LmLL

Novo Pivô

49

Método de Jordan

Exemplo 11:

A matriz ampliada resulta em:

Substituindo a linha 1 por

3/13/100

8530

4211

Ab

M12 = a12/a22=- 1/3

Pivô

3/43/101

3/83/5104211

8530)3/1(4211

1

1

21211

L

L

LmLL

50

Método de Jordan

Exemplo 11:

Matriz ampliada resulta em:

Substituindo as linhas 1 e 2 por

3/13/100

8530

3/43/101

Ab

30302

3/13/100)15(]8530[

1001

3/13/100)1(]3/43/101[

32322

1

31311

L

LmLL

L

LmLL

M13 = a13/a33=1

M23 = a23/a33=-5/(1/3) = -15

Novo Pivô

51

Método de Jordan

Exemplo 11:

A matriz ampliada fica da seguinte forma:

Produzindo o seguinte vetor resultado:

Qual a vantagem do método em relação ao de Gauss?

3/13/100

3030

1001

Ab

52

Decomposição em LU

O objetivo é fatorar a matriz dos coeficientes A em um produto de duas matrizes L e U.

Seja:

nn

n333

n22322

n1131211

3n2n1n

3231

21

u000

uu00

uuu0uuuu

1lll001ll001l0001

LU

53


E a matriz coeficiente A:

Têm-se:

nn3n2n1n

n22 22 1

n11 21 1

aaaa

aaaaaa

A

nn

n333

n22322

n1131211

3n2n1n

3231

21

nn3n2n1n

n22221

n11211

u000

uu00

uuu0uuuu

1lll001ll001l0001

]LU[

aaaa

aaaaaa

A

54


Resumo de Passos:

Seja um sistema Ax = b de ordem n.

Então, o sistema Ax = b pode ser escrito como:

LUx = b

55


Resumo dos Passos:

Fazendo Ux = y, a equação anterior reduz-se a Ly = b.

Resolvendo o sistema triangular inferior Ly = b, obtém-se o vetor y.

56


Resumo dos Passos:

Substituição do valor de y no sistema Ux = y Obtenção de um sistema triangular superior cuja solução é o vetor x procurado;

Aplicação da fatoração LU na resolução de sistemas lineares Necessidade de solução de dois sistemas triangulares

57


Para se obter os elementos da matriz L e da matriz U, deve-se calcular alternadamente os elementos das linhas de U e os elementos da colunas de Lcomo segue.

.ji,u/)ula(l

,ji,ulau

jj

j

k

kjikijij

i

k

kjikijij

1

1

1

1

58


Exemplo 12:

A partir do sistema:

Encontrar as matrizes LU e achar o vetor solução x*.

53

743

025

321

321

321

xxx

xxx

xxx

59


Exemplo 12:

Matriz A

1a.Linha de U

u1j = a1j, j=1,2,3 u11=5, u12 = 2, u13 =1

1a.Coluna de L

li1 = ai1/u11, i=2,3 l21=3/5

l31 = a31/u11 l31=1/5

33

2322

131211

3231

21

00

0.

1

01

001

][

311

413

125

u

uu

uuu

LUA

ll

l

33

2322

32 00

0

125

.

15/1

015/3

001

][

u

uuLU

l

60

Decomposição em LU Exemplo 12:

Seguindo:

2a.Linha de U

u2j = a2j-l21.u1j, j=2,3 u22= a22-l21.u12

u22=1-3/5*2 = -1/5

u23= a23-l21.u13 =4-3/5*1 = 17/5

2a.Coluna de L

li2 = (ai2-li1.u12)/u22, i=3 l32 = (a32-l31.u12)/u22

l32=(1-1/5*2)/-1/5, l32=-3

33

2322

32 00

0

125

.

15/1

015/3

001

][

u

uuLU

l

311

413

125

A

61


Exemplo 12:

Seguindo:

3a.Linha de U

u33 = a33-l31.u13-l32.u23 u33=3-1/5*1- (-3) * 17/5 = 13.

3300

5/175/10

125

.

135/1

015/3

001

][

311

413

125

u

LUA

1300

5/175/10

125

.

135/1

015/3

001

][

311

413

125

LUA

62


Para obter a solução do sistema Ax = b, devemos resolver dois sistemas triangulares: Ly = b e Ux = y.

Lembrando Ax=b:

Assim Ly=b, isto é:

5

7

0

.

135/1

015/3

001

3

2

1

y

y

y

5

7

0

.

311

413

125

3

2

1

x

x

x

y1 = 0

y2 = -7

y3 = -26

63


De Ux = y:

26

7

0

.

1300

5/175/10

125

3

2

1

x

x

x

13x3 = -26 x3= -2

-1/5x2 + 17/5x3 = -7 x2=1

5x1 + 2x2 + x3 = 0 x1 =0

x1 = 0

x2 = 1

x3 = -2

64

Sistemas Lineares - Bibliografia

Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo Numérico: Aspectos teóricos e

computacionais. MAKRON Books, 1996, 2ª ed.

Barroso, L. C. et al. Cálculo Numérico com

aplicações. Harbra, 1987, 2ª ed.

Arenales, S. & Darezzo, A. Cálculo Numérico-Aprendizagem com apoio de software. Thomson,

2008, 1ª ed.

Burian, R., Lima, A. C. & Junior, A. H. - Cálculo

Numérico. LTC, 2007, 2ª ed.

Documents

Resolução Numérica de Sistemas Lineares Parte Ijorge.cavalcanti/6CN_Sistemas_Parte1.pdf · 2 Sistemas Lineares Muitos problemas de matemática numérica são modelados em termos