Por que Akra-Bazzi precisa que a função de pedágio g seja limitada?

8

Seguindo a resposta de vonbrand, quero escrever um pequeno documento sobre teoremas mestres mais fortes para nossos alunos, um dos quais é o teorema de Akra-Bazzi. Copiei o teorema do trabalho deles [1] e encontrei - além de uma pequena confusão notacional² - o seguinte problema.

Os autores exigem (grifo meu):

g(x) é definido para os valores reais e é uma função limitada , positiva e não decrescente xx0

Aqui, é a função de pedágio, ou seja, a recorrência tem a formag

T(n)=g(n)+i=1kaiT(nbi1) .

Agora, no final de seu artigo (p209), eles dão vários exemplos para aplicar seu resultado e usam funções em que claramente não são delimitadas.Ω(n)

Ao examinar a prova, eles parecem exigir principalmente que integrais do formulário

abg(x)xp+1dx

tem valores finitos. Portanto, exigir que seja limitado em cada intervalo compacto pode ser suficiente; Não trabalhei com a prova em detalhes. É possível que eles digam isso?g

Minha pergunta é: como o teorema de Akra-Bazzi deve ser declarado para que seja consistente com provas e exemplos?


  1. Sobre a solução de equações de recorrência linear por M. Akra e L. Bazzi (1998)
  2. Eles exigem . Isso é alguma notação que eu não conheço ou um erro de digitação? Presumo que o significado pretendido seja .aiR+(0,)R
Rafael
fonte

Respostas:

5

Dê uma olhada nas anotações de Tom Leighton , referenciadas no artigo da Wikipedia. Suas anotações aparentemente têm menos erros de digitação que o artigo original. A condição que ele exige de é ter crescimento polinomial , o que significa que, se você dimensionar o argumento por uma constante, a quantidade que a função dimensiona também será limitada por uma constante.g

Yuval Filmus
fonte
2

A melhor versão do teorema de Akra-Bazzi que eu vi é a de Lehman, Leighton, Meyer "Matemática para Ciência da Computação" , a discussão começa na página 1019. Uma versão impressa (mais antiga) está disponível. Nenhuma prova, no entanto. Seria necessário ler a nota de Leighton para verificar se as notas da aula / versão do livro estão corretas (possui condições um pouco diferentes, que são muito mais fáceis de verificar).

vonbrand
fonte
Isso parece ser um comentário, não uma resposta? Estou esquecendo de algo?
Raphael