Aula7: Interpolaopolinomial deLagrange7.1 InterpolaoSeja f uma funo real denida num conjunto de pontos x0, x1, . . . , xn. Pretende-se calcularo valor def(x), comx = xi,i = 0, 1, . . . , n. Tal situao muitofrequente,por exemplo,no contexto das equaes diferenciais. Quando se usam mtodos numricos para aproximara soluo de uma equao diferencial esta ca apenas conhecida num conjunto de pontos.A interpolao permite assim encontrar uma funo que passa por esse conjunto de pontose que pode funcionar como uma aproximao soluo da equao.Em linhas gerais, o conceito de interpolao consiste em determinar uma funo (x) =a00(x) + +ann(x), gerada por uma certa famlia de funes {k}nk=0, por forma a quef(xi) = (xi), i = 0, 1, . . . , n.A funo nestas condies designada por funo interpoladora de fnos pontos de suporte(interpolao)x0, x1, . . . , xn.Nada nos garante que o problema da interpolao tenha sempre soluo. Por exemplo,fazendo0(x)=1e1(x)=x2,noexistenenhumafuno(x)=a0 + a1x2quepassenos pontos(1, 1) e(1, 0).7.2 Interpolaopolinomial deLagrangeUmcasoparticular deinterpolaocomgrandeimportnciadevidoaograndenmerodeaplicaesainterpolaopolinomial. Almdisso, asfrmulasdesenvolvidasparaainterpolaopolinomial estonabasedodesenvolvimentodemuitosmtodosnumricosparaoclculoderazesdeequaesnolineares, clculodeintegraisederivadas, bemcomo a resoluo de equaes diferenciais.No caso da interpolao polinomial, as funes geradoras so, por exemplo, k(x) = xk,k= 0, 1, . . . , n.47InterpolaopolinomialdeLagrange 48Denio7.1Sejafumafunodenidanumintervalo [a, b]econhecidanospontosdapartioa = x0< x1< < xn1< xn= b. (7.1)UmpolinmioPquesatisfazf(xi) = P(xi), i = 0, 1, . . . , n, (7.2)chamadopolinmiointerpolador(deLagrange)defnospontosdapartiodada.Exerccio7.1Dadaatabelaxi2,3 2,4 2,5 2,6log xi0,361728 0,380211 0,397940 0,414973,determineovaloraproximadodelog 2,45,usandointerpolaopolinomial.Resoluo: Vamos calcular opolinmioP3de graumenor ouigual a 3, interpolador dey=log xnospontos2,3, 2,4, 2,5e2,6. DeacordocomadeniotemosP3(2,3)=0,361728, P3(2,4)=0,380211, P3(2,5)=0,397940, eP3(2,6)=0,414973. Isto, seP3(x) = a0 + a1x + a2x2+ a3x3,temosque___a0 + 2,3a1 + 5,29a2 + 12,167a3= 0,361728a0 + 2,4a1 + 5,76a2 + 13,824a3= 0,380211a0 + 2,5a1 + 6,25a2 + 15,625a3= 0,397940a0 + 2,6a1 + 6,76a2 + 17,576a3= 0,414973.Sendoosistemapossveledeterminadotalpolinmioexisteenico. AssimP3(x) = 0,404885 + 0,528963x 0,107300x2+ 0,009667x3opolinmiopretendido. Temosentoquelog 2,45 P3(2,45) = 0,389170. Compare-se este valor com o valor exacto log 2,45 = 0,38916608 . . .. Note-se que o erro cometidonaaproximaonoexcede0,4 105.A determinao do polinmio interpolador por este processo pouco ecientee poucoestvel. Quanto ecincia, note-se que a resoluo do sistema linear requer(n + 1)3/3 +(n+1)2(n+1)/3 multiplicaes/adies (O(n3) operaes). Para alm de pouco eciente,este processo tambm pouco estvel: na prtica verica-se que este mtodo no permiteir alm de valores den da ordem da dezena quando se trabalha em aritmtica com 6 ou 7decimais.InterpolaopolinomialdeLagrange 497.2.1 Existnciaeunicidade. FrmuladeLagrangeOmtododedeterminar umpolinmiointerpolador usadonoexerccioanterior noeciente nem estvel. Apresentaremos, neste captulo, alguns mtodos mais ecientes paraa sua determinao.O prximo teorema, devido a Joseph-Louis Lagrange (1736-1813), estabelece a existnciae unicidade do polinmio de grau inferior ou igual a n interpolador de uma funo em n+1pontos distintos. Alm disso, indica-nos um processo que permite a sua determinao.Teorema7.1(Lagrange) Sejaf umafunodenidanumintervalo[a, b] econhecidanospontosdapartio(7.1). ExisteumeumspolinmioPndegraumenorouigual aninterpoladordefnospontosdados.Demonstrao: Consideremos o polinmioPndenido porPn(x) =n

