11

Quando se deseja calcular derivadas numéricas, o método apresentado por Bengt Fornberg aqui (e relatado aqui ) é muito conveniente (preciso e simples de implementar). Como o artigo original data de 1988, eu gostaria de saber se hoje existe uma alternativa melhor (como (ou quase) simples e mais precisa)?

finite-difference precision Vincent
fonte

1

Difícil dizer sem saber o que você quer diferenciar. Você já considerou a diferenciação automática ?

precisa saber é o seguinte

@BiswajitBanerjee: Para coeficientes de diferença finita, a diferenciação automática não se aplica.

amigos estão

@ GeoffOxberry: Eu estava me referindo ao problema físico real, ou seja, a parte da ciência da "ciência computacional".

precisa saber é o seguinte

@Incent: você está tentando diferenciar uma função ou uma tabela? Se os dados da tabela, os dados da tabela são barulhentos? Você está tentando discretizar um PDE?

user14717

9

Visão geral

Boa pergunta. Existe um artigo intitulado "Melhorando a precisão do método de diferenciação de matrizes para pontos de colocação arbitrária" de R. Baltensperger. Não é grande coisa na minha opinião, mas tem um ponto (que já era conhecido antes do surgimento em 2000): enfatiza a importância de uma representação precisa do fato de que a derivada da função constante deve seja zero (isso vale exatamente no sentido matemático, mas não necessariamente na representação numérica). $f(x)=1$

É simples perceber que isso requer que a soma das linhas das n-ésimas matrizes derivadas seja zero. É comum impor essa restrição ajustando a entrada diagonal, ou seja, definindoÉ claro que esse recurso não se aplica exatamente ao trabalhar em um computador devido a erros de arredondamento nos cálculos de ponto flutuante. O mais surpreendente é que esses erros são ainda mais graves ao usar as fórmulas analíticas para a matriz derivada (que estão disponíveis para muitos pontos de colocação clássicos, por exemplo, Gauss-Lobatto). $D^{(n)}$

\begin{matrix} (1) & D_{j j}^{(n)} := - \sum_{\begin{matrix} i = 1 \\ i \neq j \end{matrix}}^{N} D_{i j} . \end{matrix}

$\tag 1 D^{(n)}_{jj} := -\sum_{\substack{i=1\\i \neq j }}^N D_{ij}\,.$

Agora, o artigo (e suas referências) afirma que o erro da derivada está na ordem do desvio da soma da linha de zero. O objetivo é, portanto, torná-los numericamente o menor possível.

Testes numéricos

O ponto positivo é que o procedimento de Fornberg parece ser bastante bom nesse sentido. Na figura abaixo, comparei o comportamento da primeira matriz exata, ou seja, analítica, e a derivada do algoritmo de Fornberg, para número variável de pontos de colocação de Chebyshev-Lobatto.

Novamente, acreditando na afirmação no artigo citado, isso implica que o algoritmo de Fornberg produzirá resultados mais precisos para a derivada.

Para provar isso, usarei a mesma função do artigo, e avalie o erroIsso é feito para (i) a matriz derivada obtida analiticamente, (ii) matriz derivada de Fornberg e (iii) uma versão ajustada da matriz Fornberg, onde a Eq acima. (1) é aplicado de maneira bastante direta viaAqui está o que eu recebo (novamente para o exemplo de Gauss-Lobatto abscissas):

\begin{matrix} (2) & f (x) = \frac{1}{1 + x^{2}} . \end{matrix}

$\tag 2 f(x) = \frac{1}{1+x^2}\,.$

\begin{matrix} (3) & E_{n} = max_{i \in {0, \dots, n}} | f^{'} (x_{i}) - \sum_{j = 1}^{n} D_{i j} f (x_{j}) | . \end{matrix}

$\tag 3 E_n = \max_{i\in \{0,\ldots,n\}} \bigg| f^\prime(x_i) - \sum_{j=1}^n D_{ij} f(x_j) \bigg|\,.$

\begin{matrix} (4) & {\tilde{D}}_{j j} = D_{j j} - (\sum_{i = 1}^{n} D_{j i}), for all j . \end{matrix}

$\tag 4 \tilde D_{jj} = D_{jj} - \left(\sum_{i=1}^n D_{ji} \right), \qquad \text{for all}\ j\,.$

Conclusão

Em conclusão, o método de Fornberg parece ser bastante preciso, no caso mesmo em cerca de 3 ordens de grandeza mais acuradas do que os resultados das fórmulas analíticas. Isso deve ser preciso o suficiente para a maioria dos aplicativos. Além disso, isso é notável porque Fornberg parece não incluir explicitamente esse fato em seu método (pelo menos não há menção nos dois artigos de Fornberg). $N=512$

Outra ordem de magnitude pode ser obtida para este exemplo através de uma inclusão direta da Eq. (4). Como essa é uma abordagem bastante simples e aplicada apenas uma vez para cada derivada, não vejo razão para não usá-la.

O método do artigo de Baltensperger - que usa uma abordagem mais sofisticada para avaliar a soma na Eq. (1) para reduzir erros de arredondamento - produz aproximadamente a mesma ordem de magnitude para o erro. Portanto, pelo menos neste exemplo, é aproximadamente equivalente ao método "Ajustberg Fornberg" acima.

davidhigh
fonte

4

Supondo que você esteja tentando diferenciar uma implementação numérica de uma função contínua, há um grande número de métodos:

1) diferenciação automática. O método mais preciso e geral. Difícil de codificar, exigindo sobrecarga do operador e pesquisa dependente de argumento. Coloca um fardo para o usuário entender esses conceitos. Também luta com singularidades removíveis, como diferenciar sinc em . $x= 0$

