Qual é a melhor maneira de encontrar descontinuidades de uma função de caixa preta?

20

Foi sugerido que este poderia ser um lugar melhor para esta pergunta do que o Mathematics Stack Exchange, onde eu a fiz antes .

Suponha que se tenha uma função de caixa preta que possa ser avaliada em qualquer lugar (barato) em um intervalo especificado e não tenha ruído (exceto a granularidade do ponto flutuante, por exemplo). Qual seria a melhor maneira de encontrar as descontinuidades dessa função? Não sei quantas descontinuidades podem existir e talvez não.[a,b]

Eu posso pensar em alguns métodos simples (amostragem uniforme, refinar onde existem grandes diferenças entre amostras, ...), mas talvez haja uma maneira melhor?

A função é "razoável", na medida em que se poderia supor que ele tenha, no máximo, muitas descontinuidades, o mesmo para derivadas mais altas, não me importo se pequenas descontinuidades patológicas forem perdidas ... (o aplicativo é plotagem automatizada de funções 1d) .

-

Obrigado a todos que responderam, particularmente Pedro; o método descrito em Pachón, Platte e Trefethen parece ser a melhor abordagem para mim, então agora vou implementá-lo

n00b
fonte
Eu tenho que saber se qualquer um dos métodos propostos podem lidar com
1x1x
JM
@JM: Vou adicionar um gráfico desta função quando terminar a implementação.
N00b
@ n00b: Você pode achar esse conceito útil. : mathoverflow.net/q/165038/14414
Rajesh Dachiraju

Respostas:

18

Se você estiver usando o Matlab, poderá estar interessado no projeto Chebfun . Chebfun pega uma função, faz uma amostra e tenta representá-la como um interpolante polinomial. Se sua função tiver descontinuidades, o Chebfun deve ser capaz de detectá-las com o splitting oncomando Você pode encontrar alguns exemplos aqui .

Se você está interessado nos algoritmos subjacentes, uma boa referência é o artigo de Pachón, Platte e Trefethen " Piecewise Smooth Chebfuns ".

Pedro
fonte
Obrigado Pedro, eu estou familiarizado com o Chebfun, que é ótimo, mas enorme (e vem com um alto custo implícito via licença do Matlab). Então, eu estou realmente procurando por um pequeno algoritmo rígido para esse problema que eu mesmo implementaria.
N00b
@ n00b: bom argumento. Adicionei uma referência ao artigo que descreve os algoritmos subjacentes, por exemplo, para detecção de bordas.
Pedro
Ah, excelente! Eu não tinha visto este artigo e, contrariamente às minhas expectativas, parece que o localizador de descontinuidade Chebfun não usa Chebfuns - então isso parece ser eminentemente útil. Vou lê-lo com cuidado e inspecionar o código correspondente ....
n00b
11

Suspeito que o algoritmo chebfun deva parecer mais prático, mas é necessário mencionar mais uma maneira de detectar descontinuidades, a saber, a transformada discreta de wavelet. Você pode ter uma idéia de como isso funciona , consultando esta página de documentação do Mathematica , consulte a seção> Aplicativos> Detectar descontinuidades e bordas.

f

faleichik
fonte
8

Os métodos Ponderados Não-Oscilatórios Ponderados (WENO) usam "indicadores de suavidade" para detectar descontinuidades nos métodos finitos de volume e diferença. A partir da descrição de Chebfun que Pedro deu, parece que a idéia geral é a mesma: construa um conjunto de polinômios interpoladores e use-os para calcular alguma medida de suavidade.

Veja GS Jiang e CW Shu, Implementação eficiente de esquemas de ENO ponderados, J.Comput.Phys., Vol. 126, pp. 202--228, 1996.

Matthew Emmett
fonte
5

Junto com o @Pedro, eu examinaria os algoritmos de detecção de borda. Uma descontinuidade é um infinito na derivada; portanto, considere olhar para uma malha cada vez mais fina e segmentar regiões de interesse.

A aproximação da diferença finita à derivada de uma função contínua deve reduzir à medida que a malha é refinada. A comparação do resultado da diferença finita para a derivada entre malhas pode então revelar divergências no gradiente que sinalizam descontinuidades.

f(x)=sign(x)|x|x=0hx0

Phil H
fonte
1
Uma sutileza do problema é que, embora uma descontinuidade possa ser vista como tendo um infinito na derivada, o oposto não é verdadeiro - o sinal da função (x) * sqrt (| x |) é perfeitamente contínuo em x = 0, mas a derivada é infinita lá
n00b
Também discordo do comentário de que "qualquer função contínua deve ser suave em uma escala suficientemente pequena". A suavidade tem a ver com derivados contínuos; a continuidade da função original é uma condição necessária, mas não suficiente.
Geoff Oxberry
1
@ GeoffOxberry: removeu essa declaração. É um resultado razoável no DF, mas não analiticamente.
Phil H