Ensaio sobre um novo método para determinar os máximos e os mínimos das fórmulas integrais definidas

O problema da braquistócrona lançado por Bernoulli despertou o interesse dos geómetras do seu tempo e das gerações posteriores. Entre estes, detaca-se Euler que foi o primeiro a tratar esse e uma generalização desse tipo de problemas.

O métondo foi estendido por Lagrange numa Memória cujo título vem em epígrafe encontrado-se uma tradução que realizei aqui. Decidi traduzir o artigo não apenas por conter importantes ideias no campo do cálculo das variações mas também por considerar que foi aí que o autor expôs pela primeira vez o método dos multiplicadores. Além disso conseguiu coaduná-lo com a resolução de problemas de mecânica numa Memória posterior.

Existência de quantidades transcendentes

Um número qualquer diz-se irracional se não for solução de nenhuma equação da forma onde e são números inteiros. Sabemos, por exemplo, que constitui um número nesta classe.

Como generalização ao que foi apresentado, dizemos que um número é algébrico se for solução de alguma equação polinomial

cujo grau é um número finito.

Posto isto, somos levados a indagar se existirão números que não são solução de nenhuma equação algébrica. A resposta é positiva e foi dada por Liouville na sua Memória sobre uma classe de quantidades raras cujo valor não é algébrico nem mesmo redutível às irracionalidades algébricas, na qual construiu alguns exemplos.

Mais tarde Hermite mostrou que é transcendente e Lindemann, por intermédio de uma generalização conveniente, demonstrou que é transcendente. É pertinente referir um resultado ainda mais geral devido a Weirstrass, o qual recebe o pomposo nome de Teorema de Hermite-Lindemann-Weirstrass, no qual se afirma que se um conjunto de números algébricos for linearmente independente sobre então o conjunto de números é algebricamente independente sobre .

Factorização de polinómios em polinómios com raízes simples

Um polinómio é susceptível de conter raízes cuja multiplicidade é superior a um. Por exemplo, o polinómio

possui as raízes , , e onde a primeira tem multiplicidade , a segunda e a terceira têm multiplicidade e a quarta tem multiplicidade . Este polinómio admite uma factorização da forma

onde

Os polinómios goazam de uma propriedade especial. São primos entre si e, como tal, por intermédio do algoritmo de Euclides estendido, é possível mostrar que somos capazes de realizar a decomposição da expressão racional

onde é um polinómio qualquer. Convém salientar o facto de que não é necessário proceder ao cálculo explícito das raízes para obter uma factorização do género, tendo em conta que, sendo uma raiz de ordem de um polinómio então esta será uma raiz de ordem da sua derivada, . Em particular, se a for raiz simples de então não poderá ser raiz de .

Com base na decomposição explicitada, Hermite elaborou um método que permite determinar a parte algébrica do integral de uma função raional sem calcular explicitamente as raízes, relegando o seu cálculo explícito para a determinação da parte logarítmica.

Com isto em mente, elaborei um pequeno vídeo com uma explicação de como esta factorização funciona.

O problema do transporte

Suponhamos que estamos na presença de uma série de fontes, cada qual com um determinado número de provisões. As provisões de cada uma das fontes terão de ser transportadas para um conjunto de clientes, os quais requerem, cada um, uma determinada quantidade de provisões. As provisões têm de ser transportadas das fontes para os clientes estando associado um custo de transporte por provisão entre cada fonte e cliente. Pretende-se determinar as quantidades de provisões que são transportadas de cada uma das fontes e os clientes de modo a minimizar o custo respectivo.

Não pretendo expor aqui uma descrição deste famigerado problema de optimização. No entanto, como iniciei o meu doutoramento na área, tenho ensaiado a implementação de alguns algoritmos dos quais conto precisamente com o que permite resolver este problema. Trata-se de uma variação do algoritmo do simplex e podemos encontrá-lo no livro Introduction to Operations Research de Hillier e Liberman.

Disponibilizo o código da minha implementação em C# aqui.

Para o utilizar, segue um pequeno exemplo de código:

int[] supplyVector = new int[4] { 50, 60, 50, 50 };
int[] demandVector = new int[5] { 30, 20, 70, 30, 60 };
double[,] costs = new double[4, 5] {
{ 16, 16, 13, 22, 17 },
{ 14, 14, 13, 19, 15 },
{ 19, 19, 20, 23, double.MaxValue },
{ double.MaxValue,0, double.MaxValue, 0, 0 } };
TransportationProblemDouble transportationProblem = new TransportationProblemDouble(
supplyVector,
demandVector,
costs);
transportationProblem.Run();
Console.WriteLine("z={0}", transportationProblem.ObjectiveFunctionValue);
for (int i = 0; i < transportationProblem.Results.GetLength(0); ++i)
{
for (int j = 0; j < transportationProblem.Results.GetLength(1); ++j)
{
Console.WriteLine("[{0},{1}]->{2}", i, j, transportationProblem.Results[i, j]);
}
}