2) Uma transformação Chebyshev. Projete sua função em um intervalo de polinômios de Chebyshev e diferencie a recorrência de três termos. Super rápido, muito preciso. Mas requer que você tenha um domínio de interesse compactamente suportado; fora do domínio selecionado , a recorrência de três termos é instável. $[a,b]$

3) Diferenciação finita. Subestimado em 1D; consulte as dicas e truques de Nick Higham em computação numérica . A idéia é que, se você equilibrar o erro de truncamento e o erro de arredondamento, não precisará selecionar um tamanho de etapa; pode ser escolhido automaticamente. No Boost, essa idéia é usada para recuperar (por padrão) 6/7 dos dígitos corretos para o tipo. (Higham mostra apenas a idéia para o caso mais simples de 1/2 dos dígitos corretos, mas a idéia é facilmente estendida.) Os coeficientes são da tabela equidistante de Fornberg, mas o tamanho da etapa é escolhido sob a suposição de que a função pode ser avaliada para 1ULP. precisão. A desvantagem é que são necessárias duas avaliações de função para recuperar metade dos dígitos do tipo, 4 para recuperar 3/4 dos dígitos, etc. Em 1D, não é um mau negócio. Em dimensões superiores, é catastrófico.

4) A derivada da etapa complexa. Use . Leve para ser o arredondamento da unidade e isso recuperará quase todos os bits corretos. No entanto, é meio trapaceiro, porque geralmente é mais difícil implementar uma função no plano complexo do que codificar manualmente sua derivada real. Ainda é uma idéia legal e útil em determinadas circunstâncias. $f'(x) \approx \Im(f(x+ih))$ $h$

user14717
fonte

1

Eu não estou ciente de qualquer pessoa tendo melhorado o algoritmo de Fornberg (ver também a um pouco mais recente papel ). Como aparte, parece-me que olhar para o algoritmo dele como uma maneira de calcular derivadas numéricas não é correto. Tudo o que ele fez é derivar um algoritmo eficiente para calcular pesos para métodos de diferenças finitas. A vantagem de seu método é que ele fornece os pesos de todas as derivadas até a derivada desejada de uma só vez.

Brian Zatapatique
fonte

Eu discordaria da afirmação "olhar para o algoritmo dele como uma maneira de calcular derivadas numéricas não está certo". Depois de avaliar os pesos para o ponto , é possível calcular diretamente a derivada numérica de qualquer função via .

w_{i}

$w_i$

z

$z$

f (x)

$f(x)$

