Teoria da aproximação - Approximation theory

Em matemática , a teoria da aproximação se preocupa em como as funções podem ser mais bem aproximadas de funções mais simples e em caracterizar quantitativamente os erros assim introduzidos. Observe que o que significa melhor e mais simples dependerá do aplicativo.

Um tópico intimamente relacionado é a aproximação de funções por séries generalizadas de Fourier , ou seja, aproximações baseadas na soma de uma série de termos com base em polinômios ortogonais .

Um problema de particular interesse é o de aproximar uma função em uma biblioteca matemática de computador , usando operações que podem ser realizadas no computador ou calculadora (por exemplo, adição e multiplicação), de modo que o resultado seja o mais próximo possível da função real. Isso normalmente é feito com aproximações polinomiais ou racionais (proporção de polinômios).

O objetivo é fazer a aproximação o mais próximo possível da função real, normalmente com uma precisão próxima daquela da aritmética de ponto flutuante do computador subjacente . Isso é realizado usando um polinômio de alto grau e / ou estreitando o domínio sobre o qual o polinômio deve aproximar a função. Freqüentemente, o estreitamento do domínio pode ser feito por meio do uso de várias fórmulas de adição ou escala para a função que está sendo aproximada. Bibliotecas matemáticas modernas geralmente reduzem o domínio em muitos segmentos minúsculos e usam um polinômio de baixo grau para cada segmento.

Erro entre o polinômio ideal e log (x) (vermelho), e aproximação de Chebyshev e log (x) (azul) no intervalo [2, 4]. As divisões verticais são ^10-5 . O erro máximo para o polinômio ideal é 6,07 × 10 ⁻⁵ .

Erro entre polinômio ótimo e exp (x) (vermelho), e aproximação de Chebyshev e exp (x) (azul) no intervalo [-1, 1]. As divisões verticais são 10 ⁻⁴ . O erro máximo para o polinômio ideal é 5,47 × 10 ⁻⁴ .

Polinômios ótimos

Uma vez que o domínio (normalmente um intervalo) e o grau do polinômio são escolhidos, o próprio polinômio é escolhido de forma a minimizar o erro de pior caso. Ou seja, o objetivo é minimizar o valor máximo de , onde P ( x ) é o polinômio de aproximação, f ( x ) é a função real e x varia no intervalo escolhido. Para funções bem comportadas, existe um polinômio de N- ésimo grau que levará a uma curva de erro que oscila para frente e para trás e um total de N +2 vezes, resultando em um erro de pior caso de . É visto que existe um polinômio de N- ésimo grau que pode interpolar N +1 pontos em uma curva. Esse polinômio é sempre ideal. É possível fazer funções inventadas f ( x ) para as quais não existe tal polinômio, mas elas ocorrem raramente na prática. ${\ displaystyle \ mid P (x) -f (x) \ mid}$ ${\ displaystyle + \ varepsilon}$ ${\ displaystyle - \ varepsilon}$ ${\ displaystyle \ varepsilon}$

Por exemplo, os gráficos mostrados à direita mostram o erro na aproximação de log (x) e exp (x) para N = 4. As curvas vermelhas, para o polinômio ótimo, são niveladas , ou seja, elas oscilam entre e exatamente. Observe que, em cada caso, o número de extremos é N +2, ou seja, 6. Dois dos extremos estão nos pontos finais do intervalo, nas bordas esquerda e direita dos gráficos. ${\ displaystyle + \ varepsilon}$ ${\ displaystyle - \ varepsilon}$

Erro P ( x ) - f ( x ) para o nível de polinômio (vermelho) e para o suposto melhor polinômio (azul)

Para provar que isso é verdade em geral, suponha que P seja um polinômio de grau N possuindo a propriedade descrita, ou seja, dá origem a uma função de erro que possui N + 2 extremos, de sinais alternados e magnitudes iguais. O gráfico vermelho à direita mostra como essa função de erro pode se parecer para N = 4. Suponha que Q ( x ) (cuja função de erro é mostrada em azul à direita) seja outro polinômio de N graus que é uma melhor aproximação de f do que P . Em particular, Q está mais próximo de f do que P para cada valor x _i onde ocorre um extremo de P - f , então

{\ displaystyle | Q (x_ {i}) - f (x_ {i}) | <| P (x_ {i}) - f (x_ {i}) |.}

Quando um máximo de P - f ocorre em x _i , então

{\ displaystyle Q (x_ {i}) - f (x_ {i}) \ leq | Q (x_ {i}) - f (x_ {i}) | <| P (x_ {i}) - f (x_ {i}) | = P (x_ {i}) - f (x_ {i}),}

E quando um mínimo de P - f ocorre em x _i , então

{\ displaystyle f (x_ {i}) - Q (x_ {i}) \ leq | Q (x_ {i}) - f (x_ {i}) | <| P (x_ {i}) - f (x_ {i}) | = f (x_ {i}) - P (x_ {i}).}