A matriz que segue como exemplo provém do livro supracitado. Aproveito para referir que não testei o algoritmo em instâncias muito grandes.

No que concerne à implementação, recorri ao método de Russel para obter uma boa solução inicial. Contudo, considero pertinente referir que o de Vogel e o Norte-Oeste se encontram implementados apesar de não estarem a ser utilizados.

Algo mais sobre raízes da unidade

Na publicação Raízes da unidade faço referência a um texto que elaborei sobre as raízes da unidade onde, algures, exponho um método devido a Gauss. O autor recorreu-se desse método para mostrar um resultado muito interessante sobre a divisão da circunferência em partes iguais. No entanto, o método, tal como o descrevi, não permite concluir o processo, uma vez que somos conduzidos a um conjunto de equações primitivas com grau primo.

No texto Um comentário em teoria das equações ciclotómicas apresentei uma justificação do método de Vandermonde com base num artifício introduzido por Abel. Vou aqui brevemente mostrar como o mesmo artifício pode ser utilizado para resolver as equações primitivas supracitadas. Como exemplo, vou considerar a equação ciclotómica de grau , que se factoriza como

Seja uma raiz desta equação. Sabemos que todas as outras raízes se podem obter desta por exponenciação simples. Ordenamo-las de forma que e representamo-las abreviadamente por .

Com um pouco de esforço computacional (este esforço pode ser diminuído se nos recorrermos a determinados resultados de teoria dos números) vemos que é raíz primitiva de e as suas potências geram o seguinte grupo, por ordem:

Se considerarmos o gerador , por exemplo, factorizamos em

Note-se que é um subgrupo de e os restantes conjuntos constituem precisamente os respectivos co-conjuntos e . Definimos os períodos

Com um pouco de aritmética chegamos aos resultados

De acordo com as fórmulas de Viète vemos que , e são as três raízes da equação irredutível de grau primo

Poder-nos-íamos recorrer de uma fórmula do tipo de Cardano para resolver esta equação. No entanto, vamo-nos centrar nas possíveis relações algébricas que possam existir entre cada uma das suas raízes uma vez que conhecemos algumas das suas propriedades. Se designarmos, por simplicidade, as quantidades , e por , e , obtemos, após mais algumas manobras aritméticas, as identidades

e

Se combinarmos as expressões anteriores, obtemos

Concluímos daqui que onde constitui uma função polinomial e, consequentemente, algébrica. De acordo com o referido artifício, vemos que os resolventes

se podem escrever como funções simétricas dos e, por conseguinte, como função polinomial dos coeficientes do polinómio de grau que nos propomos resolver onde representa uma raíz de ordem da unidade. O cálculo dos resolventes simplifica-se com o auxílio das expressões

e

A prova de que qualquer período goza da propriedade que referimos permite mostrar, com base nesta técnica, que qualquer equação ciclotómica admite uma solução com base na aplicação das operações aritméticas e extracção de raízes.

O número pi

O (pi) talvez seja a constante mais conhecida em matemática e representa o coeficiente de proporcionalidade entre a área e o quadrado do raio de um círculo. Mostrou-se que esse número é transcendente e ainda hoje são despendidos esforços no cálculo das suas casas decimais.

Como o tema se alonga, apresento no skydrive o texto O número pi onde apresento alguns dos resultados clássicos. Os mais recentes ficam de fora, uma vez que se baseiam em teoria das funções especiais, a qual constitui um campo muito extenso devido à quantidade de técnicas que lhe são subjacentes.

Alguns detalhes sobre serialização e desserialização

Por vezes existe a necessidade de persistir dados num ficheiro antes do término de uma aplicação. Normalmente, quando enveredamos por linguagens orientadas a objectos como é o caso do java ou do csharp, esses dados encontram-se estruturados em objectos que poderão manter uma série de relações entre si. De modo a possibilitar a persistência de objectos completos num ficheiro ou transmiti-los para uma outra máquina por intermédio de uma rede, ambas as linguagens implementaram aquilo que recebe a designação de serialização e desserialização de objectos. Irei aqui discutir alguns detalhes aferentes a estes conceitos em csharp.

Começo com um objecto simples, SerializableObject que implementa parcialmente uma forma rude de lista com um número máximo de elementos.

public delegate void AddedDescription(object sender, AddEventArgs args);

