MS211 - Cálculo NuméricoAula 6 – Variações do Método da Eliminação de Gauss e da

Fatoração LU.

Marcos Eduardo Valle

O método da eliminação de Gauss e a Fatoração LU podem seradaptados para certos tipos de matrizes que surgem em muitassituações práticas.

Nesse casos, informações adicionais sobre a estrutura da matrizsão consideradas de forma a reduzir o esforço computacional dométodo numérico.

Na aula de hoje, veremos variações do método da eliminação deGauss e da fatoração LU.

Matriz Diagonalmente Estritamente Dominante

Para algumas matrizes, o método da eliminação de Gauss podeser aplicado sem a estratégia de pivoteamento parcial.

Definição 1

Dizemos que A ∈ Rn×n é uma matriz diagonalmenteestritamente dominante se

|aii | >∑j 6=i

|aij |, ∀i = 1, . . . ,n.

Exemplo 2

Determine quais matrizes são diagonalmente estritamentedominante:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Exemplo 2

Determine quais matrizes são diagonalmente estritamentedominante:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Resposta: A única matriz diagonalmente estritamentedominante é a matriz B.

Teorema 3Se A ∈ Rn×n é uma matriz diagonalmente estritamentedominante, então A é não-singular. Sobretudo, o sistema linearAx = b pode ser resolvido usando o método da eliminação deGauss sem pivoteamento.

A demonstração desse teorema pode ser encontrada em:“Análise Numérica, R. L. Burden e J. D. Faires. Editora Pioneira,2003”.

Matriz Simétrica

Definição 4 (Matriz Simétrica)

Uma matriz A ∈ Rn× é simétrica se AT = A, ou seja,

aij = aji , ∀i , j = 1, . . . ,n.

Exemplo 5

Determine quais matrizes são simétricas:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Matriz Simétrica

Definição 4 (Matriz Simétrica)

Uma matriz A ∈ Rn× é simétrica se AT = A, ou seja,

aij = aji , ∀i , j = 1, . . . ,n.

Exemplo 5

Determine quais matrizes são simétricas:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Resposta: As matrizes A e C são simétricas.

Matriz Definida Positiva

Definição 6 (Matriz Definida Positiva)

Uma matriz A ∈ Rn×n é definida positiva se xT Ax > 0 para todox ∈ Rn, x 6= 0.

Teorema 7 (Decomposição de Cholesky)

Se A ∈ Rn×n é uma matriz simétrica e definida positiva, então Apode ser decomposta de forma única no produto GT G, em que Gé uma matriz triangular superior com diagonal positiva.

Pode-se demonstrar o teorema acima usando a fatoração LU.

A demonstração pode ser encontrada em: “Cálculo Numérico –Aspectos Teóricos e Computacionais, M. Ruggiero e V. Lopes, 2aedição, Editora Pearson, 1997.”

Cálculo do Fator de Cholesky

Seja A ∈ Rn×n uma matriz simétrica e definida positiva.

Vamos admitir que podemos escrever A = GT G, ou seja,a11 a21 . . . an1a21 a22 . . . an2

......

. . ....

an1 an2 . . . ann

=

g11g12 g22

......

. . .g1n g2n . . . gnn

g11 g12 . . . g1ng22 . . . g2n

. . ....

gnn

Efetuando o produto por colunas, encontramos:

• Primeira coluna:a11a21

...an1

=

g11g12 g22

......

. . .g1n g2n . . . gnn

g110...0

=

g2

11g12g11

...g1ng11

Logo,

g11 =√

a11 e g1j =a1j

g11, j = 2, . . . ,n.

• Segunda coluna:a12a22a32

...an2

=

g11g12 g22g13 g23 g33

......

. . .g1n g2n g3n . . . gnn

g12g220...0

=

g11g12

g212 + g2

22g13g12 + g23g22

...g1ng12 + g2ng22

Logo,

g22 =√

a22 − g212 e g2j =

a2j − g1jg12

g22, j = 3, . . . ,n.

• i-ésima coluna:

a1i...

aii...

aji...

ani

=

g11...

. . .g1i . . . gii... . . .

.... . .

g1j . . . gij . . . gjj...

......

. . .g1n . . . gin . . . gjn . . . gnn

g1i...

gii00...0

aii = g21i + . . .+ g2

ii =⇒ gii =

√√√√aii −i−1∑k=1

g2ki ,

aji = aij = g1jg1i + . . .+ gijgii =⇒ gij =1gii

(aij −

i−1∑k=1

gkjgki

),

para j = i + 1, . . . ,n.

Fatoração de Cholesky

