Polinómio interpolador ➢ Dados n+1 pontos distintos x0, x1, ..., xn a que associamos valores funcionais y1, y2, ..., yn, pretende-se determinar um polinómio de grau menor ou igual a n, pn ( x) = a0 + a1 x + a2 x 2 + ... + an x n que interpole os dados, isto é tal que p n ( x i ) = f ( x i ) = y i , i = 0 ,1 ,..., n ➢ Ao conjunto dos pares (xi,yi), i=1,2,...,n chamamos suporte de interpolação. A nálise N um érica 29 Polinómio interpolador (cont) ➢ Exercício 2.1: Dada a seguinte tabela de uma função determine o seu polinómio interpolador usando a definição. A nálise N um érica i 0 1 2 3 xi -2 -1 0 1 yi -15 -1 1 3 30 Polinómio interpolador de Lagrange ➢ Teorema: (Lagrange) Seja Pn o conjunto dos polinómios de grau menor ou igual a n. Dados n+1 pontos suporte (xi,fi), i=0,1,...,n , existe um e um só polinómio pn ( x) ∈ Pn tal que pn ( xi ) = f i , i = 0,1,2,..., n , n pn ( x) = ∑ f i li ( x) i =0 (x − x j ) l ( x) = ∏ i j ≠ i ( xi − x j ) A nálise N um érica 31 Polinómio interpolador de Lagrange (cont) ➢ Exercício: Dada a tabela seguinte obtenha o polinómio interpolador de Lagrange. A nálise N um érica i 0 1 2 3 xi 1 2 3 4 yi 4 15 40 85 32 Erro de interpolação ➢ Erro de interpolação, num certo ponto x: en ( x) = f ( x) − pn ( x) ➢ Teorema : Seja f uma função real de variável real de classe Cn+1 no intervalo I x = [x , x0 , x1 ,..., xn ] ( I x designa o menor intervalo fechado que contém os pontos x0 , x1 ,..., xn , x ). Então existe um ξ ∈ Ix en ( x ) = f ( x ) − pn ( x ) = tal que ψ ( x ) ( n +1) (ξ ) com f (n + 1)! Fórmula para o erro de interpolação ψ ( x ) = ( x − x0 )( x − x1 )...( x − xn ) A nálise N um érica 33 Operadores de diferenças finitas ➢ A expressão do polinómio interpolador foi obtida considerando os polinómios de Lagrange li(x), i = 0,...,n, definidos sobre a partição. A determinação do polinómio interpolador de uma função usando as funções li(x) exige um grande esforço computacional e não permite obter o polinómio interpolador de grau n a partir do conhecimento do polinómio interpolador de grau n - 1. Estes dois factores levam-nos a considerar outro modo de obter o polinómio interpolador. ➢ Operadores de diferenças finitas: ● Diferenças descendentes (ou progressivas) ∆ ● Diferenças ascendentes (ou regressivas) ∇ (são utilizados quando os pontos xi de um suporte (xi, fi) são equidistantes.) ● Diferenças divididas (usa-se para pontos xi de um suporte (xi, fi) não equidistantes.) A nálise N um érica 34 Diferenças descendente e ascendentes ➢ Suporte (xi , fi) ∆ f(x ) = ∆ f i i = f (xi+1) - f (xi) e, de um modo geral, a diferença de ordem k (k ≥ 2) de f(x) para x = xi é dada por ( ) ∆k f (xi ) = ∆ ∆k −1 f (xi ) = ∆k −1 (∆f (xi )) = ∆k −1 f ( xi +1 ) − ∆k −1 f ( xi ) ∇ f(xi) = ∇ fi = f (xi) - f (xi-1) e, de um modo geral, a diferença de ordem k (k ≥ 2) de f(x) para x = xi é dada por ( ) ∇ k f (xi ) = ∇ ∇ k −1 f (xi ) = ∇ k −1 (∇f (xi )) = ∇ k −1 f ( xi ) − ∇ k −1 f ( xi −1 ) A nálise N um érica 35 Diferenças divididas ➢ Para uma função f (x) e um conjunto de pontos distintos {x0, x1,..., xn} temos: ● Diferença dividida de ordem 1 nos pontos {x0, x1} f [x 0 , x1 ] = ● f1 − f 0 x1 − x 2 Diferença dividida de ordem 2 nos pontos {x0, x1, x2} f [x 0 , x1 , x 3 ] = ● De um modo geral, usamos a notação D k f ( x i ) = f [x i , x i +1 ,..., x i + k ] para designar a diferença dividida de ordem k (k≥1) entre os (k +1) pontos {xi, xi+1,..., xi+k}, sendo D k f ( xi ) = A nálise N um érica f [x1 , x 2 ]− f [x 0 , x1 ] x2 − x0 D k −1 f ( x i + 1 ) − D k −1 f ( x i ) xi + k − xi 36 Tabela de diferenças divididas Para n = 3 xi x0 f (xi) f (x0) x1 f (x1) x2 f [.,.] f [.,.,.] f ( x1 ) − f ( x0 ) x1 − x0 f ( x2 ) − f ( x1 ) x2 − x1 f (x2) f ( x3 ) − f ( x2 ) x3 − x2 x3 f [.,.,.,.] f [ x1 , x2 ] − f [ x0 , x1 ] x2 − x0 f [x0,.,.x3] f [ x2 , x3 ] − f [ x1 , x2 ] x3 − x1 f (x3) A nálise N um érica 37 Tabela de diferenças divididas (cont) ➢ Exemplo: Considerar uma função da qual se conhecem os valores dados no seguinte quadro xi f (xi) 1 -1 5/4 0 3/2 2 2 3 5/2 1 Construir a tabela de diferenças divididas A nálise N um érica 38 Diferenças divididas e derivadas de f ➢ Lema: Para um suporte de pontos igualmente espaçados, de passo h (xi+1-xi = h , i =0,1,..., n-1), tem-se ∆k f i f [ xi , xi +1 ,..., xi + k ] = ,k ≥ 0 k! h k ➢ Teorema: Seja f ∈ C n [a,b]. Se {x0, x1, ..., xn} são n +1 pontos distintos de [a,b], então existe pelo menos um ∈ ]a,b[ tal que ξ f ( n ) (ξ ) f [ x0 , x1 ,..., xn ] = n! ➢ Teorema: Para f ∈ C n e um suporte de n +1 pontos, de passo h, existe pelo menos um ξ tal que ∆n f ( x) = h n f n (ξ ) A nálise N um érica 39 Polinómio interpolador de Newton nas diferenças divididas ➢ Suporte (xi, f i), i =0,1,...,n. pn ( x) = f 0 + ∑ f [ x0 ,..., xk ]( x − x0 )...( x − xk −1 ) Uma vez determinado o pn se pretendermos obter pn+1 basta fazer n pn +1 ( x) = pn ( x) + f [ x0 ,..., xn +1 ]∏ ( x − xi ) i =0 A nálise N um érica 40 Polinómio interpolador nas diferenças descendentes ∆ j f ( x0 ) j −1 ( x − xi ) pn ( x) = f ( x0 ) + ∑ ∏ j j!h i =0 j =1 n ➢ Efectuando a mudança de variável x → s definida por x =x0 +sh (s = (x - x0 )/h ∈IR+ ) ∆2 f 0 ∆n f 0 pn ( x) = f 0 + s∆f 0 + s( s − 1) + ... + s ( s − 1)( s − 2)( s − n + 1) 2! n! s s s pn ( x) = f 0 + ∆f 0 + ∆2 f 0 + ... + ∆n f 0 1 2 n s s ( j) = j! j e com s ( j ) = s ( s − 1 )( s − 2 )...( s − ( j − 1 )) A nálise N um érica 41 Erro de Interpolação ➢ Para o polinómio interpolador de Newton nas diferenças divididas: ● Se apenas conhecermos apenas o suporte (xi,f (xi )) en ( x ) = f ( x ) − pn ( x ) ≅ ψ ( x ) f [ x , x0 ,..., xn ] ● Ou se conhecemos também f(x) en ( x) ≤ A nálise N um érica ( x − x0 )...( x − xn ) (n + 1)! max f ( n +1) ( x) x0 ≤ x ≤ x n 42 Erro de interpolação ➢ Paro o polinómio interpolador de Newton nas diferenças descendentes s n +1 ∆ f 0 en ( x) = n + 1 ou s n +1 ( n +1) h f (ξ ), x0 < ξ < xn en ( x) = n + 1 A nálise N um érica 43 Polinómio interpolador de Hermite ➢ Seja f uma função em que são conhecidos f (xi) e f ‘ (xi) para i =0,1,...,n. H 2 n +1 ( x) = f ( x0 ) + ( x − x0 ) f [ x0 , x0 ] + ( x − x0 ) 2 f [ x0 , x0 , x1 ] + + ( x − x0 ) 2 ( x − x1 ) f [ x0 , x0 , x1 , x1 ] + ... + + ( x − x0 ) 2 ( x − x1 ) 2 ...( x − xn −1 ) 2 ( x − xn ) f [ x0 , x0 ,..., xn , xn ] A nálise N um érica 44 Aproximação polinomial de mínimos quadrados Teoria da Aproximação A função é dada explicitamente, mas pretende-se aproxima-la por outra mais simples. (ajuste de funções) Dado um conjunto de pontos, pretende-se determinar a “melhor” função dentro de uma certa classe que possa ser usada para representar os dados. Se tivermos apenas os valores da função em certos pontos, não vamos exigir que a função “aproximadora “ interpole a função dada nos pontos. Exigimos apenas que essa função “aproximadora” tome valores (nesses pontos) de forma a minimizar a distância aos valores dados, no sentido dos mínimos quadrados. A nálise N um érica 45 Aproximação Polinomial de Mínimos Quadrados ➢ Modelo linear simples ➢ (xi, yi ), i =1,..., n ● y = ax + b (recta de regressão) a ∑ xi 2 + b∑ xi = ∑ xi yi a ∑ xi + bn = ∑ yi a= n∑ xi yi − ∑ xi ∑ yi b= A nálise N um érica n∑ xi − (∑ xi ) 2 2 ∑y i − a (∑ xi ) n 46 Aproximação Polinomial de Mínimos Quadrados Aproximar um conjunto de pontos (xi,yi) i=1,2,...,m por um polinómio de grau n (n≤ m-1), p n ( x ) = n ∑ k =0 a k x k , usando a técnica dos mínimos quadrados. m m m m m 0 1 2 n 0 + + + + = a x a x a x ... a x y i xi ∑ 1∑ i 2∑ i n∑ i 0∑ i i =1 i =1 i =1 i =1 i =1 m m m m m 1 2 3 n +1 1 a 0 ∑ xi + a1 ∑ xi + a 2 ∑ xi + ... + a n ∑ xi = ∑ y i xi i =1 i =1 i =1 i =1 i =1 ... m m m m m n n +1 n+ 2 2n n a 0 ∑ xi + a1 ∑ xi + a 2 ∑ xi + ... + a n ∑ xi = ∑ y i xi i =1 i =1 i =1 i =1 i =1 A nálise N um érica 47