Por que os pontos equi-espaçados se comportam mal?

24

Descrição da experiência:

Na interpolação de Lagrange, a equação exata é amostrada em pontos (ordem polinomial ) e é interpolada em 101 pontos. Aqui varia de 2 a 64. Cada vez que , e gráficos de erro são preparados. Vê-se que, quando a função é amostrado em pontos equidistantes, o erro diminui inicialmente (isto acontece até é inferior a cerca de 15 ou mais) e, em seguida, o erro aumenta com aumento adicional no . $N$ $N - 1$ $N$ $L_1$ $L_2$ $L_\infty$ $N$ $N$

Considerando que, se a amostragem inicial for feita nos pontos de Legendre-Gauss (LG) (raízes dos polinômios de Legendre) ou em pontos de Legendre-Gauss-Lobatto (LGL) (raízes dos polinômios de Lobatto), o erro cai para o nível da máquina e não aumentar quando $N$ é aumentado ainda mais.

Minhas perguntas são,

O que exatamente acontece no caso de pontos equi-espaçados?

Por que o aumento na ordem polinomial causa o erro após um certo ponto?

Isso também significa que, se eu usar pontos equi-espaçados para reconstrução WENO / ENO (usando polinômios de Lagrange), na região suave, obteria erros? (bem, essas são apenas perguntas hipotéticas (pelo que entendi), não é realmente razoável reconstruir o polinômio da ordem de 15 ou mais para o esquema WENO)

Detalhes adicionais:

Função aproximada:

$f(x) = \cos(\frac{\pi}{2}~x)$ , $x \in [-1, 1]$

$x$ dividido em $N$ equidistantes (e mais tarde LG). A função é interpolada em 101 pontos de cada vez.

Resultados:

a) Pontos equi-espaçados (interpolação para $N = 65$ ):

insira a descrição da imagem aqui

b) Pontos equi-espaçados (gráfico de erros, escala logarítmica):

insira a descrição da imagem aqui

a) pontos LG (interpolação para $N = 65$ ):
b) pontos LG (gráfico de erro, escala de log):

insira a descrição da imagem aqui

finite-difference interpolation error-estimation polynomials Subodh
fonte

26

O problema com pontos equidistantes é que o polinômio do erro de interpolação, ou seja,

f (x) - P_{n} (x) = \frac{f^{(n + 1)} (ξ)}{(n + 1)!} \prod_{i = 0}^{n} (x - x_{i}), ξ \in [x_{0}, x_{n}]

$f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i),\quad \xi\in[x_0,x_n]$

$x_i$

Se você usar pontos de Gauss-Legendre, o polinômio de erro é significativamente melhor comportado, ou seja, não explode nas bordas. Se você usar nós Chebyshev , esse polinômio equivale e o erro de interpolação é mínimo.

Pedro
fonte

6

Há uma explicação bastante detalhada no livro de John P. Boyd Chebyshev e Fourier Spectral Methods, onde o polinômio de erro de interpolação de Pedro também é bem explicado (Capítulo 4.2 Página 85).

Bort

Obrigado. Também a constante de Lebesgue para as escolhas mencionadas acima se comporta de maneira diferente. Para pontos equi-espaçados, a constante de Lebesgue aumenta exponencialmente, enquanto para LG, LGL, Chebyshev isso meio que satura com o aumento de n. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , mas ainda há dúvidas sobre a implementação numérica ...

Subodh

Desculpe, eu não sei muito sobre ENO / WENO. Mas não esperarei problemas na região tranquila para interpolações de baixa ordem, embora os nós de quadratura sejam definitivamente a melhor escolha por razões aparentes.

Bort

22

Esta é uma pergunta realmente interessante, e há muitas explicações possíveis. Se estamos tentando usar uma interpolação polinomial, observe que o polinômio satisfaz a seguinte desigualdade irritante

$P$ $N$

