A Decomposição na Informática

Introdução

A decomposição de matrizes em LU é uma forma de fatorar uma matriz de modo a se resolver sistemas

de equações de forma mais eficiente do que a tradicional.

Por exemplo, para resolver a seguinte sistema Ax = b da forma tradicional seria encontrando a inversa de

A e multiplicando por b, sendo assim, x = A-¹ * b e assim encontrando x. Se fosse para encontrar milhões de x's

dessa forma, seria necessário um computador para realizar as operações. Porém , os cálculos para encontrar a

matriz inversa de A em uma escala gigantesca seria, devido as limitações computacionais, extremamente custoso e as operações teriam uma frequencia muito baixa.

Então, para resolver esse problema, foi criada a decomposição LU que, ao invés de realizar os inúmeros cálculos para se encontrar

a inversa de A, decompõe A em A = LU e agora fazendo LUx = b onde L e U possuem caracteristicas que fazem esse trabalho muito mais rápido e eficientemente

Como encontrar L e U?

Por exemplo, queremos encontrar os valores de x em Ax = b. Decompondo A em LU temos A = LU onde

O determinante de A tem que ser diferente de 0 e L e U são matrizes triangulares e não singulares (São singulares pois não são inversiveis).

L e U vem do inglês lower e upper respectivamente onde

U é uma matriz triangular superior e é obtida usando a eliminação de gauss.

L é uma matriz triangular inferior e é obtida usando os multiplicadores das etapas de escalonamento da eliminação de gauss usada para encontrar U.

Ficando, LUx = b.

Agora, L(Ux) = b

Ux = y

assim, Ly = b.

Resolvendo essa equações encontramos os valores de y. Como sabemos que Ux = y basta encontrar os valores de x.

A eficiencia desse método está pelo fato de L e U serem matrizes triangulares onde existem 0's em suas composições, assim facilitando e muito os cálculos.