0863

Título
VELOCIDADE DE CONVERGÊNCIA DE SEQUÊNCIAS

Aluno: Luciano Luzzi Junior - PET - Curso de Matemática Industrial (T) - Orientador: Lucas Garcia Pedroso - Departamento de Matemática - Área de conhecimento: 10104003 - Palavras-chave: otimização; convergência de sequências; velocidade de convergência.

Em otimização, estamos sempre interessados em algoritmos eficientes, no sentido de que resolvam os problemas desejados performando o mínimo possível de iterações. Em geral essa eficiência é medida através de experimentos práticos, ou seja, ao resolvermos uma quantidade grande de problemas utilizando um determinado algoritmo temos uma ideia sobre o quanto este é eficiente. No entanto, além desse estudo prático de eficiência, uma análise teórica extremamente importante é o da velocidade de convergência das sequências geradas por um algoritmo. A velocidade com que uma sequência converge a seu limite é a velocidade com que o erro de cada termo da sequência, ou seja, sua distância até o limite da sequência, tende a zero. Na primeira parte de nosso trabalho, estudaremos alguns conteúdos de Análise Real, iniciando com a teoria acerca de sequências de números reais e depois estendendo-a para sequências de ênuplas de números reais. Em particular, as próprias definições de sequências limitadas, sequências convergentes, limites, limites superior e inferior, dentre outras, serão abordadas. No estudo de velocidades de convergência propriamente dito, daremos maior atenção às velocidades do tipo q e do tipo r. Uma sequência converge q-linearmente quando a partir de um certo momento a razão entre o erro no k-ésimo termo da sequência e o erro no (k-1)-ésimo é sempre menor ou igual a uma constante menor do que um. Uma sequência converge q-superlinearmente a seu limite se a razão entre os erros no k-ésimo termo e no (k-1)-ésimo tende a zero quando k tende a infinito. Por fim, a convergência q-quadrática ocorre quando uma sequência convergente é tal que existe uma constante M tal que a razão entre o erro cometido pelo k-ésimo termo da sequência e o quadrado do erro cometido pelo (k-1)-ésimo é menor ou igual a M para todo k. Mostraremos a hierarquia entre esses tipos de convergência, a saber, que a convergência q-quadrática implica na q-superlinear que por sua vez implica na q-linear. Já sequências que convergem r-linearmente são tais que são limitadas superiormente por sequências que convergem q-linearmente, analogamente para as convergências r-superlineares e r-quadráticas. Por fim, ilustraremos cada tipo de velocidade de convergência com diversos exemplos.