Estudo da fatoração de matrizes com aplicações na resolução de sistemas lineares e em processamento de imagens

Abstract

A fatoração de uma matriz pode ser aplicada em diversas situações, principalmente aquelas que envolvem processos computacionais como o processamento de imagens (compressão de imagens e identificação de rostos, por exemplo) e a resolução de sistemas lineares. Nesta última, objetiva-se encontrar a solução do sistema Ax = b, quando possível. Este trabalho apresenta um estudo de técnicas de resolução de sistemas lineares através da fatoração da matriz do sistema. Em termos formais, se A ∈ Rm×n e b ∈ Rm, resolver o sistema linear Ax = b consiste em encontrar um vetor x ∈ Rn tal que Ax é a melhor aproximação para b, ou seja, obter um vetor x que minimize ||Ax − b||2, onde ||.||2 é norma vetorial euclidiana. Para os casos em que a matriz A é quadrada, ou seja, m = n e A é uma matriz não singular (det(A) 6 = 0), o problema tem resposta simples: x = A−1b. Entretanto, se o sistema é sobredeterminado, ou seja, m > n, é possível que nenhum x satisfaça Ax = b. Para esses casos, procura-se uma solução aproximada, que minimize ||Ax − b||2 e este problema é conhecido como problema de mínimos quadrados. Neste trabalho foi proposto o estudo dos sistemas lineares em que A é matriz quadrada de ordem n não singular (sistema com solução única) e os sistemas sobredeterminados, ou seja, os casos em que m > n. A fatoração LU e a fatoração de Cholesky foram estudadas e aplicadas aos sistemas do primeiro caso. A fatoração ortogonal (QR) e a Decomposição em Valores Singulares (SVD) foram estudadas e aplicadas na resolução do segundo. Para a primeira, a fatoração A = ̂ Q ̂R reduzida foi calculada. A fatoração SVD foi aplicada no problema de compressão de imagens e também para o reconhecimento de rostos.