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.

[3] http://en.wikipedia.org/wiki/Rolle’s_theorem