Universidade Tecnológica Federal do Paraná-UTFPR
CÁLCULO NUMÉRICO
Elaborado por: Elaine Harada Teixeira de Oliveira
Universidade Federal do Amazonas
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Resolução de Sistemas Lineares
Métodos Exatos
Fatoração LU
Profª. Dra. Tina Andreolla
Abril de 2008
Resolução de Sistemas
Lineares
• Métodos numéricos
– Exatos ou Diretos
• Método de Eliminação de Gauss
• Fatoração LU
– Métodos Iterativos ou Indiretos
• Método de Jacobi
• Método de Gauss-Seidel
Fatoração (Decomposição)
LU
Seja o sistema linear Ax = b.
O processo de fatoração para resolução deste sistema
consiste em decompor a matriz A dos coeficientes em um
produto de dois ou mais fatores e, em seguida, resolver
uma seqüência de sistemas lineares que nos conduzirá à
solução do sistema linear original.
Por exemplo, se pudermos realizar a decomposição: A = CD,
o sistema linear Ax = b, pode ser escrito:
(CD)x = b
Se y = Dx, então resolver o sistema linear Ax = b é
equivalente a resolver o sistema linear Cy = b, e em
seguida, o sistema linear Dx = y.
Decomposição LU
• A vantagem dos processos de fatoração é que
podemos resolver qualquer sistema linear que
tenha A como matriz de coeficientes.
• Se o vetor b for alterado, a resolução do novo
sistema linear será quase que imediata.
• A fatoração LU é um dos processos de
fatoração mais empregados.
• Nesta fatoração a matriz L é triangular inferior
com diagonal unitária e a matriz U é triangular
superior.
Esquema Prático para a
Fatoração LU
• Observe que teoricamente, para
obtermos as matrizes L e U, devemos
calcular a inversa de Lk−1 e Uk−1.
• Entretanto na prática podemos calcular
L e U simplesmente aplicando a
definição de produto e de igualdade de
matrizes, isto é, impondo que LU = A.
Esquema Prático para a
Fatoração LU
Seja então:
LU =
e a matriz
A=
Esquema Prático para a
Fatoração LU
• Para obtermos os elementos da matriz L e da matriz
U devemos calcular os elementos das linhas de U e
os elementos da colunas de L na seguinte ordem:
• 1ª linha de U: Fazendo o produto da 1ª linha de L
por todas as colunas de U e igualando com os
elementos da 1ª linha de A, obtemos,
Esquema Prático para a
Fatoração LU
• 1ª coluna de L: Fazendo o produto de todas as
linhas de L, (da 2ª a até a nª), pela 1ª coluna de U e
igualando com os elementos da 1ª coluna de A,
(abaixo da diagonal principal), obtemos ,
Esquema Prático para a
Fatoração LU
• 2ª linha de U: Fazendo 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), obtemos ,
Esquema Prático para a
Fatoração LU
• 2ª coluna de L: Fazendo o produto de todas as
linhas de L (da 3ª até a nª) pela 2ª coluna de U e
igualando com os elementos da 2ª coluna de A,
(abaixo da diagonal principal), obtemos ,
Esquema Prático para a
Fatoração LU
• Se continuarmos calculando 3ª linha de U, 3ª coluna
de L, 4ª linha de U, 4ª coluna de L, etc . . ., teremos
as fórmulas gerais:
Aplicação à Solução de
Sistemas Lineares
• Seja o sistema Ax = b de ordem n determinado, onde A
satisfaz as condições da fatoração LU.
• Então o sistema Ax = b pode ser escrito como: LUx = b.
• Transformamos o sistema linear Ax = b no sistema
equivalente LUx = b cuja solução é facilmente obtida.
• Fazendo Ux = y, a equação acima reduz-se a Ly = b.
• Resolvendo o sistema triangular inferior Ly = b,
obtemos o vetor y.
• Substituindo o valor de y no sistema Ux = y obtemos
um sistema triangular superior cuja solução é o vetor x
que procuramos.
• Assim, a aplicação da fatoração LU na resolução de
sistemas lineares requer a solução de dois sistemas
triangulares.
Exemplo 4.2
Seja:
A=
a) Verificar se A satisfaz as condições da fatoração LU.
b) Fatorar A em LU.
c) Através da fatoração LU, calcular o determinante de A.
d) Resolver o sistema Ax = b, onde b = (0, −7, −5)t,
usando a fatoração LU.