Interpolação (matemática)

Em matemática numérica , o termo interpolação (do latim inter = in between e polire = smooth, grind) descreve uma classe de problemas e procedimentos. Em dados discretos dados (por exemplo, valores de medição ) para uma função contínua (o chamado INTERPOL Ante ou interpolante ) são encontrados, que mapeia esses dados. Diz-se então que a função interpola os dados.

introdução

Pontos a serem interpolados

Às vezes, apenas pontos individuais de uma função são conhecidos, mas nenhuma descrição analítica da função que poderia ser usada para avaliá-la em qualquer ponto. Um exemplo são os pontos como resultado de uma medição física . Se os pontos pudessem ser conectados por uma curva (possivelmente suave), seria possível estimar a função desconhecida nos pontos intermediários. Em outros casos, uma função de difícil manuseio deve ser representada aproximadamente por uma mais simples. Uma função de interpolação pode atender a esse requisito por simplicidade. Essa tarefa é conhecida como problema de interpolação . Existem várias soluções para o problema; o usuário deve primeiro selecionar as funções de abordagem adequadas. Dependendo da função de abordagem, obtemos um interpolante diferente.

A interpolação é um tipo de aproximação : a função em consideração é reproduzida exatamente pela função de interpolação nos pontos de interpolação e pelo menos aproximadamente nos pontos restantes. A qualidade da aproximação depende da abordagem. Para apreciá-lo, são necessárias informações adicionais sobre a função . Eles geralmente surgem naturalmente, mesmo que você não saiba : Limitação, continuidade ou diferenciabilidade podem frequentemente ser assumidas. ${\ displaystyle f}$${\ displaystyle f}$

Outros métodos de aproximação, como o cálculo de ajuste , não requerem que os dados de medição sejam reproduzidos exatamente. É assim que esses métodos diferem da interpolação. O problema relacionado de extrapolação estima valores que estão além da definição dos dados.

Problemas de interpolação

O problema geral de interpolação

Dados pares de números reais ou complexos . De forma análoga ao cálculo com funções, esses são referidos como pontos de apoio , aqueles como valores de apoio e os pares como pontos de apoio . Agora escolhe-se uma função de abordagem que depende de e de outros parâmetros . O problema de interpolação é a tarefa a ser escolhida de tal forma que . ${\ displaystyle n + 1}$${\ displaystyle (x_ {i}, \, f_ {i})}$${\ displaystyle x_ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle (x_ {i}, f_ {i})}$${\ displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n})}$${\ displaystyle x}$${\ displaystyle n + 1}$${\ displaystyle a_ {j}}$${\ displaystyle a_ {j}}$${\ displaystyle \ Phi (x_ {i}, \, a_ {0}, \ ldots, a_ {n}) = f_ {i}}$

O problema de interpolação linear

Fala-se de um problema de interpolação linear, mesmo que apenas linearmente a partir do dependente, d. H. ${\ displaystyle \ Phi}$${\ displaystyle a_ {j}}$

${\ displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} \ Phi _ {1} (x) + a_ {2} \ Phi _ {2} (x) + \ cdots + a_ {n} \ Phi _ {n} (x)}$.

A interpolação polinomial em particular é um problema de interpolação linear. O seguinte se aplica à interpolação polinomial

${\ displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n}}$.

Casos especiais para , e são chamados linear , quadrática e interpolação cúbica . Em duas dimensões, fala-se de acordo com bilinear , biquadrático e bicúbico . ${\ displaystyle n = 1}$${\ displaystyle n = 2}$${\ displaystyle n = 3}$

Além disso, a interpolação trigonométrica é uma interpolação linear:

${\ displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} e ^ {xi} + a_ {2} e ^ {2xi} + \ cdots + a_ {n} e ^ {nxi}, \ quad (i ^ {2} = - 1)}$

Problemas de interpolação não linear

Um dos problemas de interpolação não linear mais importantes é

• o racional :${\ displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}, \, b_ {0}, \ ldots, b_ {m}) = {\ frac {a_ {0} + a_ { 1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n}} {b_ {0} + b_ {1} x + b_ {2} x ^ {2} + b_ {3} x ^ {3} + \ cdots + b_ {m} x ^ {m}}}}$