f^{'} (z) = \sum_{i} w_{i} f (x_{i})

$f^\prime(z) = \sum_i w_i f(x_i)$

Davidhigh

@davidhigh: Se você lê os artigos de Fornberg, eles falam sobre o cálculo de pesos para aproximações de diferenças finitas, não sobre o cálculo das próprias aproximações. Obviamente, você pode usar o algoritmo para calcular as derivadas também, mas faz mais sentido calcular os pesos, armazená-los e usá-los repetidamente para calcular as derivadas aproximadas. Caso contrário, você estará computando os pesos repetidamente quando não houver necessidade.

Brian Zatapatique 31/12/19

1

Um esquema mais simples

Além da minha outra resposta, que é mais sobre uma extensão do método Fornberg, abordarei aqui a questão de alternativas mais simples.

Para isso, esboço um esquema alternativo que produz os coeficientes derivados da interpolação lagrangiana mais diretamente. Sua implementação requer apenas algumas linhas de código, funciona para grades arbitrárias e, de acordo com meus primeiros experimentos, é tão precisa quanto a de Fornberg.

A base da implementação é a derivada da etapa imaginária que é uma variável na ordem da precisão da máquina. Sabe-se que a derivada da etapa imaginária produz valores estáveis de derivação e não sofre a instabilidade numérica de uma implementação de Diferenças finitas com .

f^{'} (x) = \frac{1}{h} Im (f (x + i h)),

$f'(x) \ = \ \frac{1}{h}\,\text{Im}\big(f(x+ih)\big)\,,$

h

$h$

h \to 0

$h\rightarrow 0$

O segundo ingrediente é o polinômio de interpolação Lagrange na grade avaliado com uma das formas baricêntricas, por exemplo, onde A fim de utilizar o derivado de complexo-passo, tem de se garantir que estas fórmulas também funcionam para complexo argumentos . Além disso, para uma dada função f (x) e vetor de coeficientes , denotamos o polinômio de interpolação através de por $L_i(x)$ $\{x_1,\ldots, x_N\}$

L_{i} (z) = {\begin{cases} 1 & if z = x_{i} \\ \frac{\frac{μ_{i}}{z - x_{k}}}{\sum_{k} \frac{μ_{k}}{z - x_{k}}} & otherwise . \end{cases}

$L_i(z) \ = \ \begin{cases}1 & \text{if }z = x_i\\\ \frac{\frac {\mu_i}{z-x_k}}{ \sum_k\frac {\mu_k}{z-x_k} } & \text{otherwise}\,. \end{cases}$

μ_{i} = \frac{1}{\prod_{k \neq i} (x_{i} - x_{k})}

$\mu_i = \frac{1}{\prod_{k\neq i} (x_i - x_k)}$

z

$z$

f_{i} = f (x_{i})

$f_i = f(x_i)$

(x_{1}, f_{i})

$(x_1,f_i)$

P (x; f) = \sum_{i = 1}^{N} f_{i} L_{i} (x) .

$P(x;f) = \sum_{i=1}^N f_i L_i(x)\,.$

Algoritmo

O algoritmo é esboçado a seguir. Ele tem os mesmos parâmetros de entrada e saída que o de Fornberg, mas é muito mais fácil.

Entrada:

$x$ : uma grade com N pontos de grade distintos
$ord$ : ordem derivada
z: um ponto no qual a derivada deve ser avaliada
Possivelmente: uma função ou seus valores funciton aos pontos de grade (somente necessários para a variante de saída 2.) $f(x)$ $f_i$

Inicialização

Inicialize os polinômios de Lagrange por interpolação barentêntrica. $L$
Inicialize uma matriz de -matrices , para $N\times N$ $D^{(o)}$ $o=0, \ldots, ord$
Defina , ou seja, a matriz unitária da dimensão $D^{(0)} := I_N$ $N\times N$
Defina $o := 0$

Algoritmo

Enquanto : $o < ord$

Calcule pelo derivado da etapa complexa para tudo que e . Aqui, denota a -ésima linha de . $D^{(o+1)}_{ik} = CSD \bigg( P\big(x_k; D^{(o)}_{i}\big) \bigg)$ $CSD$ $i$ $k$
$D^{(o)}_{i}$ $i$ $D^{(o)}$
Defina o = o + 1;

Decida o que enviar :

O vetor dos coeficientes de Diferença Finita no ponto , onde . É isso que Fornberg faz. $d^{(ord)}$ $z$ $d_i = P(z;D^{(ord)}_i)$
A função de interpolação à derivada da ordem . Para isso, é necessário inserir uma função resp. a função valoriza em para o algoritmo. $p^{(ord)}(x) = \sum_{i=1}^N f(x_i) P(x;D^{(ord)}_i)$ $f^{(ord)}(x)$ $ord$ $f_i$ $x_i$
Uma meta-função que retorna a função de interpolação da variante 2., mas para uma função arbitrária que deve ser interpolada nos pontos de grade. $\text{diff}(\text{int } ord, \text{function } g)$ $g$

Pessoalmente, eu gosto mais da variante 3.

Análise do algoritmo

Como Fornberg, esse algoritmo é . Vou postar mais resultados empíricos em relação à precisão, estabilidade etc., se encontrar tempo. $\mathcal O(ord \cdot N^2)$

davidhigh
fonte

0

Para aumentar a precisão da diferenciação numérica, faça o seguinte:

1) Escolha seu método "padrão" de alta precisão favorito com base em algum tamanho de passo h .

2) Calcule o valor da derivada com o método escolhido em 1) várias vezes com tamanhos de passo diferentes, mas razoáveis h . Cada vez que você pode escolher h como um número aleatório no intervalo (0,5 * H / 10, 1,5 * H / 10), em que H é um tamanho de etapa apropriado para o método usado.

3) Média dos resultados.

Seu resultado pode ganhar de 2 a 3 ordens de magnitude no erro absoluto wrt. o resultado não calculado pela média.

https://arxiv.org/abs/1706.10219

F. Jatpil
fonte

3

Bem-vindo ao SciComp.SE! Essa resposta seria ainda melhor se você resumisse o método brevemente.

Christian Clason

2

Além disso, seu nome de usuário sugere que você foi o autor desse documento. Leia nossas diretrizes sobre autopromoção e edite sua postagem de acordo.

27417 Wrzlprmft

Sinceramente, acho que a votação negativa é injusta se minha resposta realmente apontar para uma resposta válida.

31917 F.F. Jatpil

1

Eu também ... por isso tome minha +1 ... :-)

davidhigh

Derivados numéricos e coeficientes de diferenças finitas: alguma atualização do método de Fornberg?

Respostas: