Sistemas Lineares
Fatoração LU
Um Pouco de História

Johann Carl Friedrich Gauss (ou Gauß) foi um matemático, astrônomo e físico
alemão. Conhecido como o príncipe dos matemáticos, muitos o consideram o
maior gênio da história da matemática. Seu QI foi estimado em cerca de 240.

Gauss não encontrou nenhum colaborador entre os seus colegas
matemáticos tendo trabalhado sempre sozinho. Mas, se é verdade que o seu
isolamento relativo, a sua compreensão das matemáticas puras e aplicadas, a
sua preocupação com a astronomia e o uso freqüente que faz do latim têm a
marca do século XVIII, é inegável que, nos seus trabalhos, se reflete o
espírito de um novo período. Se, tal como os seus contemporâneos Kant,
Goethe, Beethoven e Hegel, se manteve à margem das grandes lutas
políticas da sua época, a verdade é que, no seu próprio campo, Gauss
expressou as novas idéias da sua época de uma forma muito poderosa.

As suas publicações, a sua abundante correspondência, as suas notas, e os
seus manuscritos mostram que ele possuía uma das maiores virtuosidades
científicas de todos os tempos.

No ano de 1801 Carl Friedich Gauss utilizou o método para calcular a órbita
do asteróide Ceres com pouquíssimas informações (anotações do astrônomo
siciliano Giuseppe Piazzi quem batizou o asteróide com o nome ao observarlo pela primeira vez).

O trabalho de Gauss causou sensação quando Ceres reapareceu na
constelação de virgem, local aproximado aos seus cálculos.

Uma versão preliminar da eliminação de Gauss apareceu pela primeira vez no
livro chinês “Nove Capítulo de Artes Matemática”. Até então o poder do
método não tinha sido reconhecido.

Mais tarde o método foi popularizado quando Willian Jordan (engenheiro
alemão) em 1888 publicou no seu livro de geodésica intitulado “Handbuch der
Vermessungskund”.

Embora as idéias tenham sido conhecidas antes, muitos vezes o credito pela
popularização da decomposição LU é atribuída ao lógico e matemático
britânico Alan Turing (precursor do computador), pelo seu trabalho de 1948
nesse assunto.

Ao final dos anos 1970, a Fundação Nacional de Ciências e o Departamento
de Energia dos EUA financiaram o desenvolvimento de rotinas
computacionais para inverter matrizes e resolver sistemas de equações
lineares. Aquele pesquisa levou a um conjunto de programas Fortran
chamada LINPAC que são uma referencia para muitos algoritmos
computacionais de hoje. Inclusive o chamado MATLAB. As rotinas LIMPAC
estão organizadas em torno de quatro fatorações de matrizes, uma das quais
é a decomposição LU. C.B. Moler, J.J. Dongarra, G.W. Stewart e J.R. Brunch,
os principais programadores do LINPAC, basearam muitas de suas idéias no
trabalho de Jemes Boyle e Kenneth Dritz, do Laboratório Argonne (nos EUA).
Resolução de Sistemas
Lineares

Métodos numéricos

Métodos Iterativos ou Indiretos



Método de Jacobi
Método de Gauss-Seidel
Exatos ou Diretos


Método de Eliminação de Gauss
Fatoração LU
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.
Bibliografia


ANTON, H. & BUSBY, R. Algebra Linear Contemporânea.
Editora Bookman. Porto Alegre. 2006.
RUGGIERO, M.G. & LOPES, V.L.R. Cálculo Numérico –
Aspectos Computacionais, Pearson Education. São Paulo.
1996.
Grupo 1:
Adriana Ferreira
 Carlos Eduardo
 Cláudio Mandacaru
 Michael Ferreira
 Roberto Medeiros
 Rúbia Mayra
