Interpolação Polinomial

Consideremos um conjunto de pontos (designados nós de interpolação) x0 , ... , xn , a que estão associados os valores de uma função: f0 , ... , fn, respectivamente. Pretendemos encontrar um polinómio p ( x ) :

p ( xi ) = fi
para i = 0, ..., n.

O polinómio de 3º grau interpola a função em 4 pontos

Escrevendo p( x ) = a0 + a1 x + ... + am xm, obtemos o sistema

a0 + a1 x0 + ... + am x0m = f0
...
a0 + a1 xn + ... + am xnm = fn
e para que este sistema seja possível e determinado é pelo menos necessário que m=n.
Obtemos assim o sistema linear :


em que a matriz do sistema é conhecida como Matriz de Vandermonde.
A existência e unicidade do polinómio interpolador é equivalente a assegurar que o sistema é possível e determinado para quaisquer x0 , ... , xn distintos.

Teorema:
Dados n+1 nós, x0 , ... , xn e os respectivos valores f0 , ... , fn, existe um e um só, polinómio interpolador de grau < n, para esses valores.

demonstração:

  • Unicidade:
    Supondo que existem dois polinómios interpoladores p e q de grau < n, então o polinómio p(x) - q(x) tem grau < n e n+1 raízes, já que, sendo polinómios interpoladores, verificam :
    p ( xi ) = fi = q ( xi )
    para i = 0, ..., n.
    Consequentemente, como tem n+1 raízes e grau < n, o polinómio p(x)-q(x) terá que ser nulo, logo p=q .

  • Existência:
    Podemos mostrar a existência, construindo os Polinómios de Lagrange,

    Polinómios de Lagrange
    Dados n+1 nós de interpolação x0 , ... , xn, definimos para cada i = 0, ..., n o polinómio de Lagrange li(x) de grau n tal que :

    Podemos deduzir uma expressão explícita dos polinómios de Lagrange.
    Fixando i e variando j = 0, ..., n , obtemos:


    E a constante Ci pode determinar-se, pois:

    Consequentemente:

    para i = 0, ..., n .

    Agora, basta considerar a Fórmula Interpoladora de Lagrange:

    pn( x ) = f0 l0(x) + ... + fn ln(x)

    que nos dá a expressão do polinómio interpolador, pois é fácil verficar que pn ( xi ) = fi .

    Fórmula Interpoladora de Newton

    Trata-se de uma fórmula alternativa para o cálculo do polinómio interpolador, baseada numa construção sucessiva a partir dos polinómios de graus inferiores.

    Começamos por considerar que conhecemos a expressão do polinómio pn-1(x) de grau < n-1 que interpola os nós x0 , ... , xn-1.
    O polinómio pn(x) de grau < n, que interpola os nós x0 , ... , xn-1, xn, pode-se escrever na forma:

    pn(x) = pn-1(x) + qn(x)
    em que qn(x) é um polinómio de grau < n que tem n raizes, pois
    qn( xi ) = 0
    para i = 0, ..., n-1, logo
    qn( xi ) = Cn ( x - x0) ... ( x - xn-1) .

    Por outro lado, da condição pn( xn ) = fn , obtemos

    Este coeficiente Cn , que é o coeficiente do termo xn do polinómio interpolador (nos nós x0 , ... , xn), designa-se por
    diferença dividida de ordem n
    e escreve-se f [ x0 , ... , xn ].

    Portanto, podemos agora escrever

    pn(x) = pn-1(x) + f [ x0 , ... , xn ] ( x - x0) ... ( x - xn-1)

    e podemos obter sucessivamente, a partir do polinómio interpolador de grau zero p0(x) = f0 :

    p1(x) = f0 + f [ x0 , x1 ] ( x - x0)
    p2(x) = f0 + f [ x0 , x1 ] ( x - x0) + f [ x0 , x1, x2 ] ( x - x0) ( x - x1)
    ... etc ...

    Deduzimos assim a Fórmula Interpoladora de Newton :

    Cálculo das diferenças divididas

    A diferença dividida de 1ª ordem pode ser obtida, de uma forma geral por:

    f [ xi, xj] = ( fi - fj ) / ( xi - xj )

    e uma diferença dividida de ordem k, pode ser obtida a partir das anteriores :

    f [ xi , ... , xi+k] = ( f [ xi+1, ... , xi+k ] - f [ xi, ... , xi+k-1 ] ) / ( xi+k - xi )

    (a regra subjacente é que no denominador vai ficar a diferença entre os nós, que não são comuns às diferenças divididas do numerador).

    Observa-se que qualquer permutação da ordem dos nós não altera o resultado.
    Ou seja, por exemplo, f [ x1, x2 , x3 ] = f [ x2, x3 , x1 ]

    Nota: Podemos considerar os valores fi como diferenças divididas de ordem zero, e reparamos que isso é coerente com a definição da diferença de 1ª ordem a partir delas.



    Número de operacões:
    Se resolvermos o sistema linear, como vimos no Capítulo II, é necessário efectuar um total de ~2 n3/3 operações. Usando a Fórmula de Lagrange ou a Fórmula de Newton reduzimos para ~3 n2/2. A F. Lagrange usa mais multiplicações+divisões que a F. Newton, que, por sua vez, usa mais somas+subtracções.

    Erro de Interpolação

    Caso haja um conhecimento suplementar da função que pretendemos interpolar (para além do valor nos nós de interpolação), por exemplo, se tivermos majorações do valor da derivada de ordem n, num intervalo que contenha os nós, podemos estabelecer majorações para o erro de interpolação.

    O erro de interpolação, num certo ponto x, é :

    en( x ) = f( x ) - pn( x )

    É claro, que se x fôr um dos nós, o erro é zero! Caso contrário, podemos considerar esse valor x como um novo nó, e pensar no polinómio interpolador pn+1 . Já vimos que
    pn+1( y ) = pn( y ) + f[ x0, ... , xn, x ] ( y - x0 ) ... ( y - xn )

    Considerando y = x, e como x é um novo nó de interpolação, pn+1( x ) = f ( x ), e obtemos :

    f( x ) = pn( x ) + f[ x0 , ... , xn, x ]( x - x0 ) ... ( x - xn )
    ou seja
    en ( x ) = f [ x0 , ... , xn, x ] ( x - x0 ) ... ( x - xn )

    Esta fórmula é útil do ponto vista teórico, como também veremos mais tarde, no caso da integração.
    Vamos, no entanto, aproveitar uma relação entre as diferenças divididas e as derivadas, para estabelecer uma outra fórmula.

    Teorema :
    Consideremos n+1 nós de interpolação x0 , ... , xn distintos entre si incluídos no intervalo [x0, xn] onde a função f é de classe Cn.
    Então


    Este teorema pode ser aplicado à fórmula do erro anterior, e obtemos o seguinte corolário:

    Corolário :
    Seja V um intervalo que contenha os nós x0 , ... , xn e ainda o ponto x.
    Se a função f fôr de classe Cn+1( V )
    então temos a seguinte fórmula para o erro de interpolação:

    Terminamos este parágrafo, com um exemplo de uma função em que a aproximação, por interpolação polinomial, pode conduzir a maus resultados.
    Com efeito, se considerarmos a função f (x) = (1 + 25 x2 )-1, e pensarmos em interpolá-la no intervalo [-1, 1], usando nós igualmente espaçados, ao aumentarmos o número de nós, em vez de obtermos uma melhor aproximação, vamos obter uma aproximação cada vez pior, nas extremidades do intervalo!


    Exemplo de Runge: f(x) = (1 + 25 x2 )-1
    usando 11 nós de interpolação igualmente espaçados

    Este problema poderia ser resolvido, escolhendo nós de interpolação adequados (nós de Chebychev), mas isso sai fora do alcance deste curso.