public class AddEventArgs : EventArgs
{
public string AddedDescription { get; set; }
}

[Serializable]
public class SerializableObject
{
private string[] descriptions;
private string info;

private int current = 0;

public SerializableObject(int count)
{
if (count < 0)
{
throw new ArgumentException("Parameter count must be positive.");
}

this.descriptions = new string[count];
}

public int Length
{
get
{
return this.current;
}
}

public string AddicionalInfo
{
get
{
return this.info;
}
set
{
this.info = value;
}
}

[field: NonSerialized]
public event AddedDescription DescriptionAdded;

public void Add(string description)
{
if (this.current >= this.descriptions.Length)
{
throw new Exception("Can not add more objects.");
}

if (this.DescriptionAdded != null)
{
this.DescriptionAdded.Invoke(this, new AddEventArgs() { AddedDescription = description });
}

this.descriptions[this.current++] = description;
}

public override string ToString()
{
StringBuilder result = new StringBuilder();
result.Append("{");
result.Append(this.info);
result.Append(", [");
if (this.current > 0)
{
result.Append(this.descriptions[0]);
}

for (int i = 1; i < this.current; ++i)
{
result.Append(", ");
result.Append(this.descriptions[i]);
}

result.Append("]");
result.Append("}");
return result.ToString();
}
}

Observamos que a classe SerializableObject está marcada com o atributo [Serializable]. Este atributo permite estabelecer o facto de que um objecto deste tipo admite serialização. O código que se segue serializa um objecto para um MemoryStream e volta a desserializá-lo, isto é, a recuperá-lo novamente.

class Program
{
static void Main(string[] args)
{
try
{
SerializableObject objectToSerialize = new SerializableObject(10) { AddicionalInfo = "initial" };
objectToSerialize.DescriptionAdded += AddDescriptionVerifier;

objectToSerialize.Add("string 1");
objectToSerialize.Add("string 2");
objectToSerialize.Add("string 3");
objectToSerialize.Add("string 4");

Console.WriteLine("Before serialization:");
Console.WriteLine(objectToSerialize);

var myStream = new MemoryStream();
var formatter = new BinaryFormatter();
formatter.Serialize(myStream, objectToSerialize);

myStream.Seek(0, SeekOrigin.Begin);
var deserializedObject = (SerializableObject)formatter.Deserialize(myStream);
Console.WriteLine("After serialization and desserialization:");
Console.WriteLine(deserializedObject);

deserializedObject.Add("invalid");
}
catch (Exception except)
{
Console.WriteLine(except.Message);
}
}

static void AddDescriptionVerifier(object sender, AddEventArgs args)
{
if (string.IsNullOrEmpty(args.AddedDescription))
{
throw new Exception("Can't add nulls.");
}

if (args.AddedDescription.ToLower() == "invalid")
{
throw new Exception("Invalid add element.");
}
}
}

Este requer a utilização do namespace System.Runtime.Serialization.Formatters.Binary. Existe aqui um pormenor que carece de especial atenção. A classe SerializableObject atira um evento sempre que o utilizador adiciona um item à lista. No programa, por seu turno, está implementado um listener que reage com uma excepção quando tentamos introduzir a palavra “invalid”. Verificamos que, ao executar a pequena aplicação, quando tentamos introduzir a palavra inválida no objecto desserializado, desserializedObject, o listener correspondente é executado. Contudo, podemos querer desserializar o objecto num contexto sob o qual não existe esse listener. Neste caso, somos forçados a colocar sobre o evento, SerializableObject::DescriptionAdded, o atributo [field: NonSerialized]. Este atributo permite indicar que o evento não deverá ser serializado. A palavra field que precede o verdadeiro atributo, [NonSerialized], permite instruir o compilador a considerar o evento como um campo, uma vez que o atributo é apenas válido nesse caso. Obviamente, qualquer campo marcado com [NonSerialized], não é serializado. Para serializar o objecto objectToSerialize, recorremo-nos da instância de um formatador binário. Este formatador permite serializar o objecto em formato binário. Porém, também existe um formatador que permite serializar objectos em XML.

Suponhamos agora que, sempre que desserializamos o objecto, o seu campo info terá de apresentar a palavra “deserialized”. Facilmente conseguimos este efeito se a nossa classe serializável implementar a interface IDeserializationCallback, como é mostrado de seguida.

[Serializable]
public class SerializableObject : IDeserializationCallback
{
// O resto do código aferente à classe segue aqui

void IDeserializationCallback.OnDeserialization(object sender)
{
this.info = "deserialized";
}
}