Método de interpolação

Interpolação linear

Interpolação linear realizada peça por peça

A interpolação linear estabelecida por Isaac Newton é a mais simples e provavelmente a mais utilizada na prática. Aqui, dois pontos de dados fornecidos ( ) e ( ) são conectados por uma linha. O seguinte se aplica: ${\ displaystyle x_ {0}, f_ {0}}$${\ displaystyle x_ {1}, f_ {1}}$

${\ displaystyle f (x) = f_ {0} + {\ frac {f_ {1} -f_ {0}} {x_ {1} -x_ {0}}} \, (x-x_ {0}) = f_ {0} {\ frac {x_ {1} -x} {x_ {1} -x_ {0}}} + f_ {1} {\ frac {x-x_ {0}} {x_ {1} -x_ {0}}} \,.}$

Isso corresponde a uma combinação convexa dos pontos finais e . ${\ displaystyle (x_ {0}, \, f_ {0})}$${\ displaystyle (x_ {1}, \, f_ {1})}$

Para uma explicação detalhada, consulte interpolação linear geral .

Polinômios de alto grau

Polinômio de interpolação de 7º grau

Para pontos de dados que são diferentes em pares, há exatamente um polinômio de interpolação -ésimo grau, que corresponde aos valores de suporte especificados nos pontos de interpolação especificados. A determinação dos coeficientes requer a solução de um sistema linear de equações . A existência de tal polinômio de interpolação pode ser vista, e. B. com a ajuda da fórmula de Lagrange${\ displaystyle n + 1}$ ${\ displaystyle n}$

${\ displaystyle p (x) = \ sum _ {i = 0} ^ {n} \, f_ {i} \ prod _ {k = 0, k \ neq i} ^ {n} {\ frac {x-x_ {k}} {x_ {i} -x_ {k}}}}$.

A singularidade segue do fato conhecido de que um polinômio -ésimo grau tem no máximo zeros. ${\ displaystyle n}$${\ displaystyle n}$

Para mais procedimentos para interpolação polinomial, veja aqui.

Interpolação por partes

Interpolação de spline cúbica

Como os polinômios se tornam cada vez mais instáveis ​​com o aumento do grau, i. H. vibrar fortemente entre os pontos de interpolação, polinômios com um grau maior que 5 raramente são usados ​​na prática. Em vez disso, interpola um grande conjunto de dados peça por peça . No caso da interpolação linear, seria um polígono , com polinômios de grau 2 ou 3 geralmente se fala em interpolação spline . Com os interpolantes definidos em seções, a questão da continuidade e diferenciabilidade nos pontos de interpolação é de grande importância.

Interpolação de eremita

Se, além dos pontos de interpolação , as derivadas - devem ser interpoladas, fala-se de um problema de interpolação de Hermite . A solução para este problema também pode ser especificada de forma fechada, análoga ao método de Lagrange. ${\ displaystyle x_ {i}}$${\ displaystyle k}$ ${\ displaystyle f ^ {(k)} (x_ {i}) = f_ {i} ^ {(k)}}$

Interpolação trigonométrica

Se um polinômio trigonométrico é selecionado como a função de abordagem, uma interpolação trigonométrica é obtida . A fórmula de interpolação

${\ displaystyle g (x) = {\ frac {1} {2}} a_ {0} + \ sum _ {k = 1} ^ {N-1} (a_ {k} \ cos kx + b_ {k} \ sin kx) + {\ frac {1} {2}} a_ {N} \ cos Nx \ ,, \ quad N = n / 2}$

corresponde a uma expansão de Fourier do interpolante desconhecido. Os coeficientes de Fourier e calculam-se uns aos outros ${\ displaystyle a_ {k}}$${\ displaystyle b_ {k}}$

${\ displaystyle a_ {k} \ approx {\ frac {2} {n}} \ sum _ {i = 1} ^ {n} f (x_ {i}) \ cos kx_ {i}}$e .${\ displaystyle b_ {k} \ approx {\ frac {2} {n}} \ sum _ {i = 1} ^ {n} f (x_ {i}) \ sin kx_ {i}}$