i=0f(xi)i(x), (7.3)em quei(x) =n

j=0,j=ix xjxixj, i = 1, . . . , n. (7.4)Notemos que cadai um polinmio de graun. Alm dissoi(xj) =_1 i = j0 i = j,isto i(xj) =i,jonde i,jrepresentaosmbolode Kronecker, emhonrade LeopoldKronecker(1823-1891). PortantoafunoPnumpolinmiodegraumenorouigual anquevericaascondiesdeinterpolao(7.2), oqueprovaaexistnciadesoluodoproblema em causa.Para provar a unicidade, suponhamos quePneQnso dois polinmios de grau menorou igual an interpoladores defnos pontos da partio dada. Ento o polinmioRn(x) = Pn(x) Qn(x)anula-se, pelomenos, nospontosxi, i =0, 1, . . . , n. ComoRnumpolinmiodegraumenorouigualan, elespodetern + 1zerosseforidenticamentenulo. Assimsendo,Pn(x) = Qn(x), para todo ox, o que prova o pretendido.Asexpresses(7.3)e(7.4)denemafrmuladeLagrangeparacalcularopolinmiointerpolador defnos pontos (7.1).O resultado anterior diz-nos que por n+1 pontos passa um e um s polinmio de graun. Assimtemos que,se a funaofa interpolar for umpolinmio de graun coincidecomo seu polinmio interpolador do mesmo grau, podendo assim ser escrita na formaf(x) =n

i=0f(xi)i(x).InterpolaopolinomialdeLagrange 50Exerccio7.2Dadaatabelaxi1 2 3 4f(xi) 4 15 40 85,determineumaaproximaoparaf(1.5), usandointerpolaocbica.Resoluo: Temosque0(x) =(x 2)(x 3)(x 4)(1)(2)(3)= 16(x 2)(x 3)(x 4)1(x) =(x 1)(x 3)(x 4)(1)(1)(2)=12(x 1)(x 3)(x 4)2(x) =(x 1)(x 2)(x 4)(2)(1)(1)= 12(x 1)(x 2)(x 4)3(x) =(x 1)(x 2)(x 3)(3)(2)(1)=16(x 1)(x 2)(x 3).AssimP3(x) =3

i=0f(xi)i(x) = = 1 + x + x2+ x3.Atendendo frmula de Lagrange podemos construir o seguinte algoritmo para calcularovalor de Pn(x), sendo Pnopolinmiointerpolador de f nos n+1pontos distintosx0, x1, . . . , xn.Algoritmo7.1 FrmuladeLagrangeDados: xi,i = 0, 1, . . . , n ex;P:= 0;Parai de0 atn fazer := 1;Parajde0 atn fazerSej= i ento := (x xj)/(xixj);P:= P+ f(xi);Resultado: Pn(x) = P.InterpolaopolinomialdeLagrange 51Exerccio7.3MostrequefrmuladeLagrange podeserescritanaformaPn(x) =n

i=0f(xi)w(x)(x xi)w(xi), (7.5)sendow(x) =n

j=0(x xj). (7.6)Resoluo: Atendendoa(7.6)temosquew(x) =n

i=1n

j=1,j=i(x xj) w(xi) =n

