O algoritmo lexicográfico

Suponha-se que o polinómio mónico p(x) de grau n tem n raízes alphai. Então, p(x) pode ser escrito como

polgenerico

ondeelementares são polinómios simétricos das raízes, designados por polinómios simétricos elementares. Aqui, N={1,2,…,n} e I[N,p] corresponde ao conjunto de todas as combinações em N de p elementos como descrito no artigo Combinações. Para a representação de polinómios simétricos, uso aqui a mesma notação descrita em Multiplicação de polinómios simétricos. Por exemplo, pode-se escrever

grau4polsim3

no caso de n=4. Como pode ser observado no artigo Raízes de equações polinomiais do segundo e terceiro graus, é conveniente escrever qualquer polinómio simétrico como combinação polinomial dos polinómios simétricos elementares. O algoritmo lexicográfico está orientado para esse objectivo.

Suponhamos que temos um polinómio simétrico e pretendemos escrevê-lo como combinação polinomial dos respectivos simétricos elementares. Começamos por considerar o monómio (simétrico) principal mediante a ordenação lexicográfica. Considera-se o elementar que melhor se ajusta ao grau do monómio principal. Por exemplo, o monómio elementar que melhor se ajusta a [3,2,0,0] é [1,1,0,0] e a [1,2,3,4] é precisamente [1,1,1,1]. A partir daqui, vai-se fazendo a redução dos monómios como é habitual em divisão dos polinómios.

Por exemplo, suponha-se que se pretende reduzir o monómio [3,0,0], então:

divisions

Daqui é óbvio verificar que

parteI

Procedendo da mesma forma para o monómio [2,1,0]:

divisionsI 

De onde vem parteII, como se pretendia.

O ficheiro funcSymmetric.mws contém uma implementação do algoritmo em Maple. No mesmo sítio também incluo o ficheiro algorithm.cpp que implementa o algoritmo em C++.
No caso do Maple, se o polinómio introduzido não for simétrico, o algoritmo não pára uma vez que ainda não fiz essa verificação. Para o utilizar basta fazer

[>read(`funcSymmetric.mws`):
[>simetric(x^3+y^3+z^3,{x,y,z});

obtendo-se a respectiva representação. No caso da implementação em C++, apesar de funcionar, ainda não está completo o projecto.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática. ligação permanente.

Uma resposta a O algoritmo lexicográfico

  1. Pingback: Equações polinomiais – uma observação | Sérgio's space

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s