Supõe-se que os pontos de interpolação são distribuídos equidistantemente no intervalo e são periódicos fora desse intervalo. Os coeficientes podem ser calculados de forma eficiente usando a transformada rápida de Fourier . ${\ displaystyle x_ {i}}$${\ displaystyle [0; \, 2 \ pi]}$

Interpolação logarítmica

Se você suspeita ou sabe que os dados são baseados em uma função logarítmica , este método é recomendado.

Na interpolação logarítmica dois pontos de dados conhecidos , e por uma curva logarítmica conectada. O seguinte se aplica: ${\ displaystyle (x_ {0}, f_ {0})}$${\ displaystyle (x_ {1}, f_ {1})}$

${\ displaystyle {\ frac {\ ln f- \ ln f_ {0}} {\ ln f_ {1} - \ ln f_ {0}}} = {\ frac {x-x_ {0}} {x_ {1 } -x_ {0}}}}$

Ou dito de outra forma:

${\ displaystyle f (x) = f_ {0} \ cdot \ exp \ left ({\ frac {(x-x_ {0}) (\ ln f_ {1} - \ ln f_ {0})} {x_ { 1} -x_ {0}}} \ right)}$

Exemplo: teste χ²

Regressão Gaussiana (krigagem)

Interpolação do processo gaussiano (azul) e intervalo de confiança estimado (cinza) de uma lacuna entre duas curvas (preto) com propriedades muito misturadas.

Um método de interpolação muito versátil e universal é a regressão do processo gaussiano ou o método de Krigagem . Isso significa que tanto interpolações suaves como periódicas ou alisamentos podem ser executados em qualquer dimensão. Com a ajuda da chamada função de covariância, as propriedades especiais dos dados podem ser descritas a fim de realizar a interpolação ótima para o problema.

Propriedades do método de interpolação:

• Adequado para pontos de apoio irregulares
• Interpolação em qualquer dimensão (por exemplo, interpolação de área)
• Interpolação ideal de curvas suaves, periódicas ou ruidosas
• Previsão do intervalo de confiança da interpolação

Interpolação linear geral

Seja uma função real ou complexa continuamente diferenciável com um conjunto de zeros , em que todos os zeros devem ser simples. O conjunto de índices pode ser um conjunto finito, como B. , ou um conjunto contável como ou . Os kernels de interpolação são, portanto, dados como ${\ displaystyle H (x)}$ ${\ displaystyle \ {x_ {k}: k \, \ mathrm {from} \, I \}}$${\ displaystyle I}$${\ displaystyle I = \ {1, \ dots, N \}}$${\ displaystyle I = \ mathbb {N}}$${\ displaystyle I = \ mathbb {Z}}$

