Resolução Numérica de Sistemas Lineares Parte I · 8 Classificação III Possível Possui 1 ou mais soluções Indeterminado Mais de uma solução Exemplo 05 Sistemas Lineares

Profs.: Bruno Correia da Nóbrega Queiroz

José Eustáquio Rangel de Queiroz

Marcelo Alves de Barros

Resolução Numérica de Sistemas Lineares – Parte I

Cálculo Numérico Módulo V

2

Sistemas Lineares

Forma Geral

onde:

aij coeficientes

xi incógnitas

bi termos independentes

nnnn22n11n

2nn2222121

1nn1212111

bxa...xaxa

bxa...xaxa

bxa...xaxa

3

Exemplo 01

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

x1, x2 e x3 incógnitas

5, 2 e -1 termos independentes

Sistemas Lineares

1x5x4x2

2x5x1x4

5x5x4x2

321

321

321

4

Sistemas Lineares

Forma Matricial

na qual:

4

Ax = b

nn3n2n1n

n22221

n112

aaaa

aaa

aaa

A

11

n

2

1

b

b

b

b

n

2

1

x

x

x

x

5

Sistemas Lineares

1x5x4x2

2x5x1x4

5x5x4x2

321

321

321

5

Exemplo 02

Forma Geral

Forma Matricial

1

2

5

x

x

x

.

542

514

542

3

2

1

6

Sistemas Lineares

Classificação I

Impossível Não possui solução

Exemplo 03

6

9x2x2

3xx

21

21

7

Sistemas Lineares

Classificação II

Possível Possui 1 ou mais soluções

Determinado Solução única

Exemplo 04

8xx

4xx

21

21

8

Classificação III


Indeterminado Mais de uma solução

Exemplo 05

Sistemas Lineares

8x2x2

4xx

21

21

9

Sistemas Lineares

Classificação IV


Homogêneo Vetor b=0 (x=0 sempre

existe solução)

Exemplo 06

0x3x2

0xx

21

21

10

Sistemas Lineares

nn3n2n1n

333231

2221

11

aaaa

0aaa

00aa

000a

A

Sistemas Triangulares:

Possibilidade de resolução de forma Direta

Inferior

11

Sistemas Lineares

nn

n333

n22322

n1131211

a000

aa00

aaa0

aaaa

A

Sistemas Triangulares:

Possibilidade de resolução de forma Retroativa

Superior

12

Solução Retroativa

Exemplo 7:

Dado o sistema:

Primeiro passo para sua resolução:

2x2

3x5x4

1x2xx

10xx5x4x3

4

43

432

4321

12

2x4

13


Exemplo 7:

Segundo passo:

Terceiro passo:

2x

315x4

3x5x4

3

3

43

1x

1122x

1x2xx

2

2

432

14


Exemplo 7:

Último passo:

1x

