Álgebra Linear Computacional (ALC) é um conjunto de programas relacionados com operações com matrizes, resolução de sistemas lineares e equações polinomiais que vêm sendo desenvolvidos no Departamento de Matemática da Universidade Federal da Paraíba, em João Pessoa, nos últimos 13 anos. Ainda não foi concluído por falta de tempo. Tudo o que já foi realizado, foi feito nas horas vagas.
É um conjunto de programas bastante ambicioso: calcula forma de
Jordan de uma matriz desde 1989, muito antes que programas famosos como o Maple e o
Mathematica chegassem a fazer isso. Mesmo quando o ALC e os programas famosos conseguem
resolver o mesmo problema, o ALC consegue ser bem mais rápido do que eles pois é um
programa específico para Álgebra Linear, não é de uso geral.
A versão 1.0 do ALC
A primeira versão do ALC foi feita em BASIC no início de 1989. Calculava polinômio característico, polinômio minimal, autovalores, autovetores, determinante, inversa, forma escalonada e forma de Jordan de uma matriz real de ordem no máximo 5 x 5 . Teve uma divulgação restrita a meia dúzia de amigos.
A versão 2.0 de 1991
A segunda versão do ALC começou a ser elaborada no segundo semestre de 1990 e ficou pronta no final de janeiro de 1991. Foi elaborada em Pascal e tinha muitos avanços com relação à primeira versão: agora as matrizes reais podiam ter ordem no maximo 20 x 20 e era calculada a base associada a forma de Jordan da matriz, um assunto que os autores dos livros de Álgebra Linear costumam complicar desnecessariamente.
Além disso, o ALC permite o uso modularizado de suas funções,
independemente da interface do programa.
Assim, o usuário pode adequar às suas necessidades os algoritmos e funções do
programa. Por exemplo, o minúsculo programinha em
Pascal listado a seguir, lê uma matriz digitada pelo teclado e calcula seu polinômio característico.
program Exemplo; { Calculo dos coeficientes do }
{ polinomio caracteristico de }
{$E+,N+,F+,M 65520, 0, 655200} { uma matriz }
uses
FPTCBas, AlgLin, Matrizes, Equação;
var
mat: matriz; { tipo definido em FPTCBAS }
p: polinomio; { tipo definido em EQUAção }
i: byte;
begin
LeMatriz(mat, 2); { procedimento definido em MATRIZES }
PolCaracteristico(mat, p); { procedimento definido em ALGLIN }
Writeln;
Writeln('Coeficientes do polinomio caracteristico: ');
for i := p.grau downto 0 do
Write(p.coef[i]:10:2);
end.
Suas telas coloridas foram elaboradas em vídeo monocromático, por isso suas cores parecem ter sido mal escolhidas.
Ao contrário da versão 1.0 que praticamente não teve divulgação, a versao
2.0 foi elaborado em português e em inglês e a versão em inglês "ganhou o mundo" pela
Bitnet em 1992. Ainda hoje pode ser encontrado em inúmeros locais com nome CLA20.ZIP.
Diversas universidades norte-americanas citam-no entre
os programas recomendados. (Se interessar, verifique isso você mesmo: basta fornecer
o nome cla20.zip a uma ferramenta de busca como o www.google.com ... ! )
A versão 3.0 (ainda não concluída)
Em 1993, comecei a elaborar a versão 3.0 do ALC. Quase que eu o concluía no início de 1994, mas ficou faltando uma interface amigável com o usuário e ser feito um número significativo de testes para detecção de erros de programação.
Essa é a versão mais ambiciosa e pretende ser "definitiva" também. Nela as matrizes podem ser complexas e teoricamente não tem limitação de ordem (mas é claro que essa limitação existe na prática e está relacionada à falta de memória ou à falta de precisão nos cálculos efetuados, entre outros motivos).
Agora, a linguagem utilizada é a linguagem C e o programa pode ser compilado tanto em ambientes DOS/Windows, quanto no sistema Linux.
Na parte de resolução de equações algébricas, o ALC 3.0 usa os algoritmos de Bairstow, Muller e Laguerre para resolução de tais equações (o ALC 2.0 usava apenas o algoritmo de Bairstow). Falta implementar mais um algoritmo para tornar o programa mais eficiente.
A seguir, mostramos o exemplo da resolução de uma equação polinomial
completa de coeficientes complexos que o ALC resolveu em frações de segundo.
Todas as raízes mostradas são testadas pelo programa e é mostrado o número de iterações
e o nome do algoritmo utilizado. Essa
parte do programa que cuida da resolução desse tipo de equação
está disponibilizada
na Internet desde 1996 com nome solveq30.exe.
10 9 8 7 6 5
z + (64+125i)z + (190+66i)z + (2-152i)z + (24+72i)z + (-158-69i)z
4 3 2
+ (-86-112i)z + (-109-85i)z + (116+108i)z + (-110-195i)z + (-98-139i) = 0
===============================================================================
raiz parte real parte imaginaria |p(z)| |q(1/z)| it1 it2 método
-------------------------------------------------------------------------------
1 0.5725908064 0.7010467080 3.9E-17 2.1E-16 5 1 Laguer
2 1.1638727403 0.0728930137 1.4E-16 3.6E-17 4 1 Laguer
3 0.6831487630 -0.5632018937 6.9E-17 9.6E-17 3 1 Laguer
4 0.0863186080 -1.0282635982 4.0E-12 2.9E-12 3 0 Laguer
5 -0.7676603958 -0.6581314875 1.1E-11 9.8E-12 4 0 Laguer
6 -0.5094219096 -0.0088527590 5.4E-12 4.6E-09 3 0 Laguer
7 -0.7135802485 0.7098148039 9.2E-12 8.6E-12 4 0 Laguer
8 -1.7696292382 0.4788145171 1.6E-15 4.7E-18 3 1 Laguer
9 0.2260678284 1.2975156811 3.0E-12 1.9E-13 1 0 Laguer
10 -62.9717069541 -126.0016349855 9.2E+02 2.7E-19 1 0 Laguer
===============================================================================
2/9/1 Inicio as 19:24:32:75 Fim as 19:24:32:75 Tempo gasto:
A parte da resolução de sistemas lineares
está concluída.
A seguir, um exemplo de resolução de um sistema linear com 3 equações, 5
variáveis e coeficientes complexos. Apesar de indeterminado, todas as soluções
são calculadas.
Sistema:
-1-i 4 -0 5 5 -5+5i
-3+5i 5 3 -2 5 i
-5 5 -3 2-4i 4-5i -3+3i
Solucao particular:
-1.34-0.28i -1.51+0.84i 0.71+0.88i 0 0
Base da solucao do homogeneo associado:
-0.45-1.34i -1.03-0.45i -0.30+0.15i 1 0
0.21-0.62i -1.04-0.10i -0.75-0.80i 0 1
Solucao testada e sem problemas
A parte que calcula a forma de Jordan é a mais complicada e ainda
deve ser submetida a muitos testes. Ela depende do bom funcionamento da resolução de
sistemas lineares e da resolução de equações polinomiais. Mostramos a seguir alguns
exemplos com a parte que já está funcionando:
Exemplo 1: Exemplo 2: Exemplo 3:
O que tem sido feito recentemente
Em 2000, retomamos por algumas semanas a programação do ALC. Incorporamos
uma interessante biblioteca de funções chamada Mike's Arbitrary Precision Math Library (MAPM), elaborada por
um engenheiro norte-americano. Com essa biblioteca, é possível calculo aritmético de
precisão arbitrária. Veja a seguir um exemplo de cálculo de determinante e inversa de
uma matriz. Note que o determinante é formado por números inteiros enormes, algo que
normalmente não é possível fazer com as linguagens de programação tradicionais sem o
uso de bibliotecas específicas.
Os algoritmos usados no ALC, bem como referências bibliográficas,
podem ser encontrados na sua documentação METODOS.TXT
e JORDAN.ZIP.
*** CALCULO DA FORMA DE JORDAN DE UMA MATRIZ ***
Forma de usar: [C:\] JORDEMO opcao [ordem_da_matriz]
onde
opcao = -x, para nao usar o formato racional
-q, para usar o formato racional
-a, para gerar os coeficientes aleatoriamente
-aq, para usar o formato racional e gerar os coeficientes
aleatoriamente
Exemplo: [C:\] JORDEMO -a 8
========= Matriz ==========
-2-i -1 -1 -1 -1 -1 -1 -1
1 -1-i 0 0 0 0 0 0
-1 -1 -4-i -5 -5 -5 -5 -5
0 0 1 1-i 0 0 0 0
2-i 4-2i 6-3i 8-4i 9-6i 8-6i 8-6i 8-6i
-2+i -4+2i -6+3i -8+4i -9+5i -9+5i -10+5i -10+5i
4 8 12 16 20 24 27 28
-3 -6 -9 -12 -15 -18 -20 -21
--------- Forma de Jordan ----------
1 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1-i 1 0 0 0 0
0 0 0 1-i 0 0 0 0
0 0 0 0 -1-i 1 0 0
0 0 0 0 0 -1-i 1 0
0 0 0 0 0 0 -1-i 0
0 0 0 0 0 0 0 -1
========= Matriz ==========
3-i -1 -1 -1 -1 -1
1 4-i 0 0 0 0
0 1 4-i 0 0 0
1 2 4 8-i 4 4
7+2i 14+4i 21+6i 29+8i 41+9i 45+12i
-8-2i -16-4i -24-6i -32-8i -40-10i -44-13i
Coeficientes do polinomio caracteristico:
1 -16+8i 55-120i 320+600i -2685-880i 6416-1264i -4979+3272i
2 autovalores:
[ 1 ] 4-i *** multiplicidade 5
[ 2 ] -4-3i *** multiplicidade 1
--------- Forma de Jordan ----------
4-i 1 0 0 0 0
0 4-i 1 0 0 0
0 0 4-i 1 0 0
0 0 0 4-i 0 0
0 0 0 0 4-i 0
0 0 0 0 0 -4-3i
--------- Base associada `a forma de Jordan -----------
0 0 1 -2 1 0
0 1 -2 1 0 0
1 -2 1 0 0 0
-2 1 0 0 0 0
-0 0 2 -3 0 1
-0 -0 -0 -0 -1 1
========= Matriz ==========
2-4i -1 -1 -1 -1 -1
1 3-4i 0 0 0 0
0 1 3-4i 0 0 0
5-6i 10-12i 16-18i 23-28i 24-30i 24-30i
-6+6i -12+12i -18+18i -23+24i -25+26i -24+24i
1 2 3 4 5 4+2i
Coeficientes do polinomio caracteristico:
1 -10+12i -5-68i -92+56i 663-584i -410+380i 2925+1100i
2 autovalores:
[ 1 ] -1+2i *** multiplicidade 2
[ 2 ] 3-4i *** multiplicidade 4
--------- Forma de Jordan ----------
-1+2i 1 0 0 0 0
0 -1+2i 0 0 0 0
0 0 3-4i 1 0 0
0 0 0 3-4i 1 0
0 0 0 0 3-4i 1
0 0 0 0 0 3-4i
--------- Base associada `a forma de Jordan -----------
0 0 0 0 -1 1
0 0 0 -1 1 0
0 0 1 -2 1 0
0 1 -2 1 0 0
1 -2 1 0 0 0
-2 1 0 0 0 0
-------------------- MATDEMO.EXE ----------------------
*** Operacoes com matrizes de numeros complexos ***
(C) 2000, Lenimar Nunes de Andrade, lenimar@mat.ufpb.br
-------------------------------------------------------
Forma de usar: C:\> MATDEMO3 [opcao] [ordem] [dec_impr]
onde
opcao = x, para entrar elementos pelo teclado
a, para gerar elementos aleatoriamente
ordem = ordem da matriz (valor assumido = 4)
dec_impr = numero de casas decimais impressas
(valor assumido = 5)
Exemplo: C:\> MATDEMO4 a 6 4
-------------------- MATDEMO.EXE ----------------------
*** Operacoes com matrizes de numeros complexos ***
(C) 2000, Lenimar Nunes de Andrade, lenimar@mat.ufpb.br
-------------------------------------------------------
---------------------- MATRIZ M -----------------------
-10+36i -38+2i 19+21i 35+26i -28+9i 37-19i 17-15i -8-i
18+4i -12-5i -10-3i -11i -29i -14-3i -31+33i 7-14i
-22-i -12-9i 15i 16+10i -1+36i 26 -3-31i 3+33i
18+2i 5-38i 5+18i 2+33i 19-23i 12-34i 25-7i -20-27i
6+12i 31+31i 33+39i 33+37i 4-37i -33-23i -3i 3+36i
19+8i 38+7i 5-9i 37-17i -37-24i 20+15i 2+16i 22-i
-10-33i 15+29i -38-10i 12-11i -24+33i -14-22i 10+39i 5+38i
-29+4i 11-18i -37+10i -36-25i 33+38i -5-32i -8+3i 2+16i
* As linhas de M sao vetores L.I.
* Traco de M = 16+112i
* Determinante de M = 16783952986277-68338756447644i
------------------ INVERSA DE M -----------------------
-0.00828-0.01477i 0.00360-0.00056i 0.01403+0.00882i 0.00455+0.00266i -0.00626+0.00379i 0.01078-0.00517i 0.00209+0.00390i -0.00698-0.01715i
-0.00017-0.00017i 0.00477+0.00522i -0.00352+0.00930i 0.00083+0.01007i 0.01062-0.00387i -0.00441+0.00084i -0.00331-0.00166i 0.00374+0.01090i
-0.00195+0.00206i -0.00986-0.02336i 0.00383-0.01599i 0.00233+0.00305i 0.00726-0.01196i -0.00814+0.00269i -0.01005+0.00973i 0.00734+0.00419i
0.00399-0.00657i 0.02118-0.00461i 0.01069+0.00413i 0.01313+0.00031i -0.00272-0.00592i -0.00451+0.01811i 0.00087-0.01168i -0.00114+0.01604i
-0.00962-0.00688i -0.00013-0.01863i 0.01289-0.00985i 0.01651-0.00092i -0.00933-0.00383i 0.00226+0.02184i -0.00457-0.00176i 0.00871+0.00374i
-0.00585+0.00365i -0.01089-0.01253i 0.01033-0.01389i 0.00484-0.00070i -0.00480+0.00469i 0.01419+0.00153i -0.00478+0.00777i 0.00370-0.00054i
-0.00192-0.00228i -0.02700-0.01168i -0.00568-0.00805i 0.00811-0.01098i -0.01353+0.00098i 0.01763+0.00607i 0.00499+0.00088i 0.00606-0.01422i
-0.00276+0.00906i -0.01569+0.02137i -0.00651-0.01351i -0.00997-0.00327i -0.00276+0.00787i 0.00841-0.02225i 0.01479-0.00099i -0.02028-0.01875i