Aproximação¶

Como aproximar um conjunto de dados usando uma sequência de funções simples?

• Polinômios
• Interpolação - Introdução
• Interpolação de Lagrange
• Método dos mínimos quadrados
• Códigos

Introdução¶

Qual o objetivo?

1. Modelar dados experimentais
2. Aproximar uma função complexa usando funções mais simples

Dada uma função $u(x)$ queremos aproximá-la usando um conjunto de funções que são, de alguma, forma convenientes:

$$ u \approx u^\delta (x) = \sum_{i=1}^N \hat{u}_i \phi_i(x) $$

Porque queremos fazer isso?

• Funções muito complexas
• Funções que não são conhecidas explicitamente (algumas funções especiais)
• Queremos desempenho na hora de calcular as funções: praticamente todas as funções básicas são aproximadas utilizando polinômios (muitas vezes polinômios racionais)
• Quando conhecemos apenas alguns pontos da função: sempre que você tiver um experimento ou estiver processando dados de uma sequência de simulações numéricas.

Interpolação¶

É lógico que, em geral, a aproximação é apenas uma aproximação! Então existe um erro:

$$ u(x) - u^\delta(x) = \varepsilon(x) $$

A idéia é minimizar este erro de alguma forma.

Uma possibilidade é escolher $N$ pontos $x_i$ e impor que o erro é zero nestes pontos:

$$ \varepsilon(x_i) = 0 \qquad i=1, \ldots, N $$

Esta abordagem é conhecida na literatura como colocação. Se a função $u(x)$ é conhecida apenas por alguns pontos $(x_i, u_i)$ isto é chamado de interpolação.

Isto resulta num sistema de equações lineares:

$$ \left(\begin{matrix} \phi_1(x_1) & \phi_2(x_1) & \cdots & \phi_N(x_1) \\ \phi_1(x_2) & \phi_2(x_2) & \cdots & \phi_N(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ \phi_1(x_N) & \phi_2(x_N) & \cdots & \phi_N(x_N) \\ \end{matrix}\right) \cdot\left(\begin{matrix} \hat{u}_1 \\ \hat{u}_2 \\ \vdots \\ \hat{u}_N \end{matrix} \right) = \left(\begin{matrix} u(x_1) \\ u(x_2) \\ \vdots \\ u(x_N) \end{matrix} \right) $$ Esta é a matriz de Vandermonde.

A escolha de funções $\phi_i(x)$ adequadas simplificam a solução do problema. Se, por exemplo, $\phi_i(x_k) = \delta_{ik}$ onde $\delta$, neste caso, é o delta de Kronecker, a matriz é diagonal.

Mínimos quadrados¶

Por outro lado, podemos, para uma sequência de pontos minimizar o erro quadrático total:

$$ R(\hat{u}_1, \ldots, \hat{u}_N) = \sum_{i=1}^Q \left[ u(x_i) - u^\delta(x_i)\right]^2 $$ onde $Q$ é o número de pontos. Esta operação se chama método dos mínimos quadrados.

Chamando $u(x_i) = u_i$, para minimizar este resíduo (erro quadrático total), basta derivar e igualar a zero, assim, chega-se ao seguinte sistema de equações lineares:

$$ \left( \begin{matrix} \sum_{i=1}^Q \phi_1(x_i)\cdot\phi_1(x_i) & \cdots & \sum_{i=1}^Q \phi_1(x_i)\cdot\phi_N(x_i) \\ \sum_{i=1}^Q \phi_2(x_i)\cdot\phi_1(x_i) & \cdots & \sum_{i=1}^Q \phi_2(x_i)\cdot\phi_N(x_i) \\ \vdots & \ddots & \vdots \\ \sum_{i=1}^Q \phi_N(x_i)\cdot\phi_1(x_i) & \cdots & \sum_{i=1}^Q \phi_N(x_i)\cdot\phi_N(x_i) \\ \end{matrix}\right) \cdot \left(\begin{matrix} \hat{u}_1 \\ \hat{u}_2 \\ \vdots \\ \hat{u}_N \end{matrix}\right) = \left(\begin{matrix} \sum_{i=1}^Q u_i \phi_1(x_i) \\ \sum_{i=1}^Q u_i \phi_1(x_i) \\ \vdots \\ \sum_{i=1}^Q u_i \phi_1(x_i)\end{matrix}\right) $$

Uma formulação mais geral¶

Uma formulação mais geral é escolher funções peso $w_k(x)$ de modo que $$ \int_a^b u(x)w_k(x)\:dx = \int_a^b u^\delta (x) w_k(x) \:dx $$

Escolhendo $w_k(x)$ = $\delta(x_k)$ (Delta de Dirac), recuperamos a interpolação. Escolhendo $w_k(x) = \phi_k(x)$ temos o método de Galerkin, muito usado no método de elementos finitos.

Com o método de elementos finitos, a função não necessariamente vai passar pelos pontos, mas o erro será minimizado e pode-se obter uma aproximação melhor.

Outro ponto a ser considerador é o que ocorre quando as medidas possuem erro e como isso afeta a aproximação.

Polinômios¶

$$ p_n(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots a_n x^n = \sum_{i=0}^n a_i x^i $$ Um polinômio é dado por seus coeficientes $a_i$. Em Julia, a indexação começa em 1, portanto é conveniente reescrever a definição acima como:

$$ p_n(x) = a_1 + a_2 x + a_3 x^2 + a_4 x^3 + \ldots a_n x^{n-1} + a_{n+1} x^n = \sum_{i=1}^{n+1} a_i x^{i-1} $$

Método de Horner¶

Maneira mais eficiente e mais precisa de calcular o valor de um polinômio:

$$ p_n(x) = a_1 + x\left(a_2 + x\left(a_3 + x\left(\ldots + a_{n+1} x\right) \right) \right) $$

E os tipos dos dados???¶

Polynomials.jl¶

Macro quando os coeficientes são conhecidos¶

Interpolação¶

Dado um conjunto de n pontos $(x_i, y_i)$, qual o poliômio que passa por todos?

$$ y_i = a_0 + a_1 x_i + a_2 x_i^2 + \ldots a_n x_i^n \qquad i=1, \ldots, m $$

Vandermonde¶

Com n+1 pontos distintos, se o polinômio for de grau n, pode-se montar o seguinte sistema linear:

$$ \begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & x_n^2 & \cdots & x_n^n\\ \end{bmatrix}\cdot \left\{ \begin{matrix} a_0 \\ a_1 \\ \vdots \\ a_n\\ \end{matrix}\right\} = \left\{\begin{matrix} y_0 \\ y_1 \\ \vdots \\ y_n\\\end{matrix}\right\} $$

Mas esta é uma operação cara, $\mathcal{O}(n^3)$!

Outra possibilidade¶

$$ y = f(x) \approx a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1)\cdots(x - x_{n-1}) $$

Com isso chegamos ao seguinte sistema linear triangular: $$ \begin{bmatrix} 1 & 0 & 0 & 0 &\cdots & 0\\ 1 & (x_1-x_0) & 0 & 0 & \cdots & 0\\ 1 & (x_2 - x_0) & (x_2 - x_0)(x_2 - x_1) & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & (x_n - x_0) & (x_n - x_0)(x_n - x_1) & (x_n - x_0)(x_n - x_1)(x_n-x_2) & \cdots &(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})\\ \end{bmatrix}\cdot\left\{\begin{matrix} a_0\\ a_1 \\ a_2 \\ \vdots \\ a_n\end{matrix}\right\} = \left\{\begin{matrix} y_0\\ y_1 \\ y_2 \\ \vdots \\ y_n\end{matrix}\right\} $$

