Interpolação Objetivo Interpolar uma função f(x) consiste em aproximar essa função por uma outra função g(x), escolhida entre uma classe de funções definidas (polinômios). g(x) é usada em substituição à função f. Problemática Essa necessidade de efetuar esta substituição surge quando: Quando são somente conhecidos os valores numéricos da função para um conjunto de pontos e é necessário calcular o valor de um ponto no tabelado. Quando a expressão da função é complicada de mais para ser integrada ou diferenciada. Em equação Consideremos n+1 valores distintas: x0, ..., xn (nós da interpolação) e os valores de f(x) nesses pontos: f(x0), ..., f(xn). Queremos determinar a função g(x) tal que: g(x0)=f(x0) .... g(xn)=f(xn) Graficamente Classe de funções Em nosso caso, consideramos a função g(x) com um elemento da classe de funções polinomiais. Tentaremos aproximar a função f(x) a partir de um conjunto de valores com uma função do tipo: a0+a1x+...+anxn Interpolação polinomial Dados os n+1 pontos (x0,f(x0)), ..., (xn,f(xn)), queremos aproximar f(x0) por um polinômio pn(x) de grau menor ou igual a n: f(xk)=pn(xk) ; k=0,1,...n Questões: esse polinômio existe? Ele é único? Interpolação polinomial Considerando que p o polinômio escreve-se pn(x)= a0+a1x+...+anxn , a condição f(xk)=pn(xk) ; k=0,1,...,n produz o sistema seguinte de n+1 equações , n+1 variáveis: a0 a1 x0 ... an x0 n f ( x0 ) n a0 a1 x1 ... an x1 f ( x1 ) ......... a a x ... a x n f ( x ) n n n 0 1 n Interpolação polinomial: matriz A matriz do sistema é: 1 1 A 1 1 x0 ... x0 n n x1 ... x1 ... ... ... n xn ... xn Essa matriz é uma matriz de Vandermonde, desde que x0, ..., xn são pontos distintos, temos det A0. Então o sistema admite uma solução única. Prova Podemos proceder da forma seguinte: O determinante pode ser considerado como um polinômio em x0: 1 x0 ... x0 n 1 x1 ... 1 ... ... x1n a 0 a1 x0 a 2 x0 2 ... a n x0 n ... n 1 xn ... xn E um polinômio de grau n com n raízes: x1 a xn, ele pode ser escrito aP(xi-x0); i0 Determinante de Vandermonde O determinante da matriz de Vandermonde pode ser escrito da forma seguinte: 1 x0 ... x0 1 x1 ... 1 ... ... 1 xn n n 1 x ( x j xi ) ... 0i j n ... xn n Interpolação polinomial: teorema Em outros termos podemos dizer que: Existe um único polinômio pn(x) de grau n tal que pn(xk)=f(xk), k=0,1,...,n desde que xixj por jk. Obter pn(x) Para obter o polinômio pn(x), existem diversos métodos, o mais direto sendo a resolução do sistema linear. A escolha do método depende de várias condições: a estabilidade do sistema, performance computacional, ... Resolução do sistema Vamos encontrar o polinômio de grau 2 que interpola os pontos da tabela: x -1 f(x) 4 0 1 2 -1 Considerando p2(x)=a0+a1x+a2x2. Temos o sistema:a 0 -a1 +a 2 =4 7 2 a 0 1, a1 , a 2 a 0 =1 3 3 a +2a +4a =-1 1 2 0 Condicionamento A determinação dos coeficientes pela resolução do sistema é um processo simples, mas o sistema pode ser mal condicionado e sua resolução com numeração a ponto flutuante produzir resultados errados. Existem outros métodos para determinar os polinômios de interpolação. Como existe uma solução única, qualquer método que determina uma solução, determina a solução única. Forma de Lagrange Considerando os n+1 pontos (x0,y0=f(x0)), ..., (xn,yn= f(xn)) e o polinômio interpolador pn(x). Lagrange propôs de representar o polinômio pn(x) da forma: pn(x)=y0L0(x)+..+ynLn(x), onde Lk(x) são polinômios de grau n e a condição pn(xi)=yi, i=0,...,n seja satisfeita. Forma de Lagrange A melhor forma de ter a condição: pn(xi)=yi i=0,...,n, é impor: 1 se k i Lk (x i )= 0 se k i Por isso, consideramos: ( x x0 )( x x1 )...( x xk 1 )( x xk 1 )...( x xn ) Lk ( x) ( xk x0 )( xk x1 )...( xk xk 1 )( xk xk 1 )...( xk xn ) Forma de Lagrange O numerador de Lk(x) é um produto de n fator em x, então Lk(x) é de grau n. Podemos verificar também que: 1 se k i Lk (x i )= 0 se k i A forma de Lagrange para o polinômio n interpolador é: (x x j ) n pn ( x) yk Lk ( x), Lk ( x) k 0 j 0, j k n j 0, j k ( xk x j ) Interpolação linear Interpolação de dois pontos (x0,y0=f(x0)) e (x1,y1=f(x1)). Usando a forma de Lagrange, temos: ( x x0 ) ( x1 x) y0 ( x x0 ) y1 ( x x1 ) pn ( x) y0 y1 ( x0 x1 ) ( x1 x0 ) ( x1 x0 ) Exemplo x -1 Seja a tabela: f(x) 4 Temos: 0 1 2 -1 ( x x1 )( x x2 ) ( x 0)( x 2) x2 2x L0 ( x) ( x0 x1 )( x0 x2 ) (1 0)(1 2) 3 ( x x0 )( x x2 ) ( x 1)( x 2) x 2 x 2 L1 ( x) ( x1 x0 )( x1 x2 ) (0 1)(0 2) 2 ( x x0 )( x x1 ) ( x 1)( x 0) x 2 x L2 ( x) ( x2 x0 )( x2 x1 ) (2 1)(2 0) 6 x2 2 x x2 x 2 x2 x 7 2 2 pn ( x) 4 1 x x 3 2 6 3 3 Forma de Newton Considerando os n+1 pontos (x0,f(x0)), ..., (xn,f(xn)) e o polinômio interpolador pn(x). Newton propôs de representar o polinômio pn(x) da forma: pn(x)=d0+d1(x-x0)+d2(x-x0)(x-x1)+...+dn(x-x0)...(x-xn-1) Os coeficientes dk, k=0,...,n são diferenças divididas de ordem k entre os pontos (xj,f(xj)), j=0,...,k Operador diferenças divididas f(x) é uma função tabelada em x0,...,xn. Os operadores de diferenças divididas são definidos por: f [ x0 ] f ( x0 ) f [ x0 , x1 ] f [ x1 ] f [ x0 ] x1 x0 f [ x , x , x ] f [ x1 , x2 ] f [ x0 , x1 ] 0 1 2 x2 x0 f [ x ,..., x ] f [ x1 ,..., xn ] f [ x0 ,..., xn 1 ] 0 n xn x0 ordem 0 ordem1 ordem 2 ordem n Operador diferenças divididas x Ordem 0 Ordem 1 Ordem 2 ... Ordem n x0 f[x0] f[x0,x1] x1 f[x1] f[x0,x1,x2] f[x1,x2] x2 f[x2] f[x1,x2,x3] f[x0,...,xn] f[xn-2, xn-1, xn] .... xn f[xn] f[xn-1, xn] Operador diferenças divididas Exemplo: x f(x) -1 1 x -1 0 1 1 0 1 2 -1 2 -2 1 0 0 3 Ordem 0 Ordem 1 Ordem 2 Ordem 3 Ordem 4 1 -1/2 -1 0 1/6 0 -1 -1 3 -2 0 0 -1 -1/24 Forma de Newton Podemos provar que as diferenças divididas satisfazem a propriedade seguinte: f [ x0 ,..., xk ] f [ x j0 ,..., x jk ] Onde j0, ..., jk é qualquer permutação de 0, ..., k. Forma de Newton Forma de Newton para o polinômio interpolador: Seja uma função f(x) contínua e com tantas derivadas contínuas necessárias num intervalo [a,b]. Sejam a=x0<x1<...<xn=b Vamos construir o polinômio pn(x) que interpola f(x) em x0, ..., xn, construindo sucessivamente os polinômios pk(x), k=0,...,n Forma de Newton Para x[a,b], xx0 Temos: f ( x) f ( x0 ) f [ x0 , x] x x0 f ( x) f ( x0 ) ( x x0 ) f [ x0 , x] p0 ( x) E0 ( x) Podemos notar que E0(x) é o erro cometido aproximando f(x) por p0(x) Forma de Newton f [ x0 , x ] f [ x1 , x0 ] f [ x0 , x1 , x ] f [ x1 , x0 , x ] x x1 f ( x) f ( x0 ) ( x x0 ) f [ x1 , x0 ] ( x x0 )( x x1 ) f [ x0 , x1 , x ] P1 ( x) E1 ( x) Forma de Newton f [ x1 , x0 , x] f [ x2 , x1 , x0 ] f [ x0 , x1 , x2 , x] f [ x2 , x1 , x0 , x] x x2 f ( x) f ( x0 ) ( x x0 ) f [ x1 , x0 ] ( x x0 )( x x1 ) f [ x0 , x1 , x] P2 ( x) ( x x0 )( x x1 )( x x2 ) f [ x0 , x1 , x2 , x] E2 ( x) Forma de Newton Continuando assim para todos pk(x), temos pn(x)=f(x0)+(x-x0)f[x0,x1]+... +(x-x0)..(x-xn-1) f[x0,...,xn] O erro é dado por: En(x)=(x-x0)..(x-xn)f[x0,...,xn,x] Forma de Newton Considerando a tabela: x -1 f(x) 4 x -1 Ord 0 4 Ord 1 1 2/3 -1 2 -1 2 -1 Ord 2 -3 0 0 1 2 2 7 p3 ( x) x x 1 3 3 Estudo do erro A aproximar a função f(x) por um polinômio, comete-se um erro: En(x)=f(x)-pn(x) Estudo do erro Teorema: Sejam x0<...<xn, seja f(x) com derivadas até ordem (n+1) para x no intervalo [x0,xn]. Em qualquer ponto x do intervalo [x0,xn], o erro é dado por: f ( n1) ( x ) En ( x) ( x x0 )....( x xn ) , onde x [ x0 , xn ] (n 1)! Estudo do erro Do teorema precedente, podemos deduzir que: f ( n1) ( x ) f [ x0 , x1 ,..., xn , x] , x [ x0 , xn ], x [ x0 , xn ] Dois corolários: (n 1)! Se f(n+1)(x) é contínua em [x0,xn], En ( x) ( x x0 )....( x xn ) M n1 , M n 1 max ( f ( n1) ( x) ) x[ x 0, xn ] (n 1)! Se além disso, x1-x0=x2-x1=...=xn-xn-1=h hn1 En ( x) M n1 4(n 1) Estudo do erro Se a função é dada na forma de uma tabela, só podemos estimar o valor absoluto do erro. Mas a tabela de diferencias divididas é construída até ordem n+1, podemos usar o maior valor destas diferenças como aproximação para: M n1 (n 1)! Nesse caso, o valor do erro pode ser majorado com: En ( x) ( x x0 )...( x xn ) max(diferencias divididas de ordem n 1) Interpolação inversa Trata-se de, conhecendo um valor y de (f(x0),f(xn)), aproximar um valor de x tal que f(x)=y. Uma solução consiste em interpolar f(x) é em seguida resolver a equação f(x)=y. No caso de graus elevados (>2), a resolução da equação pode ser difícil e não temos avaliação do erro cometido. Uma outra solução consiste em efetuar uma interpolação inversa, ou seja determinar um polinômio interpolador de f-1(x). Com a interpolação inversa, podemos calcular uma avaliação do erro cometido. A interpolação inversa só poder ser feita com uma função monótona. Grau do polinômio Trata-se de determinar o grau do polinômio para interpolar uma função em um ponto: Deve-se construir a tabela de diferenças divididas. Se na vizinhança do ponto de interesse, as diferenças divididas de ordem k são praticamente constantes, podemos concluir que um polinômio de grau k é suficiente. Newton-Gregory No caso em que os x0,...,xn são igualmente espaçados, podemos usar a forma de Gregory-Newton. Diférenças ordinarias: Df(x)=f(x+h)-f(x) D2f(x)=Df(x+h)-Df(x) D3f(x)=D2f(x+h)-D2f(x).......... Newton-Gregory Podemos construir a tabela de diferenças ordinárias da mesma forma que a tabela de diferenças divididas. Teorema: x j x0 jh, j 0,1,..., n Se: n D Então: f [ x ,..., x ] f ( x0 ) 0 n n h n! Newton-Gregory No caso em que os x0,...,xn são igualmente espaçados, podemos escrever o polinômio interpolador: Df ( x0 ) D 2 f ( x0 ) pn ( x) f ( x0 ) ( x x0 ) ( x x0 )( x x1 ) 2 h 2h D n f ( x0 ) .......... ( x x0 )....( x xn 1 ) hn n ! Newton-Gregory Usando uma mudança de variáveis: s=(x-x0)/h Temos: (x-xj)=(s-j)h e pn(x)=f(x0)+sDf(x0)+s(s-1)D2f(x0)/2+...