j=1,j=i(xixj),ecomotali(x) =w(x)(x xi)w(xi),oqueprovaopretendido.Paradeterminaro esforocomputacionalnecessrio obtenodopolinmio interpo-lador pela frmula de Lagrange, note-se que, supondo as constantesFi=f(xi)w(xi), i = 0, . . . , n,calculadasapriori, o clculodovalor dopolinmio interpoladornumdeterminadopontopode ser dado porPn(x) = w(x)_F0x x0+ +Fnx xn_.Esteclculo requern(n + 1) multiplicaesen(n + 2) adies,isto ,O(n2) operaes, oque torna a frmula de Lagrange muito mais eciente que o processo matricial.AfrmuladeLagrangepossui, noentanto, oinconveniente deobrigar arefazer osclculos dos polinmios (7.4) sempre que ocorra uma alterao nos pontos de suporte. Naprticaestasituaoacontececomfrequncia, porexemplo, quandopretendemospassardepnapn+1, pelaadiodemaisumpontoxn+1aosuportedeinterpolao, amdeestudarocomportamentodoerro. EsteproblemaresolvidopeloalgoritmodeNewtondas diferenas divididas, que no ser objecto de estudo nesta disciplina.7.2.2 ErrodeinterpolaoPor denio, o polinmio interpolador coincide com a funo num dado conjunto de pontosde suporte. Interessa-nos saber, no entanto, se para os outros pontos do domnio da funo,o polinmio interpolador constitui uma boa ou uma m aproximao para a funo. Nessesentido temos o seguinte teorema, que apresentamos sem demonstrao.InterpolaopolinomialdeLagrange 52Teorema7.2SejaPnopolinmiodegraumenorouigual aninterpoladordafunofnospontosdapartio(7.1). Sef Cn([a, b])esef(n+1)forcontnuaem]a, b[, entoparacadax [a, b]existe= (x) ]a, b[tal quee(x) = f(x) Pn(x) =f(n+1)()(n + 1)!w(x), (7.7)ondew(x)afunodadapor(7.6).Na prtica, o erro de interpolao num pontox usado na forma|e(x)| = |f(x) Pn(x)| Mn+1(n + 1)!|w(x)|, (7.8)ondeMn+1=maxx[a,b]f(n+1)(x).Note-seasemelhanaexistenteentreafrmuladoerronainterpolaoenafrmuladeTaylor. Adiferenaestque, enquantoaprimeirausainformaoemvriospontosdistintos, a segunda recorre apenas a um nico ponto.Exerccio7.4Determineumaestimativaparaoerroquesecometeunaaproximaoefec-tuadanoExerccio7.1.Resoluo: Nestecasotemos,atendendoa(7.8),|e3(x)| = | log x P3(x)| M44!|(x 2,3)(x 2,4)(x 2,5)(x 2,6)|,ondeM4= maxx[2,3,2,6]f(4)(x) = maxx[2,3,2,6]6x4ln10= 0,093116.Fazendox = 2,45vem| log 2,45 P3(2.45)| 0,09311624|(2,45 2,3)(2,45 2,4)(2,45 2,5)(2,45 2,6)|,ouseja|e3(2,45)|0,917 105.Exerccio7.5Considereafunof(x)=cos xparaxem[0, ]. Determineonmerodepontos a considerar no intervalo dado para que o erro mximo da aproximao de f(x) por umpolinmiointerpoladornessespontossejainferiora0,5.InterpolaopolinomialdeLagrange 53Resoluo: Temosque,parax [0, ],|f(x) Pn(x)| maxx[0,]f(n+1)(x)(n + 1)!|w(x)| =|w(x)|(n + 1)!

n+1(n + 1)!.Restaassimdeterminarqualomenorvalordenquesatisfazn+1(n + 1)! 0,5.Portentativas...n = 6 77!= 0,599n = 7 88!= 0,235.Logoomenornmerodepontosquegarantemaaproximaopretendidaso8.Exerccio7.6Seja fuma funo nas condies do teorema anterior e tal que (7.8) se verica.SejaPnoseupolinmiointerpoladornospontosdapartio(7.1).1. Mostrequeoseuerrodeinterpolaoverica|f(x) Pn(x)| Mn+14(n + 1)hn+1, x [a, b], (7.9)comh = maxi=1,...,n(xixi1).2. Mostrequeseapartio(7.1)foruniformesetem|f(x) Pn(x)| Mn+14(n + 1)nn+1(b a)n+1, x [a, b].Resoluo: Vamosapenasdemonstrar(7.9). Paratal,bastaprovarquemaxx[a,b]|w(x)| hn+1n!4,comwafunonodal(7.6). Vamosefectuarademonstraoporinduo.Paran = 1temosquew(x) = (x x0)(x x1). Assim,temosquew(x) = 0 x =x0 + x12.Comotal,maxx[a,b]|w(x)| = max_|w(a)|,w_x0 + x12_, |w(b)|_ =w_x0 + x12_

h24.InterpolaopolinomialdeLagrange 54Suponhamos que (7.9) se vericaparan e provemos asua veracidade para n +1, isto,quemaxx[a,b]n+1

j=0(x xj)

hn+2(n + 1)!4,coma =x0e xn+1=b. Dadox[a, b] temos que x[a, xn] oux[xn, b].Consideremosaprimeirahiptese. Temosentomaxx[a,b]n+1

j=0(x xj) =maxx[a,b]n

j=0(x xj)|x b| hn+1n!4(n + 1)h =hn+2(n + 1)!4,oqueprovaopretendido. Ocasoemqueseconsideraasegundahiptesedemonstra-sedeformaanloga.Consideremosumafunofdenidanumintervalo[a, b]ondeestdenidaumapar-tiouniforme(7.1)esejaPnoseupolinmiointerpoladordeLagrange. Provmos, noexerccio anterior, quemaxx[a,b]|f(x) Pn(x)| Mn+14(n + 1)nn+1(b a)n+1,para todo ox [a, b]. Se existir uma constante positivaMtal queMn+1 M, n N, (7.10)conclumos quelimn+_maxx[a,b]|f(x) Pn(x)|_ limn+_M4(n + 1)nn+1(b a)n+1_ = 0.Neste caso, o processo de interpolao convergente, isto , o aumento do grau do polinmioimplica um aumento de preciso.Noentantoexistemfunesparaasquaisnopodemosconcluirqueumaumentodograudoprovocaumaumentodaproximidadedopolinmiointerpoladorcomafunointerpolada. Issoacontecequandonopossvel encontrarummajorante(7.10)paraasderivadas da funo. Um exemplo que ilustra esta situao foi considerado por Carle DavidTolmRunge (1856-1927), em 1901, e o apresentado no exerccioseguinte.Exerccio7.7Considereafuno(deRunge)f(x)=1/(1 + 25x2), x[1, 1]. Veriquegracamentequemaxx[1,1]|f(x) P3(x)|maxx[1,1]|f(x) P8(x)| ,emqueP3eP8so,respectivamente,ospolinmios deLagrange degrau3e8interpoladoresdefempartiesuniformesde[1, 1].InterpolaopolinomialdeLagrange 557.3 ExercciosdeaplicaoengenhariaExerccio7.8Conhecem-seascoordenadasdecincopontosdeumacurvaplanaquerepre-sentaumaregiodeumapeaemcorte. DetermineopolinmiodeLagrangedegrau4queinterpolaareferidacurvasabendoqueospontosdecoordenadasconhecidasso: P1= (1, 2),P2=(2, 1), P3=(3, 1), P4=(4, 2.5)eP5=(5, 4). Determineaindavaloresaproximadosparaasordenadasdospontoscujasabcissasso0,2,5e6.Exerccio7.9Naseguintetabelasodadosdiferentesvaloresparaopesoespeccopdaguaadiferentestemperaturast(emgrauscentgados):t 0 1 2 3p 0,999871 0,999928 0,999969 0,999991.Usandointerpolaolinear, quadrticaecbica, determineumaaproximaoparapquandot = 4oC. Compareosresultadosobtidossabendoqueovalorexacto1,000000.Exerccio7.10Durante a sedimentao da reaco de saponicao entre quantidades equi-molares de hidrxidode sdioe acetatode etilo, aconcentraoc (gmole/litro) de cadareagentevariacomotempot(min)deacordocomaequao1c=1c0+ kt,onde c0 a concentrao inicial e k (litro/g mole min) a constante de reaco. Foram obtidososseguintesresultadosemlaboratriotemperaturade77oF:1/c 24,7 32,4 38,4 45,0 52,3 65,6 87,6 102 154 192t 1 2 3 4 5 7 10 12 20 25.1. Obtenhaumaestimativaparaaconcentraoinicial.2. Obtenhaumaestimativaparaaconcentraoaomde15minutosecompare-acomasoluoobtidaemlaboratrio(aomde15minutosobteve-se1/c = 135).Exerccio7.11OcensodapopulaodosEstadosUnidos, entre1930e1980, produziuosseguintesresultados:Ano 1930 1940 1950 1960 1970 1980Populao(103) 123203 131669 150697 179323 203212 226505.Use umpolinmiointerpolador apropriadoparaestimar apopulaonos anos de 1920,1965, e 2000. Sabendo que a populao no ano de 1920 era de 105711103, o que pode inferirquantoprecisodasaproximaesobtidasparaosanosde1965e2000?InterpolaopolinomialdeLagrange 56Exerccio7.12Determine uma aproximao para o instante da passagem do perigeu da LuaemMaro,1999,apartirdosvalorestabeladosparaaszerohorasdecadadiadia 19 20 21distncia 57,071 56,955 57,059.Indiquetambmadistncia(emraiosmdiosdaTerra)daTerraLuanesseinstante.Exerccio7.13Usandointerpolaocbicalivre, determineumaaproximaoparaadecli-nao aparente de Vnus para o dia 9 de Maio de 1999, s 18h30m45s, a partir das EfemridesAstronmicas(ondeesttabeladaparacadadia,szerohoras)dia 7 8 9 10i+5o5147,55 +6o2225,20 +6o5254,57 +6o2314,96.Apartir dafunoobtida, determineumaaproximaoparaoinstanteemqueadeclinaoaparentedeVnusnodia9deMaiode1999foimxima.Aula8: InterpolaodeChebyshev,trigonomtricaeFFT8.1 InterpolaodeChebyshevUmaquestointeressanteconsisteemsabercomodiminuiroserrodeinterpolaosemaumentaronmerodepontosdesuporte. Afrmula(7.8) mostraqueoerrodeinterpo-laodependetanto domximode|f(n+1)(x)|,para todo ox pertencenteao intervalodeinterpolao, como demaxx[a,b]|w(x)| (8.1)(que depende da escolha dos pontos de interpolao). A questo interessante est em saber,para um dado n, qual a escolha dos pontos de interpolao que minimiza (8.1). A respostapode ser dada custa dos chamadospolinmiosdeChebyshev.Paran=0, 1, 2, . . . ex[1, 1]ospolinmios deChebyshevdagraunsodenidospela relaoTn(x) = cos (narccos x).Uma forma simples de provar queTn, de facto, um polinmio, atendendo frmula derecorrncia (ver Exerccio 8.1)Tn+1(x) = 2xTn(x) Tn1(x), n = 1, 2, . . . . (8.2)Exerccio8.1Obtenhaafrmulade recorrncia(8.2) e concluaque Tn, de facto, umpolinmio.Exerccio8.2MostrequeopolinmiodeChebyshevTntemosseuszeroslocalizadosnospontos xk= cos(2k1)2n, k = 1, . . . , n, e os extremos localizados em xk= coskn , k= 0, . . . , n,nosquaisTn(xk) = (1)k.Da denio de polinmio de Chebyshev resulta imediatamente que|Tn(x)|1,n = 0, 1, 2, . . .. Assim sendo, comoTn(1) = 1, temos quemaxx[1,1]|Tn(x)| =1. Almdisso, atendendoaoExerccio8.2, oszerosdospolinmiosdeChebyshevestotodos no intervalo[1, 1]. fcil provar que o coeciente do termo de maior grau de Tn an= 2n1. Assim sendo,o polinmio Tn:= 21nTn mnico, isto , o seu coeciente do termo de maior grau igual57ZerosdospolinmiosdeChebyshev, interpolaotrigonomtricaeFFT 58unidade. Designemospor Pn([a, b])aclassedospolinmiosmnicosdegraumenorouigual an em[a, b].Teorema8.1Opolinmio Tndetodosospolinmiosde Pn([1, 1])oquetemmenornorma,isto,maxx[1,1]|Tn(x)|maxx[1,1]|P(x)|, P Pn([1, 1]).Demonstrao(nofoidada): Sabemos quemaxx[1,1]|Tn(x)| = 21n. Suponhamosqueexiste P Pn([1, 1])tal quemaxx[1,1]|P(x)|