Entrada: Matriz A ∈ Rn×n simétrica e definida positiva.para i = 1 : n faça

• gii =

√√√√aii −i−1∑k=1

g2ki .

para j = i + 1 : n faça

• gij =1gii

(aij −

i−1∑k=1

gkjgki

).

fimfimSaída: Matriz G triangular superior com diagonal positiva.

Exemplo 8

Determine, se possível, a fatoração de Cholesky das matrizes

A =

2 −1 0−1 2 −10 −1 2

e C =

6 4 −34 −2 0−3 0 1

.

Exemplo 8

Determine, se possível, a fatoração de Cholesky das matrizes

A =

2 −1 0−1 2 −10 −1 2

e C =

6 4 −34 −2 0−3 0 1

.Resposta: Temos que A = GT G em que

G =

√

2 −1√2

0√32 −

√23

2√3

.Ao tentar fatorar a matriz C, encontra-se a raiz quadrada de umnúmero negativo. Logo, embora simétrica, C não é definidapositiva.

A fatoração de Cholesky pode ser usada para verificar se umamatriz é simétrica e definida positiva; se o método falhar, ahipótese é falsa!

A fatoração de Cholesky requer a metade do número deoperações efetuadas na fatoração LU!

Conhecendo a fatoração de Cholesky, o sistema Ax = b éresolvido em dois estágios:1. GT y = b.2. Gx = y.

No GNU Octave, a fatoração de Cholesky de uma matriz Asimétrica e definida positiva é obtida através do comando:» G = chol(A)

Matriz Banda

Definição 9 (Matriz Banda)

Dizemos que A ∈ Rn×n é uma matriz banda se existem inteiros pe q, com 1 < p,q < n, tais que

aij = 0, se i > j + p ou j > i + q.

O valor p + q + 1 é chamado tamanho da banda. Além disso, p échamado tamanho da banda inferior e q é o tamanho da bandasuperior.

Em muitas situações, encontramos matrizes banda que sãotambém diagonalmente dominante ou simétrica e definidapositiva.

Exemplo 10

Determine quais matrizes são banda e, no caso afirmativo, otamanho da banda:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Exemplo 10

Determine quais matrizes são banda e, no caso afirmativo, otamanho da banda:

A =

[2 −1 0−1 2 −10 −1 2

], B =

[7 2 03 5 −10 5 −6

]e C =

[6 4 −34 −2 0−3 0 1

].

Resposta: As matrizes A e B são matrizes banda comp = q = 1, ou seja, o tamanho da banda é p + q + 1 = 3.

Definição 11 (Matriz Tridiagonal)

Uma matriz banda A ∈ Rn×n com p = q = 1 é chamada matriztridiagonal.

De um modo geral, uma matriz A ∈ Rn×n tridiagonal é da forma:

A =

a1 c1b2 a2 c2

b3 a3 c3. . . . . . . . .

bn−1 an−1 cn−1bn an

O método da eliminação de Gauss e a fatoração LU sãodeterminados de modo a introduzir zeros apenas no lugar doselementos b2,b3, . . . ,bn.

Fatoração LU

A fatoração LU de uma matriz tridiagonal é da forma:

A =

1β2 1

β3 1. . . . . .

βn−1 1βn 1

︸ ︷︷ ︸

L

α1 c1α2 c2

α3 c3. . . . . . . . .

αn−1 cn−1αn

︸ ︷︷ ︸

U

.

Identificando A = LU, concluímos que

α1 = a1, βi =bi

αi−1e αi = ai − βici−1, ∀i = 2, . . . ,n.

Algoritmo de Thomas

A solução de um sistema linear tridiagonal Ax = b pode serobtida resolvendo os sistemas sistemas lineares Ly = b e Ux = y.

Usando os fatores L e U obtidos anteriormente, concluímos que

y1 = b1 e yi = bi − βiyi−1, ∀i = 2, . . . ,n,

exn =

yn

αne xi =

yi − cixi+1

αi, ∀i = n − 1, . . . ,1.

Esta técnica, conhecida como algoritmo de Thomas, permitecalcular a solução do sistema linear tridiagonal com O(n)operações aritméticas.

Considerações Finais

Na aula de hoje apresentamos duas variações do método daeliminação de Gauss e da fatoração LU:• Fatoração de Cholesky:

Uma matriz simétrica (A = AT ) e definida positiva (xT Ax > 0)é escrita como A = GT G, em que G é triangular superior.

• Algoritmo de Thomas:Modificação do método da eliminação de Gauss/fatoração LUpara um sistema linear tridiagonal.

Esses dois tipos de matrizes aparecem em diversas aplicações!

Muito grato pela atenção!