Preciso encontrar todas as raízes de uma função escalar em um determinado intervalo. A função pode ter descontinuidades. O algoritmo pode ter uma precisão de ε (por exemplo, está ok se o algoritmo não encontrar duas raízes distintas mais próximas que ε).
Esse algoritmo existe? Você poderia me apontar documentos sobre isso?
Na verdade, tenho uma função para encontrar um zero em um determinado intervalo usando o algoritmo de Brent e uma função para encontrar um mínimo em um determinado intervalo. Usando essas duas funções, criei meu próprio algoritmo, mas fiquei pensando se existe um algoritmo melhor. Meu algoritmo é assim:
Começo com um intervalo [a,b]e uma função f. Se sign(f(a+ε)) ≠ sign(f(b-ε)), eu sei que há pelo menos um zero entre ae b, e acho z = zero(]a,b[). Testo se zrealmente é um zero (pode ser uma descontinuidade), procurando o valor de z-εe z+ε. Se for, adiciono-o à lista de zeros encontrados. Se f(a+ε)e f(b-ε)ambos são positivos, eu procuro m = min(]a, b[). Se f(m)ainda é positivo, procuro m = max(]a,b[)porque pode haver uma descontinuidade entre ae b. Eu faço o oposto se f(a+ε)e f(b-ε)foram negativos.
Agora, a partir do ponto em que encontrei ( zou m), construo uma pilha contendo os zeros, descontinuidades e pontos de inflexão da minha função. Após a primeira iteração, a pilha agora se parece [a, z, b]. Começo novamente o algoritmo a partir de intervalos ]a,z[e ]z,b[. Quando, entre dois pontos ae b, os extremos têm o mesmo sinal que os dois intervalos, e não há descontinuidades nos dois extremos, removo o intervalo da pilha. O algoritmo termina quando não há mais intervalos.
fonte
Respostas:
Se você estiver usando o Matlab, poderá experimentar o sistema Chebfun (aviso: eu costumava ser um desenvolvedor ativo deste projeto). Ele pode encontrar todas as raízes de uma função unidimensional em um intervalo aberto ou fechado para precisão da máquina.
A idéia principal por trás do localizador de raiz Chebfun é usar uma combinação de bissecção recursiva e a Matriz de Colega, um análogo da Matriz de Acompanhamento , nos coeficientes de um interpolante da função de destino.
Eu tenho uma versão simplificada do código aqui . A função
chebrootsassume uma função anônima como primeira entrada, o intervalo finito como segundo e terceiro argumento e um grauNcomo quarto e último argumento. Para resultados razoáveis, você pode definirNcomo100.fonte
Em geral, essa é uma busca sem esperança - sem algumas informações sobre a continuidade e / ou diferenciabilidade da função, tudo pode acontecer. Considere, por exemplo, a função MATLAB definida no intervalo de 0 a 1:
função y = f (x)
y = 1,0;
se (x == 0,01)
y = 0,0;
fim
se (x == 0,013)
y = 0,0;
fim
if (x == 0,753124)
y = 0,0;
fim
Tratando essa função como uma caixa de bloco, não há como ver que há zeros nesses três pontos e nenhum outro ponto no intervalo de 0 a 1 sem verificar cada número de ponto flutuante entre 0 e 1.
fonte