Introdução
Nesta dissertação estudamos problemas de interpolação suave em espaços Euclidianos
e outras variedades Riemanianas. A motivação para a necessidade de construir curvas
interpoladoras suaves vem de diversas aplicações à engenharia.
Ao longo do tempo foram propostas diferentes abordagens para o problema da geração
de splines interpoladores. As dificuldades inerentes à extensão de resultados conhecidos, guiaram os nossos trabalhos de investigação por dois percursos que correspondem a
abordagens distintas do mesmo problema. Se por um lado, dedicamos uma parte deste
trabalho ao estudo de curvas spline em espaços Euclidianos, que sejam solução de certos
problemas de optimização, por outro, dedicamos parte dos nossos esforços ao desenvolvimento de algoritmos geométricos que permitem gerar de forma eficiente curvas spline
de suavidade arbitrária em outras variedades Riemanianas. Nunca deixamos contudo
de questionar o comportamento optimal das curvas geradas. Trabalhos anteriores em
espaços não Euclidianos parecem indicar não ser possı́vel alcançar o melhor de “dois
mundos”. Se se pretende gerar curvas interpoladoras que sejam óptimas num certo sentido, então o reverso da medalha surge geralmente com a dificuldade da determinação de
expressões explı́citas para as curvas que se vislumbram. Por estes motivos esta dissertação
encontra-se dividida em duas partes.
A primeira parte intitulada “Funções spline associadas a operadores diferenciais e
controlo optimal”, é dedicada à caracterização de certas curvas spline em espaços Euclidianos e ao estudo da sua relação com problemas de interpolação dinâmica1 . A segunda
parte desta tese denominada “Algoritmos geométricos para a geração de curvas spline em
variedades Riemanianas”, é por sua vez dedicada ao desenvolvimento de dois algoritmos
geométricos, para a geração de curvas spline em certas variedades Riemanianas conexas
e compactas.
Seguimos com uma pequena introdução histórica sobre funções spline, que nos conduz
ao ponto em que iniciámos os trabalhos de investigação que compõem a primeira parte
desta dissertação, e permite enquadrar o trabalho por nós desenvolvido.
1 Expressão
introduzida por Crouch e Jackson no inı́cio da década de 90 em [18] e [35], para designar
problemas de controlo optimal em que se pretende conduzir variáveis de estado de um sistema de controlo, por um conjunto de condições de interpolação, através da determinação de variáveis de controlo
adequadas.
1
Introdução
As funções spline2 despontaram na área da aproximação numérica, durante a década
de 50 do século XX, é contudo aceite que a primeira referência matemática a splines surgiu
em 1946 num artigo de Schoenberg. Estas surgiram no contexto da procura de melhores soluções para problemas de interpolação, onde além das condições de interpolação
clássicas, há também determinadas condições de continuidade. Na sua génese, as funções
spline eram simplesmente funções definidas num intervalo real [a, b], com expressão polinomial em cada intervalo de uma partição ∆ de [a, b] e com a exigência acrescida de
um certo grau de suavidade em cada ponto intermédio de ∆ (na ligação dos polinómios
adjacentes). Ou seja, em vez de aproximar uma função por um único polinómio num
intervalo [a, b], concretiza-se a aproximação pela colagem de várias funções polinomiais.
Prescinde-se da suavidade global da função que aproxima para obter uma aproximação
melhor.
A natureza e as propriedades fundamentais dos splines polinomiais, permitiram que
fossem rapidamente adoptados em diversas áreas de matemática aplicada tais como,
modelação geométrica na construção de automóveis e na construção de aeronaves (na
indústria automóvel, pode referir-se em particular os trabalhos de De Casteljau na
Citroën, de Bézier na Renault e de De Boor na General Motors), levando a teoria das
funções spline a um desenvolvimento fulgurante. Algum tempo mais tarde, em desenho
assistido por computador, as funções spline tiveram um papel determinante como ferramenta essencial na reprodução de formas complexas suaves. Neste contexto, os splines
polinomiais são agora curvas parametrizadas seccionalmente polinomiais. O sucesso da
utilização extensiva de splines polinomiais nas diversas áreas, deveu-se em grande parte
à sua simplicidade do ponto de vista computacional e à sua capacidade intrı́nseca de
reproduzir formas complexas.
Os splines cúbicos são com toda a certeza os splines polinomiais mais divulgados. São
por definição funções reais definidas no intervalo [a, b] ⊂ R, duas vezes continuamente
diferenciáveis em [a, b], que em cada intervalo de uma partição
∆ : a = t 0 < t1 < · · · < tm = b
de [a, b], têm uma expressão polinomial de grau máximo três. Mostra-se que um spline
cúbico existe e é único se forem prescritas mais duas condições de interpolação nas
derivadas, uma no instante inicial e outra no instante final. Usualmente, prescrevemse os valores da primeira derivada em t = a e t = b. A curva resultante é o spline cúbico
mais conhecido, que é geralmente designado por spline cúbico clássico. Uma alternativa
consiste em prescrever os valores da segunda derivada, originando o spline cúbico natural,
2A
palavra spline provém do nome de um instrumento usado por engenheiros para o ajustamento
de curvas suaves, por determinados pontos de interpolação. Imagens esclarecedoras sobre o uso de
splines encontram-se no endereço (http://www.cs.wisc.edu/∼deboor/draftspline.html). Uma recolha
bibliográfica sobre splines em teoria da aproximação, mantida por Larry Schumaker e Carl de Boor,
pode ser consultada, por exemplo, em (http://www.cs.wisc.edu/∼deboor/bib/bib.html).
2
Introdução
se forem prescritos valores nulos. O spline cúbico clássico tem uma propriedade optimal
interessante. Mostra-se que é o único minimizante da funcional integral
J(x(·)) =
Z
b
(ẍ(t))2 dt
a
no conjunto das funções x : [a, b] → R que satisfazem idênticas condições de interpolação
e são duas vezes continuamente diferenciáveis em [a, b]. A extensão natural ao caso de
curvas parametrizadas em espaços Euclidianos de dimensão arbitrária é relativamente
simples de concretizar.
A extensão do conceito de spline polinomial não tardou e progrediu em diversas
direcções. Uma generalização importante surgiu na década de 60 com os splines generalizados escalares de Ahlberg, Nilson e Walsh [2]3 . Este conjunto de funções spline contém
em particular todos os splines polinomiais. São funções reais definidas em [a, b] que, em
cada intervalo de uma partição ∆ de [a, b], são solução de uma equação diferencial da
forma
L∗ L x = 0
onde L é um operador diferencial linear de ordem p e L∗ é o adjunto de L. Em cada
instante t = a e t = b prescrevem-se p condições de interpolação e exige-se que a função
que resulta da ligação de todos os segmentos, seja suave de classe C 2p−2 no intervalo [a, b].
Existe um único spline generalizado escalar associado ao operador L, à partição ∆ e ao
conjunto de condições de interpolação prescrito. O spline cúbico clássico ocorre quando
p = 2 e L ≡ D2 . A propriedade optimal deste spline cúbico encontra também uma
generalização natural. O spline generalizado escalar é o único minimizante da funcional
J(x(·)) =
Z
b
(Lx(t))2 dt
a
no conjunto das funções x : [a, b] → R que satisfazem as mesmas condições de interpolação
e são de classe C 2p−2 no intervalo [a, b].
Com Schultz e Varga [70] surgiram em 1967 as funções L-spline, conjunto de funções
que contém os splines generalizados de Ahlberg, Nilson e Walsh como caso particular.
Schultz e Varga vão um pouco mais longe, permitindo nos instantes intermédios de uma
partição ∆ de [a, b], condições de interpolação nas derivadas e um número variável de
condições de suavidade. Em cada instante intermédio as condições de suavidade e as
condições de interpolação nas derivadas totalizam 2p condições. O número de condições
de interpolação nas derivadas e o número de condições de suavidade pode contudo variar
com equilı́brio, de ponto para ponto da partição ∆ de [a, b].
A evolução constante permite que hoje em dia o termo spline tenha uma
conotação um pouco mais “suave”. Podemos afirmar que os splines são, na
3 Os
mesmos autores são, ainda na mesma época, responsáveis pela primeira referência bibliográfica
inteiramente dedicada ao estudo das funções spline [3].
3
Introdução
sua essência, funções interpoladoras com um certo grau de suavidade global,
resultado da ligação (colagem com certas condições de suavidade) de funções
mais simples que são os seus segmentos.
O estudo de splines no contexto da análise de problemas de controlo optimal, teve inı́cio
no princı́pio da década de 90, como resposta à procura de outro tipo de ferramentas
matemáticas, para lidar com questões de ı́ndole prática, associadas por exemplo, a problemas de tráfego aéreo ou a problemas de planeamento de trajectórias para sistemas
mecânicos. Os trabalhos de investigação de Crouch e Jackson para dinâmicas lineares [18]
e dinâmicas não-lineares [35], parecem-nos ser as primeiras publicações sobre splines em
espaços Euclidianos e controlo optimal. Um pouco mais tarde, Martin e seus colaboradores [46], estabeleceram uma relação directa entre os splines generalizados de Ahlberg,
Nilson e Walsh e certos problemas de controlo optimal para sistemas lineares com uma
única entrada e uma única saı́da (SISO 4 ). Este trabalho inovador é no entanto um pouco
obscuro. Os autores transmitem a ideia da descoberta de um vasto leque de novos splines
ignorando que estes, não são mais do que, os já bem conhecidos splines generalizados escalares. O enquadramento correcto com uma simplicidade de processos considerável é
conseguido mais tarde por Rodrigues em [66] e Rodrigues, Silva Leite e Simões em [60].
Com estes três trabalhos ficou claro que os splines generalizados podem ser interpretados, como output óptimo de problemas de controlo optimal, para sistemas contı́nuos
invariantes no tempo, na forma canónica de controlabilidade.
Os resultados obtidos estabeleceram uma pequena ponte entre a teoria das funções
spline (associadas a operadores diferenciais) e a teoria de sistemas, apresentando por
essa via uma nova perspectiva sobre o assunto. As funções spline são afinal mais do que
soluções de certos problemas de interpolação, surgem naturalmente como componente
fundamental em problemas de controlo optimal.
A ligação entre splines em espaços Euclidianos e controlo optimal é um dos temas que
Martin e seus colaboradores continuaram a explorar, consulte-se por exemplo [74], [45],
[25] e [26]. Contudo, em grande parte destes trabalhos, a ligação não é estabelecida com
splines generalizados escalares mas sim com splines suavizantes, isto é, de uma forma
simples, funções spline que em vez de interpolar, passam razoavelmente perto dos dados
prescritos (situação que é conveniente considerar quando, por exemplo, se acredita que
a obtenção dos dados iniciais está sujeita a erros). Estas funções spline surgiram com
destaque no trabalho de Wahba na área da estatı́stica [79]. Vem a propósito mencionar
o recente trabalho de doutoramento de Luı́s Machado onde é desenvolvido o estudo de
splines suavizantes no contexto global das variedades Riemanianas [44].
Surge agora o momento de descrever os progressos que alcançámos após a obtenção
dos resultados descritos em [66] e [60]. Progredimos na procura de estabelecer ligações
entre a teoria das funções spline, associadas a operadores diferenciais e a teoria dos
4 Do
4
Inglês “single input single output”.
Introdução
sistemas de controlo. É neste contexto que surgem os resultados originais que constituem
a primeira parte desta tese. No primeiro capı́tulo estendemos os resultados obtidos, para
os splines generalizados escalares de Ahlberg, Nilson e Walsh, à classe mais geral das
funções L-spline de Schultz e Varga. A perspectiva sobre o assunto é agora bem mais
vasta o que permite definir com mais clareza certos aspectos não observáveis, aquando
do estudo feito para os splines generalizados escalares. O segundo capı́tulo é totalmente
dedicado à definição e equivalência de uma classe de novos splines multi-dimensionais,
em espaços Euclidianos de dimensão arbitrária, associados a operadores diferenciais lineares com coeficientes matriciais e problemas de controlo optimal para sistemas com
entradas múltiplas e saı́das múltiplas (MIMO 5 ). Os resultados são obtidos directamente
para a situação mais geral em que a dinâmica é variante no tempo. Estes resultados
levantam problemas complicados de natureza computacional, que na sua versão mais
simples envolvem polinómios matriciais directamente associados à resolução do problema
quadrático de valores próprios. Em qualquer destes capı́tulos a abordagem começa por
ser variacional. Este é do nosso ponto de vista o caminho natural a percorrer entre duas
áreas aparentemente “desconexas”.
Iniciamos a descrição do outro percurso que culminou na obtenção dos resultados
contidos na segunda parte desta tese, incluindo factos históricos relevantes que permitem
enquadrar o trabalho desenvolvido.
O estudo de splines em espaços não Euclidianos é consequência da procura de novas
técnicas em muitas aplicações à engenharia onde os espaços de configuração são estruturas geométricas não Euclidianas. Esta necessidade fez com que os desenvolvimentos
posteriores passassem pela adaptação e generalização a variedades Riemanianas (como
é o caso de alguns grupos de Lie) das técnicas e métodos desenvolvidos em espaços
Euclidianos. O problema do planeamento de trajectórias para sistemas mecânicos é um
exemplo importante. Por exemplo, Z̆efran, Kumar e Croke em [78], estudaram o problema da construção de uma trajectória suave para o movimento de um corpo rı́gido,
com o conhecimento prévio das posições e orientações inicial e final do corpo. Analisaram estes problemas numa perspectiva optimal considerando determinadas funcionais
custo. Trata-se concretamente de um problema de planeamento de trajectórias no grupo
de Lie especial Euclidiano SE(3, R).
Uma generalização do conceito de spline cúbico em variedades Riemanianas surgiu
em 1989 com o trabalho pioneiro de Noakes, Heinzinger e Paden [50]. Esta generalização
baseia-se na extensão a variedades Riemanianas do conceito Euclidiano de polinómio
cúbico. Estes são definidos como as soluções de um problema de segunda ordem do
cálculo das variações, que consiste em minimizar a funcional integral
J(γ(·)) =
Z
0
5 Do
1
D
D dγ D dγ
dt dt , dt dt
E
dt
Inglês “multi input multi output”.
5
Introdução
no conjunto das curvas na variedade, que são em simultâneo de classe C 2 e satisfazem
condições de interpolação nos instantes t = 0 e t = 1. Na expressão da funcional, h·,·i
D
denota a derivada covariante de um campo de
identifica a métrica Riemaniana e dt
vectores ao longo de uma curva na variedade. Observa-se que os splines cúbicos em va-
riedades são afinal as curvas com todas as condições prescritas, que minimizam o integral
do quadrado da norma da componente tangencial da sua aceleração. Esta generalização
coincide em particular com a formulação variacional (clássica) de um polinómio cúbico
em espaços Euclidianos. A abordagem utilizada em [50] despertou um interesse renovado
por estes assuntos, bem patente nos trabalhos posteriores de Crouch e Silva Leite [21, 22]
no contexto dos problemas de interpolação dinâmica em variedades Riemanianas e de
Camarinha [15] no estudo da geometria dos polinómios cúbicos Riemanianos. O estudo de
splines polinomiais de ordem superior em variedades Riemanianas surgiu com Camarinha,
Silva Leite e Crouch em [14].
O constante e crescente uso de splines em variedades Riemanianas, bem como o interesse em evitar as dificuldades decorrentes da abordagem variacional, nomeadamente,
a incapacidade em resolver as equações de Euler-Lagrange com a consequente não determinação de expressões explı́citas para as curvas interpoladoras, deram o impulso
necessário a outra abordagem para gerar curvas interpoladoras em variedades Riemanianas, que consiste na generalização do algoritmo clássico de De Casteljau. Este algoritmo
que é bastante eficaz do ponto de vista numérico, permite em espaços Euclidianos a construção de curvas polinomiais de qualquer grau, através de um método recursivo onde em
cada etapa se aplica sucessivamente um processo de interpolação linear. A construção de
splines polinomiais é consequência da aplicação repetida do algoritmo. A generalização
natural deste algoritmo a outras variedades Riemanianas conexas e completas, tais como
grupos de Lie de matrizes conexos e compactos, como por exemplo, o grupo ortogonal especial das rotações no espaço SO(3, R), foi apresentada por Park e Ravani em [51]. Estes
conceberam a ideia simples de substituir os segmentos de recta, em espaços Euclidianos,
por arcos de geodésica, em variedades Riemanianas. Esta generalização envolve um certo
grau de sofisticação, valendo a pena destacar que é do ponto de vista teórico bastante
simples. Uma das vantagens deste novo algoritmo em relação à abordagem variacional
reside na obtenção de expressões explı́citas para os splines gerados. O estudo e aplicação
do algoritmo na esfera n-dimensional e em grupos de Lie matriciais conexos e compactos
surgiu posteriormente com Crouch, Kun e Silva Leite em [19, 20]. Contudo, ao contrário
dos splines obtidos por via da abordagem variacional, o comportamento optimal das curvas geradas por aplicação da generalização do algoritmo de De Casteljau, é ainda hoje
desconhecido. Recentemente, em [4], Altafini apresentou um estudo do algoritmo de De
Casteljau no grupo especial Euclidiano SE(3, R).
Este é o momento para descrever qual é a nossa contribuição para este tema de investigação. Iniciámos o estudo do algoritmo de De Casteljau com a finalidade de o estender à
construção de splines não polinomiais em Rn . Seguindo o trabalho de Nagy e Vendel [76],
6
Introdução
apresentámos em Rodrigues, Silva Leite e Rosa [59], o estudo em espaços Euclidianos de
dimensão arbitrária da construção de uma curva spline, cujos segmentos são definidos
à custa de uma combinação convexa de arcos de circunferência e segmentos de recta.
Exige-se que esta curva spline passe por um conjunto de pontos antecipadamente prescritos, tal como acontece com a aplicação do algoritmo de De Casteljau. Esta construção
geométrica partilha algumas propriedades com o algoritmo clássico de De Casteljau que
importa salientar, nomeadamente:
i) Cada segmento da curva spline depende apenas dos dados iniciais na sua vizinhança
e por isso a sua construção é realizada de forma individual. Esta propriedade local é
do ponto de vista das aplicações uma propriedade desejável. Uma alteração pontual
de algum dado inicial não requer o cálculo completo (de novo) da curva final.
ii) Pequenas adaptações permitem que o algoritmo contemple a construção de um spline,
para o qual, além dos pontos de interpolação são também prescritas as velocidades.
iii) A implementação do algoritmo não envolve dificuldades e permite a obtenção de
uma expressão explı́cita para a curva final.
A expressão explı́cita da curva spline obtida em [59], envolve geralmente a presença de
funções trigonométricas, consequentemente, os desenvolvimentos alcançados significaram
um pequeno progresso no que diz respeito à extensão do algoritmo de De Casteljau. O
trabalho descrito apresenta ainda a análise do comportamento optimal da curva spline
em certos casos particulares.
Este último trabalho teve no entanto um efeito inesperado a outro nı́vel, pois permitiu o despertar de uma nova perspectiva sobre a construção geométrica operada pelo
algoritmo clássico de De Casteljau. A observação de que toda a iteração do algoritmo
clássico é também resultado de um processo de combinação convexa, conduziu-nos ao
conceito de função suavizante de um spline. Este conceito acabou por ser fundamental
na obtenção de dois novos algoritmos geométricos para a geração de curvas spline em
variedades Riemanianas, que descrevemos na segunda parte desta dissertação.
Iniciamos esta segunda parte com uma sı́ntese de conceitos e resultados de geometria
Riemaniana que são essenciais nos desenvolvimentos posteriores.
Em seguida, apresentamos um algoritmo geométrico com apenas três passos que permite a construção eficiente de curvas interpoladoras de uma classe de suavidade arbitrária.
Observando a estrutura do algoritmo pode considerar-se que este é uma extensão do algoritmo clássico de De Casteljau. As semelhanças são evidentes e muitas propriedades
são partilhadas. O caso em que a variedade Riemaniana é um grupo de Lie matricial
conexo e compacto, munido da métrica Riemaniana bi-invariante, é analisado com algum
detalhe. Consideramos em particular o grupo ortogonal especial.
Por último, e com o objectivo de melhorar a complexidade dos algoritmos já propostos, apresentamos um outro algoritmo geométrico que permite a construção eficiente
7
Introdução
de curvas spline de uma classe de suavidade arbitrária apenas em dois passos. Analisamos
a descrição deste novo algoritmo em grupos de Lie matriciais conexos e compactos (tal
como fizemos para o algoritmo anterior) e também na esfera n-dimensional. Embora
à primeira vista os dois algoritmos pareçam oriundos da mesma famı́lia (que também
inclui o algoritmo de De Casteljau) na verdade eles têm naturezas diferentes e divergem
em alguns aspectos importantes.
Para concluir esta introdução indicamos mais alguns aspectos da estrutura da tese.
Iniciamos cada capı́tulo da tese com um breve resumo dos principais objectivos que pretendemos atingir. Terminamos cada capı́tulo com algumas observações sobre a divulgação
dos resultados e referências bibliográficas sobre áreas especı́ficas de matemática, cujas ferramentas usamos em cada capı́tulo.
Nos comentários finais apresentamos algumas questões em aberto, descrevendo algumas das dificuldades que encontrámos no decorrer do nosso trabalho e perspectivamos o
que pensamos ser o nosso trabalho futuro.
No final desta tese, após cada referência bibliográfica, pode encontrar-se uma descrição
das páginas do texto onde cada referência foi citada.
Usámos o software matemático Mapler em todos os exemplos apresentados no texto
que de alguma forma exigiram algum esforço computacional.
8