Interpolação: Método de Lagrange e Método de Newton

1 Interpolação Parte 2 Método de Lagrange Método de Newton Este método será apresentado inicialmente a partir de um caso de interpolação de ordem 2 e na sequencia será ampliado para casos de maior ordem P2x a0 a1 x a2 x2 tal que P2xi yi i 0 n Polinômio interpolador de Lagrange Consequentemente P2 x tem grau 2 x x0 x1 x2 fx y0 y1 y2 Dados três pontos distintos x0 y0 x1 y1 x2 y2 Então n2 Forma do polinômio interpolador A fórmula de Lagrange para encontrar tal polinômio é a seguinte P2x y0L0x y1L1x y2L2x 1 As funções L0x L1x e L2x são chamadas de funções de base de Lagrange e tem grau 2 Além de serem polinômios de grau 2 essas funções são definidas de modo que Onde i j 0 1 2 1 2 3 2 O polinômio 1 interpola os dados Verificação P2x y0L0x y1L1x y2L2x 1 Para um conjunto de n1 dados xi fxi o polinômio interpolador Px que passa por todos os pontos conhecidos é Forma geral do método de Lagrange Aonde Lkx são polinômios de grau n tais que L x k i ki sendo que ki se k i se k i 0 1 1 1 0 0 n n n L x f x L x f x L x f x P x Para o ponto x0 temse p x L x f x L x f x L x f x p x f x f x f x p x f x n n n 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 De forma análoga para o ponto x1 temse p x L x f x L x f x L x f x p x f x f x f x p x f x n n n 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 Ou seja p x f x i i px então passa sobre os pontos xifxi 4 5 6 3 Uma forma de construir os polinômios Lkx pode ser L x e L x se i k k k k i 1 0 Note que p x L x f x n i i i n 0 L x x x x x i j jj i n i j jj i n 0 0 Forma de Lagrange Compacta Interpolação para 2 pontos xi x0 x1 f xi f x0 f x1 1 1 0 0 1 L x f x L x f x P x 1 0 x L x L n12 n1 Então Interpolação Linear As funções Li x devem satisfazer L0 x0 1 L0 x1 0 L1 x0 0 L1 x1 1 As funções abaixo satisfazem estas condições 1 0 1 0 x x x x x L 0 1 0 1 x x x x x L e Finalmente temos 1 0 1 0 0 1 0 1 f x x x x x f x x x x x p x 1 1 0 0 1 L x f x L x f x P x 7 8 9 4 Exemplo Ajuste com uma reta n2 1 0 1 0 0 1 0 1 1 x f x x x x x f x x x x P x 2 82 4 1 55 65 2 4 2 13 4 2 4 1 x x x x x P 60 1 25 1 x x P x 2 4 fx 31 56 1 1 0 0 1 L x f x L x f x P x clear close all clc x2 4 y31 56 plotxybo Plota gráfico com dados iniciais axis0 6 0 8 ylabelyxlabelx titleInterpolacao Lagrange grid x10016 P1x125x106 hold on plotx1P1xr 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 y x Interpolacao Lagrange Ordem 1 Interpolação para 3 pontos xi x0 x1 x2 fxi fx0 fx1 fx2 2 2 1 1 0 0 2 0 2 f x L f x L f x L f x L x p i i i 2 1 0 x L x L x L Para n2 Interpolação quadrática 10 11 12 5 Para n2 interpolação parabólica as funções Li x devem satisfazer As funções a seguir satisfazem as condições acima L0 x0 1 L1 x0 0 L2 x0 0 L0 x1 0 L1 x1 1 L2 x1 0 L0 x2 0 L1 x2 0 L2 x2 1 2 0 1 0 2 1 0 x x x x x x x x L 2 1 0 1 2 0 1 x x x x x x x x L 1 2 0 2 1 0 2 x x x x x x x x L 2 1 2 0 2 1 0 1 2 1 0 1 2 0 0 2 0 1 0 2 1 x f x x x x x x x x x f x x x x x x x x x f x x x x x x x x p x Então Seja a tabela 2 2 1 1 0 0 2 0 2 x y L y L x x y L x y L x p k k k x 1 0 2 fx 4 1 1 3 2 2 1 0 1 2 0 2 2 0 1 0 2 1 0 x x x x x x x x x x x x x L 2 2 2 1 0 0 2 1 2 2 1 0 1 2 0 1 x x x x x x x x x x x x x L 6 0 1 2 2 0 1 2 1 2 0 2 1 0 2 x x x x x x x x x x x x x L Devemos interpolar os 3 pontos com uma forma de Lagrange parabólica 2 1 0 1 2 3 4 2 1 0 1 2 3 4 5 6 y x Interpolacao Lagrange Ordem 1 Enfim a forma de Lagrange da interpolação 6 1 2 2 1 3 2 4 2 2 2 2 x x x x x x x p 2 2 3 2 3 7 1 x x x p x1 0 2 y4 1 1 plotxybo axis2 4 2 6 Plota os dados iniciais ylabelyxlabelx titleInterpolacao Lagrange Ordem 1 grid x12014 P1x173x123x12 hold on plotx1P1xr Observase que este resultado é o mesmo que com a resolução do sistema linear 13 14 15 6 Entradas número de dados conhecidos n vetores x e y de dados valor a ser interpolado z Algoritmo de Lagrange Exercício A tabela informa o número de carros x mil que passam por um determinado pedágio em um determinado dia a Faça um gráfico de horário vs número de carros para verificar qual a tendência da curva b Estime o número de carros que passariam pelo pedágio às 1110 usando a forma de Lagrange para encontrar um polinômio interpolador px que estima o número de carros em função do tempo b1 Use uma reta como função interpoladora b2 Use uma parábola como polinômio interpolador Horário 1000 1030 1100 1130 1200 1230 No Carros 269 164 109 104 149 244 Metodo de Interpolação de Lagrange clearclose all clc h1005125 ncar269 164 109 104 149 244 plothncarb axis9 13 0 35 ylabelx1000carros xlabelhora title Pedágio nlengthh zinput Entre com o hora em que vc deseja saber o número de carros r0 for i1n c1 d1 for j1n atenção índices programa X teoria if ij cczhj ddhihj end end rrncaricd end fprintf Número de carrosx1000 86f r grid hold on plotzrbs 16 17 18 7 Problema de quantidade de carros que passa pelo pedagio pelo Metodo de Lagrange Metodo de interpolacao polinomial utilizando as funcoes de lagrange Lx PnxL0xY0L1xY1 LnxYn Para facilitar o processo numerico o calculo é feito caonsiderando xz hora de interesse Observacao Na teoria os vetores X e Y iniciam na posicao zero01 n Computacionalmente sao 1 2 n1 clearclose all clc Entrada de dados X1005125 Vetor X0 X1 Xn horas Ncar269 164 109 104 149 244 Vetor FXy0 y1 yn plotXNcarb axis9 13 0 35 ylabelx1000carros xlabelhora title Pedágio nlengthX z inputEntre com a hora em que vc deseja saber o número de carros que passam pelo pedagio Montagem do Pnx e calculo de rPnZ Funcoes de lagrande LzjNumzDenz PzPnz SUMNcariLzj Pz0 Inicializa a resposta Pnz0 Sucessivamente serão adicionados os termos NcariLzj for i1n Num1 Inicializacao numerador Den1 Inicializacao denominador for j1n if ij NumNumzXj DenDenXiXj end end PzPzNcariNumDen Acumula termo YiLi em end Resultados obtidos fprintf Número de carrosx1000 106f Pz grid hold on plotzPzrLineWidth2 MarkerSize10 MarkerEdgeColorr MarkerFaceColor020505 O algoritmo executa um total de operações aritméticas na ordem de n2 A complexidade computacional é menor do que resolver um sistema de equações lineares On3 Embora simples avaliar um novo ponto z é computacionalmente custoso na Forma de Lagrange para o polinômio interpolador Observações sobre o Método de Lagrange Polinômio interpolador de Newton A forma de Newton para o polinômio pnx que interpola fx em n1 pontos distintos x0 x1 xn é a seguinte 1 1 0 1 0 2 0 1 0 n n n x x x x x x d x x x x d x d x d x p xi x0 x1 xn fxi fx0 fx1 fxn No Método de Newton os valores de dk são obtidos por técnicas de diferenças divididas de ordem k Dados 19 20 21 8 Operador Diferenças Divididas dk Seja fx definida em n1 pontos distintos x0 x1 xn O operador diferenças divididas é dado por 0 0 0 f x f x d 0 1 0 1 0 1 0 1 1 0 1 x x f x x f x x f x f x x f x d 0 3 2 1 0 3 2 1 3 2 1 0 3 x x x x f x x f x x x x x f x d 0 1 2 1 0 2 1 2 1 0 x x x x x f x x f x x x x x f x d n n n n n 0 2 1 0 2 1 2 1 0 2 x x x f x f x x x x f x d Ordem 0 1 2 3 n Operador de diferenças divididas É possível verificar que há semelhança entre as diferenças divididas e a derivada da função fx Pelo Teorema do Valor Médio Valido para algum c a b Assim pode se demostrar que f c a b f a f b x f a b f f c a b f Diferenças divididas secante entre os pontos A e B Seja fx cosx e os pontos x0 02 e x1 03 Cálculo da diferença dividida de ordem 1 de fx nos pontos x0 e x1 Sendo f x senx e tomando x 025 verificase que f025 sen025 02474 Ou seja neste caso Verificação numérica da primeira derivada de fx por diferenças divididas 22 23 24 9 Forma de Newton Operador Diferenças Divididas Construímos a tabela de diferenças divididas 0 0 f x f x x Ordem 0 Ordem 1 Ordem 2 Ordem n x0 x1 x2 xn x0 x1 f x1 x2 f 2 1 0 x x x f 0x f 1x f 2x f nx f x2 x3 f 1 n n x x f 3 2 1 x x x f 1 0 nx x x f xi x0 x1 xn fxi fx0 fx1 fxn Dados Então mostrase que a forma de Newton para o polinômio de ordem n que interpola fx é 2 1 0 kx x x x f 0 1 1 0 f x x x f x 2 0 1 2 1 0 x f x x x x x f 2 1 0 1 1 0 2 1 0 1 0 1 0 0 0 n n n x x x f x x x x x x x x x f x x x x x x f x x x f x x p é simétrica nos argumentos ou seja EXEMPLO Usando a forma de Newton defina o polinômio P2x que interpola fx nos pontos dados x 1 0 2 fx 4 1 1 2 1 0 1 0 1 0 0 0 2 f x x x x x x x f x x x x f x P x 02 3 1 1 3 4 2 x x x x P x Ordem 0 Ordem 1 Ordem 2 1 4 3 0 1 23 1 2 1 2 2 3 2 3 7 1 x x P x 25 26 27 10 x Ordem 0 Ordem 1 Ordem 2 Ord3 Ordem 4 1 Fx01 Fx0x10 0 1 Fx0x1x212 1 16 1 0 0 124 1 0 2 1 0 1 3 2 Exemplo Sejam os dados Tabela de diferenças divididas de Newton x 1 0 1 2 3 fx 1 1 0 1 2 2 1 24 1 0 1 1 1 6 0 1 0 1 2 1 1 0 1 4 x x x x x x x x x x x p 2 1 1 1 24 1 1 1 6 1 1 1 2 4 x x x x x x x x x x p 4 3 2 1 0 4 3 2 1 0 3 2 1 0 3 2 1 0 2 1 0 1 0 1 0 0 0 4 f x x x x x x x x x x x x x x x f x x x x x x x x x x x x f x x x x x x x f x x x x f x x p A forma de Newton que interpola estes pontos é dada por x 1 0 1 2 3 fx 1 1 0 1 2 n4 p4 x Entrada número de pontos n vetores x e y de dados Forma de Newton Algoritmo para identificação dos coeficientes di 28 29 30 11 Funções para interpolação disponíveis no MATLAB Polinômio com as raízes especificada Função polyr Encontra os coeficientes de um polinômio r vetor com as raízes de um polinômio Raiz de polinômio Função roots a Calcula as raízes de um polinômio em forma de um vetor coluna a coeficientes do polinômio p polyfitxy3 x 1 2 3 4 5 y 55 431 128 2907 4984 EXAMPLE Consider the xy test data A third degree polynomial that approximately fits the data is p 01917 315821 603262 353400 Compute the values of the polyfit estimate over a finer range and plot the estimate over the real data values for comparison x2 115 y2 polyvalpx2 polyval ax avalia o valor de um polinômio de grau n a um valor específico x2 plotxyox2y2 grid on x and y are vectors containing the x and y data to be fitted and n is the degree of the polynomial to return Curvas Spline para Interpolação Quando polinômios de grau muito alto são necessários para interpolar uma função amostrada em um dado conjunto de pontos erros numéricos são mais prováveis Como alternativa em vez de um só polinômio usase vários polinômios um para cada par de dados consecutivos ajustando se os coeficientes de forma a permitir uma transição suave de um polinômio para outro garantindo continuidade sempre que possível 31 32 33 12 Função splinexyxi Encontra os polinômios interpoladores dados os pontos com coordenadas em x y e calcula o valor da spline no ponto xi As splines se tornam excelentes curvas interpoladoras devido ao fato de serem bastante suaves e além disso são bastante viáveis computacionalmente porque não exigem a resolução de sistemas lineares muito grandes e também evitam certas oscilações indesejadas Spline cúbico dados de interpolação Exemplo x 0 10 Intervalo de pontos y sinx Curva senoidal calculado nos pontos x xx 0 025 10 Intervalo de uma malha fina yy splinexyxx cálculo da curva spline nos pontos da malha plotxyoxxyy plota os pontos do spline nos pontos da malha httpwwwmathworkscomhelpcurvefitexampleshowto constructsplineshtml Construir curvas Spline how to construct splines in various ways using the spline functions in Curve Fitting Toolbox Exemplo Predicting US population t 1900101990 p 75995 91972 105711 123203 131669 150697 179323 203212 226505 249633 xx 19001990 yy splinetpxx plottpoxxyy P2000splinetp2000 hold on plot2000P2000bs grid Ver no help do MATLAB Predicting the US Population 34 35 36