Resolver este sistema é muito mais barato: $\mathcal{O}(n^2)$

Interpolação de Lagrange:¶

$$ y(x) = \sum_{i=1}^n y_i h_i(x) $$

onde $h_i(x)$ é o interpolador de Lagrange:

$$ h_k(x) = \prod_{i=1\ldots n,}^n \frac{x - x_i}{x_k - x_i} \qquad i\ne k $$

Propriedade: $$ h_i(x_i) = \delta_{ij} \quad \text{onde} \quad \delta_{ij} = \left\{\begin{matrix}1, \: i=j \\ 0, i\ne j\\ \end{matrix}\right. $$

Vamos organizar a interpolação de Lagrange¶

Interpolação Linear¶

Mínimos quadrados¶

Pacotes¶

• Interpolations
• Dierckx
• GridInterpolations

Exercícios¶

Problema 1¶

Interpole a função de Runge com $-1 \le x \le 1$: $$ f(x) = \frac{1}{1 + 25x^2} $$

1. Use 11 pontos uniformemente distribuídos
2. Aumente o número de pontos
3. Tente usar os pontos $x_k = \cos\left(\frac{k\pi}{N}\right)$ para $k = 0\ldots N$.
4. Brinque com o número de pontos

Problema 2¶

Procure na Net o método de diferenças divididas de Newton a interpole a função anterior nos mesmos pontos. Este método é simplesmente um jeito inteligente de resolver a matriz apresentada lá em cima.

Problema 3¶

Use a biblioteca Interpolations.jl e Dierckx.jl para fazer as interpolações. Compare a interpolação linear com os splines.

Problema 4¶

Crie funções para fazer os seguintes problemas de mínimos quadrados:

• $y = a_0 x^ a_1$
• $y = a_0 \exp \left( a_1 \cdot x\right)$
• Polinômio genérico de ordem n