Resolução de Sistemas Lineares- Parte 1

• Exemplo 1: Problema da treliça • Treliça: estrutura composta de barras (metálicas

ou de madeira) unidas por rótulas (nós) nas suas extremidades.

• Determinar as componentes horizontal e vertical das forças que atuam nas junções da treliça.

1

23

4

5

6

7

8

9

10

11

12

13

1415

16

171

2

3

4

5

6

7

8

910

F1 F2 F3

Fh Fh

• Forças que atuam na treliça: 17• O número de junções (j) está relacionado com o

número de componentes da treliça (m):

2j-3 = m

Neste caso: 2 (10) – 3 = 17

• Logo, as componentes das forças são determinadas pelas condições de equilíbrio nas junções.

• Condições de equilíbrio:• Junção 2:

• Junção 3:

0

0

045cos45cos

531

541

541

faffaF

faffaF

fffF

y

x

aax

0

0

13

62

FfF

ffF

y

x

• Junção 4:

• Junção 5:

• Junção 6:

0

0

2975

10965

FafffaF

ffaffaF

y

x

0

0

7

84

FF

ffF

y

x

0

0

13119

131298

faffaF

faffafF

y

x

• Junção 7:

• Junção 8:

• Junção 9:

• Junção 10:

0

0

11

1410

FF

ffF

y

x

0

0

1615

1612

affaF

fafF

y

x

0

0

101513

171413

fffaF

fffaF

y

x

0 1716 ffaFx

Junção 10:

Junção 1:

Sistema linear com 17 variáveis

e 17 equações

hx FffaF 1716

hx FffaF 21

),...,,,( 17321 ffff

Um sistema linear com m equações e

n incógnitas pode ser escrito na forma:

coeficientes constantes variáveis

nnmnmm

n

nn

bxaxaxa

bxaxaxa

bxaxaxa

...

...

...

2211

222222121

11212111

mna nb nx

Resolver o sistema linear

Calcular os valores de , caso existam, que satisfaçam as m equações.

)...,,2,1( njx j

• Notação matricial:

onde

é a matriz dos coeficientes.

BXA

mnmm

n

n

aaa

aaa

aaa

A

21

22221

11211

é o vetor das variáveis

é o vetor dos termos independentes

nx

x

x

X2

1

nb

b

b

B2

1

• Consideremos a situação de duas equações e de duas variáveis

solução única retas concorrentes

infinitas soluções retas coincidentes

nenhuma solução retas paralelas

23

32

21

21

xx

xx

1

1x

624

32

21

21

xx

xx

23x

224

32

21

21

xx

xx

Comentário 1: no caso geral de equações

e variáveis também temos estas três situa-

ções: solução única, infinitas soluções e ne-

nhuma solução.

Notação: solução exata

solução aproximada

x

mn

x

RESOLUÇÃO DE SISTEMAS LINEARES nxn

Métodos Diretos: fornecem solução exata, a

menos de arredondamentos e caso exista,

após um número finito de operações.]

Métodos Iterativos: geram uma seqüência de

vetores , dada aproximação inicial ,

que converge para solução , caso exista.

kx 0x x

MÉTODOS DIRETOS

Método de Cramer pertence a esta classe.

• Para calcular o determinante de um sistema 20x20 temos 21x20!x19 multiplicações, mais este número de adições.

• Um computador de 1GHz (109 operações por segundo) levaria 3X104 anos para calcular a solução deste sistema

• Necessitamos de métodos mais eficientes!!!

AAbAxbAAxAbAx de inversa a é onde 1111

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

• O Método da Eliminação de Gauss consiste em transformar o sistema linear original num sistema linear equivalente com matriz dos coeficientes triangular superior.

Sistemas equivalentes têm a mesma solução.

Sistema linear triangular tem solução imediata.

MÉTODOS DIRETOSELIMINAÇÃO DE GAUSS

Teorema 1: Seja um sistema linear. Aplicandosobre as equações deste uma seqüência de operaçõeselementares escolhidas entre:

a) trocar a ordem das equações,b) multiplicar uma equação por constante,c) adicionar um multiplo de uma equação a outra;

obtemos um novo sistema equivalente.

bAx

bxA~~

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

• Suponha . A eliminação e efetuada por colunas.

• O elemento é denominado pivô na primeira etapa. O elemento é o pivô da segunda etapa. O proces-so repete-se até termos um sistema linear triangular.

• Os elementos são os multiplicadores da primeira etapa. Para gerar os zeros da coluna 1 linha i, faça na linha i. Repita o procso para a coluna 2.

11a

0ADet

22a

1111 aam ii

11 LmLL iii

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

Exemplo: seja o sistema linear

3234

22

1423

321

321

321

xxx

xxx

xxx 3/53/223/1

3/53/23/1

1423

32

32

321

xx

xx

xxx

03/24

3/53/23/1

1423

3

32

321

x

xx

xxx

0

5

3

x

12122 LmLL

3

4,

3

13121 mm

13133 LmLL

13/1

3/132 m

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

Problema: Pivô nulo ou próximo de zero!!!!

Estratégia de pivoteamento parcial• No início de cada eliminação de Gauss,

trocando as linhas, escolher para o pivô o maior da coluna j.ija

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

Estratégia de pivoteamento total• No início de cada eliminação de Gauss,

escolher para o pivô o maior entre todos elementos que atuam no processo de eliminação.