Portanto, como pode ser visto no gráfico, [ P ( x ) - f ( x )] - [ Q ( x ) - f ( x )] deve alternar no sinal para os N + 2 valores de x _i . Mas [ P ( x ) - f ( x )] - [ Q ( X ) - f ( x )] reduz a P ( x ) - Q ( X ) que é um polinómio de grau N . Esta função muda de sinal, pelo menos, N 1 vezes, de modo, pelo valor Intermediário teorema , que tem N + 1 zeros, o que é impossível para um polinómio de grau N .

Aproximação de Chebyshev

Pode-se obter polinômios muito próximos do ótimo expandindo a função dada em termos de polinômios de Chebyshev e então cortando a expansão no grau desejado. Isso é semelhante à análise de Fourier da função, usando os polinômios de Chebyshev em vez das funções trigonométricas usuais.

Se alguém calcular os coeficientes na expansão de Chebyshev para uma função:

{\ displaystyle f (x) \ sim \ sum _ {i = 0} ^ {\ infty} c_ {i} T_ {i} (x)}

e então corta a série após o termo, obtém-se um polinômio de N- ésimo grau aproximando f ( x ). ${\ displaystyle T_ {N}}$

A razão pela qual este polinômio é quase ótimo é que, para funções com séries de potências de convergência rápida, se a série for cortada após algum termo, o erro total decorrente do corte é próximo ao primeiro termo após o corte. Ou seja, o primeiro termo após o corte domina todos os termos posteriores. O mesmo é verdadeiro se a expansão for em termos de polinômios de compensação. Se uma expansão de Chebyshev for interrompida depois , o erro assumirá a forma próxima a um múltiplo de . Os polinômios de Chebyshev têm a propriedade de serem nivelados - eles oscilam entre +1 e −1 no intervalo [−1, 1]. tem N +2 extremos de nível. Isso significa que o erro entre f ( x ) e sua expansão de Chebyshev para está próximo a uma função de nível com N +2 extremos, portanto, está perto do polinômio de N- ésimo grau ótimo . ${\ displaystyle T_ {N}}$ ${\ displaystyle T_ {N + 1}}$ ${\ displaystyle T_ {N + 1}}$ ${\ displaystyle T_ {N}}$

Nos gráficos acima, observe que a função de erro azul às vezes é melhor do que (dentro da) função vermelha, mas às vezes é pior, o que significa que não é exatamente o polinômio ideal. A discrepância é menos séria para a função exp, que tem uma série de potências convergentes extremamente rápidas, do que para a função log.

A aproximação de Chebyshev é a base para a quadratura de Clenshaw-Curtis , uma técnica de integração numérica .

Algoritmo de Remez

O algoritmo Remez (às vezes escrito Remes) é usado para produzir um polinômio ótimo P ( x ) aproximando uma dada função f ( x ) em um determinado intervalo. É um algoritmo iterativo que converge para um polinômio que tem uma função de erro com extremos de nível N +2. Pelo teorema acima, esse polinômio é ótimo.

O algoritmo de Remez usa o fato de que se pode construir um polinômio de N- ésimo grau que leva a valores de erro de nível e alternados, dados N +2 pontos de teste.

Dado N +2 pontos de teste , , ... (onde e são presumivelmente os pontos finais do intervalo de aproximação), estas equações precisam ser resolvidos: ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$ ${\ displaystyle x_ {N + 2}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {N + 2}}$

{\ displaystyle {\ begin {alinhados} P (x_ {1}) - f (x_ {1}) & = + \ varepsilon \\ P (x_ {2}) - f (x_ {2}) & = - \ epsilon \\ P (x_ {3}) - f (x_ {3}) & = + \ epsilon \\ & \ \ \ vdots \\ P (x_ {N + 2}) - f (x_ {N + 2} ) & = \ pm \ varepsilon. \ end {alinhado}}}

Os lados direitos alternam em sinal.

Isso é,

{\ displaystyle {\ begin {alinhados} P_ {0} + P_ {1} x_ {1} + P_ {2} x_ {1} ^ {2} + P_ {3} x_ {1} ^ {3} + \ pontos + P_ {N} x_ {1} ^ {N} -f (x_ {1}) & = + \ varejpsilon \\ P_ {0} + P_ {1} x_ {2} + P_ {2} x_ {2 } ^ {2} + P_ {3} x_ {2} ^ {3} + \ dots + P_ {N} x_ {2} ^ {N} -f (x_ {2}) & = - \ varepsilon \\ & \ \ \ vdots \ end {alinhado}}}