10125)1(4x3

10xx5x4x3

1

1

4321

15

Métodos Numéricos

Diretos

Solução pode ser encontrada a partir de um número finito de passos

Método de Gauss

Método da Eliminação de Jordan

Fatoração LU

16

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 – Seidel

17

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.

18

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.

19

Método de Gauss

Passos do Método de Gauss

Construção da matriz aumentada Ab

19

nnn3n2n1n

2n22221

1n11211

baaaa

baaa

baaa

Ab

20

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

11

21

211212a

am:qualna,LmL

21

Método de Gauss

11

31

3113133a

am:qualna,LmLL


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

22

Método de Gauss


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.

23

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.

24

Método de Gauss

Exemplo 8:

Resolver o sistema:

Matriz aumentada Ab

1xx3x2

3x3x4x4

5xx3x2

321

321

321

1132

3344

5132

Ab

25

Método de Gauss

Exemplo 8:

Faz-se:

Assim:

2a

am,LmLL

11

21

2112122

7120L

513223344L

2

2

26

Método de Gauss

Exemplo 8:

Faz-se:

Assim:

1a

am,LmLL

11

31

2313133

6260L

513211132L

3

3

27

Método de Gauss

Exemplo 8:

Obtém-se a matriz:

6260

7120

5132

Ab

28

Método de Gauss

Exemplo 8:

Substituindo a linha 3 por:

Têm-se:

3a

am,LmLL

22

32

3213233

15500L

712036260L

3

3

29

Método de Gauss

Exemplo 8:

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

15500

7120

5132

Ab

30

Método de Gauss

Exemplo 8:

Usa-se a solução retroativa:

1x22x5362x

5xx32x

2x732x7x2x

3x155x

111

321

2232

33

31

Método de Gauss

Exemplo 9:

Resolver o sistema.

Representando o sistema pela matriz aumentada:

9,8x8,7x7,5x7,2

7,11x5,4x3,2x2,4

10x3,3x4,5x5,1

321

321

321

9,88,77,57,2

7,115,43,22,4

103,34,55,1

]AB[

32

Método de Gauss

Exemplo 9:

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

9,11,864,020 L

103,35,41,5(2,7/1,5)

8,97,85,72,7LmLL

16,34,7412,820 L

103,35,41,5(4,2/1,5)

11,74,52,34,2LmLL

3

13133

2

12122

33

Método de Gauss

Exemplo 9:

Representando o sistema pela matriz aumentada:

9,11,864,020

16,34,7412,820

103,35,41,5

[AB]

34

Exemplo 9:

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

Método de Gauss

3,98883,346300L

16,34,7412,82012,824,02/

9,11,864,020L

LmLL

3

3

13233

35

Exemplo 9:

Obtêm-se a seguinte matriz ampliada:

Método de Gauss

3,98883,346300

16,34,7412,820

103,35,41,5

[AB]

36

Método de Gauss

Exemplo 9:

O que termina com a triangulação:

3,9888x3,3463x0x0

16,3x4,74x12,82x0

10x3,3x5,41,5x

321

321

321

37

Método de Gauss

Exemplo 9:

Com solução:

x3 = -3,9888/3,3463=-1,1918

x2 =[ -16,3 - (-4,74)(-1,1920)]/(-12,82) = 1,7121

x1 = [10 - 5,4(1,7122) - 3,3(-1,1920)]/1,5 = 3,1251

38

Método do Pivoteamento Parcial

Semelhante ao método de Gauss;

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 com precisão de 4 casas decimais

9,8x8,7x7,5x7,2

7,11x5,4x3,2x2,4

10x3,3x4,5x5,1

321

321

321

40


Exemplo 10:

Matriz aumentada original deve ser ajustada:

9,88,77,57,2

7,115,43,22,4

103,34,55,1

9,88,77,57,2

103,34,55,1

7,115,43,22,4

41


Exemplo 10:

Sistema inalterado, elemento pivô 4,2.

Encontrar as novas linhas:

]1,37864,90714,22140[L

]11,74,52,34,2[(2,7/4,2)

]8,97,85,72,7[LmLL

]5,82141,69294,57860[L

]11,74,52,34,2[1,5/4,2)

]103,35,41,5[LmLL

3

13133

2

12122

(

42


Exemplo 10:

A matriz ampliada fica da forma:

Como o elemento já é o pivô da 2ª

coluna, tem-se:

1,37864,90714,22140

5,82141,69294,57860

11,74,52,34,2

]3,98863,346300[L

]5,82141,69294,57860[5786)(4,2214/4,

]1,37864,90714,22140[LmLL

3

23233

4,5786

43


Exemplo 10:

A matriz ampliada fica na forma:

3,9886-3,346300

5,82141,69294,57860

11,74,52,34,2

44


Exemplo 10:

A solução do sistema triangular que resultou dessas operações é:

x3 = -3,9886/3,3463 = -1,1919

x2 = [5,8214-1,6929(-1,1919)]/(4,5786) = 1,7121

x1 = [11,7- 2,3(1,7121)- 4,5(-1,1919)]/4,2 = 3,1252

45


Exemplo 9: Exemplo 10 (com pivoteamento):

x3 = -1,1918 x3 = -1,1919

x2 = 1,7121 x2 = 1,7121

x1 = 3,1252 x1 = 3,1251

Solução encontrada no Matlab:

x1 = -1,19198135198135

x2 = 1,71216783216783

x3 = 3,12522144522145

46

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.

47

Método de Jordan

Sistema diagonal equivalente:

nn

33

22

11

a000

0a00

00a0

000a

]A[

48

Método de Jordan

Exemplo 11:

A partir do sistema:

Com matriz aumentada:

4x2x3x2

2x3x2x5

1xx5x

321

321

321

4232

1151

2325

4232

2325

1151

Ab

49

Método de Jordan

Exemplo 11:


Substituindo a linha 3 por :

0,21/5

a

a

m0,60,44,60L

,2325(1/5)1151LmLL

11

21

212

12122

,

0,42/5

a

a

m3,20,82,20L

2325(2/5)4232LmLL

11

31

313

13133

,

50

Método de Jordan

Exemplo 11:

A matriz ampliada resulta em:


3,20,82,20

0,60,44,60

2325

Ab

8, 0,472,2/4,6

a

a

m2,9130,60900L

0,60,44,60(2,2/4,6)3,20,82,20LmLL

22

32

323

23233

51

Método de Jordan

Exemplo 11:

A matriz ampliada resulta em:

Substituindo a linha 2 por

913,2609,000

6,04,06,40

1325

Ab

1,31304,60L

2,9130,60900)(0,4/0,609

0,60,44,60LmLL

2

32322

52

Método de Jordan

Exemplo 11:

Matriz ampliada resulta em:

Substituindo a linha 1 por

913,2609,000

313,106,40

1325

Ab

2/4,6

a

a

m,1,571305L

,1,31304,60(2/4,6)1325L

22

12

121

1

53

Método de Jordan

Exemplo 11:


A matriz ampliada fica da seguinte forma:

3/0,609

a

a

m12,779005L

2,9130,60900(3/0.609)

1,571305L

33

13

131

1

2,9130.60900

1,31304,60

12,779005

Ab

54

Método de Jordan

Exemplo 11:

E as soluções são:

x1 =-2,556 , x2= -0,285, x3=4,783

55

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

uuu0

uuuu

1lll

0

01ll

001l

0001

LU

56


E a matriz coeficiente A:

Tem-se, então:

nn3n2n1n

n22221

n11211

aaaa

aaa

aaa

A

nn

n333

n22322

n1131211

3n2n1n

3231

21

nn3n2n1n

n22221

n11211

u000

uu00

uuu0

uuuu

1lll

0

01ll

001l

0001

]LU[

aaaa

aaa

aaa

A

57


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

58


1ª linha de U: Faze-se o produto da 1ª linha de L por todas as colunas de U e a iguala com todos os elementos da 1ª linha de A, assim:

.n,...,2,1j,au

,auau1

,auau1

,auau1

j1j1

n1n1n1n1

12121212

11111111

59


1ª coluna de L: Faz-se o produto de todas as linhas de L, (da 2ª a até a nª), pela 1ª coluna de U e a iguala com os elementos da 1ª coluna de A, (abaixo da diagonal principal), obtendo ,

.n,...,2,1l,u

al

,u

alaul

,u

alaul

,u

alaul

11

1l

1l

11

1l

1l1l111l

11

31

31311131

11

21

21211121

60


2ª linha de U: Faz-se o produto da 2ª linha de L por todas as colunas de U, (da 2ª até a nª), e igualando com os elementos da 2ª linha de A, (da diagonal principal em diante), obtêm-se ,

.n,...,3j,ulau

,ulauauul

,ulauauul

,ulauauul

j121j2j2

n121n2n2n2n2n121

1321232323231321

1221222222221221

61


2ª coluna de L: Faz-se o produto de todas as linhas de L (da 3ª até a nª) pela 2ª coluna de U e a iguala com os elementos da 2ª coluna de A, (abaixo da diagonal principal), obtendo ,

.n,...,3l,u

ulal

,u

ulalaulul

,u

ulalaulul

,u

ulalaulul

22

121l2l

2l

22

121l2l

2l2l222l121l

22

124142

424222421241

22

123132

323222321231

62


Temos a seguinte fórmula geral:

.jl,u/)ula(l

,jl,ulau

jjkjlkljlj

1l

1k

kjlkljlj

63


Resumo de Passos:

Seja um sistema Ax = b de ordem n, onde A satisfaz as condições da fatoração LU.

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

LUx = b

64


Resumo dos Passos:

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

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

65


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

66

Erros - Avaliação de Erros

No sistema Ax = b , no qual:

o erro da solução é x – x’ .

n

2

1

n

2

1

nn2n1n

n22221

n11211

b

b

b

b

x

x

x

x

aaa

aaa

aaa

]A[

67

Procedimento de Determinação do Erro

Determinar:

Ax’ = b’

Erros - Avaliação de Erros

68

Erros – Resíduo

Procedimento de Determinação do Erro

Fazer:

Resíduo = b – b’

Resíduo = b – b’ = Ax - Ax’ = A(x – x’) = Aerro

69

Erros – Resíduo

Verifica-se que:

O resíduo não é o erro, apenas uma estimativa do mesmo;

Quanto menor for o resíduo, menor será o erro.

70

Exemplo 12:

Refinar a solução do sistema:

Cuja solução encontrada através pelo método de Gauss, utilizando a solução retroativa é:

1,1918]´- 1,7121 [3,1252x(0)

Erros – Resíduo

9,8x8,7x7,5x7,2

7,11x5,4x3,2x2,4

10x3,3x4,5x5,1

321

321

321

71

Exemplo 12:

O resíduo calculado é:

Vê-se pelo resíduo que a precisão

alcançada não foi satisfatória.

O vetor x(0) é chamado de vetor solução.

0.0010

0.0006

0.0002

Axbr(0)(0)

Erros – Resíduo

72

Exemplo 12:

Com o intuito de melhorar a solução, considera-se um novo vetor x(1) chamado de vetor solução melhorado.

Erros – Resíduo

73

Exemplo 12:

De forma que : x(1) = x(0) + δ(0), onde δ(0) é o vetor de correção. Assim:

)0()0(

)0()0(

)0()0(

)0()0(

)1(

rA

AxbA

bAAx

b)x(A

bAx

Erros – Resíduo

74

Exemplo 12:

Calcular o vetor de correção:

0,0010

0,0006

0,0002

δ

δ

δ

3

2

1

.

9,88,77,57,2

7,115,43,22,4

103,34,55,1

Erros – Resíduo

75

Exemplo 12:

A solução é:

0,0002

0,0001

0,0000

(0)

δ

Erros – Resíduo

76

Exemplo 12:

Desta forma, a solução melhorada será:

1920,1

7122,1

1252,3

δxx)0()0()1(

Erros – Resíduo

77

Exemplo 12:

Cujo novo resíduo é:

0,0000

0,0000

0,0000

Axbr(1)(1)

Erros – Resíduo

78

Exemplo 12:

Em exemplos onde o resíduo ainda não seja satisfeito pode-se utilizar o mesmo procedimento:

x(2)=x(1)+δ(1)

Assim, o vetor correção δ(1), será calculado por A δ(1) =r(1).

Erros – Resíduo

79

Exemplo 12:

Acha-se assim, sempre uma solução melhorada e com resíduo tendendo a zero.

Erros – Resíduo

80

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.

Asano, C. H. & Colli, E. Cálculo Numérico: Fundamentos e Aplicações. Departamento de Matemática Aplicada – IME/USP, 2007.

Sanches, I. J. & Furlan, D. C. Métodos Numéricos. DI/UFPR, 2006.

Paulino, C. D. & Soares, C. Erros e Propagação de Erros, Notas de aula, SE/ DM/ IST [Online] http://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_2004-2005/PE_erros.pdf [Último acesso 07 de Junho de 2007].

Documents

Resolução Numérica de Sistemas Lineares Parte I · 8 Classificação III Possível Possui 1 ou mais soluções Indeterminado Mais de uma solução Exemplo 05 Sistemas Lineares