• Problema: Muitas operações de comparação!!

ija

MÉTODOS DIRETOS

ELIMINAÇÃO DE GAUSS

Pivoteamento Parcial X Pivoteamento total

parcial continuar

total continuar

150420

77530

63010

5123

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

150420

63010

77530

5123

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

150420

77530

63010

5123

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

152400

61030

73570

5213

2341

2341

2341

2341

xxxx

xxxx

xxxx

xxxx

MÉTODOS DIRETOS

FATORAÇÃO LU

Seja o sistema linear . Este processo de

fatoração consiste em decompor a matriz em

Um produto de dois ou mais fatores.

Exemplo: Seja , então resolver

É equivalente a resolver e depois

.

bxA A

bxA DCAbyC

yxD

MÉTODOS DIRETOS

FATORAÇÃO LU

Na fatoração a matriz é

triangular inferior com diagonal unitária

e a matriz é triangular superior.

LULA

U

MÉTODOS DIRETOS

FATORAÇÃO LU

Teorema da fatoração LUDada uma matriz quadrada nxn. Se

então existe uma única matriz triangular inferior

, com diagonal principal unitária, e uma

única matriz triangular superior , tais

que

, e

0ADet

ijmL

ijuU AUL

n

iiiuA

0

det

MÉTODOS DIRETOS

FATORAÇÃO LU

Exemplo de fatoração LU. Considere

onde

Do método de Gauss sem pivoteamento:

3234

22

1423

321

321

321

xxx

xxx

xxx

234

211

423

A

FATORAÇÃO LU

No último passo foi acrescentados os multiplicadores

Os multiplicadores são definidos como segue: da

equação (linha) j subtraímos a equação (linha) i

multiplicada por , de modo a escalonar a matriz

Continuando o processo:

234

211

423

A

3/103/10

3/23/10

423

3/103/13/4

3/23/13/1

423

ijm

ijm A

FATORAÇÃO LU

Assim, as matrizes L e U são

234

211

423

A

3/103/13/4

3/23/13/1

423

113/4

013/1

001

L

413/4

3/23/13/1

423

400

3/23/10

423

U AUL

FATORAÇÃO LU

Resolvendo o sistema por fatoração LU:

Continuando

0

5

3

x

3234

22

1423

321

321

321

xxx

xxx

xxx

bxA

byL

33/4

23/1

1

321

21

1

yyy

yy

y

yxU 04

3/53/23/1

1423

3

32

321

x

xx

xxx

0

3/5

1

y

FATORAÇÃO LU + PIVOTEAMENTO

Fatoração LU com pivoteamento parcial.Fatoração LU com pivoteamento total.

O pivoteamento pode ser implementado por

meio da matriz de permutação.

Definição: Uma matriz quadrada de ordem n é uma matriz de permutação se pode ser obtida da matriz identidade de ordem n permutando-se suas linhas (ou colunas).

FATORAÇÃO LU + PIVOTEAMENTO

Exemplo de matriz permutação

Seja

Note:

001

100

010

P

413

562

951

562

951

413

001

100

010

AP

562

951

413

A

FATORAÇÃO DE CHOLESKY

Definição: Uma matriz quadrada de ordem n é

definida positiva se .

Definição: A fatoração de Cholesky de uma matriz ,

simétrica positiva, é dada por

com uma matriz triangular inferior com elementos da

diagonal estritamente positivos.

AnT xxAx 0

A

,:onde nnGGGA T

G

FATORAÇÃO DE CHOLESKY

Do teorema LU, temos , onde é uma

matriz diagonal de ordem n. Ainda, se for simétrica,

então e a fatoração escreve-se como:

Portanto,

ADUDLA

TLU

iiTT dLDDLLDLA iidonde

DLG

FATORAÇÃO DE CHOLESKY

Considere a matriz

Calculando os fatores L U

83214

214112

1124

412416

A

81000

1100

0210

412416

1104/1

0124/3

0014/1

0001

83214

214112

1124

412416

A

FATORAÇÃO DE CHOLESKY

Calculando os fatores

ULA

81000

1100

0210

412416

1104/1

0124/3

0014/1

0001

83214

214112

1124

412416

UDLDL e

TLDLA

1000

1100

0210

4/14/34/11

81000

0100

0010

00016

1104/1

0124/3

0014/1

0001

FATORAÇÃO DE CHOLESKY

Enfim,

Ou ainda,

TLDDLA

1000

1100

0210

4/14/34/11

9000

0100

0010

0004

9000

0100

0010

0004

1104/1

0124/3

0014/1

0001

TGGA

9000

1100

0210

1314

9101

0123

0011

0004

FATORAÇÃO DE CHOLESKY

Teorema da Fatoração de Cholesky

Se é uma matriz simétrica positiva definida,

então existe uma única matriz triangular inferior

com diagonal estritamente positiva, tal que

A

G

TGGA

FATORAÇÃO DE CHOLESKY

Resolução de sistemas lineares é semelhante

ao método LU. Seja , então resolver

é equivalente a resolver e

depois .

TGGAbxA byG

yxGT

COMPARAÇÃO DOS MÉTODOS

Fatoração de Cholesky: Primeiro verificar se uma matriz simétrica é definida positiva. Em caso positivo, continuar com o método de Cholesky.O método de Cholesky requer

aproximadamente a metade das operações necessárias para a fatoração LU, da ordem de n3/6 operações.