Imaginemos um terceiro cenário no qual existe uma classe com um número elevado de campos que aglomera toda a estrutura relativa ao nosso modelo de dados. No entanto, pretendemos descartar campos fazendo essa escolha em tempo de execução. Neste caso, o atributo [NonSerialized] torna-se impotente, uma vez que apenas pode ser alterado em tempo de compilação.

De modo a responder ao problema, somos conduzidos àquilo que recebe o nome de Surrogates (delegados). No caso da serialização, um Surrogate é uma classe que implementa a interface ISerializationSurrogate e permite gerir a informação que é serializada. Esta interface implementa duas funções que lidam com o objecto a tratar, um SerializationInfo que contém a informação a ser serializada, um StreamingContext que permite definir um contexto de serialização e um ISurrogateSelector. Esta última classe permite percorrer uma série de Surrogates de modo a encontrar aquele que se adequa ao tratamento de um dado objecto. O código que se segue implementa o nosso Surrogate.

class MySerializationSurrogate<ObjectType> : ISerializationSurrogate
where ObjectType : class
{
public void GetObjectData(object obj, SerializationInfo info, StreamingContext context)
{
List<string> listInContex = context.Context as List<string>;
if (listInContex == null)
{
throw new SerializationException("There are no defined fields in context to be serialized.");
}

foreach (var item in listInContex)
{
var serializable = typeof(ObjectType).GetField(item, BindingFlags.Instance | BindingFlags.NonPublic).GetValue(obj);
info.AddValue(item, serializable);
}
}

public object SetObjectData(object obj, SerializationInfo info, StreamingContext context, ISurrogateSelector selector)
{
List<string> listInContex = context.Context as List<string>;
if (listInContex == null)
{
throw new SerializationException("There are no defined fields in context to be deserialized.");
}

foreach (var item in listInContex)
{
var property = typeof(ObjectType).GetField(item, BindingFlags.Instance | BindingFlags.NonPublic);
var deserialized = info.GetValue(item, property.FieldType);

property.SetValue(obj, deserialized);
}

return null;
}
}

Aqui estão implementadas as duas funções, GetObjectData que colecciona os dados dos campos do objecto a serializar e inclui no SerializationInfo, o qual realiza a serialização dessa informação. A lista dos campos a serializar é incluída no respectivo StreamingContext. Por seu turno, a função SetObjectData permite obter, com base no contexto, os campos que são para desserializar e reconstrói o objecto preenchendo apenas esses campos (os restantes ficam nulos). Existe uma sobrecarga do construtor da classe BinaryFormatter que permite receber o contexto e o selector. Ao selector, adicionamos o nosso Surrogate e ao contexto adicionamos a lista dos campos que queremos serializar ou desserializar.

static void Main(string[] args)
{
SerializableObject objectToSerialize = new SerializableObject(10) { AddicionalInfo = "initial" };
objectToSerialize.DescriptionAdded += AddDescriptionVerifier;

objectToSerialize.Add("string 1");
objectToSerialize.Add("string 2");
objectToSerialize.Add("string 3");
objectToSerialize.Add("string 4");

Console.WriteLine("Before serialization:");
Console.WriteLine(objectToSerialize);

var myStream = new MemoryStream();
SurrogateSelector surrogateSelector = new SurrogateSelector();
var context =  new StreamingContext(StreamingContextStates.All, new List<string>(){"info", "current"});
MySerializationSurrogate<SerializableObject> surrogate = new MySerializationSurrogate<SerializableObject>();
surrogateSelector.AddSurrogate(typeof(SerializableObject), context, surrogate);
BinaryFormatter formatter = new BinaryFormatter(surrogateSelector, context);

formatter.Serialize(myStream, objectToSerialize);

surrogateSelector = new SurrogateSelector();
context = new StreamingContext(StreamingContextStates.All, new List<string>() { "info", "current" });
surrogate = new MySerializationSurrogate<SerializableObject>();
surrogateSelector.AddSurrogate(typeof(SerializableObject), context, surrogate);
formatter = new BinaryFormatter(surrogateSelector, context);

myStream.Seek(0, SeekOrigin.Begin);
var deserializedObject = (SerializableObject)formatter.Deserialize(myStream);
Console.WriteLine("After serialization and desserialization:");
Console.WriteLine(deserializedObject);
}

A execução do código anterior resulta numa excepção provocada pela tentativa de aceder a um campo por intermédio de uma referência nula. De facto, como serializamos e desserializamos apenas os campos info e current, o campo description fica a nulo. No entanto, este é acedido na função ToString onde é lançada a excepção. Podemos, porventura, precaver esta situação na função IDeserializationCallback.OnDeserialization onde forçamos os campos nulos a adquirir um valor por defeito, mantendo a integridade do objecto.