| P^{'} (x) | \leq \frac{N}{\sqrt{1 - x^{2}}} max_{x} | P (x) |

$|P^{\prime}(x)| \leq \frac{N}{\sqrt{1-x^2}}\max _x |P(x) |$

para cada . Isso é conhecido como desigualdade de Bernstein ; observe a singularidade dessa desigualdade. Isso pode ser limitado pela desigualdade de Markov $x \in (-1,1)$

max_{x} | P^{'} (x) | \leq N^{2} max_{x} | P (x) |

$\max _x |P^{\prime} (x) | \leq N^2 \max _x |P(x) |$

e observe que isso é nítido no sentido de que os polinômios de Chebysehv fazem disso uma equação. Portanto, em outras palavras, temos o seguinte limite combinado.

| P^{'} (x) | \leq min (\frac{N}{\sqrt{1 - x^{2}}}, N^{2}) max_{x} | P (x) |

$|P^{\prime}(x)| \leq \min \left(\frac{N}{\sqrt{1-x^2}},N^2\right)\max _x |P(x) |$

O que isso significa: os gradientes de polinômios crescem linearmente em sua ordem em qualquer lugar, exceto em pequenas vizinhanças dos limites do intervalo. Nos limites, eles crescem mais como . Não é por acaso que todos os nós de interpolação estáveis têm um agrupando perto dos limites. O agrupamento é necessário para controlar os gradientes da base, enquanto que perto do ponto médio pode ser um pouco mais relaxado. $N^2$ $1/{N^2}$

Acontece, no entanto, que este não é necessariamente um fenômeno polinomial, sugiro o seguinte artigo:

http://math.la.asu.edu/~platte/pub/prevised.pdf

Diz vagamente: se você tem o mesmo poder de aproximação da base polinomial, não pode usar pontos igualmente espaçados de maneira estável.

Reid.Atcheson
fonte

1

Não são os pontos igualmente espaçados que são o problema. É o suporte global das funções básicas, juntamente com pontos igualmente espaçados, que é o problema. Um interpolante perfeitamente bem condicionado, usando pontos igualmente espaçados, é descrito na Análise Numérica de Kress, usando funções de base spline cúbica-b de suporte compacto.

user14717
fonte

certo, mas então a sua interpolação não será suavizar globalmente (somente para o seu exemplo)

C^{2}

$C^2$

GoHokies

@GoHokies: Os splines compactamente suportados podem ser tão suaves quanto desejado por convolução iterativa. Qual é o caso de uso da interpolação ?

C^{\infty}

$C^{\infty}$

user14717

ponto justo. ("posição-velocidade-aceleração") é suficiente para a maioria das aplicações. você pode querer para alguns problemas de valor-limite, mas não consegue pensar em nenhum caso de uso comum acima disso.

C^{2}

$C^2$

C^{4}

$C^4$

GoHokies

1

O que exatamente acontece no caso de pontos equi-espaçados?

Por que o aumento na ordem polinomial causa o erro após um certo ponto?

Isso é semelhante ao fenômeno de Runge, onde, com nós equi-espaçados, o erro de interpolação chega ao infinito com o aumento do grau polinomial, ou seja, o número de pontos.

Uma das raízes desse problema pode ser encontrada na constante de Lebesgue, conforme observado pelo comentário de @ Subodh à resposta do @Pedro. Essa constante relaciona a interpolação com a melhor aproximação.

Algumas anotações

Temos uma função para interpolar sobre os nós . Na interpolação de Lagrange são definidos os polinômios de Lagrange : $f \in C([a,b])$ $x_k$

L_{k} (x) = \prod_{i = 0, i \neq j}^{n} \frac{x - x_{i}}{x_{k} - x_{i}}

$L_k(x) = \prod_{i=0, i\neq j}^{n}\frac{x-x_i}{x_k-x_i}$

com isso é definido o polinômio de interpolação sobre os pares para notação leve $p_n \in P_n$ $(x_k, f(x_k))$ $(x_k, f_k)$

p_{n} (x) = \sum_{k = 0}^{n} f_{k} L_{k} (x)

$p_n(x) = \sum_{k=0}^n f_kL_k(x)$

Agora considere uma perturbação nos dados, isso pode ser, por exemplo, para arredondamento, portanto temos . Com isso, o novo polinômio é: $\tilde{f}_k$ $\tilde{p}_n$

{\tilde{p}}_{n} (x) = \sum_{k = 0}^{n} {\tilde{f}}_{k} L_{k} (x)

$\tilde{p}_n(x) = \sum_{k=0}^n \tilde{f}_k L_k(x)$

As estimativas de erro são:

p_{n} (x) - {\tilde{p}}_{n} (x) = \sum_{k = 0}^{n} (f_{k} - {\tilde{f}}_{k}) L_{k} (x)

$p_n(x) - \tilde{p}_n(x) = \sum_{k=0}^n (f_k - \tilde{f}_k) L_k(x)$

| p_{n} (x) - {\tilde{p}}_{n} (x) | \leq \sum_{k = 0}^{n} | f_{k} - {\tilde{f}}_{k} | | L_{k} (x) | \leq (max_{k} | f_{k} - {\tilde{f}}_{k} |) \sum_{k = 0}^{n} | L_{k} (x) |

$| p_n(x) - \tilde{p}_n(x) | \leq \sum_{k=0}^n |f_k - \tilde{f}_k| |L_k(x)| \leq \left ( \max_k |f_k - \tilde{f}_k| \right) \sum_{k=0}^n |L_k(x)|$

Agora é possível definir a constante da Lebesgue como: $\Lambda_n$

Λ_{n} = max_{x \in [a, b]} \sum_{k = 0}^{n} | L_{k} (x) |

$\Lambda_n = \max_{x \in [a,b]} \sum_{k=0}^n |L_k(x)|$

Com isso, as estimativas finais são:

| | p_{n} - {\tilde{p}}_{n} | |_{\infty} \leq (max_{k} | f_{k} - {\tilde{f}}_{k} |) Λ_{n}

$|| p_n - \tilde{p}_n ||_{\infty} \leq \left ( \max_k |f_k - \tilde{f}_k| \right) \Lambda_n$

(observação marginal, nós olhamos apenas norma também porque estamos sobre um espaço de medida finita, então ) $\infty$ $L^{\infty} \subseteq \dots \subseteq L^1$

A partir do cálculo acima, obtivemos que é: $\Lambda_n$

independente da data:
depende apenas da distribuição dos nós;
um indicador de estabilidade (quanto menor, melhor).

Também é norma do operador de interpolação respeitar o norma. $|| \cdot||_\infty$

Com o seguinte teorema, temos uma estimativa do erro de interpolação com a constante de Lebesgue:

Seja e como acima, temos que é o erro do melhor polinômio de aproximação uniforme $f$ $p_n$
$| | f - p_{n} | |_{\infty} \leq (1 + Λ_{n}) d_{n} (f)$ $|| f - p_n ||_{\infty} \leq (1 + \Lambda_n) d_n(f)$ $d_{n} (f) = inf_{q_{n} \in P_{n}} | | f - q_{n} | |_{\infty}$ $d_n(f) = \inf_{q_n \in P_n} || f - q_n ||_{\infty}$

seja, se é pequeno, o erro da interpolação não está longe do erro da melhor aproximação uniforme e o teorema compara o erro de interpolação com o menor erro possível, que é o erro da melhor aproximação uniforme. $\Lambda_n$

Para isso, o comportamento da interpolação depende da distribuição dos nós. Há um limite inferior sobre que, dada a distribuição de um nó, existe uma constante tal que: para que a constante cresça, mas como ela cresce. importan. $\Lambda_n$ $c$

Λ_{n} \geq \frac{2}{π} \log (n) - c

$\Lambda_n \geq \frac{2}{\pi} \log(n) - c$

Para nós equi-espaçados omiti alguns detalhes, mas vemos que o crescimento é exponencial.

Λ_{n} \approx \frac{2^{n + 1}}{e n \log (n)}

$\Lambda_n \approx \frac{2^{n+1}}{en \log(n)}$

Para nós Chebyshev também aqui, omiti alguns detalhes, há estimativas mais precisas e complicadas. Veja [1] para mais detalhes. Observe que os nós da família Chebyshev têm crescimento logarítmico e, a partir das estimativas anteriores, está próximo do melhor que você pode obter.

Λ_{n} \leq \frac{2}{π} \log (n) + 4

$\Lambda_n \leq \frac{2}{\pi} \log(n) + 4$

Para outras distribuições de nós, consulte, por exemplo, a tabela 1 deste artigo .

Há muita referência no livro sobre interpolação. On-line, esses slides são legais como resumo.

Também este artigo aberto ([1])

Uma comparação numérica de interpolação de sete grades para polinômio no intervalo para várias comparações.

Mauro Vanzetto
fonte

1

É bom estar ciente dos interpoladores Floater-Hormann quando você precisar (ou quiser) trabalhar com pontos equidistantes . $\{x_i\}_{i=1\ldots n}$

Dado o número inteiro com , seja o interpolante polinomial de . Então o interpolante FH de uma função em tem a forma $d$ $0 \le d \le n$ $p_i$ $\{ x_i, \ldots x_{i+d} \}$ $f$ $\{x_i\}_{i=1\ldots n}$

r_{n} (x) := \frac{\sum_{i = 0}^{n - d} λ_{i} (x) p_{i} (x)}{\sum_{i = 0}^{n - d} λ_{i} (x)}

$r_n(x) := \frac{\sum_{i=0}^{n-d} \lambda_i(x) \, p_i(x)}{\sum_{i=0}^{n-d} \lambda_i(x)}$

com as "funções de mesclagem"

λ_{i} (x) = \frac{(- 1)^{i}}{(x - x_{i}) \dots (x - x_{i + d})}

$\lambda_i(x) = \frac{(-1)^i}{(x-x_i) \ldots (x - x_{i+d})}$

Algumas propriedades desses interpolantes:

eles são interpolantes racionais baricêntricos, sem pólos reais ;
obter ordens de aproximação arbitrárias para , independentemente da distribuição dos pontos; ${\cal O}(h^{d+1})$ $f \in C^{d+2}[a,b]$
são um pouco semelhantes aos splines, pois misturam interpolantes polinomiais (locais) com os atuando como funções de mesclagem; $p_0, \ldots p_{n-d}$ $\lambda$
eles reproduzem polinômios de grau no máximo (ou se for ímpar); $d$ $d+1$ $n-d$
pode ser escrito em forma barricêntrica (consulte a seção 4 do artigo de Floater e Hormann).

Advertência ao emptor : Como esperado (consulte o artigo referenciado por @ Reid.Atcheson), o aumento de diminui rapidamente o condicionamento do processo de aproximação. $d$

Há algum trabalho bastante recente feito por Klein para aliviar esse problema. Ele modificou a abordagem original de Floater-Hormann adicionando novos valores de dados correspondentes a pontos fora do intervalo de interpolação original construído a partir de uma extensão suave de fora de usando apenas os dados fornecidos . Esse conjunto de dados "global" é interpolado por uma nova função racional FH e avaliado apenas dentro de . $2 d$ $[a,b]$ $f$ $[a,b]$ $f_0, \ldots f_n$ $r_{n+2d}$ $[a,b]$

Os detalhes são detalhadamente apresentados no artigo de Klein (link abaixo), onde é mostrado que esses interpolantes racionais estendidos têm constantes de Lebesgue que crescem logaritmicamente com e (enquanto que para o esquema FH original, esse crescimento é exponencial em , consulte Bos et al. ). $n$ $d$ $d$

A biblioteca Chebfun usa interpolantes de FH ao criar chebfunsdados equidistantes, conforme explicado aqui .

Referências:

MS Floater e K. Hormann, interpolação racional baricêntrica sem pólos e altas taxas de aproximação, Numerische Mathematik 107 (2007).

G. Klein, Uma Extensão da Família Floater-Hormann de Interpolantes Racionais Baricêntricos, Matemática da Computação , 82 (2011) - preprint

L. Bos, S. De Marchi, K. Hormann e G. Klein, Sobre a constante de Lebesgue de interpolação racional baricêntrica em nós equidistantes, Numer. Matemática. 121 (2012)

GoHokies
fonte

Por que os pontos equi-espaçados se comportam mal?

Respostas: