3.1.3 Aproximação de Funções — Interpolação — Interpolação de Lagrange

1. Interpolação Lagrangiana

Seja a função que desejamos aproximar

$$f(x) = \sum_{j=1}^{n} l_j(x)f(a_j) + E(x) = y(x) + E(x) $$

tal que mantemos as restrições que mantém o erro dos pontos tabulares nulos e que seja independente de $f(x)$ . Tomamos

$$l_j(a_k) = \delta_{ij} \hspace{50pt} (j,k) = 1,\ldots,n $$

onde $\delta\_{jk}$ é o Delta de Kronecker. Como $l\_j(x)$ é um polinômio, isto implica que terá o fator

$$(x – a_1)(x – a_2) \ldots (x – a_{j-1}) (x – a_{j+1}) \ldots (x – a_n) $$

e como $l\_j(a\_j) = 1$ , podemos escrever para os termos gerais:

$$l_j(x) = \dfrac{(x-a_1)\ldots(x-a_{j-1})(x-a_{j+1})\ldots(x-a_n)}{(a_j-a1)\ldots(a_j-a_{j-1})(a_j-a_{j+1})\ldots(a_j-a_n)}$$

Note que há outras possíveis representações para o polinômio $l\_j(x)$, mas apenas a equação acima será um polinômio de grau $n-1$ . Isto torna conveniente escrever $l\_j(x)$ como

$$l_j(x) = \dfrac{p_n(x)}{(x-a_j)p’_n(a_j)} $$

onde $p’\_n(x) = \frac{dp\_n}{dx}$ e $p\_n(x) = \prod\_{i=1}^{n}(x-a_i)$.

Para fazermos uma análise do erro de aproximação associado, devemos obter expressão $E(x)$ , considerando a função

$$F(z) = f(z) – y(z) – [f(x) – y(x)]\frac{p_n(z)}{p_n(x)} $$

com $y(x)$ sendo a função ajustada da original. A função $F(z)$ como uma função de $z$ com $n+1$ raízes nos pontos $a\_0,a\_1,\ldots,a_n$ e assumindo $x$ sempre diferente dos pontos tabulares. Assim, ao aplicarmos o teorema de Rolle $n$ vezes, teremos que

$$F^{(n)}(z) = f^{(n)}(z) – y^{(n)}(z) – [f(x) – y(x)]\frac{n!}{p_n(x)} $$

terá ao menos um zero no intervalo determinado por $[a\_1,a\_n]$ . Chamando este zero de $z = \xi$ e notando que $y^{(n)}(z) = 0$ , teremos

$$0 = F^{(n)}(\xi) = f^{(n)}(\xi) – [f(x) – y(x)] \frac{n!}{p_n(x)} $$

que pode ser utilizado no cálculo do erro como

$$E(x) = \frac{p_n(x)}{n!}f^{(n)}(\xi) $$

Utilizando a equação

$$f(x) = \sum_{j=1}^{n} l_j(x)f(a_j) + E(x) = y(x) + E(x) $$

e agora de posse das funções $l_j(x)$ e $E(x)$ , podemos obter a formula para a interpolação de Lagrange:

$$y(x) = \sum_{j=0}^{n} P_j(x)f(x_j) $$

onde

$$P_j(x) = \prod_{i=0}^{n} \dfrac{x-x_i}{x_j-x_i} $$

Da expressão acima, podemos notar que diferentes graus de polinômios podem ser gerados. Por exemplo:

• Polinômios de primeiro grau (interpolação linear):

  $$y(x) = f_1(x) = \frac{x-x_1}{x_0 – x_1}f(x_0) + \frac{x-x_0}{x_1-x_0}f(x_1) $$

• Polinômios de segundo grau (interpolação quadrática):

  $$y(x) = f_2(x) = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}f(x_0) + \frac{(x-x0)(x-x2)}{(x_1-x_0)(x_1-x_2)}f(x_1) + \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}f(x_2) $$

 

2. Implementação

def interpolation_lagrange(x, x_j, f_j, n=0):
    """
    Return x evaluated in Lagrangian interpolation function.

    interpolation_lagrange(x, x_j, f_j)

    INPUT:
      * x: evalue at this point
      * x_j: LIST, tabular points
      * f_j: LIST, tabular points (must be same size of x_j)
      * n: polynom degree (optional)

    return:
      * y(x): interpolated and evaluated x value

    Author: Pedro Garcia [sawp@sawp.com.br]
    see: http://www.sawp.com.br

    License: Creative Commons
             http://creativecommons.org/licenses/by-nc-nd/2.5/br/

    Oct 2010
    """

    if type(x_j) != type(f_j) or type(x_j) != type([]):
        print "Error: wrong type parameters"
        return float("NaN")

    if len(x_j) != len(f_j):
        print "Error: the tabular points must have same size"
        return float("NaN")

    if n < = 0:
        n = len(x_j)
    else:
        n = n + 1

    p = 0.0
    for i in xrange(n):
        li = f_j[i]
        xi = x_j[i]
        for j in xrange(n):
            xj = x_j[j]
            if i != j:
                li = li * (x - xj) / (xi - xj)
        p += li
    return p

Esta função está disponível em http://www.sawp.com.br/code/interpolation/interpolation_lagrange.py assim como um exemplo de como utilizá-la.

 

3. Copyright

Este documento é disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.

References

[1] Anthony Ralston and Philip Rabinowitz, A First Course in Numerical Analysis (2nd ed.), McGraw-Hill and Dover, (2001), 423-424.

[2] N.B Franco, Cálculo Numérico, Pearson Prentice Hall, (2006), 69.

<a name="bibitem3" href='http://en.wikipedia.org/wiki/Rolle's_theorem'>[3] http://en.wikipedia.org/wiki/Rolle’s_theorem </a>