Desde que , ..., foram dados, todos os seus poderes são conhecidos, e , ..., também são conhecidos. Isso significa que as equações acima são apenas N +2 equações lineares nas N variáveis +2 , , ..., , e . Dados os pontos de teste , ... ,, pode-se resolver este sistema para obter o polinômio P e o número . ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {N + 2}}$ ${\ displaystyle f (x_ {1})}$ ${\ displaystyle f (x_ {N + 2})}$ ${\ displaystyle P_ {0}}$ ${\ displaystyle P_ {1}}$ ${\ displaystyle P_ {N}}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {N + 2}}$ ${\ displaystyle \ varepsilon}$

O gráfico abaixo mostra um exemplo disso, produzindo um polinômio de quarto grau aproximando -se de [-1, 1]. Os pontos de teste foram definidos em −1, −0,7, −0,1, +0,4, +0,9 e 1. Esses valores são mostrados em verde. O valor resultante de é 4,43 × 10 ⁻⁴ ${\ displaystyle e ^ {x}}$ ${\ displaystyle \ varepsilon}$

Erro do polinômio produzido pela primeira etapa do algoritmo de Remez, aproximando e ^x no intervalo [-1,1]. As divisões verticais são 10 ⁻⁴ .

Observe que o gráfico de erro realmente assume os valores nos seis pontos de teste, incluindo os pontos finais, mas esses pontos não são extremos. Se os quatro pontos de teste internos fossem extremos (ou seja, a função P ( x ) f ( x ) tivesse máximos ou mínimos lá), o polinômio seria ótimo. ${\ displaystyle \ pm \ varepsilon}$

A segunda etapa do algoritmo de Remez consiste em mover os pontos de teste para as localizações aproximadas onde a função de erro teve seus máximos ou mínimos locais reais. Por exemplo, pode-se dizer, olhando para o gráfico, que o ponto em -0,1 deveria estar em cerca de -0,28. A maneira de fazer isso no algoritmo é usar uma única rodada do método de Newton . Uma vez que se conhece a primeira e a segunda derivadas de P ( x ) - f ( x ) , pode-se calcular aproximadamente o quanto um ponto de teste deve ser movido para que a derivada seja zero.

Calcular as derivadas de um polinômio é simples. Deve-se também ser capaz de calcular a primeira e a segunda derivadas de f ( x ). O algoritmo de Remez requer uma capacidade de calcular , e de precisão extremamente elevada. Todo o algoritmo deve ser executado com uma precisão maior do que a precisão desejada do resultado. ${\ displaystyle f (x) \,}$ ${\ displaystyle f '(x) \,}$ ${\ displaystyle f '' (x) \,}$

Depois de mover os pontos de teste, a parte da equação linear é repetida, obtendo um novo polinômio, e o método de Newton é usado novamente para mover os pontos de teste novamente. Essa sequência é continuada até que o resultado converta para a precisão desejada. O algoritmo converge muito rapidamente. A convergência é quadrática para funções bem comportadas - se os pontos de teste estiverem dentro do resultado correto, eles estarão aproximadamente dentro do resultado correto após a próxima rodada. ${\ displaystyle 10 ^ {- 15}}$ ${\ displaystyle 10 ^ {- 30}}$

O algoritmo de Remez é normalmente iniciado escolhendo os extremos do polinômio de Chebyshev como os pontos iniciais, uma vez que a função de erro final será semelhante a esse polinômio. ${\ displaystyle T_ {N + 1}}$

Revistas principais

Veja também

Referências

NI Achiezer (Akhiezer) , Teoria da aproximação, traduzida por Charles J. Hyman Frederick Ungar Publishing Co., Nova York 1956 x + 307 pp.
AF Timan, Theory of aproximation of functions of a real variable , 1963 ISBN 0-486-67830-X
C. Hastings, Jr. Aproximações para computadores digitais . Princeton University Press, 1955.
JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Computer Approximations . Wiley, 1968, Lib. Cong. 67-23326.
L. Fox e IB Parker. "Chebyshev Polynomials in Numerical Analysis." Oxford University Press London, 1968.
Pressione, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (2007), "Section 5.8. Chebyshev Approximation" , Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
WJ Cody Jr., W. Waite, Manual do software para as funções elementares . Prentice-Hall, 1980, ISBN 0-13-822064-6 .
E. Remes [Remez] , "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 CR Acad. Sci. , Paris, 199 , 337-340.
KG. Steffens, "The History of Approximation Theory: From Euler to Bernstein," Birkhauser, Boston 2006 ISBN 0-8176-4353-2 .
T. Erdélyi , "Extensões do teorema de Bloch-Pólya sobre o número de zeros reais distintos de polinômios", Journal de théorie des nombres de Bordeaux 20 (2008), 281-287.
T. Erdélyi, "A desigualdade de Remez para combinações lineares de gaussianas deslocadas", Math. Proc. Camb. Phil. Soc. 146 (2009), 523-530.
LN Trefethen , "teoria da aproximação e prática da aproximação", SIAM 2013. [1]

Languages

In other projects