Curso Online de Matrizes - Fatoração LU

fausset – carlos alberto sassi
2010

matrizes – fatoração lu

introdução

nos capítulos anteriores nós usamos a notação de vetor-matriz e operações para resolver sistemas de equações lineares. neste parte e nos próximos nós investigaremos métodos para resolver problemas relacionados a algebra linear. nós vamos considerar a fatoração de uma matriz em produto de duas outras matrizes l, matriz inferior triangular e u matriz superior triangular para uma matriz 3 x 3 o problema é encontrar l e u, tal que lu = a, isto é:

existem dois métodos para encontrar a fatoração lu, o método de gauss (eliminação) e computação direta. o primeiro cria uma matriz triangular superior durante o processo de eliminação e a correspondente matriz inferior com 1’s na diagonal principal, onde esta pode ser construída com os multiplicadores usados na eliminação. no caso de matrizes tri-diagonais a fatoração pode ser obtida muito eficientemente pelos vetores contidos na diagonal principal, e elementos acima e abaixo desta.
o segundo método de decomposição direta, é mais generalizado e que se obtém seguindo o fato de que a fatoração lu não é única. os três mais importante são as diferentes formas possíveis dos elementos da diagonal principal. a forma doolittle, com 1’s na diagonal principal de l, nos da os mesmos fatores produzidos pela eliminação gaussiana. a forma crout tem 1’s na diagonal principal da matriz u. enquanto que a forma cholesky tem os elementos das diagonais tanto de l e u iguais., isto é e isto é muito importante no caso de matrizes simétricas positivas definidas, desde que no caso preserva a simetria e produz uma fatoração l = u’. para matrizes simétricas positivas definidas uma modificação na forma de cholesky da a fatoração ldi. a fatoração lu de a pode ser usada para resolver problemas de sistemas de equações lineares, especialmente quanto ax = b.

deve ser resolvido repetidas vezes usando a matriz a, com diferentes valores de b. a fatoração lu também pode ser usada para encontrar a inversa de a e o determinante de a.
exemplo: 1. – aplicação na análise de circuitos elétricos.
consideremos o problema de encontrar a corrente nas diferentes partes do circuito elétrico mostrado na figura 1. suponha agora que desejamos investigar o efeito de mudanças nas variações de voltagens e queda de voltagens nos sub-circuitos. as equações para os três loops podem ser escritas de uma forma geral como segue:

nos podemos resolver um novo circuito eficientemente pelo método figura 1
fatoração lu dos coeficientes da matriz (os quais não mudam desde que não se modificam os resistores e suas dimensões).

sumário

apresentação
1 lu fatoração – gaussiana
2 fatoração lu de matrizes tri-diagonais
3 fatoração lu com pivo
4 fatoração lu direta
4.41. fatoração doolittle.
5 fatoração lu cholesky
6 fatoração lu – aplicações.
7 fatoração lu – problemas.

capítulo i –lu fatoração gaussiana

o processo de eliminação de gauss forma a base para encontrar a representação da matriz a conhecida como fatoração lu. a matriz inferior triangular l , com 1’s na sua diagonal principal pode ser encontrada pelos multiplicadores utilizados na eliminação gaussiana. o processo de eliminação transforma a matriz original a em uma matriz triangular superior u. a matriz inferior triangular l é formada pelos multiplicadores (inversos negativos) que foram usados no processo de eliminação em posições apropriadas a matriz inferior, conforme exemplo a seguir:
exemplo 2. sistema 3 x 3.
nós inicialmente ilustramos a fatoração lu para as matrizes inicializadas por l = i e u = a, então temos:

1º passo – a primeira linha de u permanece inalterada.
multiplicar a primeira linha por -2, e adicionar o resultado a segunda linha.
armazenar o negativo do multiplicador de primeira na primeira coluna, segunda linha de l.
também multiplicar a primeira linha por -3 e adicionar o resultado a terceira linha.
armazenar o negativo do multiplicador na primeira coluna, terceira linha de l.
os resultados das matrizes são:

capítulo i –lu fatoração gaussiana

2º passo – a primeira e a segunda linhas de u permanecem inalteradas.
multiplicar a segunda linha por -4 e adicionar o resultado a terceira linha.
armazenar o negativo do multiplicador na segunda coluna, terceira linha de l.
as matrizes resultantes são:

multiplicar l por u, para verificar o resultado.

capítulo i –lu fatoração gaussiana

exemplo 3. – sistema 4 x 4.
nós agora vamos considerar a fatoração lu para uma matriz 4 x 4.

1º passo –linha 1 permanece inalterada e linhas de 2 a 4 são modificadas para:

capítulo i –lu fatoração gaussiana

2º passo linhas 1 e 2 permanecem inalteradas, e linhas 3 e 4 são transformadas em:

3º passo a linha 4 é então alterada para concluir o estágio final.

capítulo i –lu fatoração gaussiana

exemplo 4 – fatoração lu para resolver o circuito elétrico.

as matrizes após o primeiro estágio da eliminação gaussiana são:

as matrizes após o segundo estágio da eliminação gaussiana são:

capítulo i –lu fatoração gaussiana

resolvendo o sistema ai = lui = v, fazendo y = ui então ly = v

donde,
resolvendo o sistema ui = y

donde,

capítulo ii – fatoração de matrizes tridiagonais.

como nós encontramos com a eliminação gaussiana, a fatoração lu de matrizes tridiagonais t pode ser obtida usando muito menos cálculos computacionais (e menos memória de computador para armazenamento das matrizes), que para o caso de matrizes completas da mesma dimensão.
função matlab para fatoração de matrizes tridiagonais. nos codematlab que segue, os multiplicadores são armazenados no vetor bb e que forma a diagonal da matriz l, pode ser escrito diretamente do vetor l da original, e a modificação da diagonal principal da matriz triangular superios, dd, pode ser escrito acima da diagonal d acima da original.
exemplo 5. – fatoração lu de um sistema tridiagonal.
consideremos novamente um sistema 4 x 4 de matriz tridiagonal que segue:

podemos representar pelos vetores

para este exemplo, n= 4, temos os seguintes passos na função matlab