Uma versão modular do Algoritmo de Greville para matrizes
pseudo-inversas*
Carlos Hoppen,
Vilmar Trevisan
UFRGS – Instituto de Matemática
Avenida Bento Gonçalves 9500
91509-900 Porto Alegre - RS - BRASIL
E-mail: [email protected], [email protected].
Muitos problemas nas ciências aplicadas envolvem
a solução do conjunto de equações Ax = b. Quando
A é uma matriz não singular, temos um sistema
determinado cuja solução é x = A-1b. Em muitos
casos, porém, A é matriz singular ou nem mesmo é
matriz quadrada. É nesse contexto que definimos a
matriz pseudo-inversa, também dita matriz inversa
generalizada de A. Essa matriz, denotada por A+,
pode ser caracterizada como a única matriz que
satisfaz as equações
AXA = A
XAX = X
(AX)H = AX
(XA)H = XA
Uma propriedade fundamental dessa matriz é que a
solução do problema de mínimos quadrados
associado ao sistema Ax = b é justamente o vetor
x*= A+ b. Portanto, a noção de inversa generalizada
pode sintetizar a solução de qualquer sistema de
equações lineares.
Esse fato justifica o interesse no desenvolvimento
de algoritmos eficientes para o cálculo dessa matriz.
Dentre os algoritmos algébricos para esse problema,
destacamos o Algoritmo de Greville, um algoritmo
iterativo desenvolvido em 1965 que computa a
matriz pseudo-inversa de A a partir das matrizes
pseudo-inversas correspondentes a algumas de suas
submatrizes. Apesar da simplicidade de sua
especificação formal e do fato de que objetos
algébricos podem ser representados exatamente na
memória do computador, de modo que podem ser
tratados sem perda de precisão e significado, o
Algoritmo de Greville depara com uma dificuldade
comum dos algoritmos algébricos, o crescimento
das expressões intermediárias e o alto custo
operacional decorrente disso.
___________________
•trabalho realizado com apoio FAPERGS, processo 011316.6
Uma técnica para amenizar essa dificuldade é a
utilização de métodos modulares: em um primeiro
estágio, os problemas são resolvidos em diversos corpos
finitos Zp. As soluções são então combinadas para
recuperação da solução racional do problema, através de
ferramentas como o Algoritmo Chinês dos Restos ou o
levantamento p-ádico.
Nosso objetivo nesse trabalho é desenvolver um
algoritmo modular baseado no Algoritmo de Greville
para a obtenção da matriz inversa generalizada,
possibilitando assim a resolução de qualquer sistema de
equações lineares de maneira exata. Além da
implementação
modular
de
um
algoritmo,
introduziremos
outros
aspectos
que
julgamos
importantes. Vamos propor um algoritmo em que as
operações racionais podem ser mantidas modularmente.
Isso será possível pela utilização da representação
modular de números racionais, que permite a
recuperação de números fracionários. De fundamental
importância também será o estabelecimento de cotas
superiores para a solução procurada, já que a escolha dos
primos p que determinam os corpos finitos sobre os quais
aplicaremos o método modular dependem de uma
estimativa a priori do tamanho solução desejada.
Referências
[1] A. Ben-Israel, T.N.E. Greville, Generalized Inverses:
Theory and Applications, John Wiley & Sons, 1974.
[2] M. Lauer, Computation by Homomorphic Images,
Computer Algebra – Symbolic and Algebraic
Computation,
Computing
Supplementum
4,
Springer-Verlag, 139-168, 1982.
[3] M. M. Sanchez, Um algoritmo modular para o
cálculo da matriz pseudo-inversa,, Dissertação de
Mestrado, UFRGS, 1999.
[4] J. Springer, Exact solutions of general integer
systems of linear equations, ACM Transactions on
Mathematical Software, vol. 12, 51-61, 1986
327