Métodos de decomposição LU

Métodos de decomposição LU

(Parte 1 de 2)

Métodos de decomposição LU

A decomposição LU é das técnicas mais usadas para resolver sistemas de equações algébricas. Vamos abordar dois tipos de decomposição LU: por eliminação de Gauss e pelo método de Crout.

A eliminação de Gauss pode ser usada para decompor uma matriz dos coeficientes [A], em duas matrizes [L] e [U], onde [U] é uma matriz triangular superior (todos os elementos abaixo da diagonal principal são nulos), e [L] é uma matriz triangular inferior. Seja [A] uma matriz quadrada, por exemplo 3x3,

A = ú

Através de passos de eliminação, podemos reduzir a matriz original dos coeficientes, [A], numa matriz [U]

A = œ

O 1º passo na eliminação de Gauss é multiplicar a 1ª linha da matriz [A] pelo a e subtrair este resultado à 2ª linha de [A], eliminando 21a. Igualmente,

a , e subtrai-se este resultado à 3ª linha de

modo a eliminar 31a. O passo final (note-se que é uma matriz 3x3) consiste em

A matriz [L]é uma matriz triangular inferior, cujos os elementos da diagonal principal são 1’s e os restantes elementos são os factores f21, f31, f32

Multiplicando as matrizes [L] e [U], obtemos a matriz original [A]. A eliminação de Gauss representa uma decomposição LU de [A]. O exemplo seguinte mostra uma aplicação deste método. Considerando um sistema de três equações:

zyx yx zyx

Este sistema pode ser representado matricialmente por Ax = b, ou seja

ºØ z

Aplicando os passos de eliminação, que consistem em subtrair a certas linhas múltiplos de outras linhas, obteve-se um sistema Ux = d

ºØ z

O 1º passo da eliminação consistiu em subtrair à 2ª linha a 1ª multiplicada por 3.

No 2º passo multiplicou-se a 1ª linha por –1/2 e subtraiu-se à 3ª linha. O último passo (neste caso por ser uma matriz 3x3), consistiu em subtrair à 3ª linha a 2ª multiplicada por –5/4. A matriz [L] será:

L = œ

Note-se que os elementos por baixo da diagonal principal são exactamente os multiplicadores 3,-1/2, -5/4, utilizados nos passos do processo de eliminação, e verificase a seguinte igualdade: [L]{ Ux – d } = Ax – b, de onde se conclui que:

LU = A ۜ

e que

Ld = b Û œ œ œ

Esta decomposição é um algoritmo eficiente para decompor a matriz [A] nas matrizes [L] e [U]. Seja [U] uma matriz 4x4, triangular superior com 1’s na diagonal principal:

U =

u u u

L =

e [L] uma matriz triangular inferior

l l l l

Poderemos então escrever LU = A,

l l l l u u u

O método de Crout derivado através da multiplicação de matrizes do lado esquerdo ( L e U ) e depois equacionando os resultados para o lado direito.

Recorrendo às regras de multiplicação de matrizes, e para matrizes 4x4 temos os seguintes passos:

1º passo - Multiplicar as linhas de [L] pela 1ª coluna de [U].

Como se pode observar a 1ª coluna de [L] é a 1ª coluna de [A]. Generalizando este resultado temos :

1il = 1ia , para i = 1,2,...,n

2º passo – A seguir a 1ª linha de [L] pode ser multiplicada pelas colunas de [U].

O primeiro resultado (11l= 11a) já foi estabelecido anteriormente. As restantes relações podem ser generalizadas por:

aujj= , para j = 2,3,,n

3º passo – Da 2ª à 4ª linha da matriz [L], vamos multiplicá-las pela 2ª coluna de [U].

12122ulaliii-= , para i = 2,3,,n

Resolvendo estas equações em ordem a 22l , 32l , 42l e generalizando temos:

4º passo – A seguir, os coeficientes da 2ª linha de [U] podem ser calculados multiplicando a 2ª linha de [L] pela 3ª e 4ª coluna de [U].

= , para j =3,3,,n

ulau j -

23213133ululaliiii--=, para i = 3,4, ... , n

Repetindo o processo podemos calcular os outros elementos das matrizes.

3 l ululau j

= , para j = 4,5,, n
34324214144ulululaliiiii---=, para i = 4,5, ... , n

Inspeccionando as equações referentes aos termos gerais, refira-se as seguintes fórmulas concisas para a implementação do método:

(1). 1il = 1ia ,para i = 1,2, ... ,n
aujj= , para j = 2,3,, n
Para j = 2,3,,n-1

kjikijijulal, para i = j, ... , n

(4). j i ikjijk jk l ulau

, para k = j+1, j+2,, n
(5). å

knnknnnn ulal

Observe-se o exemplo seguinte para melhor compreensão deste método.

zyx zyx zyx

De acordo com (1), a 1ª coluna de [L] é idêntica à 1ª coluna de [A].

11l= 2 ; 21l = -1 ; 31l = 3 A equação (2) pode ser usada para calcular a 1ª coluna de [U].

a u== 1/2

Usando a equação (4), podemos calcular o último elemento da matriz [U].

ulau - = = -1

então pode-se escrever L = œ œ œ e U = œ œ œ

(Parte 1 de 2)

Comentários