${\ displaystyle L_ {k} (x): = {\ frac {H (x)} {H '(x_ {k}) (x-x_ {k})}} = {\ frac {G (x, x_ {k})} {G (x_ {k}, x_ {k})}}}$

e continuou continuamente com o valor 1 no ponto . A função auxiliar é definida fora da diagonal como ${\ displaystyle x = x_ {k}}$${\ displaystyle G (x, y)}$${\ displaystyle x = y}$

${\ displaystyle G (x, y): = {\ frac {H (x) -H (y)} {xy}}}$e continuamente continuou a crescer .${\ displaystyle G (x, x): = H '(x)}$

O seguinte se aplica aos zeros , em que o delta de Kronecker foi usado. ${\ displaystyle L_ {k} (x_ {j}) = \ delta _ {k, j}}$

Se os valores são dados para cada um, uma função de interpolação é definida por ${\ displaystyle f_ {k}}$${\ displaystyle k \ in I}$

${\ displaystyle F (x): = \ sum _ {k \ in I} f_ {k} \ cdot L_ {k} (x) = \ sum _ {k \ in I} {\ frac {G (x, x_ {k})} {G (x_ {k}, x_ {k})}} f_ {k}}$.

No caso de um conjunto contável de zeros, a condição de convergência deve ser

${\ displaystyle \ sum _ {k \ in I} \ left | {\ frac {f_ {k}} {H '(x_ {k}) (1+ | x_ {k} |)}} \ right | <\ infty}$

ser preenchidas.

Exemplos

• Com pontos de apoio pré-determinados e uma função real com , a função pode ser formada. Então você consegue${\ displaystyle \ {x_ {1}, \ dotsc, x_ {N} \}}$${\ displaystyle h}$${\ displaystyle h (0) = 0}$${\ displaystyle h '(0) \ neq 0}$${\ displaystyle H (x): = h (x-x_ {1}) \ dotsm h (x-x_ {N})}$

${\ displaystyle L_ {k} (x) = {\ frac {h (x-x_ {k})} {h '(0) (x-x_ {k})}} \ cdot \ prod _ {j \ neq k} {\ frac {h (x-x_ {j})} {h (x_ {k} -x_ {j})}}}$.

O método de interpolação resultante é a interpolação de Lagrange. Outros exemplos são para funções de interpolação que diminuem em direção ao infinito em direção a zero ou para uma função de interpolação restrita com uma fórmula de cálculo clara.${\ displaystyle h (x) = x}$${\ displaystyle h (x) = x / (1 + x ^ {2})}$${\ displaystyle h (x) = \ sin (x)}$

• Com o polinômio de divisão de círculo , i. H. As -ésimas raízes da unidade , como pontos de apoio, resultam na transformação discreta de Fourier como método de cálculo dos coeficientes do polinômio de interpolação. Aplica-se e geralmente para que${\ displaystyle H (x): = x ^ {N} -1}$${\ displaystyle N}$ ${\ displaystyle x_ {k}: = \ exp (i2 \ pi \, k / N)}$${\ displaystyle k = 1, \ dots, N}$${\ displaystyle L_ {N} (x) = {\ frac {1} {N}} (1 + x + \ dotsb + x ^ {N-1})}$${\ displaystyle L_ {k} (x) = L_ {N} ({\ bar {x}} _ {k} \, x)}$

${\ displaystyle F (x) = \ sum _ {n = 0} ^ {N-1} x ^ {n} \ cdot {\ frac {1} {N}} \ sum _ {k = 1} ^ {N } f_ {k} {\ bar {x}} _ {k} ^ {n}}$ é.

• Com e zeros , é medido como a função de interpolação, o número cardinal${\ displaystyle H (x): = \ sin (\ pi x)}$${\ displaystyle x_ {k} = k}$${\ displaystyle k \ in \ mathbb {Z}}$

${\ displaystyle F (x) = \ sum _ {k \ in \ mathbb {Z}} f_ {k} {\ frac {\ sin (\ pi x)} {(- 1) ^ {+} k \ pi ( xk)}} = \ sum _ {k \ in \ mathbb {Z}} f_ {k} {\ frac {\ sin (\ pi (xk))} {\ pi (xk)}}}$.

Isso desempenha um papel central no teorema de amostragem de Nyquist-Shannon . A condição de convergência é

${\ displaystyle \ sum _ {k \ in \ mathbb {Z}} \ left | {\ frac {f_ {k}} {1+ | k |}} \ right | <\ infty}$.

Representação de ponto de apoio de polinômios

Seja um polinômio. Este polinômio pode ser representado na chamada representação de coeficiente especificando o vetor . Uma representação alternativa que dispensa os coeficientes é a representação do ponto de interpolação . O polinômio é avaliado para valores com e , i. ou seja, os valores da função são calculados. O par de vetores é chamado de representação do ponto de apoio do polinômio . Uma grande vantagem dessa representação é que dois polinômios podem ser multiplicados em etapas (consulte os símbolos de Landau ) na representação do ponto de suporte . Na representação do coeficiente, entretanto, as etapas são necessárias. A transformação da representação do coeficiente na representação do ponto de apoio é, portanto, de especial importância e é chamada de transformação de Fourier . A transformação reversa é obtida por interpolação. ${\ displaystyle p (x) = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + \ dotsb + a_ {n-1} x ^ {n-1}}$${\ displaystyle (a_ {0}, \ dotsc, a_ {n-1})}$${\ displaystyle a_ {0}, \ dotsc, a_ {n-1}}$${\ displaystyle n}$${\ displaystyle x_ {i}}$${\ displaystyle 0 \ leq i \ leq n-1}$${\ displaystyle i \ in \ mathbb {N}}$${\ displaystyle p (x_ {i}) = y_ {i}}$${\ displaystyle ((x_ {0}, \ dotsc, x_ {n-1}), (y_ {0}, \ dotsc, y_ {n-1}))}$${\ displaystyle p}$${\ displaystyle \ Theta (n)}$${\ displaystyle \ Theta (n ^ {2})}$

Formulários

Interpolação ao dimensionar uma imagem

Em muitas aplicações de métodos de interpolação, afirma-se que novas informações são obtidas a partir de dados existentes por interpolação . Mas isso está errado. Apenas o curso de uma função contínua entre pontos de amostragem conhecidos pode ser estimado por interpolação . Esta estimativa baseia-se principalmente no pressuposto de que o curso é algo “suave”, o que na maioria dos casos conduz a resultados plausíveis. No entanto, a suposição não precisa ser necessariamente correta. Componentes de frequência mais alta que foram perdidos quando um sinal foi digitalizado devido ao teorema de amostragem não podem ser reconstruídos novamente por interpolação subsequente.

Uma aplicação bem conhecida de interpolação é o processamento digital de sinais . Ao converter um sinal de uma taxa de amostragem baixa para uma alta (consulte a conversão da taxa de amostragem ), os valores de amostra do sinal de saída são interpolados daqueles do sinal de entrada. Um caso especial é o dimensionamento de imagens na computação gráfica .

Interpolação em dimensões superiores

Os procedimentos simples mostrados acima são geralmente descritos apenas para problemas 1D. Interpolações de spline com, por exemplo B. Splines de placa fina ou outras funções de base radial ou o método de krigagem ou a regressão do processo gaussiano. Uma maneira simples de interpolar pontos em dimensões superiores ( ) que estão em uma grade regular é aplicar interpolações 1D recursivamente. ${\ displaystyle \ mathbb {R} ^ {2}, \ mathbb {R} ^ {3}, ...}$

Isso é explicado usando o exemplo de interpolação bilinear.

São dados valores numéricos nos vértices , , e . Estamos procurando o valor interpolado no local . ${\ displaystyle Q_ {11}}$${\ displaystyle Q_ {12}}$${\ displaystyle Q_ {21}}$${\ displaystyle Q_ {22}}$${\ displaystyle P}$

Procedimento: A interpolação linear é aplicada duas vezes, por ex. B. primeiro para a direção x. É determinado a partir e com a interpolação 1D linear. Em seguida, é determinado da mesma maneira. O valor an resulta como uma interpolação linear 1D na direção y entre e . ${\ displaystyle R_ {1}}$${\ displaystyle Q_ {11}}$${\ displaystyle Q_ {21}}$${\ displaystyle R_ {2}}$${\ displaystyle P}$${\ displaystyle R_ {1}}$${\ displaystyle R_ {2}}$

3D: Existem pontos de canto com valores numéricos para uma interpolação trilinear . A primeira interpolação no eixo x resulta em pontos intermediários que são perpendiculares a um plano . Neste plano, a interpolação ocorre na direção y e os pontos intermediários resultam em uma linha na direção z na posição . A última interpolação nesta linha resulta finalmente em pontos, ou seja, a solução procurada. ${\ displaystyle 2 ^ {3}}$${\ displaystyle 2 ^ {2}}$${\ displaystyle x = P_ {x}}$${\ displaystyle y = P_ {y}}$${\ displaystyle 2 ^ {1}}$${\ displaystyle x = P_ {x}, y = P_ {y}}$${\ displaystyle 2 ^ {0}}$

O método pode ser usado para qualquer dimensão por meio de recursões sucessivas.

literatura

• Josef Stoer: Matemática Numérica 1 . 8ª edição, Springer 1999.
• Bernd Jähne : Processamento digital de imagens . 4ª edição, Springer 1997.
• Oppenheim, Schafer: Discrete-Time Signal Processing . Oldenbourg 1992.
• Crochiere, Rabiner: Multirate Digital Signal Processing . Prentice Hall 1983.

Links da web

• Ferramenta online para interpolação linear e quadrática com visualização
• Newton, Lagrange e página Cubic Spline também com miniaplicativo Java