DanielDeSouzaGrilo_DISSERT

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE CIÊNCIAS EXATAS E DA TERRA
PROGRAMA DE PÓS-GRADUAÇÃO EM MATEMÁTICA
APLICADA E ESTATÍSTICA
Daniel de Souza Grilo
Sobre a Integração Indefinida de Funções
Racionais Complexas: teoria e
implementação de algoritmos racionais
Natal
2015
Daniel de Souza Grilo
Sobre a Integração Indefinida de Funções
Racionais Complexas: teoria e
implementação de algoritmos racionais
Dissertação apresentada ao Pro-
grama de Pós-graduação em Ma-
temática Aplicada e Estatística
da Universidade Federal do Rio
Grande do Norte, para a obtenção
de Título de Mestre em Matemática
Aplicada, na Área de Computação
Algébrica.
Orientador: Nir Cohen
Natal
2015
ii
Grilo, Daniel de S.
Sobre a Integração Indefinida de Funções Racionais
Complexas: teoria e implementação de algoritmos racio-
nais
162 páginas
Dissertação (Mestrado) - Programa de Pós-
graduação em Matemática Aplicada e Estatística da Uni-
versidade Federal do Rio Grande do Norte. Centro de
Ciências Exatas e da Terra. Departamento de Matemá-
tica.
1. Integração indefinida
2. Funções racionais
3. Algoritmos
I. Universidade Federal do Rio Grande do Norte. Centro
de Ciências Exatas e da Terra. Departamento de Ma-
temática. Programa de Pós-graduação em Matemática
Aplicada e Estatística.
Comissão Julgadora:
Prof. Dr. Prof. Dr.
Examinador Interno Examinador Externo
Prof. Dr. Nir Cohen
Presidente
iii
Dedicado a minha família e, in memoriam, a
Manuel Eric Bronstein e
Petrus Thomas Ratajczyk.
iv
Agradecimentos
À Alma Mater e ao PPgMAE/UFRN que me abençoaram e nutriram tanto
com saber quanto com trabalho.
Em seguida, agradeço a todos os mestres que contribuíram para o meu co-
nhecimento acadêmico, em especial aqueles que me influenciaram diretamente na
elaboração deste trabalho. Nominalmente, os Professores Doutores Nir Cohen, Ed-
gar Silva Pereira, Roberto Hugo Bielschowsky, Marcelo Ferreira Siqueira e Vilmar
Trevisan.
Agradeço ainda aos coordenadores e vice-coordenadores do PPgMAE/UFRN
de todos os tempos, pela disposição nobre em cuidar de um programa de pós-
graduação. Uma missão nada trivial. Em especial, agradeço às Professoras Dou-
toras Carla Almeida Vivacqua e Elaine Gouvea Pimentel, por todo o suporte
dado.
Finalmente, agradeço a todos com quem convivo: meus colegas de curso, meus
amigos, minha família e, acima de tudo, àqueles a quem dedico este trabalho,
especialmente minha mãe Márcia Barros de Souza, meu pai José Arimatéia Pi-
taguares Grilo, minha irmã Lara de Souza Barreto e minha amada noiva Ana
Helena Almeida Libanio de Araújo.
v
Resumo
Apresentamos algoritmos de integração indefinida de funções racionais sobre
subcorpos dos complexos, a partir de uma abordagem algébrica. Estudamos o
algoritmo local de Bernoulli e algoritmos racionais de integração para a classe de
funções em questão, a saber, os algoritmos de Hermite; Horowitz-Ostrogradsky;
Rothstein-Trager e Lazard-Rioboo-Trager. Estudamos também o algoritmo de Ri-
oboo para conversão de logaritmos envolvendo extensões complexas para funções
arco tangente reais, quando estes logaritmos surgem da integração de funções
racionais com coeficientes reais. Concluímos fornecendo pseudocódigos e códigos
para implementação no software Maxima relativos aos algoritmos estudados neste
trabalho, e, além disso, a algoritmos para cálculo de mdc de polinômios; decompo-
sição em frações parciais; fatoração livres de quadrados; cálculo de subresultantes,
entre outros algoritmos acessórios ao trabalho. Será também apresentado no
apêndice o algoritmo de Zeilberger-Almkvist para integração de funções hiperex-
ponenciais, bem como seu pseudocódigo e código para Maxima. Como alternativa
aos algoritmos de Rothstein-Trager e Lazard-Rioboo-Trager, apresentamos ainda
um código para o algoritmo de Bernoulli para denominadores livres de quadrados;
e outro para o algoritmo de Czichowski, ainda que este não seja estudado em
detalhes no trabalho, devido às bases teóricas necessárias para o seu entendimento,
as quais se encontram fora do escopo deste trabalho.
Diversos exemplos são fornecidos de modo a demonstrar o o funcionamento
dos algoritmos de integração deste trabalho.
Palavras-chave: Integração Indefinida; Funções Racionais; Algoritmos.
vi
Abstract
We present indefinite integration algorithms for rational functions over sub-
fields of the complex numbers, through an algebraic approach. We study the local
algorithm of Bernoulli and rational algorithms for the class of functions in concern,
namely, the algorithms of Hermite; Horowitz-Ostrogradsky; Rothstein-Trager and
Lazard-Rioboo-Trager. We also study the algorithm of Rioboo for conversion of
logarithms involving complex extensions into real arctangent functions, when
these logarithms arise from the integration of rational functions with real coef-
ficients. We conclude presenting pseudocodes and codes for implementation in
the software Maxima concerning the algorithms studied in this work, as well as
to algorithms for polynomial gcd computation; partial fraction decomposition;
squarefree factorization; subresultant computation, among other side algorithms
for the work. We also present the algorithm of Zeilberger-Almkvist for integration
of hyperexpontential functions, as well as its pseudocode and code for Maxima. As
an alternative for the algorithms of Rothstein-Trager and Lazard-Rioboo-Trager,
we yet present a code for Benoulli’s algorithm for square-free denominators; and
another for Czichowski’s algorithm, although this one is not studied in detail in
the present work, due to the theoretical basis necessary to understand it, which
is beyond this work’s scope.
Several examples are provided in order to illustrate the working of the inte-
gration algorithms in this text
Keywords: Indefinite Integration; Rational Functions; Algorithms.
Lista de Figuras
4.1 Gráfico de 𝑓 próximo do intervalo [−5/4,− 3/4]. . . . . . . . . . . 68
4.2 Gráfico da forma descontínua de ∫ 𝑓 = 𝐹1(𝑥). . . . . . . . . . . . 70
4.3 Gráfico de ∫ 𝑓 = 𝐹2(𝑥). . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4 Comparação das formas contínua e descontínua de ∫ 𝑓 . . . . . . . 73
4.5 Comparação das formas contínua e descontínua de ∫ 𝑓 . . . . . . . 78
Lista de Figuras viii
Sumário
1 Introdução 1
1.1 Motivação e Objetivos do Trabalho . . . . . . . . . . . . . . . . . 1
1.2 Histórico do Problema Abordado . . . . . . . . . . . . . . . . . . 2
1.3 Visão Geral dos Capítulos e Seções . . . . . . . . . . . . . . . . . 6
1.4 Esclarecimentos Acerca do Presente Texto . . . . . . . . . . . . . 8
2 Noções Preliminares 11
2.1 Resultantes e Sequências de Restos Polinomiais . . . . . . . . . . 11
2.1.1 Resultantes e Subresultantes . . . . . . . . . . . . . . . . . 11
2.1.2 Sequências de Restos Polinomiais . . . . . . . . . . . . . . 15
2.2 Fatoração Livre de Quadrados . . . . . . . . . . . . . . . . . . . . 18
3 Integração Indefinida de Funções Racionais Complexas 25
3.1 O Algoritmo de Bernoulli . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 O Algoritmo de Hermite . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Versão Original do Algoritmo de Hermite . . . . . . . . . . 29
3.2.2 Versão Quadrática do Algoritmo de Hermite . . . . . . . . 30
3.2.3 Versão Linear do Algoritmo de Hermite . . . . . . . . . . . 31
3.2.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 O Algoritmo de Horowitz-Ostrogradsky . . . . . . . . . . . . . . . 36
3.3.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 O Algoritmo de Rothstein-Trager . . . . . . . . . . . . . . . . . . 39
3.4.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 O Algoritmo de Lazard-Rioboo-Trager . . . . . . . . . . . . . . . 50
Sumário x
3.5.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Integração Indefinida de Funções Racionais Reais 59
4.1 O Algoritmo de Rioboo para Funções RacionaisReais . . . . . . . 60
4.1.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 Pseudocódigos e Códigos em Maxima 79
5.1 Funções para Manipulação de Polinômios . . . . . . . . . . . . . . 80
5.1.1 Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.2 LC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.3 Mon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.4 Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.1.5 RPoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2 MDC de Polinômios e Resultantes . . . . . . . . . . . . . . . . . . 83
5.2.1 PDiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.2 PPsDiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2.3 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.4 ExGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2.5 HExGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2.6 HFExGCD . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.7 DioExGCD . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.8 DioHExGCD . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2.9 DioHFExGCD . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.10 SubRes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.11 Normalize . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 Fatorações e Frações Parciais . . . . . . . . . . . . . . . . . . . . 94
5.3.1 LFactor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3.2 SQFR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3.3 PFrac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4 Hermite e Horowitz . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4.1 HermO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4.2 HermQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4.3 HermL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
xi Sumário
5.4.4 HorOstro . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5 Logaritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5.1 Bern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5.2 RothTra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.5.3 LaRiTra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5.4 Czi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6 Conversão Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.6.1 Classic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.6.2 Rioboo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.6.3 Rioboo2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.7 Manipuladores de Extensões Algébricas . . . . . . . . . . . . . . . 112
5.7.1 NoSolve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.7.2 DomSolve . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.7.3 LinSolve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.7.4 QuadSolve . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.7.5 CubeSolve . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.7.6 Solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.7.7 RHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.7.8 SolveSys . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.7.9 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.7.10 VerifyRatSols . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.8 Montagem de Integrais de Funções Racionais . . . . . . . . . . . . 119
5.8.1 RealLog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.8.2 ComplLog . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.8.3 InertLog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.8.4 GenList . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.8.5 IRF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6 Considerações Finais 131
6.1 A Integração de Funções Elementares . . . . . . . . . . . . . . . . 131
6.2 O Cenário da Computação Algébrica . . . . . . . . . . . . . . . . 132
6.3 Referências em Computação Algébrica . . . . . . . . . . . . . . . 133
6.4 Acerca dos Códigos para Implementação em Maxima . . . . . . . 134
Sumário xii
A Integração de Funções Hiperexponenciais 143
A.1 O Algoritmo de Almkvist-Zeilberger . . . . . . . . . . . . . . . . . 143
A.1.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
A.2 Pseudocódigos e Códigos para o Algoritmo de Almkvist-Zeilberger 158
A.2.1 DenMult . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
A.2.2 IHF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Capítulo 1
Introdução
1.1 Motivação e Objetivos do Trabalho
O problema da integração indefinida de funções é, como conhecemos, aquele
de encontrar uma função cuja derivada seja precisamente aquela função que
se integra. Por isto, este também é chamado de problema da antiderivação. O
primeiro contato que se tem com este problema geralmente se dá durante os cursos
de Cálculo. Nesta ocasião, o estudante, via de regra, é apresentado a diversas
técnicas de integração que, na maior parte das vezes, necessitam de uma medida de
intuição e heurística para que possam ser utilizadas de maneira apropriada. Não
raro, o processo de integração acaba por depender fortemente de uma mudança de
variável adequada, ou se resume à detecção de algum padrão do integrando que
indique qual expressão dentro de uma tabela de integrais é a solução do problema.
Porém, quando queremos automatizar processos com eficiência através de
implementações em máquinas, apesar de podermos desenvolver códigos heurísticos,
o mais desejável é que se busque por algoritmos de terminação finita que não
contem com recursos que seriam próprios do uso da razão, e que possam ser bem
delimitados por um conjunto finito de tarefas sequenciadas.
Felizmente, o problema da integração de funções pode, de fato, ser automati-
zado de maneira não heurística para certas classes de integrandos. Neste trabalho,
mostraremos como isto pode ser feito para o caso simples em que o integrando é
uma função racional complexa, isto é, a razão entre dois polinômios complexos.
Capítulo 1. Introdução 2
A intenção é expor uma teoria introdutória sobre o problema (e resolução) da
integração indefinida de funções à luz da Computação Algébrica, utilizando algo-
ritmos que são usados ainda hoje em diversos Sistemas de Computação Algébrica
(doravante CAS — do inglês, Computer Algebra System). A resolução algorít-
mica do problema da integração de funções racionais é o ponto de partida para
se entender como buscar uma solução, nas mesmas condições, para o problema
mais geral da integração de funções elementares — uma classe de funções que
engloba o conjunto das funções racionais.
Os algoritmos abordados neste trabalho, com exceção do algoritmo de Ber-
noulli, são classificados como algoritmos racionais, no sentido de que, no curso de
sua execução, não requerem fatorações completas do denominador do integrando
e evitam introduções de constantes algébricas desnecessárias à resolução do pro-
blema, tanto na representação final da integral, quanto durante os cálculos. Além
disso, a base de seu funcionamento são as operações de corpo, isto é, as quatro
operações aritméticas básicas aplicadas, neste contexto, a polinômios. Isto é per-
cebido de maneira muito forte nos constantes cálculos de mdc entre polinômios
que serão realizados.
O desenvolvimento teórico do presente trabalho baseia-se em conceitos da
teoria de Álgebra Abstrata. No que concerne a esta teoria, o que for omitido aqui
poderá ser encontrado entre os capítulos de I a IV, VII e IX de [16].
1.2 Histórico do Problema Abordado
Segundo M. Ostrogradsky [26], tanto Newton quanto Leibniz tentaram desenvol-
ver métodos de integração indefinida para funções racionais reais, semobterem
êxito completo. A abordagem utilizada por Leibniz consistia em fatorar o de-
nominador do integrando sobre os reais, realizar a decomposição completa em
frações parciais e integrar parcela a parcela. Ele obteve sucesso em calcular a
integral de quaisquer termos com denominadores lineares (a menos de uma po-
tência) na decomposição em frações parciais, mas não conseguiu o mesmo para
os denominadores quadráticos de maneira completa.
Continuando os esforços de Leibniz, J. Bernoulli consegue resolver o subpro-
blema da integração de termos com denominadores quadráticos, publicando, no
3 1.2. Histórico do Problema Abordado
Acta Eruditorum de 1703, o que se acredita ser o algoritmo de terminação finita
mais antigo para a integração de funções racionais de que se tem registro [21, Cap.
IX, p. 353], o qual é lecionado ainda hoje em grande parte dos cursos de Cálculo.
Infelizmente, este método, apesar de bastante simples, apresenta uma dificul-
dade computacional proibitiva, que acaba por fazer com que, na prática, ele não
seja utilizado com frequência. A dificuldade em questão é a necessidade de se
saber a fatoração completa do denominador do integrando sobre os reais (o que,
não raro, pode recorrer a expressões envolvendo muitas extensões algébricas) e
decompor o integrando em frações parciais completas com esta dada fatoração (o
que requer muitas operações aritméticas envolvendo diversos termos algébricos
distintos). Por outro lado, além de uma importância histórica, este método possui
uma importância teórica que motiva o seu estudo. Ele é capaz de explicitar a
integral de uma função racional com coeficientes reais como sendo a soma en-
tre uma parte racional real — uma função racional real que dispensa quaisquer
extensões algébricas com unidade imaginária —, e outra parte transcendental
real — formada por somas de logaritmos e arcos tangentes de polinômios com
coeficientes reais. Desse modo, a integral de uma função racional real obtida pelo
método de Bernoulli é ainda contínua no intervalo de definição do integrando, de
modo que o Teorema Fundamental do Cálculo pode ser aplicado corretamente
para o cálculo da integral definida da função original, qualquer que seja o inter-
valo de integração. O método possui ainda uma variante para funções racionais
com coeficientes complexos em geral, em qual caso, a parte racional vem a ser
ainda uma função racional complexa e a parte transcendental pode ser expressa
apenas como uma combinação linear com coeficientes complexos de logaritmos
de polinômios com coeficientes complexos.
Diante destas considerações, a pesquisa por métodos alternativos de integração
de funções racionais prosseguiu, de modo que, no século XIX, este problema já
consistia numa área de pesquisa ativa. Em 1845, M. Ostrogradsky [26] propôs
um método de integração que dispensa qualquer tipo de fatoração (mais ainda,
dispensa qualquer decomposição em frações parciais e introdução de números
algébricos durante os cálculos) e que é capaz de calcular completamente a parte
racional da integral de uma função racional utilizando o corpo de constantes ori-
ginal do integrando, deixando a parte transcendental inerte. Mais precisamente,
Capítulo 1. Introdução 4
o método expressa a parte transcendental como sendo a integral não calculada
de um novo integrando racional completamente determinado e cujo denominador
é livre de quadrados (dito de outro modo, todas as suas raízes possuem multipli-
cidade 1). Este era o método ensinado nas escolas russas naquela época e está
presente em textos de Análise russos mais antigos [10, Cap. VIII, §2]. Foi redes-
coberto por E. Horowitz no século XX, que também apresentou detalhadamente
um estudo sobre a sua complexidade [13], razão pela qual o método recebe, hoje,
o nome de algoritmo de Horowitz-Ostrogradsky.
Porém, no restante do mundo, outros métodos foram descobertos e ensinados.
Um método notável também descoberto no século XIX é o algoritmo de Hermite.
Foi publicado em 1872 [12].
Essencialmente, tanto o método de Ostrogradsky quanto o método de Her-
mite produzem os mesmos resultados. A diferença é que o primeiro condiciona o
problema da integração à resolução de um sistema linear para explicitar tanto a
parte racional quanto o integrando da parte transcendental, enquanto o segundo,
originalmente, utiliza fatorações livres de quadrados do denominador, decomposi-
ção em frações parciais do integrando e a resolução de uma equação diofantina
de polinômios para “retirar partes” do integrando a cada passo e construir a
parte a parte racional sucessivamente, deixando aquilo que não pode ser “retirado”
para formar o integrando da parte transcendental (este processo ocasiona suces-
sivas reduções de potência do denominador de cada parcela das frações parciais,
razão pela qual o método de Hermite é chamado de redução). O modo como
cada algoritmo trabalha reflete apenas na forma final da expressão, mas não na
validade.
Duas melhorias podem ser feitas ao método de Hermite. A primeira dispensa
a necessidade de se decompor o integrando em frações parciais e é conhecida
como versão quadrática do método de Hermite. A segunda dispensa ainda a
necessidade prévia de se conhecer a fatoração livre de quadrados do denominador
— esta é calculada a cada passo do processo —, sendo conhecida como versão
linear do mesmo método e foi proposta por D. Mack [22]. Tais nomenclaturas
derivam da própria complexidade destas versões [2, Cap. 2, §2]. Mantêm, contudo,
o caráter de redução.
Embora os métodos de Ostrogradsky e Hermite não contem com fatorações
5 1.2. Histórico do Problema Abordado
completas do denominador e calculem de maneira satisfatória a parte racional
da integral utilizando somente operações de corpo (isto é, sem introduzir novas
extensões algébricas no corpo de constantes, nem introduzindo funções transcen-
dentais como logaritmos ou arcos tangentes), eles não são capazes de resolver
definitivamente o problema da integração indefinida de funções racionais, uma
vez que só são capazes de fornecer a parte transcendental da integral em termos
de um novo integrando racional. O problema da integração indefinida da parte
transcendental sem fatoração completa permaneceria em aberto por mais de um
século e só viria a ser resolvido recentemente. Em registro, o primeiro método
para a integração da parte transcendental sem fazer uso de fatorações completas
do denominador do integrando foi descoberto de maneira independente por M.
Rothstein [31] e B. Trager [34]. A proposta deste método é descobrir o menor
número de extensões que deve ser feita ao corpo de constantes original do inte-
grando, de modo que a integral possa ser expressa como uma combinação linear
de logaritmos de polinômios cujos coeficientes (tanto da combinação quanto dos
polinômios) pertencem à nova extensão. Uma vez descobertas as extensões neces-
sárias (as quais são as raízes de um polinômio obtido por cálculo de resultantes),
os polinômios que aparecem como argumentos dos logaritmos são determinados
por cálculos de mdc a partir das extensões.
Uma melhoria ao método de Rothstein-Trager foi descoberta e publicada por
D. Lazard e R. Rioboo [17] e, de maneira independente, também por Trager,
apesar de ele não tê-la publicado formalmente [11, Cap. 11, §5]. A ideia por
trás desta melhoria — conhecida como algoritmo de Lazard-Rioboo-Trager — é
utilizar subresultantes para calcular de modo quase direto os argumentos que
aparecem nos logaritmos da parte transcendental, dispensando cálculos de mdc
envolvendo novas constantes algébricas.
Em 1995, uma alternativa aos métodos de Rothstein-Trager e Lazard-Rioboo-
Trager utilizando bases de Gröbner seria proposta por Czichowski [9].
Apesar de os algoritmos de Hermite e Ostrogradsky, combinados com os al-
goritmos de Rothstein-Trager, Lazard-Rioboo-Trager e Czichowski fornecerem
soluções satisfatórias ao problema da integração indefinida de funções racionais,
as fórmulas encontradas para as integrais nem sempre podem ser utilizadas para
calcular corretamentea integral definida de funções racionais reais. É o caso,
Capítulo 1. Introdução 6
por exemplo, quando a integral possui extensões complexas. Felizmente, em con-
formidade com o próprio algoritmo e Bernoulli, Rioboo mostrou em [28] um
método para expressar a integral de uma função racional com coeficientes reais
como sendo também uma função com coeficientes reais, utilizando, tanto quanto
possível, somente operações de corpo e, se necessário, anexando minimamente
extensões reais ao corpo de constantes. Tanto quanto o método de Bernoulli, o
processo não gera novas singularidades (denominadores polinomiais não constan-
tes), o que significa que integral encontrada é, ainda, contínua no intervalo de
definição do integrando original. A ideia é agrupar pares conjugados de logaritmos
complexos que apareçam na expressão complexa da integral e convertê-los em
uma combinação linear envolvendo um logaritmo e funções arcos tangentes, onde
os argumentos de cada parcela são polinômios e todos os coeficientes na expressão
são reais. Obtemos, novamente, uma função contínua no intervalo de definição
do integrando e, dessa forma, também é possível calcular a integral definida de
uma função racional de maneira correta, sem recorrer a métodos aproximativos, e
sim utilizando de maneira direta o Teorema Fundamental do Cálculo, do mesmo
modo que no algoritmo de Bernoulli.
O ponto importante de se combinar os algoritmos racionais mencionados é
que, do mesmo modo como comparamos os algoritmos de Hermite e Horowitz, o
resultado final é essencialmente o mesmo do algoritmo de Bernoulli, tanto no caso
de integração de funções com coeficientes complexos, quanto no caso de funções
com coeficientes estritamente reais, porém a forma deste resultado costuma ser
consideravelmente mais simples, se comparada àquela fornecida pelo método de
Bernoulli.
1.3 Visão Geral dos Capítulos e Seções
Como dissemos na seção 1.1, buscaremos desenvolver algoritmos de integração
indefinida para funções racionais à luz da Computação Algébrica. Com exceção
do algoritmo de Bernoulli, todos os algoritmos que estudaremos procurarão se ater
ao máximo a operações racionais. Como já vimos na seção 1.2, isto quer dizer que
evitaremos, tanto quanto pudermos, introduzir extensões algébricas desnecessárias
durante a resolução dos problemas, e que, via de regra, nos limitaremos a trabalhar
7 1.3. Visão Geral dos Capítulos e Seções
com operações de corpo para obter os resultados desejados. Além de estarmos
interessados em resultados mais simples, a razão para isto reside no fato de
querermos diminuir a complexidade dos algoritmos, mas isto não será tratado com
detalhes neste texto — nosso foco será demonstrar como os métodos funcionam,
e não analisar seu desempenho.
No capítulo 2, estudaremos brevemente conceitos envolvendo resultantes, sequên-
cias de restos de polinômios e fatorações livres de quadrados. Apesar destes conteú-
dos estarem presentes em certos textos de Álgebra, não são comumente estudados,
de modo que sua exposição é razoável no presente texto. São fundamentais para
embasar teoricamente os capítulos posteriores.
No capítulo 3 apresentaremos os algoritmos racionais e não heurísticos para
a integração de funções racionais. Como introdução, apresentaremos o algoritmo
de Bernoulli. Em seguida, estudaremos os algoritmos de Hermite; de Horowitz-
Ostrogradsky; de Rothstein-Trager; e Lazard-Rioboo-Trager. Optamos por omitir
uma apresentação detalhada do algoritmo de Czichowski devido à demanda teórica
para o seu entendimento.
Complementando o terceiro capítulo, o capítulo 4 será dedicado ao problema
da integração definida de funções racionais com coeficientes reais, onde explicita-
remos o algoritmo clássico e o algoritmo de Rioboo para conversão de logaritmos
complexos em uma combinação de funções arco tangente envolvendo apenas
extensões reais, conforme mencionado na seção 1.2.
Apresentaremos, no capítulo 5, códigos para implementação no software Ma-
xima (software livre copyleft do CAS pioneiro Macsyma) que possibilitam a
construção de um programa para integração de funções racionais sobre subcorpos
dos complexos. Os principais são baseados em pseudocódigos presentes em [2,
Caps. 1, 2], os quais também são apresentados juntamente com seus respectivos
códigos no presente trabalho. Aqui, também apresentaremos um código para o
algoritmo de Czichowksi.
O capítulo 6 trará as considerações finais. Falaremos brevemente sobre o
campo da Computação Algébrica como um todo e do problema mais geral da
integração indefinida de funções elementares. Apresentaremos também referências
de literatura acerca do problema da integração de funções em geral. Também
serão feitos alguns comentários acerca do funcionamento dos códigos apresentados
Capítulo 1. Introdução 8
no capítulo 5.
Ao longo do trabalho serão apresentados exemplos que ilustram o funciona-
mento dos algoritmos de integração e dos códigos fornecidos no capítulo 5.
No apêndice A, apresentaremos o algoritmo de Zeilberger-Almkvist para a
integração de funções hiperexponenciais. Trata-se de um algoritmo aplicado a
funções cuja derivada logarítmica seja uma função racional e que é sempre capaz
de encontrar a integral de uma função dessa forma quando a mesma pode ser
expressa como um múltiplo racional seu. Dentre outras classes de funções, pode
ser aplicado a funções racionais, mas diferente dos demais algoritmos estudados,
este nem sempre é capaz de obter uma solução para esta classe de funções. Além
de apresentar este algoritmo, também forneceremos os pseudocódigos e os códigos
para implementação em Maxima relativos ao mesmo.
1.4 Esclarecimentos Acerca do Presente Texto
Antes de prosseguirmos, alguns esclarecimentos são válidos.
1. A sigla “DFU” indica “domínio de fatoração única”. A função cont(𝑎) indica
o conteúdo do polinômio 𝑎, isto é, o mdc de seus coeficientes, enquanto
que pp(𝑎) indica a parte primitiva, definida como sendo 𝑎/ cont(𝑎). cl(𝑝)
indica o coeficiente líder do polinômio 𝑝, isto é, o coeficiente (não nulo)
do termo 𝑥grau(𝑝) em 𝑝. A função pquo(𝑎,𝑏) indica o pseudoquociente da
pseudodivisão de 𝑎 por 𝑏, enquanto prem(𝑎,𝑏) indica o pseudo-resto da
mesma pseudodivisão, isto é, equivalem respectivamente ao quociente e resto
da divisão de cl(𝑏)𝛿+1𝑎 por 𝑏, onde 𝛿 = max(−1, grau(𝑎) − grau(𝑏)). Note
que pquo(𝑎,𝑏) e prem(𝑎,𝑏) são polinômios cujo domínio de coeficientes é o
mesmo que o de 𝑎 e 𝑏 não sendo necessário recorrer a um corpo de frações,
caso o domínio original não seja um. Subscritos 𝑥 como em pp𝑥, cl𝑥, cont𝑥
e prem𝑥 irão indicar que os argumentos destas funções serão tratados como
polinômios na variável 𝑥.
2. 𝐼 é a unidade imaginária, isto é, 𝐼2 = −1.
3. Dois mdc para um par de polinômios serão tratados como iguais a menos
9 1.4. Esclarecimentos Acerca do Presente Texto
de uma multiplicação por elemento do corpo de coeficientes, ou seja, apenas
o grau e a relação entre os coeficientes é importante. Isto quer dizer que a
expressão 𝑔 = mdc(𝑎,𝑏), por exemplo, indica que 𝑔 é um dos possíveis mdc
para 𝑎 e 𝑏.
4. Dados dois polinômios 𝑝 e 𝑞, estes são ditos primos entre si, relativa-
mente primos, ou coprimos, se grau(mdc(𝑝,𝑞)) = 0. Uma fração redu-
zida é aquela em que o numerador e o denominador são primos entre si.
Uma fração própria é aquela em que o grau do numerador é menor que o
grau do denominador.
5. Não estamos interessados nos valores dos logaritmos que aparecem durante
este trabalho, mas nas suas propriedades algébricas. Isto quer dizer que,
sempre que o leitor se deparar com um logaritmo complexo, poderá fixar
qualquer valor para o mesmo, dentro do conceito de ramos de um logaritmo
complexo. Além disso, como a variável de integração será sempre complexa,
não utilizaremos o valor absoluto sobre o argumento dos logaritmos na
integral, ficando implícita a existência de uma parte real e outra imaginária
na fórmula da integral. Por outro lado, caso se deseje uma resposta para
uma variável de integração real, supondoque o integrando seja uma função
racional com coeficientes reais, poderemos, da mesma forma, empregar os
algoritmos aqui estudados e simplesmente substituir os argumentos dos
logaritmos pelos seus valores absolutos no final.
6. Quando quer que haja denominadores mônicos, estaremos supondo que o nu-
merador e o denominador da fração tenha sido multiplicado pelo inverso do
coeficiente líder do denominador para efeitos de simplificação dos cálculos.
7. Os exemplos apresentados seguirão a notação dos códigos e pseudocódigos
apresentados no capítulo 5.
8. Está implícito que 𝑥 é a variável de integração de todas as integrais presentes
neste trabalho, donde omitiremos o diferencial 𝑑𝑥. Sempre que não houver
ambiguidades, a variável 𝑥 também será omitida de expressões funcionais,
isto é, a expressão 𝑓(𝑥) passará a ser representada por 𝑓 .
Capítulo 1. Introdução 10
9. As imagens deste trabalho foram geradas com o apoio do CAS Maple. Já
os códigos foram elaborados no ambiente do CAS Maxima.
Capítulo 2
Noções Preliminares
2.1 Resultantes e Sequências de Restos Polino-
miais
2.1.1 Resultantes e Subresultantes
Estudamos agora as resultantes e subresultantes. A resultante ente dois polinômios
é uma ferramenta que auxilia na detecção de seus fatores comuns, ou mesmo na
detecção de raízes comuns entre os mesmos que estejam no fecho algébrico do
corpo de constantes dos polinômios. As subresultantes de um par de polinômios,
por sua vez, possuem uma relação especial com qualquer sequência de restos
polinomiais gerada por este par e possuem uma importante propriedade algébrica
envolvendo homomorfismos sobre anéis de polinômios induzidos a partir do anel
de coeficientes em questão. Utilizaremos os conceitos de resultante e subresultante
ao estudarmos os algoritmos de Rothstein-Trager e Lazard-Rioboo-Trager.
Definição 2.1.1. Seja 𝑅 um anel comutativo e 𝑝,𝑞 ∈ 𝑅[𝑥] ∖ {0}. Escrevamos
𝑝 = 𝑎𝑚𝑥𝑚 + · · · 𝑎1𝑥 + 𝑎0 e 𝑞 = 𝑏𝑛𝑥𝑛 + · · · 𝑏1𝑥 + 𝑏0, onde 𝑎𝑚 ̸= 0, 𝑏𝑛 ̸= 0 e pelo
menos um entre 𝑚 e 𝑛 é não nulo. A matriz de Sylvester de 𝑝 e 𝑞 é a matriz
(𝑚 + 𝑛)× (𝑚 + 𝑛) definida por
Capítulo 2. Noções Preliminares 12
𝑆(𝑝,𝑞) =
⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝
𝑎𝑚 · · · · · · · · · 𝑎1 𝑎0
. . .
𝑎𝑚 · · · · · · · · · 𝑎1 𝑎0
𝑏𝑛 · · · 𝑏1 𝑏0
. . .
. . .
. . .
𝑏𝑛 · · · 𝑏1 𝑏0
⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠
⎫⎪⎪⎪⎬⎪⎪⎪⎭ n linhas⎫⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎭
m linhas
onde as 𝑝-linhas são repetidas 𝑛 vezes e as 𝑞-linhas são repetidas 𝑚 vezes. A
resultante entre 𝑝 e 𝑞 é o determinante de 𝑆(𝑝,𝑞) e é indicada por res(𝑝,𝑞).
A seguir, enunciamos alguma propriedades algébricas das resultantes.
Lema 2.1.1 ([11], Cap. 9, §5). Sejam 𝑅 um anel comutativo, 𝑝,𝑞 ∈ 𝑅[𝑥] polinô-
mios de graus 𝑚 e 𝑛 respectivamente e 𝑐 ∈ 𝑅 não nulo.
1. res(𝑐,𝑞) = 𝑐𝑛;
2. res(𝑝,𝑝) = 0;
3. res(𝑝,𝑞) = (−1)𝑚𝑛 res(𝑞,𝑝);
4. res(𝑐𝑝,𝑞) = 𝑐𝑛 res(𝑞,𝑝);
5. res(𝑥𝑘𝑝,𝑞) = 𝑏𝑘0 res(𝑝,𝑞) para 𝑘 > 0, onde 𝑏0 é o termo independente de 𝑞;
Lema 2.1.2 ([15] Cap. IV §8, [11] Cap. 9 §5). Sejam 𝑅 um anel comutativo,
𝛼1, . . . ,𝛼𝑚,𝛽1, . . . ,𝛽𝑛𝑎,𝑏 ∈ 𝑅 com 𝑎 ̸= 0, 𝑏 ≠ 0, e polinômios 𝑝 = 𝑎(𝑥−𝛼1) · · · (𝑥−
𝛼𝑚) e 𝑞 = 𝑏(𝑥− 𝛽1) · · · (𝑥− 𝛽𝑛) em 𝑅[𝑥]. Então,
res(𝑝,𝑞) = 𝑎𝑛𝑏𝑚
𝑚∏︁
𝑖=1
𝑛∏︁
𝑗=1
(𝛼𝑖 − 𝛽𝑗) = 𝑎𝑛
𝑚∏︁
𝑖=1
𝑞(𝛼𝑖) = (−1)𝑚𝑛𝑏𝑚
𝑛∏︁
𝑗=1
𝑝(𝛽𝑗).
Como consequência do Lema 2.1.2, podemos deduzir facilmente o corolário
abaixo, analisando as fatorações irredutíveis dos polinômios 𝑝 e 𝑞 abaixo, sobre o
fecho algébrico destes polinômios.
13 2.1. Resultantes e Sequências de Restos Polinomiais
Corolário 2.1.1 ([15] Cap. IV §8). Suponha que 𝐷 seja um domínio de integri-
dade. Seja 𝐾 o corpo quociente de 𝐷 e 𝐾 o fecho algébrico de 𝐾. Então, dados
quaisquer 𝑝,𝑞 ∈ 𝐷[𝑥] ∖ {0},
res(𝑝,𝑞) = 0⇐⇒ ∃𝛾 ∈ 𝐾 tal que 𝑝(𝛾) = 𝑞(𝛾) = 0.
O Corolário 2.1.1 acima nos diz que dois polinômios em um domínio de
integridade 𝐷 possuem raízes comuns no fecho algébrico do corpo quociente de
𝐷 se e só se a resultante entre eles é nula.
Proposição 2.1.1 ([15] Cap. IV §8). Seja 𝑅 um anel comutativo. Para quais-
quer 𝑝,𝑞 ∈ 𝑅[𝑥] de grau positivo, existem 𝜎,𝜏 ∈ 𝑅[𝑥], com grau(𝜎) < grau(𝑞) e
grau(𝜏) < grau(𝑝) tais que res(𝑝,𝑞) = 𝜎𝑝 + 𝜏𝑞.
Em outras palavras, o Proposição 2.1.1 nos diz que a resultante de dois po-
linômios se encontra no ideal gerado por estes. Consequentemente, se 𝐷 é um
DFU, então a resultante de dois polinômios em 𝐷 é nula se e só estes se possuem
um fator comum não trivial. Formalmente temos o resultado abaixo.
Corolário 2.1.2 (Critério de Sylvester, [11] Cap. 7 §3, [2] Cap. 1 §4). Suponha
que 𝐷 seja um DFU. Então, dados quaisquer 𝑝,𝑞 ∈ 𝐷[𝑥]− {0},
res(𝑝,𝑞) = 0⇐⇒ grau(mdc(𝑝,𝑞)) > 0.
Apresentamos agora as subresultantes, que são polinômios obtidos a partir de
submatrizes da matriz de Sylvester. Sua definição formal segue abaixo.
Definição 2.1.2. Sejam 𝑅 um anel comutativo, 𝑝,𝑞 ∈ 𝑅[𝑥] ∖ {0}, 𝑚 = grau(𝑝),
𝑛 = grau(𝑞), 𝑆 a matriz de Sylvester de 𝑝 e 𝑞, e 𝑗 um inteiro tal que 0 ≤ 𝑗 <
min(𝑚,𝑛). Seja 𝑗𝑆 a matriz 𝑚 + 𝑛− 2𝑗 por 𝑚 + 𝑛 obtida deletando-se de 𝑆:
1. as linhas de 𝑛− 𝑗 + 1 até 𝑛 (i.e. as 𝑗 últimas linhas correspondentes a 𝑝),
2. as linhas de 𝑛 + 𝑚− 𝑗 + 1 até 𝑛 + 𝑚 (i.e. as 𝑗 últimas linhas de 𝑞).
Além disso, para 0 ≤ 𝑖 ≤ 𝑗 seja 𝑗𝑆𝑖 a matriz quadrada obtida deletando-se as
colunas de 𝑚 + 𝑛− 2𝑗 a 𝑚 + 𝑛 (i.e. as 2𝑗 + 1 últimas colunas) de 𝑗𝑆, exceto pela
Capítulo 2. Noções Preliminares 14
coluna 𝑚 + 𝑛− 𝑖− 𝑗. A 𝑗-ésima subresultante de 𝑝 e 𝑞 é definida por
𝑆𝑗(𝑝,𝑞) =
𝑗∑︁
𝑖=0
det(𝑗𝑆𝑖)𝑥𝑖 ∈ 𝑅[𝑥].
É evidente que grau(𝑆𝑗(𝑝,𝑞)) ≤ 𝑗 para cada 𝑗. Quando 𝑆𝑗(𝑝,𝑞) < 𝑗 dizemos
que 𝑆𝑗(𝑝,𝑞) é defectiva, e regular em caso contrário. Além disso, 0𝑆0 = 𝑆, donde
𝑆0(𝑝,𝑞) = res(𝑝,𝑞).
Encerrando esta subseção, explicitamos o seguinte resultado a respeito das su-
bresultantes (e, consequentemente, das resultantes), o qual revela uma importante
propriedade sobre as mesmas.
Proposição 2.1.2 ([23] §7.8). Sejam 𝑅 e 𝑆 anéis comutativos, 𝜎 : 𝑅 → 𝑆 um
homomorfismo de anéis, 𝜎 : 𝑅[𝑥]→ 𝑆[𝑥] o homomorfismo de anéis de polinômios
induzido por 𝜎, isto é, satisfazendo
𝜎
(︁∑︁
𝑎𝑗𝑥
𝑗
)︁
=
∑︁
𝜎(𝑎𝑗)𝑥𝑗, (2.1)
e 𝑝,𝑞 ∈ 𝑅[𝑥] ∖ {0}. Se grau(𝜎(𝑝)) = grau(𝑞) então
𝜎(𝑆𝑗(𝑝,𝑞)) = 𝜎(cl(𝑝))grau(𝑞)−grau(𝜎(𝑞))𝑆𝑗(𝜎(𝑝),𝜎(𝑞))
para 0 ≤ 𝑗 < min(grau(𝑝), grau(𝜎(𝑞)).
Em outras palavas, a Proposição 2.1.2 nos fornece um modo de calcular
𝑆𝑗(𝜎(𝑝), 𝜎(𝑞)) a partir de 𝑆𝑗(𝑝,𝑞), quando pelo menos um dos coeficientes lí-
deres de 𝑝 ou 𝑞 não é levado em 0. Ainda, se o homomorfismo 𝜎 não diminui
o grau de 𝑝 e de 𝑞, isto é, grau(𝜎(𝑝)) = grau(𝑝) e grau(𝜎(𝑞)) = grau(𝑞), ou se
ambos 𝑝 e 𝑞 são mônicos, então as subresultantes 𝑆𝑗(𝑝,𝑞), na verdade, comutam
com o homomorfismo 𝜎. Ou seja, passamos a ter:
𝜎(𝑆𝑗(𝑝,𝑞)) = 𝑆𝑗(𝜎(𝑝),𝜎(𝑞))
A Proposição 2.1.2 constitui a chave para se demonstrar o Teorema 3.5.1, o qual é
a base do algoritmo de Lazard-Rioboo-Trager para o cálculo da parte logarítmica
da integral de uma função racional. Durante a demonstração do Teorema 3.5.1,
15 2.1. Resultantes e Sequências de Restos Polinomiais
teremos o homomorfismo 𝜎 : K[𝑧]→ K(𝛼) que é a identidade sobre K ⊆ C e leva
𝑧 em 𝛼, e mostraremos que, para calcular as subresultantes 𝑆𝑗(𝑐,𝑎−𝛼𝑏) ∈ K(𝛼)[𝑥],
onde 𝑎,𝑏,𝑐 ∈ K[𝑥] e 𝛼 é uma extensão algébrica sobre K, podemos simplesmente
calcular 𝑆𝑗(𝑐,𝑎− 𝑧𝑏) ∈ K[𝑧][𝑥] e utilizar
𝑆𝑗(𝑐,𝑎− 𝛼𝑏) = 𝑆𝑗(𝑐,𝑎− 𝜎(𝑧)𝑏) = 𝜎(𝑆𝑗(𝑐,𝑎− 𝑧𝑏)),
evitando, assim, cálculos sobre extensões algébricas do corpo de constantes K
para se obter 𝑆𝑗(𝑐,𝑎− 𝛼𝑏).
2.1.2 Sequências de Restos Polinomiais
Nesta seção, estudamos as sequências de restos polinomiais, que generalizam o
algoritmo de Euclides para o cálculo de mdc. Nosso principal objetivo será de-
senvolver um método eficiente para o cálculo de resultantes e subresultantes. Ao
longo desta seção, 𝐷 seráum domínio de integridade.
Definição 2.1.3. Sejam 𝑝,𝑞 ∈ 𝐷[𝑥] com 𝑞 ̸= 0 e grau(𝑝) ≥ grau(𝑞). Uma
Sequência de Restos Polinomiais (SRP) para 𝑝 e 𝑞 é uma sequência (𝑟𝑖)𝑖≥0
em 𝐷[𝑥] satisfazendo
1. 𝑟0 = 𝑝, 𝑟1 = 𝑞,
2. Para 𝑖 ≥ 1,
𝛽𝑖𝑟𝑖+1 =
⎧⎪⎨⎪⎩0 se 𝑟𝑖 = 0prem(𝑟𝑖−1,𝑟𝑖) se 𝑟𝑖 ̸= 0
onde (𝛽𝑖)𝑖≥1 é uma sequência de elementos não nulos de 𝐷.
Pela definição de SRP, é evidente que 𝑟𝑖+1 = 0 ou grau(𝑟𝑖+1) < grau(𝑟𝑖) para
𝑖 ≥ 1. Portanto, uma SRP sempre possui uma quantidade finita de elementos não
nulos, e se 𝑟𝑖 ̸= 0, 𝑟𝑗 ̸= 0, grau(𝑟𝑖) = grau(𝑟𝑗) e 𝑖,𝑗 ≥ 1, então 𝑖 = 𝑗. Em outras
palavras o grau é estritamente decrescente na sequência, de modo que só 𝑟0 e 𝑟1
podem ter o mesmo grau.
Capítulo 2. Noções Preliminares 16
A escolha de diferentes 𝛽𝑖 na Definição 2.1.3 origina tipos diferentes de SRP.
A SRP euclidiana é obtida tomando-se 𝛽𝑖 = 1 para todo 𝑖, e é simplesmente a
sequência de pseudo-restos sucessivos de 𝑝 e 𝑞, obtidos de modo semelhante ao que
teríamos no algoritmo de Euclides em um domínio euclidiano. Outro exemplo de
SRP é a SRP primitiva, obtida quando definimos 𝛽𝑖 = cont(prem(𝑟𝑖−1,𝑟𝑖)) ∈ 𝐷.
Definição 2.1.4. Sejam 𝑝,𝑞 ∈ 𝐷[𝑥]. Dizemos que 𝑝 é semelhante a 𝑞 se existem
𝛼,𝛽 ∈ 𝐷 ∖ {0} tais que 𝛼𝑝 = 𝛽𝑞.
A similaridade é uma relação de equivalência. O seguinte resultado aponta
para o fato importante de que, se 𝐷 é um DFU, então o último elemento não
nulo de uma SRP do par 𝑝,𝑞 ∈ 𝐷[𝑥] é semelhante a mdc(𝑝,𝑞).
Proposição 2.1.3 ([2] Cap. 1 §5). Suponha que 𝐷 seja um DFU e sejam
𝑝,𝑞 ∈ 𝐷[𝑥] com 𝑞 ̸= 0 e grau(𝑝) ≥ grau(𝑞). Seja (𝑟0,𝑟1, . . . ,𝑟𝑘,0, . . . ) uma SRP
qualquer de 𝑝 e 𝑞 com 𝑟𝑘 ̸= 0. Então mdc(𝑟𝑖,𝑟𝑖+1) é semelhante a mdc(𝑟𝑗,𝑟𝑗+1)
para quaisquer 0 ≤ 𝑖,𝑗 ≤ 𝑘. Em particular (fazendo 𝑖 = 0, 𝑗 = 𝑘), temos que 𝑟𝑘 é
semelhante a mdc(𝑝,𝑞).
Portanto, toda SRP de 𝑝 e 𝑞 contém mdc(𝑝,𝑞) (a menos de um elemento
multiplicativo pertecente ao domínio de coeficientes).
Dada uma SRP qualquer de 𝑝 e 𝑞, o teorema abaixo mostra que toda su-
bresultante não nula de 𝑝 e 𝑞 é semelhante a algum elemento da SRP e traz
fórmulas explicitas para os coeficientes de similaridade, isto é, mostra como as
subresultantes de 𝑝 e 𝑞 podem ser recuperadas a partir de qualquer SRP gerada
por 𝑝 e 𝑞.
Teorema 2.1.1 (Teorema Fundamental das SRP, [11] Cap. 7 §3, [27]). Sejam
𝑝 e 𝑞 ̸= 0 polinômios em 𝐷[𝑥] com grau(𝑝) ≥ grau(𝑞), e seja (𝑟0,𝑟1, . . . ,𝑟𝑘,0 . . . )
uma SRP de 𝑝 e 𝑞 com 𝑟𝑘 ̸= 0. Para 𝑖 = 1, . . . ,𝑘, sejam 𝑛𝑖 = grau(𝑟𝑖) e 𝜌𝑖 o
coeficiente líder de 𝑟𝑖. Então, para qualquer 𝑗 em {0, . . . , grau(𝑞)− 1},
𝑆𝑗(𝑝,𝑞) =
⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩
𝜂𝑖𝑟𝑖 se 𝑗 = 𝑛𝑖−1 − 1,
𝜏𝑖𝑟𝑖 se 𝑗 = 𝑛𝑖,
0 caso contrário
17 2.1. Resultantes e Sequências de Restos Polinomiais
onde
𝜂𝑖 = (−1)𝜑𝑖𝜌1−𝑛𝑖−1+𝑛𝑖𝑖−1
𝑖−1∏︁
𝑗=1
⎡⎢⎣
⎛⎝ 𝛽𝑗
𝜌
𝑙+𝑛𝑗−1−𝑛𝑗
𝑗
⎞⎠1+𝑛𝑗−𝑛𝑖−1 𝜌𝑛𝑗−1−𝑛𝑗+1𝑗
⎤⎥⎦
𝜏𝑖 = (−1)𝜎𝑖𝜌𝑛𝑖−1−𝑛𝑖−1𝑖
𝑖−1∏︁
𝑗=1
⎡⎣⎛⎝ 𝛽𝑗
𝜌
𝑙+𝑛𝑗−1−𝑛𝑗
𝑗
⎞⎠𝑛𝑗−𝑛𝑖 𝜌𝑛𝑗−1−𝑛𝑗+1𝑗
⎤⎦ (2.2)
e
𝜑𝑖 =
𝑖−1∑︁
𝑗=1
(𝑛𝑗 − 𝑛𝑖−1 + 1)(𝑛𝑗−1 − 𝑛𝑖−1 + 1), 𝜎𝑖 =
𝑖−1∑︁
𝑗=1
(𝑛𝑗−1 − 𝑛𝑖)(𝑛𝑗 − 𝑛𝑖). (2.3)
A SRP das subresultantes de 𝑝 e 𝑞 é uma SRP que satisfaz 𝜂𝑖 = 1 no
teorema anterior. É obtida através das seguintes regras de recursão:
𝑟0 = 𝑝, 𝑟1 = 𝑞, 𝛿1 = −1, 𝛽1 = (−1)𝛾1+1
e ⎧⎨⎩ 𝛿𝑖+1 = (− cl(𝑟𝑖))
𝛾𝑖𝛿1−𝛾𝑖𝑖
𝛽𝑖+1 = − cl(𝑟𝑖)𝛿𝛾𝑖+1𝑖+1
para 𝑖 ≥ 1, onde 𝛾𝑖 = grau(𝑟𝑖−1) − grau(𝑟𝑖). Sua propriedade principal é dada
pelo seguinte resultado.
Teorema 2.1.2 ([4] §7, [7, 27]). Sejam 𝑝 e 𝑞 polinômios em 𝐷[𝑥] com grau(𝑝) ≥
grau(𝑞) e (𝑟0,𝑟1, . . . ,𝑟𝑘,0, . . . ) a SRP das subresultantes de 𝑝 e 𝑞, com 𝑟𝑘 ̸= 0 e
𝑛𝑖 = grau(𝑟𝑖) para 𝑖 = 1, . . . ,𝑘. Então,
∀𝑗 ∈ {0, . . . , grau(𝑞)− 1}, 𝑆𝑗(𝑝,𝑞) =
⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩
𝑟𝑖 se 𝑗 = 𝑛𝑖−1 − 1
𝜏𝑖𝑟𝑖 se 𝑗 = 𝑛𝑖
0 caso contrário
onde 𝜏𝑖 é dado pela fórmula 2.2.
O algoritmo das subresultantes, capaz de calcular a resultante de dois
polinômios 𝑝 e 𝑞 deriva do resultado acima. Se grau(𝑝) ≥ grau(𝑞) então, por
definição, temos que res(𝑝,𝑞) = 𝑆0(𝑝,𝑞). Calculando a SRP das subresultantes
Capítulo 2. Noções Preliminares 18
de 𝑝 e 𝑞, temos que se grau(𝑟𝑘) > 0 então 𝑝 e 𝑞 possuem um fator comum, de
modo que res(𝑝,𝑞) = 0. Senão, pelo Teorema 2.1.2 temos que 𝑆0(𝑝,𝑞) = 𝑟𝑘 se
grau(𝑟𝑘−1) = 1, ou 𝑆0(𝑝,𝑞) = 𝜏𝑘𝑟𝑘, se grau(𝑟𝑘−1) > 1. No segundo caso, como
𝜂𝑘 = 0, o cálculo de 𝜏𝑘 fica simplificado, pois 2.3 se torna
𝜎𝑘 =
𝑘−1∑︁
𝑗=1
𝑛𝑗−1𝑛𝑗
e, portanto,
(−1)𝜎𝑘 =
𝑘−1∏︁
𝑗=1
(−1)𝑛𝑗−1𝑛𝑗
No produto acima, um fator −1 so aparece se ambos 𝑛𝑗−1 e 𝑛𝑗 forem ímpares.
Além disso, como grau(𝑟𝑘) = 0, 𝜌𝑘 = 𝑟𝑘 e a equação 2.2 se torna
𝜏𝑘 = (−1)𝜎𝑘𝑟𝑛𝑘−1−1𝑘
𝑘−1∏︁
𝑗=1
⎡⎣⎛⎝ 𝛽𝑗
𝜌
𝑙+𝑛𝑗−1−𝑛𝑗
𝑗
⎞⎠𝑛𝑗 𝜌𝑛𝑗−1−𝑛𝑗+1𝑗
⎤⎦ .
Por outro lado, se grau(𝑝) < grau(𝑞), podemos calcular a SRP de 𝑞 e 𝑝 e utilizar
a fórmula 3 do Lema 2.1.1: res(𝑝,𝑞) = (−1)grau(𝑝) grau(𝑞) res(𝑞,𝑝).
Na subseção 5.2.10, fornecemos um pseudocódigo, juntamente com um código
para implementação no Maxima do algoritmo das subresultantes.
2.2 Fatoração Livre de Quadrados
A fatoração livre de quadrados é um tipo especial de fatoração capaz de agrupar
as raízes de um polinômio de acordo com a sua multiplicidade, mas de maneira
que não seja necessário saber quais são estas raízes (e nem mesmo a fatoração
irredutível do polinômio em questão). Isto é, o fator de potência 𝑘 em uma fatora-
ção livre de quadrados contém todas as raízes (considerando o fecho algébrico do
polinômio) de multiplicidade 𝑘, mas este fator não se decompõe completamente
em termos de suas raízes (a menos que haja só uma raiz).
Este tipo de fatoração possui propriedades especiais de fundamental impor-
tância, como veremos, para o algoritmo de Hermite e, de maneira indireta, para
algoritmo e Horowitz-Ostrogradsky. O algoritmo de Lazard-Rioboo-Trager tam-
19 2.2. Fatoração Livre de Quadrados
bém utiliza esta fatoração em certo ponto.
Definição 2.2.1. Sejam 𝑝 ∈ 𝐷[𝑥] e pp(𝑝) =
𝑛∏︁
𝑖=1
𝑝𝑒𝑖𝑖 a fatoração em fatores
irredutíveis de sua parte primitiva, onde 𝑒𝑖 ≥ 1 para cada 𝑖. Definimos a parte
livre de quadrados de 𝑝 como sendo
𝑝* =
𝑛∏︁
𝑖=1
𝑝𝑖
e para cada 𝑘 ∈ Z, 𝑘 ≥ 0, definimos a 𝑘-deflação (ou 𝑘-ésima deflação, e apenas
deflação quando 𝑘 = 1) de 𝑝 como sendo
𝑝−𝑘 =
𝑛∏︁
𝑖=1
𝑝
max(0,𝑒𝑖−𝑘)
𝑖 =
𝑛∏︁
𝑖|𝑒𝑖>𝑘
𝑝𝑒𝑖−𝑘𝑖 .
Em outras palavras a 𝑘-deflação diminui em 𝑘 unidades a multiplicidade
de cada raiz, mas apenas enquanto a potência da respectiva raiz não se tornar
negativa. Observe que 𝑝−0 = pp(𝑝). Além disso, convencionamos 𝑝− = 𝑝−1 ou
seja,
𝑝− =
𝑛∏︁
𝑖=1
𝑝𝑒𝑖−1𝑖 .
Pela Definição 2.2.1, temos que 𝑝−𝑖+𝑗 = (𝑝−𝑖)−𝑗 , para quaisquer 𝑖,𝑗 ≥ 0, e, por-
tanto,
𝑝−𝑘+1 = (𝑝−𝑘)−. (2.4)
Além disso,
𝑝*𝑝− = pp(𝑝). (2.5)
As equações (2.4) e (2.5) combinadas fornecem
𝑝−𝑘+1 = 𝑝
−𝑘
(𝑝−𝑘)* , para 𝑘 ≥ 0. (2.6)
Em 𝐷[𝑥], o cálculo da parte livre de quadrados e das deflações de um polinômio,
apesar da definição, pode ser feito evitando-se a fatoração em fatores irredutíveis,
bastando que recorramos cálculos de mdc (estamos em um DFU). O Teorema
2.2.1 a seguir nos diz que qualquer fator primo de 𝑝 ∈ 𝐷[𝑥] divide mdc(𝑝,𝑑𝑝/𝑑𝑥)
Capítulo 2. Noções Preliminares 20
uma vez a menos. Além disso, a recíproca vale se 𝐷 tem característica 0, de modo
que, se 𝑝 for primitivo, passamos a ter
𝑝− = mdc
(︃
𝑝,
𝑑𝑝
𝑑𝑥
)︃
(2.7)
e, desta forma, 𝑝* pode ser calculado através de 2.5. As demais deflações de 𝑝
podem ser calculadas recursivamente através de 2.4.
Lema 2.2.1 ([2], Cap. 1, §6). Sejam 𝐷 um DFU, 𝑝,𝑞 ∈ 𝐷[𝑥] ∖ 𝐷 e 𝑛 > 0 um
inteiro. Então,
1. 𝑝𝑛+1 | 𝑞 =⇒ 𝑝𝑛 | mdc(𝑞,𝑑𝑞/𝑑𝑥),
2. se 𝑝 é irredutível e 𝐷 tem característica 0, então 𝑝𝑛 | mdc(𝑞,𝑑𝑞/𝑑𝑥) =⇒
𝑝𝑛+1 | 𝑞.
Sejam 𝐷 um DFU e 𝑥 uma indeterminada sobre 𝐷. As considerações anteriores
nos permitem concluir queé mais fácil calcular partes livres de quadrados e
deflações do que calcular a fatoração em fatores irredutíveis de um polinômio em
𝐷[𝑥]. Isto nos motiva a definir um tipo especial de fatoração.
Definição 2.2.2. Um polinômio 𝑝 ∈ 𝐷[𝑥] é dito livre de quadrados, ou livre
de fatores quadráticos se não existe 𝑞 ∈ 𝐷[𝑥] ∖𝐷 tal que 𝑞2 | 𝑝 em 𝐷[𝑥].
Ou seja, um polinômio é livre de quadrados quando sua fatoração em fatores
irredutíveis sobre 𝐷, ou sobre qualquer extensão de 𝐷 tem todos os expoentes
iguais a 1.
Definição 2.2.3. Seja 𝑝 ∈ 𝐷[𝑥]. Uma fatoração livre de quadrados (flq)
de 𝑝 é uma fatoração da forma 𝑝 =
𝑘∏︁
𝑖=1
𝑝𝑖𝑖 onde cada 𝑝𝑖 é livre de quadrados e
mdc(𝑝𝑖,𝑝𝑗) = 1 para 𝑖 ̸= 𝑗.
Uma vez que os elementos de 𝐷, vistos como elementos de 𝐷[𝑥], são sempre
livres de quadrados por definição, e que 𝑝 = cont(𝑝) pp(𝑝), se pp(𝑝) =
𝑘∏︁
𝑖=1
𝑝𝑖𝑖 é a
flq de pp(𝑝), então
𝑝 = (cont(𝑝)𝑝1)
𝑘∏︁
𝑖=2
𝑝𝑖𝑖
21 2.2. Fatoração Livre de Quadrados
é uma flq de 𝑝. Portanto, só precisamos nos preocupar em calcular a flq da parte
primitiva de um polinômio. Além disso, se 𝐷 possui característica 0, a flq de 𝑝
separa as suas raízes pelas multiplicidades, agrupando em 𝑝𝑖 aquelas com multi-
plicidade 𝑖, pois qualquer raiz de 𝑝 deve ser raiz de exatamente um destes 𝑝𝑖 (os
𝑝𝑖 são coprimos).
Proposição 2.2.1 ([2], Cap. 1, §7, [25]). Sejam 𝑝 ∈ 𝐷[𝑥]∖𝐷, pp(𝑝) =
𝑛∏︁
𝑖=1
𝑝𝑒𝑖𝑖 uma
fatoração em fatores irredutíveis de pp(𝑝), 𝑚 = max(𝑒1, . . . ,𝑒𝑛) e 𝑞𝑖 =
∏︁
𝑗|𝑒𝑗=𝑖
𝑝𝑗
para 1 ≤ 𝑖 ≤ 𝑚. Então,
1. 𝑝−𝑘 =
𝑚∏︁
𝑖=𝑘+1
𝑞𝑖−𝑘𝑖 = 𝑞𝑘+1𝑞2𝑘+2 . . . 𝑞𝑚−𝑘𝑚 para qualquer 𝑘 ≥ 0.
2.
𝑞𝑖 =
𝑝−𝑖−1
*
𝑝−𝑖 *
para 1 ≤ 𝑖 ≤ 𝑚. (2.8)
3. pp(𝑝) =
𝑚∏︁
𝑖=1
𝑞𝑖𝑖 é uma fatoração livre de quadrados de pp(𝑝).
Temos, portanto, uma maneira de calcular os fatores de uma flq de um polinô-
mio em termos de suas deflações e vice-versa. Além disso, se 𝐷 tem característica
0, conseguimos o seguinte algoritmo para calcular a parte primitiva de um po-
linômio: como vimos na subseção anterior, vale em 𝐷[𝑥] a equação (2.7), isto é,
𝑝−1 = 𝑝− = mdc(𝑝,𝑑𝑝/𝑑𝑥), o que nos dá 𝑞1 = (𝑝−0)* = 𝑝* = pp(𝑝)/𝑝−. Indutiva-
mente, se temos (𝑝−𝑘)* e 𝑝−𝑘+1 , então conseguimos calcular
mdc
(︁
(𝑝−𝑘)*,𝑝−𝑘+1
)︁
= mdc(𝑞𝑘+1 · · · 𝑞𝑚,𝑞𝑘+2𝑞2𝑘+3 · · · 𝑞𝑚−𝑘−1𝑚 ) = (𝑝−𝑘+1)*,
e 𝑞𝑘+1 e 𝑝−𝑘+2 podem ser obtidos respectivamente por 2.8 e 2.6. Seguimos até
encontrar o primeiro 𝑘 inteiro positivo tal que 𝑝−𝑘+1 ∈ 𝐷, em qual caso teremos 𝑝−𝑘
livre de quadrados, com 𝑘 = 𝑚−1 e 𝑞𝑚 = 𝑝−𝑘 . Ou seja, conseguimos o algoritmo
de Musser, que encontra uma flq para 𝑝 utilizando apenas operações racionais
e cálculos de mdc em 𝐷[𝑥].
Há, porém, um algoritmo mais eficiente que o descrito acima, que atua através
da redução de grau dos polinômios que aparecem nos mdc de cada iteração. É
Capítulo 2. Noções Preliminares 22
chamado algoritmo de Yun [36]. Mantendo a notação, a ideia é considerar a
seguinte sequência de polinômios:
𝑌𝑘 =
𝑚∑︁
𝑖=𝑘
(𝑖− 𝑘 + 1)𝑑𝑞𝑖
𝑑𝑥
(𝑝−𝑘−1)*
𝑞𝑖
=
𝑚∑︁
𝑖=𝑘
(𝑖− 𝑘 + 1)𝑞𝑘 · · · 𝑞𝑖−1
𝑑𝑞𝑖
𝑑𝑥
𝑞𝑖+1 · · · 𝑞𝑚 para 𝑘 ≥ 1. (2.9)
O lema abaixo traz algumas propriedades desta sequência.
Proposição 2.2.2 ([2] Cap. 1, §7, [36]). Com a notação acima,
mdc((𝑝−𝑖−1)*,𝑌𝑖) ∈ 𝐷,
𝑑𝑝−𝑖−1/𝑑𝑥 = 𝑝−𝑖𝑌𝑖, (2.10)
e com 𝑞𝑖 como definido na Proposição 2.2.1,
𝑌𝑖 −
𝑑(𝑝−𝑖−1)*
𝑑𝑥
= 𝑞𝑖𝑌𝑖+1 (2.11)
para 1 ≤ 𝑖 ≤ 𝑚.
Temos que (𝑝−𝑖−1)* = 𝑞𝑖(𝑝−𝑖)
* e mdc((𝑝−𝑖)*,𝑌𝑖+1) = 1, donde concluímos, por
(2.11) que
mdc
(︃
(𝑝−𝑖−1)*,𝑌𝑖 −
𝑑(𝑝−𝑖−1)*
𝑑𝑥
)︃
= 𝑞𝑖. (2.12)
Esta é a base para o algoritmo de Yun, o qual descrevemos a seguir.
Novamente, suponha que 𝑝 é primitivo. Temos que 𝑝− = mdc(𝑝,𝑑𝑝/𝑑𝑥) e,
portanto,
𝑝−0
* = 𝑝* = pp(𝑝)/𝑝− e 𝑌1 =
𝑑𝑝/𝑑𝑥
𝑝−
por (2.10).
Indutivamente, se temos 𝑝−𝑘−1 * e 𝑌𝑘, 𝑞𝑘 pode ser calculado através de (2.12), e
𝑌𝑘+1 e 𝑝−𝑘
* são obtidos respectivamente por (2.11) e (2.8). Seguimos até que
𝑌𝑘 = 𝑑𝑝−𝑘−1
*
/𝑑𝑥, quando temos que 𝑝−𝑘−1 é livre de quadrados, com 𝑘 = 𝑚 e
𝑞𝑘 = 𝑝−𝑘−1 = 𝑝−𝑘−1
*. Na subseção 5.3.2, fornecemos um pseudocódigo, juntamente
com um código para implementação no Maxima do algoritmo de Yun.
Observamos uma consequência da Proposição 2.2.1. Se o DFU 𝐷 possui
23 2.2. Fatoração Livre de Quadrados
característica 0 e 𝑝 ∈ 𝐷[𝑥] ∖ 𝐷 é primitivo e livre de quadrados então, pelo
item 1 da Proposição 2.2.1, mdc(𝑝,𝑑𝑝/𝑑𝑥) = 𝑝− = 1, pois, neste caso, 𝑚 = 1.
Reciprocamente, se mdc(𝑝,𝑑𝑝/𝑑𝑥) = 1 então 𝑝 = 𝑝−0 é livre de quadrados. Ou
seja,
Teorema 2.2.1 ([11], Cap. 8, §2). Sejam 𝐷 um DFU de característica 0 e 𝑝 ∈
𝐷[𝑥] ∖𝐷 um polinômio primitivo. Então, 𝑝 é livre de quadrados se e só se
grau
(︃
mdc
(︃
𝑝,
𝑑𝑝
𝑑𝑥
)︃)︃
= 0.
Evidentemente, se 𝑝 é um polinômio irredutível então grau(mdc(𝑝,𝑝′)) = 0,
do contrário, 𝑝 possuiria divisor não trivial. Assim, todo polinômio irredutível é
livre de quadrados.
Capítulo 2. Noções Preliminares 24
Capítulo 3
Integração Indefinida de Funções
Racionais Complexas
Apresentamos agora algoritmos de integração de funções racionais sobre um sub-
corpo dos complexos (portanto, de característica 0). O primeiro algoritmo a ser
apresentado é o algoritmo de Bernoulli, que é comumente estudado nos cursos
de Cálculo, mas não costuma ser o método utilizado pelos CAS da atualidade.
Seguimos com o algoritmo de Hermite e suas variantes e o algoritmo de Horowitz-
Ostrogradsky. Ambos são capazes de expressar a integral de uma função racional
como sendo a soma entre uma função racional e a integral de uma função racional
própria cujo denominador é livre de quadrados. Finalizamos apresentando os algo-
ritmos de Rothstein-Trager e de Lazard-Rioboo-Trager, que efetivamente calculam
a integral deixada pelos últimos algoritmos, expressando-a como uma combinação
linear de logaritmos com certas propriedades desejáveis, como veremos.
3.1 O Algoritmo de Bernoulli
Seja 𝑓 = 𝑝/𝑞 ∈ R(𝑥) uma função racional reduzida com coeficientes reais. A
divisão polinomial nos permite expressar 𝑓 = 𝑠 + 𝑟/𝑞, onde 𝑠,𝑟 ∈ R[𝑥], com 𝑟/𝑞
reduzida e própria. Seja
𝑞 =
𝑛∏︁
𝑖=1
(𝑥− 𝑎𝑖)𝑒𝑖
𝑚∏︁
𝑗=1
(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)𝑓𝑗
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 26
a fatoração em fatores irredutíveis de 𝑞 sobre os reais, com todos 𝑎𝑖,𝑏𝑗,𝑐𝑗 ∈ R e
𝑒𝑖,𝑓𝑗 inteiros positivos. Decompondo 𝑓 em frações parciais completas, temos
𝑓 = 𝑠 +
𝑛∑︁
𝑖=1
𝑒𝑖∑︁
𝑘=1
𝐴𝑖𝑘
(𝑥− 𝑎𝑖)𝑘
+
𝑚∑︁
𝑗=1
𝑓𝑗∑︁
𝑘=1
𝐵𝑗𝑘𝑥 + 𝐶𝑗𝑘
(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)𝑘
(3.1)
onde todos 𝐴𝑖𝑘,𝐵𝑗𝑘,𝐶𝑗𝑘 ∈ R. Portanto, pela linearidade da integração, ∫ 𝑓 é a
soma das integrais das parcelas do lado direito da equação (3.1). A integral de
𝑠 ∈ R[𝑥] é fácil de ser calculada, pois 𝑠 é um polinômio. Para as outras parcelas,
temos: ∫︁ 𝐴𝑖𝑘
(𝑥− 𝑎𝑖)𝑘
=
⎧⎪⎨⎪⎩𝐴𝑖𝑘(𝑥− 𝑎𝑖)
1−𝑘/(1− 𝑘) se 𝑘 > 1
𝐴1𝑘 log(𝑥− 𝑎𝑖) se 𝑘 = 1
(3.2)
e, notando que 𝑏2𝑗 − 4𝑐𝑗 < 0, uma vez que 𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗 é irretdutível sobre os
reais,
∫︁ 𝐵𝑗1𝑥 + 𝐶𝑗1
(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)
=𝐵𝑗12 log(𝑥
2 + 𝑏𝑗𝑥 + 𝑐𝑗)
+ 2𝐶𝑗1 − 𝑏𝑗𝐵𝑗1√︁
4𝑐𝑗 − 𝑏2𝑗
arctg
⎛⎝ 2𝑥 + 𝑏𝑗√︁
4𝑐𝑗 − 𝑏2𝑗
⎞⎠
e para 𝑘 > 1,
∫︁ 𝐵𝑗𝑘𝑥 + 𝐶𝑗𝑘
(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)𝑘
= (2𝐶𝑗𝑘 − 𝑏𝑗𝐵𝑗𝑘)𝑥 + 𝑏𝑗𝐶𝑗𝑘 − 2𝑐𝑗𝐵𝑗𝑘(𝑘 − 1)(4𝑐𝑗 − 𝑏2𝑗)(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)𝑘−1
+
∫︁ (2𝑘 − 3)(2𝐶𝑗𝑘 − 𝑏𝑗𝐵𝑗𝑘)
(𝑘 − 1)(4𝑐𝑗 − 𝑏2𝑗)(𝑥2 + 𝑏𝑗𝑥 + 𝑐𝑗)𝑘−1
. (3.3)
A regra explicitada por (3.3) pode ser aplicada recursivamente sobre a integral
do lado direito desta equação, até que atinjamos 𝑘 = 1. Assim, completamos o
algoritmo de Bernoulli.
O método explicitado serve para funções racionais com coeficientes reais.
Porém, uma variante pode ser obtida para funções cujos coeficientes estejam
num subcorpo K qualquer dos complexos. Mantendo a notação, suponhamos
𝑓 = 𝑝/𝑞 ∈ K(𝑥) e consideremos a fatoração completa em termos lineares de 𝑞,
273.1. O Algoritmo de Bernoulli
isto é 𝑞 =
𝑛∏︁
𝑖=1
(𝑥 − 𝑎𝑖)𝑒𝑖 , onde os 𝑎𝑖 pertencem ao fecho algébrico de K. Temos a
seguinte decomposição em frações parciais completas de 𝑓 :
𝑓 = 𝑠 +
𝑛∑︁
𝑖=1
𝑒𝑖∑︁
𝑘=1
𝐴𝑖𝑘
(𝑥− 𝑎𝑖)𝑘
. (3.4)
Basta, então, aplicar (3.2) para cada termo cada termo próprio do lado direito.
Esta abordagem é equivalente a expandir 𝑓 em sua série de Laurent em todos
os seus polos finitos, uma vez que, em 𝑥 = 𝑎𝑖, a série de Laurent é
𝑓 = 𝐴𝑖𝑒𝑖(𝑥− 𝑎𝑖)𝑒𝑖
+ · · ·+ 𝐴𝑖2(𝑥− 𝑎𝑖)2
+ 𝐴𝑖1(𝑥− 𝑎𝑖)
+ · · ·
onde os 𝐴𝑖𝑗 são os mesmos que em (3.4). Portanto, podemos perceber esta abor-
dagem como a expansão do integrando em série em torno de seus polos (incluíndo
∞), seguida de integração termo a termo da série e interpolação, através da soma
de todos os termos polares, obtendo, assim, a integral de (3.4).
Dada a natureza desta variante do método de Bernoulli de se basear em ex-
pansão de séries, dizemos que sua abordagem é local. Em termos computacionais,
a inconveniência deste método reside no fato de sermos levados a computar exten-
sões de números algébricos sobre K que não necessariamente precisam aparecer na
integral, a saber, os coeficientes da série de Laurent, além de precisarmos realizar
cálculos de frações parciais envolvendo estes números algébricos. No Exemplo
3.1.2 a seguir, realizamos cálculos em Q(𝐼) e obtemos o resultado final a partir
deste corpo, mas existe uma integral que pode ser expressa inteiramente sobre
Q(𝑥). Por outro lado, certas integrais não são possíveis de serem expressas sem a
introdução de novas extensões algébricas constantes, como ∫ 𝑑𝑥/(𝑥2 − 2), a qual
necessita da extensão
√
2. Portanto, de maneira geral, é possivel que precisemos
introduzir novas extensões algébricas de K em algum momento.
Nosso objetivo, portanto, é conseguir um método que nos possibilite efetuar o
máximo possível de cálculos permanecendo no corpo K(𝑥) do qual o integrando
𝑓 faz parte e, caso seja necessário realizar extensões sobre o corpo de constantes
K, queremos fazer isto o mínimo possível. É exatamente isto que vamos conseguir
nas próximas seções.
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 28
Na subseção 5.5.1, um código para implementação no Maxima do algoritmo de
Bernoulli aplicado a integrandos reduzidos, próprios e com denominadores livres
de quadrados.
3.1.1 Exemplos
Exemplo 3.1.1 (extraído de [2], Cap 2, §1). Seja 𝑓 = 1/(𝑥2 + 1)2 ∈ Q(𝑥).
Observe que o denominador já está fatorado em fatores irredutíveis sobre R, e
portanto, 𝑓 já está decomposta em frações parciais. Portanto, nas fórmulas do
algoritmo de Bernoulli, com 𝑗 = 1, 𝑘 = 1, 𝑏1 = 𝐵12 = 0 e 𝑐1 = 𝐶12 = 1, temos
∫︁ 1
(𝑥2 + 1)2 =
2𝑥
4(𝑥2 + 1) +
2𝑑𝑥
4(𝑥2 + 1) =
𝑥
2(𝑥2 + 1) +
1
2 arctg(𝑥).
Exemplo 3.1.2 (extraído de [2], Cap 2, §1). Seja 𝑓 = 1/(𝑥3 + 𝑥) ∈ Q(𝑥). O
denominador se fatora em fatores irredutíveis em R na forma 𝑥3 + 𝑥 = 𝑥(𝑥2 + 1).
Portanto, temos a seguinte decomposição em frações parciais de 𝑓 :
1
𝑥3 + 𝑥 =
1
𝑥
− 𝑥
𝑥2 + 1 .
Seguindo as fórmulas do algoritmo de Bernoulli temos
∫︁ 1
𝑥3 + 𝑥 = log(𝑥)−
1
2 log(𝑥
2 + 1). (3.5)
Se tivéssemos escolhido fatorar 𝑓 sobre os complexos, a fatoração em fatores
irredutíveis do denominador ficaria 𝑥3 + 𝑥 = 𝑥(𝑥 + 𝐼)(𝑥− 𝐼), e a decomposição
em frações parciais seria
1
𝑥3 + 𝑥 =
1
𝑥
− 1/2
𝑥 + 𝐼 −
1/2
𝑥− 𝐼
.
Portanto, uma representação alternativa para a integral de 𝑓 seria
∫︁ 1
𝑥3 + 𝑥 = log(𝑥)−
1
2 log(𝑥 + 𝐼)−
1
2 log(𝑥− 𝐼).
Observamos, portanto, que a última expressão introduz números algébricos des-
29 3.2. O Algoritmo de Hermite
necessários na representação da integral de 𝑓 , enquanto que a representação (3.5)
evita esta introdução. Isto motivará o algoritmo de Rothstein-Trager, a ser estu-
dado mais adiante.
3.2 O Algoritmo de Hermite
Como vimos na seção 3.1, se 𝑓 ∈ K(𝑥), onde K é um subcorpo dos complexos,
podemos expressar ∫︁
𝑓 = 𝑐
𝑑
+
𝑚∑︁
𝑖=1
𝛾𝑖 log(𝑣𝑖) (3.6)
onde 𝑐,𝑑,𝑣1, . . . ,𝑣𝑚 ∈ K[𝑥] e 𝛾1, . . . ,𝛾𝑚 ∈ K. No lado direito, a fração 𝑐/𝑑 ∈ K(𝑥)
é chamada de parte racional da integral, sendo o restante a parte logarítmica ou
transcendental, como já mencionamos no Capítulo 1. O algoritmo de Hermite
permite encontrar completamente a parte racional da integral de 𝑓 , enquanto
expressa a parte logarítmica implicitamente por ∫ 𝑎/𝑏, onde 𝑎/𝑏 ∈ K(𝑥) é uma
fração reduzida, própria e de denominador livre de quadrados.
3.2.1 Versão Original do Algoritmo de Hermite
Novamente, seja 𝑓 = 𝑝/𝑞 ∈ K(𝑥) uma fração reduzida. Valendo-nos da divisão
euclidiana, escrevamos 𝑓 = 𝑠 + 𝑟/𝑞, onde 𝑠,𝑟 ∈ R[𝑥], com 𝑟/𝑞 própria. Seja
𝑞 = 𝑞11 · · · 𝑞𝑘𝑘 a flq de 𝑞. A decomposição em frações parciais em relação a esta
fatoração é
𝑓 = 𝑠 +
𝑘∑︁
𝑖=1
𝑟𝑖
𝑞𝑖𝑖
onde cada 𝑟𝑖 ∈ K[𝑥] e vale 0, ou grau(𝑟𝑖) < grau(𝑞𝑖𝑖). Como no algoritmo de
Bernoulli, reduzimos o nosso problema a integrar cada uma das parcelas próprias
por vez no lado direito da equação acima. Observando ainda que, como cada
𝑞𝑖 é livre de quadrados e, portanto, temos que mdc(𝑞𝑖,𝑞′𝑖) = 1, se 𝑖 > 1 então
podemos utilizar o algoritmo de Euclides estendido (vide pseudocódigos e códigos
das subseções 5.2.3, 5.2.4, 5.2.5, 5.2.6, 5.2.7, 5.2.8 e 5.2.9 para cálculo de mdc)
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 30
para encontrar 𝜎,𝜏 ∈ K[𝑥] tais que
𝑟𝑖
1− 𝑖 = 𝜎𝑞
′
𝑖 + 𝜏𝑞𝑖
com grau(𝜎) < grau(𝑞𝑖). Logo, grau(𝜎𝑞′𝑖) < grau(𝑞2𝑖 ) ≤ grau(𝑞𝑖𝑖) e, portanto,
grau(𝜏) < grau(𝑞𝑖−1𝑖 ). Multiplicando ambos os lados por (1− 𝑖)/𝑞𝑖𝑖, temos
𝑟𝑖
𝑞𝑖𝑖
= −(𝑖− 1)𝜎𝑞
′
𝑖
𝑞𝑖𝑖
+ (1− 𝑖)𝜏
𝑞𝑖−1𝑖
.
Adicionando e subtraindo 𝜎′/𝑞𝑖−1𝑖 no lado direito, temos
𝑟𝑖
𝑞𝑖𝑖
=
(︃
𝜎′
𝑞𝑖−1𝑖
− (𝑖− 1)𝜎𝑞
′
𝑖
𝑞𝑖𝑖
)︃
+ (1− 𝑖)𝜏 − 𝜎
′
𝑞𝑖−1𝑖
.
Finalmente, integrando ambos os lados,
∫︁ 𝑟𝑖
𝑞𝑖𝑖
= 𝜎
𝑞𝑖−1𝑖
+
∫︁ (1− 𝑖)𝜏 − 𝜎′
𝑞𝑖−1𝑖
. (3.7)
Uma vez que grau((1− 𝑖)𝜏 − 𝜎′) < grau(𝑞𝑖−1𝑖 ), o integrando à direita em (3.7) é
semelhante ao da esquerda, porém com a potência do denominador reduzida em
uma unidade. De maneira semelhante ao algoritmo de Bernoulli, podemos repetir
esta fórmula recursivamente à direita, até que a potência do denominador seja
1. Quando atingimos esta condição, obtemos 𝑐𝑖,𝑑𝑖,𝑎𝑖 ∈ K[𝑥] tais que grau(𝑎𝑖) <
grau(𝑞𝑖) e 𝑟𝑖/𝑞𝑖𝑖 = (𝑐𝑖/𝑑𝑖)′ + 𝑎𝑖/𝑞𝑖, para cada 𝑖. Portanto, obtemos 𝑔,ℎ ∈ K(𝑥) tais
que 𝑓 = 𝑔′ + 𝑠 + ℎ, onde ℎ é uma fração própria cujo denominador é livre de
quadrados (é o produto dos 𝑞𝑖) e, ∫ ℎ é a parte logarítmica da integral de 𝑓 . A
parte racional, portanto, é 𝑔 + ∫ 𝑠.
3.2.2 Versão Quadrática do Algoritmo de Hermite
Uma variante do algoritmo de Hermite nos permite chegar ao mesmo resultado
sem a necessidade de se computar a decomposição em frações parciais de 𝑓 .
Descrevemos esta variante a seguir.
Mantendo a notação, supondo que na flq de 𝑞 tenhamos 𝑘 ≥ 2 (caso contrário 𝑞
31 3.2. O Algoritmo de Hermite
já seria livre de quadrados), definamos 𝑞 = 𝑞/𝑞𝑘𝑘 . Como mdc(𝑞𝑞′𝑘,𝑞𝑘) = 1, podemos
utilizar o algoritmo de Euclides estendido para calcular 𝜎,𝜏 ∈ K[𝑥] tais que
𝑝
1− 𝑘 = 𝜎𝑞𝑞
′
𝑘 + 𝜏𝑞𝑘
e grau(𝜎) < grau(𝑞𝑘). Multiplicando ambos os lados por (1− 𝑘)/(𝑞𝑞𝑘𝑘), temos
𝑝
𝑞𝑞𝑘𝑘
= (1− 𝑘)𝜎𝑞
′
𝑘
𝑞𝑘𝑘
+ (1− 𝑘)𝜏
𝑞𝑞𝑘−1𝑘
.
Logo, adicionando e subtraindo 𝜎′/𝑞𝑘−1𝑘 do lado direito, temos
𝑝
𝑞𝑞𝑘𝑘
=
(︃
𝜎′
𝑞𝑘−1𝑘
− (𝑘 − 1)𝜎𝑞
′
𝑘
𝑞𝑘𝑘
)︃
+ (1− 𝑘)𝜏 − 𝑞𝜎
′
𝑞𝑞𝑘−1𝑘
.
Finalmente, integrando dos dois lados:
∫︁ 𝑝
𝑞𝑞𝑘𝑘
= 𝜎
𝑞𝑘−1𝑘
+
∫︁ (1− 𝑘)𝜏 − 𝑞𝜎′
𝑞𝑞𝑘−1𝑘
.
Novamente, a integral à direita é similar à integral à esquerda, com a redução de
potência em uma unidade no denominador. O processo segue recursivamente até
que se obtenha um denominador livre de quadrados.
Como o expoente dos fatores livres de quadrados é reduzido em uma unidade
em cada passo, no pior dos casos, o número de passosde redução e 1+2+· · ·+(𝑘−1),
o que tem complexidade 𝑂(𝑘2) e, portanto, chamamos esta variante de versão
quadrática do método de Hermite.
3.2.3 Versão Linear do Algoritmo de Hermite
Uma última variante do algoritmo de Hermite é fornecida a seguir e é devida a D.
Mack [22]. Nela, não precisamos calcular nem a decomposição em frações parciais
do integrando, nem, a priori a fatoração livre de quadrados de seu denominador
(esta última sendo computada ao longo do processo).
Como estamos trabalhando sobre um corpo K, podemos supor que o denomi-
nador 𝑞 da função 𝑓 é um polinômio primitivo. Como nos algoritmos de fatoração
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 32
livre de quadrados, calculamos 𝑞− = mdc(𝑞,𝑞′) e 𝑞* = 𝑞/𝑞−. Se grau(𝑞−) = 0,
então 𝑞 é livre de quadrados, senão, como 𝑞− = 𝑞−*𝑞−2 por 2.5, 𝑞−′ = 𝑞−2𝑌2 pela
Proposição 2.2.2, onde 𝑌2 é dado por (2.9) e 𝑞1 = 𝑞*/𝑞−
* pela Proposição 2.2.1,
temos
𝑞*𝑞−
′
𝑞−
= 𝑞
*𝑞−2𝑌2
𝑞−
= 𝑞
*𝑞−2𝑌2
𝑞−*𝑞−2
= 𝑞
*
𝑞−*
𝑌2 = 𝑞1𝑌2 ∈ K[𝑥]. (3.8)
Além disso, como consequência da Proposição 2.2.1, mdc(𝑞1,𝑞−) = 1, e mdc(𝑌2,𝑞−
*) =
1 pela Proposição 2.2.2, o que implica que
mdc
(︃
𝑞*𝑞−
′
𝑞−
,𝑞−
*
)︃
= mdc(𝑞1𝑌2,𝑞−
*) = 1.
Portanto, podemos utilizar o algoritmo de Euclides estendido para encontrar
𝜎,𝜏 ∈ K[𝑥] tais que
𝑝 = 𝜎
(︃
−𝑞
*𝑞−
′
𝑞−
)︃
+ 𝜏𝑞−*.
Dividindo-se ambos os lados por 𝑞 = 𝑞*𝑞− = 𝑞1𝑞−
*
𝑞−, temos
𝑝
𝑞
= −𝜎𝑞
−′
𝑞−2
+ 𝜏
𝑞1𝑞−
.
Adicionando e subtraindo 𝜎′/𝑞− do lado direito, temos
𝑝
𝑞
=
(︃
𝜎′
𝑞−
− 𝜎𝑞
−′
𝑞−2
)︃
+ 𝜏 − 𝑞1𝜎
′
𝑞1𝑞−
.
Finalmente, integrando ambos os lados, temos
∫︁ 𝑝
𝑞
= 𝜎
𝑞−
+
∫︁ 𝜏 − 𝑞1𝜎′
𝑞1𝑞−
. (3.9)
Como 𝑞1𝑞− = (𝑞1𝑞2)𝑞23 · · · 𝑞𝑚−1𝑚 , o integrando foi reduzido a um cujo denominador
possui fatoração livre de quadrados com no máximo 𝑚−1 expoentes diferentes, ao
invés de 𝑚 como no início do processo. Aplicando recursivamente o método para
integral do lado direito da fórmula (3.9), terminamos o processo em no máximo
𝑚 − 1 passos, quando teremos um denominador livre de quadrados. Por causa
desta complexidade linear, este método costuma ser chamado de versão linear
33 3.2. O Algoritmo de Hermite
do algoritmo de Hermite.
Notamos que uma melhoria pode ser feita à versão linear do método de Hermite.
Podemos calcular os parâmetros do próximo passo a partir dos atuais. Seja 𝑝/𝑞 o
integrando atual, com
𝑝 = 𝜏 − 𝑞1𝜎′ = 𝜏 −
𝑞*
𝑞−*
𝜎′
e
𝑞 = 𝑞1𝑞− = 𝑞1𝑞2𝑞23 · · · 𝑞𝑚−1𝑚 .
Temos que
𝑞* = 𝑞1𝑞− = 𝑞1𝑞2𝑞3 · · · 𝑞𝑚 = 𝑞*,
ou seja 𝑞* permanece o mesmo ao longo da redução. Por outro lado,
𝑞− = 𝑞3𝑞24 · · · 𝑞𝑚−2𝑚 = 𝑞−2 ,
o que, de maneira geral, significa que, no 𝑖-ésimo (caso todos os expoentes sejam
positivos) 𝑞− é substituído por sua 𝑖-ésima deflação.
Finalmente, observamos que todas as variantes do algoritmo de Hermite podem
ser realizadas sobre um DFU, ao invés de um corpo, sendo o resultado expresso em
seu corpo quociente. Neste caso, na variante linear, o denominador do integrando
obrigatoriamente deve ser primitivo, ao contrário das demais variantes.
Nas subseções 5.4.1, 5.4.2 e 5.4.3, fornecemos pseudocódigos, juntamente com
códigos para implementação no Maxima, respectivamente, das versões original,
quadrática e linear do método de Hermite.
3.2.4 Exemplos
Aplicaremos as três versões do algoritmo de Hermite a uma mesma função.
Exemplo 3.2.1 (gerado com dados obtidos pelo código 5.4.1, versão original da
redução de Hermite). Sejam 𝐴 = 3𝑥6−𝑥4−6 ∈ Q[𝑥], 𝐷 = 𝑥8−12𝑥6+48𝑥4−64𝑥2 ∈
Q[𝑥] e 𝑓 = 𝐴/𝐷 ∈ Q(𝑥), isto é,
𝑓 = 3𝑥
6 − 𝑥4 − 6
𝑥8 − 12𝑥6 + 48𝑥4 − 64𝑥2 ∈ Q(𝑥).
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 34
Temos que a fatoração em fatores irredutíveis do denominador é 𝐷 = 𝑥2(𝑥 −
2)3(𝑥 + 2)3, enquanto que sua flq é 𝐷 = 𝑥2(𝑥2 − 4)3 = 𝐷22𝐷33. A decomposição
em frações parciais de 𝑓 sobre esta fatoração é
𝑓 = 332𝑥2 +
93𝑥4 + 4𝑥2 − 144
32(𝑥2 − 4)3 .
Aplicando a versão original do algoritmo de Hermite sobre 𝑓 , temos, nos termos
da fórmula de recursão:
𝑖 𝑉 𝑗 𝐴𝑖 𝐵 𝐶
2 𝑥 1 3/32 −3/32 0
3 𝑥2 − 4 2 (93𝑥4 + 4𝑥2 − 144)/32 −85𝑥/82 −(93𝑥2 + 36)/64
3 𝑥2 − 4 1 (93𝑥2 + 121)/32 −493𝑥/256 121/128
Portanto,
∫︁ 3𝑥6 − 𝑥4 − 6
𝑥8 − 12𝑥6 + 48𝑥4 − 64𝑥2 = −
493𝑥
256(𝑥2 − 4)−
85𝑥
32(𝑥2 − 4)2−
3
32𝑥+
∫︁ 251
256(𝑥2 − 4) .
Exemplo 3.2.2 (gerado com dados obtidos pelo código 5.4.2, versão quadrática
da redução de Hermite). Com a versão quadrática, temos a seguinte tabela para 𝑓 :
𝑖 𝑉 𝑈 𝑗 𝐵 𝐶 𝐴
2 𝑥 𝐷33 1 −3/32 −(93𝑥5 + 4𝑥3 − 144𝑥)/32 (93𝑥5 + 4𝑥3 − 144𝑥)/32
3 𝐷3 𝑥 2 −85𝑥/32 −(93𝑥3 + 36𝑥)/64 (93𝑥3 + 121𝑥)/32
3 𝐷3 𝑥 1 −493𝑥/256 121𝑥/128 251𝑥/256
Portanto,
∫︁ 3𝑥6 − 𝑥4 − 6
𝑥8 − 12𝑥6 + 48𝑥4 − 64𝑥2 = −
493𝑥
256(𝑥2 − 4)−
85𝑥
32(𝑥2 − 4)2−
3
32𝑥+
∫︁ 251
256(𝑥2 − 4) .
da mesma maneira que na versão linear, porém não necessitamos da decomposição
em frações parciais.
35 3.2. O Algoritmo de Hermite
Exemplo 3.2.3 (gerado com dados obtidos pelo código 5.4.3, versão linear de
Mack da redução de Hermite). Mantendo a função 𝑓 , temos:
1. 𝑔 ← 0;
2. 𝐷− ← mdc(𝐷,𝑑𝐷/𝑑𝑥) = 𝑥5 − 8𝑥3 + 16𝑥;
3. 𝐷* ← 𝐷/𝐷− = 𝑥3 − 4𝑥;
4. Entramos no primeiro passo da redução:
𝐷−2 ← mdc(𝑥5 − 8𝑥3 + 16𝑥,5𝑥4 − 24𝑥2 + 16) = 𝑥2 − 4;
5. 𝐷−* ← 𝐷−/𝐷−2 = 𝑥3 − 4𝑥;
6.
(𝐵,𝐶)← ExtendedEuclidean(−5𝑥2 + 4,𝑥3 − 4𝑥,𝐴)
=
(︃
−73𝑥
2 + 48
32 ,
96𝑥3 − 13𝑥
32
)︃
;
7. 𝐴← (96𝑥3 − 13𝑥)/32 + 146𝑥/32 = (96𝑥3 + 133𝑥)/32;
8.
𝑔 ← 𝑔 + 𝐵
𝐷−
= − 73𝑥
2 + 48
32(𝑥5 − 8𝑥3 + 16𝑥)
9. 𝐷− ← 𝐷−2 = 𝑥2 − 4
10. Entramos no segundo passo da redução:
𝐷−2 ← mdc(𝑥2 + 2,2𝑥) = 1;
11. 𝐷−* ← 𝐷−/𝐷−2 = 𝑥2 − 4;
12. (𝐵,𝐶)← ExtendedEuclidean(−2𝑥2,𝑥2 − 4,(96𝑥3 + 133𝑥)/32) = (−517𝑥/256,
−133𝑥/128)
13.
𝑔 ← 𝑔 + 𝐵
𝐷−
= − 73𝑥
2 + 48
32(𝑥5 − 8𝑥3 + 16𝑥) −
−517𝑥
256(𝑥2 − 4)
14. 𝐷− ← 𝐷−2 = 1.
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 36
Portanto,
∫︁ 3𝑥6 − 𝑥4 − 6
𝑥8 − 12𝑥6 + 48𝑥4 − 64𝑥2 = −
73𝑥2 + 48
32(𝑥5 − 8𝑥3 + 16𝑥) −
−517𝑥
256(𝑥2 − 4) +
∫︁ 251𝑥
256(𝑥3 − 4𝑥)
o que equivale ao que obtivemos nas duas outras versões do algoritmo de Hermite,
mas precisamos de apenas dois passos de redução, ao invés de três.
3.3 O Algoritmo de Horowitz-Ostrogradsky
O algoritmo de Hermite nos permite obter
∫︁ 𝑝
𝑞
= 𝑐
𝑑
+
∫︁ 𝑎
𝑏
, (3.10)
com 𝑎,𝑏,𝑐,𝑑 ∈ K[𝑥], mdc(𝑐,𝑑) = mdc(𝑎,𝑏) = 1, 𝑎/𝑏 própria e 𝑏 livre de quadrados.
O algoritmo de Horowitz-Ostrogradsky é uma alternativa ao método de
Hermite. Ao invés de uma redução, calcula diretamente os polinômios 𝑑 e 𝑏 na
equação (3.10), e, a partir disso, obtém os polinômios 𝑎 e 𝑐 através da resolução
de um sistema linear cujas incógnitas são os coeficientes destes dois últimos
polinômios. Dispensa completamente os cálculos de frações parciais e fatoração
livre de quadrados.
Teorema 3.3.1 ([11], Cap. 11, §4). Seja 𝑓 = 𝑝/𝑞 ∈ K(𝑥) uma função racional
reduzida e própria. Sejam 𝑔 = 𝑐/𝑑 a parte racional de sua integral e ℎ = 𝑎/𝑏 o
integrando aparecendo na parte transcendental, como encontramos pelo algoritmo
de Hermite (note que 𝑠 = 0). Então
𝑑 = 𝑞− e 𝑏 = 𝑞*.
Além disso, grau(𝑎) < grau(𝑏) e grau(𝑐) < grau(𝑑).
Demonstração. Seja
𝑞 =
𝑘∏︁
𝑖=1
𝑞𝑖𝑖
a fatoração livre de quadrados de 𝑞. A demonstração é bastante direta e consiste,
basicamente, de observar a contribuição da integral de cada fração parcial do
37 3.3. O Algoritmo de Horowitz-Ostrogradsky
integrando original para os denominadores da parte racional e do integrando
da parte transcendental no algoritmo de Hermite. Em suma, na equação (3.10),
encontramos que
𝑏 =
𝑘∏︁
𝑖=1
𝑞𝑖, 𝑑 =
𝑘∏︁
𝑖=2
𝑞𝑖−1𝑖 ,
com grau(𝑎) < grau(𝑏) e grau(𝑐) < grau(𝑑). Ou seja,
𝑑 = 𝑞− e 𝑏 = 𝑞*.
O resultado acima é a base para o algoritmo de Horowitz-Ostrogradsky. Dife-
renciando a equação (3.10) aplicada à fração reduzida e própria 𝑝/𝑞, temos
𝑝
𝑞
= 𝑑𝑐
′ − 𝑐𝑑′𝑑2
+ 𝑎
𝑏
.
Multiplicando a equação acima por 𝑞 = 𝑏𝑑, temos
𝑝 = 𝑏𝑐′ − 𝑐𝑏𝑑
′
𝑑
+ 𝑑𝑎. (3.11)
Seja 𝑞 =
𝑘∏︁
𝑖=1
𝑞𝑖𝑖 a flq de 𝑞. Observe que
𝑏𝑑′ =
(︃
𝑘∏︁
𝑖=1
𝑞𝑖
)︃⎛⎝ 𝑘∑︁
𝑖=2
(𝑖− 1)𝑞𝑖−2𝑖
𝑘∏︁
𝑖 ̸=𝑗≥2
𝑞𝑗−1𝑗
⎞⎠ = 𝑞1 𝑘∑︁
𝑖=2
(𝑖− 1)𝑞𝑖−1𝑖
𝑘∏︁
𝑖 ̸=𝑗≥2
𝑞𝑗𝑗 .
Portanto, 𝑏𝑑′ é divisível por 𝑑, donde a equação (3.11) constitui uma identidade
polinomial. Definamos 𝑚 = grau(𝑏) e 𝑛 = grau(𝑑). Como os únicos polinômios
que não conhecemos nesta identidade são 𝑎 e 𝑐, e como os limites superiores de
seus graus são, respectivamente, 𝑚− 1 = grau(𝑏)− 1 e 𝑛− 1 = grau(𝑑)− 1, esta
identidade polinomial origina um sistema linear cujas variáveis são os coeficientes
destes polinômios, os quais se escrevem, para efeitos de resolução deste sistema,
𝑎 = 𝑎𝑚−1𝑥𝑚−1 + ... + 𝑎1𝑥 + 𝑎0
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 38
e
𝑐 = 𝑐𝑛−1𝑥𝑛−1 + ... + 𝑐1𝑥 + 𝑐0.
O grau do polinômio do lado esquerdo da equação (3.11) é
grau(𝑝) ≤ grau(𝑞)− 1 = grau(𝑏) + grau(𝑑)− 1 = 𝑚 + 𝑛− 1
enquanto no lado direito, o limitante para o grau é
max(𝑚 + 𝑛− 2,𝑚 + 𝑛− 2,𝑚 + 𝑛− 1) = 𝑚 + 𝑛− 1.
Portanto, igualando os coeficientes dos dois lados da equação (3.11), obtemos um
sistema linear determinado de 𝑚 + 𝑛 linhas e 𝑚 + 𝑛 incógnitas sobre K.
Observe que este método é uma alternativa ao algoritmo de Hermite e não
requer o cálculo da fatoração livre de quadrados de 𝑞 em momento algum.
Enquanto a complexidade deste método é muito boa para funções racionais,
sua generalização não é tão simples quanto o método de Hermite para classes
maiores de funções, de modo que o algoritmo para funções elementares acaba por
utilizar a versão linear do algoritmo de Hermite [2, p. 46].
Na subseção 5.4.4, fornecemos um pseudocódigo, juntamente com código para
implementação no Maxima do algoritmo de Horowitz-Ostrogradsky.
3.3.1 Exemplos
Continuamos utilizando a função 𝑓 dos exemplos da seção anterior.
Exemplo 3.3.1 (gerado com dados obtidos pelo código 5.4.4, algoritmo de Ho-
rowitz-Ostrogradsky). Seguindo os passos do algoritmo de Horowitz-Ostrogradsky,
temos:
𝐷− = 𝑥5 − 8𝑥3 + 16𝑥;
𝐷* = 𝐷/𝐷− = 𝑥3 − 4𝑥;
𝑚 = grau(𝐷*)− 1 = 2, 𝑛 = grau(𝐷−)− 1 = 4.
Temos a identidade polinomial
39 3.4. O Algoritmo de Rothstein-Trager
𝐻 ← 𝐴−𝐷*
(︃
𝑛∑︁
𝑖=0
𝑏𝑖𝑥
𝑖
)︃′
+
(︃
𝑛∑︁
𝑖=0
𝑏𝑖𝑥
𝑖
)︃
𝑑*𝐷−
′
𝐷−
−𝐷−
⎛⎝ 𝑚∑︁
𝑗=0
𝑐𝑗𝑥
𝑗
⎞⎠
= (−𝑐2)𝑥7 + (𝑏4 − 𝑐1 + 3)𝑥6 + (2𝑏3 − 𝑐0 + 8𝑐2)𝑥5
+ (3𝑏2 + 12𝑏4 + 8𝑐1 − 1)𝑥4 + 4(𝑏1 + 2𝑏3 + 2𝑐0 − 4𝑐2)𝑥3
+ (5𝑏0 + 4𝑏2 − 16𝑐1)𝑥2 + (−16𝑐0)𝑥 + (−4𝑏0 − 6)
Formamos o sistema onde cada coeficiente de 𝐻 equivale a 0. A solução é
(𝑏0,𝑏1,𝑏2,𝑏3,𝑏4,𝑐0,𝑐1,𝑐2) =
(︂
−32 ,0,
371
64 ,0,−
517
256 ,0,−
251
256 ,0
)︂
.
Portanto,
∫︁ 3𝑥6 − 𝑥4 − 6
𝑥8 − 12𝑥6 + 48𝑥4 − 64𝑥2 = −
73𝑥2 + 48
32(𝑥5 − 8𝑥3 + 16𝑥) −
−517𝑥
256(𝑥2 − 4) +
∫︁ 251𝑥
256(𝑥3 − 4𝑥)
o que é coerente com a resposta dada pelo algoritmo de Hermite.
3.4 O Algoritmo de Rothstein-Trager
Terminado o algoritmo de Hermite (ou Horowitz-Ostrogradsky), resta-nos calcular
a parte logarítmica da integral de 𝑓 = 𝑝/𝑞, a saber, ∫ ℎ = ∫ 𝑎/𝑏, onde, como vimos,
𝑎/𝑏 é uma fração reduzida e própria, cujo denominador é livre de quadrados. Se
considerarmos K o fecho algébrico de K, e se 𝑏 =
𝑛∏︁
𝑖=1
(𝑥− 𝛼𝑖), temos que ℎ deve
ter a forma
ℎ =
𝑛∑︁
𝑖=1
𝛾𝑖
𝑥− 𝛼𝑖
(3.12)
onde 𝛾1, . . . ,𝛾𝑛 ∈ K. Dessa forma,
∫︁
ℎ =
𝑛∑︁
𝑖=1
𝛾𝑖 log(𝑥− 𝛼𝑖). (3.13)
Uma vez que a soma de logaritmos é o logaritmo do produto de seus argumentos,
quaisquer logaritmos sob um mesmo 𝛾𝑖 na expressão acima podem ser unificados
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 40
num único logaritmo. Em outras palavras, queremos encontrar um método de
encontrar os resíduos distintos entre os 𝛾𝑖 necessários para expressar
∫︁
ℎ sem
fatorar 𝑏 completamente. Os 𝛾𝑖 são os resíduos de ℎ que aparecem na expansão
de Laurent de desta função em torno de cada ponto 𝑥 = 𝛼𝑖, i.e.
ℎ = 𝛾𝑖
𝑥− 𝛼𝑖
+ 𝑐0 + 𝑐1(𝑥− 𝛼𝑖) + 𝑐2(𝑥− 𝛼𝑖)2 + · · · . (3.14)
Utilizando a equação (3.12), temos que
𝑎 =
𝑛∑︁
𝑖=1
𝛾𝑖
𝑏
𝑥− 𝛼𝑖
=
𝑛∑︁
𝑖=1
𝛾𝑖
𝑛∏︁
𝑗 ̸=𝑖
(𝑥− 𝛼𝑗).
Portanto, para cada polo 𝛼𝑖
𝑎(𝛼𝑖) = 𝛾𝑖
𝑛∏︁
𝑗 ̸=𝑖
(𝛼𝑖 − 𝛼𝑗) = 𝛾𝑖𝑏′(𝛼𝑖)
Assim, se 𝛼 é um polo de ℎ para calcularmos o resíduo 𝛾 deste polo, podemos
usar a fórmula
𝛾 = 𝑎(𝛼)
𝑏′(𝛼) . (3.15)
Logo, encontrar todos os resíduos distintos equivale a resolver em 𝛾 a equação
(3.15) para cada polo 𝛼. Ou seja, equivale a resolver
𝑎(𝛼)− 𝛾𝑏′(𝛼) = 0 para todo 𝛼 | 𝑏(𝛼) = 0.
Isto é o mesmo que encontrar todas as raízes distintas do polinômio
𝑅(𝑧) =
∏︁
𝛼|𝑏(𝛼)=0
(𝑎(𝛼)− 𝑧𝑏′(𝛼))
o que, pelo Lema 2.1.2 equivale a
𝑅(𝑧) = res𝑥(𝑎(𝑥)− 𝑧𝑏′(𝑥),𝑏(𝑥)). (3.16)
41 3.4. O Algoritmo de Rothstein-Trager
Qualquer raiz repetida em (3.16) implicará em redução no número de logaritmos
aparecendo em (3.13). Portanto, podemos escrever
∫︁
ℎ =
𝑘∑︁
𝑖=1
𝑐𝑖 log(𝑣𝑖) (3.17)
onde os 𝑐𝑖 são as raízes distintas de (3.16) e os 𝑣𝑖 são mônicos, livres de quadrados
e dois a dois coprimos. O seguinte resultado mostra que as raízes 𝑐𝑖 são todas
necessárias e provê um mecanismo simples para calcular os 𝑣𝑖.
Teorema 3.4.1 (Algoritmo de Rothstein-Trager, [11], Cap. 11, §5, [31, 34]). Sejam
𝑎,𝑏 ∈ K*[𝑥] tais que mdc(𝑎,𝑏) = 1, com 𝑏 livre de quadrados e 𝑎/𝑏 reduzida e
própria. Suponha que, para K*, seja possível escrever
∫︁ 𝑎
𝑏
=
𝑛∑︁
𝑖=1
𝑐𝑖 log(𝑣𝑖) (3.18)
onde os 𝑐𝑖 ∈ K* são constantes não nulas distintas e os 𝑣𝑖 ∈ K*[𝑥] são livres de
quadrados e dois a dois coprimos de grau positivo. Então os 𝑐𝑖 são todas as raízes
distintas do polinômio
𝑅(𝑧) = res𝑥(𝑎− 𝑧𝑏′,𝑏) ∈ K*[𝑧]
e os 𝑣𝑖 são os polinômios
𝑣𝑖 = mdc(𝑎− 𝑐𝑖𝑏′,𝑏) ∈ K*[𝑥].
Demonstração. Diferenciando a equação (3.18), temos
𝑎
𝑏
=
𝑛∑︁
𝑖=1
𝑐𝑖
𝑣′𝑖
𝑣𝑖
. (3.19)
Seja
𝑢𝑖 =
𝑛∏︁
𝑗 ̸=𝑖
𝑣𝑗, 1 ≤ 𝑖 ≤ 𝑛.
Capítulo 3. Integração Indefinida de Funções Racionais Complexas 42
Multiplicando ambos os lados de (3.19) por 𝑏
𝑛∏︁
𝑗=1
𝑣𝑗, temos
𝑎
𝑛∏︁
𝑗=1
𝑣𝑗 = 𝑏
𝑛∑︁
𝑖=1
𝑐𝑖𝑣
′
𝑖𝑢𝑖. (3.20)
Mostraremos que, a menos de uma constante multiplicativa,
𝑏 =
𝑛∏︁
𝑗=1
𝑣𝑗. (3.21)
Observe que mdc(𝑎,𝑏) = 1, donde (3.20) 𝑏 |
𝑛∏︁
𝑗=1
𝑣𝑗. Por outro lado, para cada 𝑗,
temos de (3.20) que
𝑣𝑗 | 𝑏
𝑛∑︁
𝑖=1
𝑐𝑖𝑣
′
𝑖𝑢𝑖.
Por definição, cada 𝑣𝑗 divide 𝑢𝑖 para 𝑗 ̸= 𝑖. Isto quer dizer que
𝑣𝑗 | 𝑏𝑣′𝑗𝑢𝑖.
Como os 𝑣𝑖 são supostos livres de quadrados, temos que mdc(𝑣𝑗,𝑣′𝑗) = 1. Além
disso, mdc(𝑣𝑗,𝑢𝑗) = 1, pela definição de 𝑢𝑗 e pelo fato de que os 𝑣𝑖 são dois a dois
primos entre si. Resta, portanto, que 𝑣𝑗 | 𝑏 para 1 ≤ 𝑗 ≤ 𝑛. Portanto,
𝑛∏︁
𝑗=1
𝑣𝑗 | 𝑏,
donde verificamos (3.21).
As equações (3.20) e (3.21) combinadas implicam
𝑎 =
𝑛∑︁
𝑖=1
𝑐𝑖𝑣
′
𝑖𝑢𝑖.
A seguir, mostraremos que, para cada 𝑗,
𝑣𝑗 | (𝑎− 𝑐𝑗𝑏′). (3.22)
43 3.4. O Algoritmo de Rothstein-Trager
Observe que, de (3.21), temos
𝑏′ =
𝑛∑︁
𝑖=1
𝑣′𝑖𝑢𝑖.
Portanto,
𝑎− 𝑐𝑗𝑏′ =
𝑛∑︁
𝑖=1
𝑐𝑖𝑣
′
𝑖𝑢𝑖 − 𝑐𝑗
𝑛∑︁
𝑖=1
𝑣′𝑖𝑢𝑖 =
𝑛∑︁
𝑖=1
(𝑐𝑖 − 𝑐𝑗)𝑣′𝑖𝑢𝑖. (3.23)
No último somatório, para cada termo com 𝑖 ̸= 𝑗, temos que 𝑣𝑗 | 𝑢𝑖, enquanto que
quando 𝑖 = 𝑗, o termo desaparece. Portanto, verificamos (3.22). De (3.21) e (3.22)
temos que 𝑣𝑗 é um divisor comum de 𝑎− 𝑐𝑗𝑏′ e 𝑏 para cada 𝑗. Mostraremos que
se trata de um mdc. É suficiente mostrar que para 𝑘 ̸= 𝑗, mdc(𝑎 − 𝑐𝑗𝑏′,𝑣𝑘) = 1.
Para isto, utilizando (3.23), temos que
mdc(𝑎− 𝑐𝑗𝑏′,𝑣𝑘) = mdc
(︃
𝑛∑︁
𝑖=1
(𝑐𝑖 − 𝑐𝑗)𝑣′𝑖𝑢𝑖,𝑣𝑘
)︃
= mdc((𝑐𝑘 − 𝑐𝑗)𝑣′𝑘𝑢𝑘,𝑣𝑘). (3.24)
A última igualdade acima se verifica porque 𝑣𝑘 é um fator de cada 𝑢𝑖, para
𝑖 ̸= 𝑘. Porém, para 𝑘 ̸= 𝑗, o mdc acima é 1, pois 𝑐𝑘 ̸= 𝑐𝑗, mdc(𝑣𝑘,𝑣′𝑘) = 1 e
mdc(𝑣𝑘,𝑢𝑘) = 1. Portanto, mostramos que
𝑣𝑗 = mdc(𝑎− 𝑐𝑗𝑏′,𝑏), 1 ≤ 𝑗 ≤ 𝑛.
Logo, temos que res𝑥(𝑎 − 𝑐𝑗𝑏′,𝑏)