Prévia do material em texto
Métodos Numéricos Interpolação / Aproximação Renato S. Silva, Regina C. Almeida Interpolação / Aproximação situação: uma fábrica despeja dejetos no leito de um rio; objetivo: determinar a quantidade de dejetos expelidos durante o dia; metodologia idealizada: fazer a coleta de amostra a cada hora; realizado: após muitas tentativas, apenas 4 tiveram sucesso hora quantidade de poluentes (Kg/hora) 08:00 2 10:00 3 13:00 4 17:00 1 Como estimar o que se deseja dos dados observados? Geoma/03 – p.1/41 Exemplo: despejo de poluente Tentar extrair dos dados coletados alguma indicação sobre a função que descreve a taxa de mudança na quantidade de poluição ao longo do dia buscar alguma informação sobre a integral - quantidade de poluentes ao dia reescrevendo os dados de outra maneira, com o tempo medido a partir do horário de início de funcionamento da fábrica número de horas quantidade de poluentes após as 08:00h (Kg/hora) 0 2 2 3 5 4 9 1 Geoma/03 – p.2/41 Exemplo: despejo de poluente Representação gráfica das medidas: Geoma/03 – p.3/41 Exemplo: despejo de poluente Para preencher as lacunas nos dados, admite-se que os valores de uma medida são constantes até a seguinte: Geoma/03 – p.4/41 Exemplo: despejo de poluente Alternativamente, admite-se variação linear entre os valores coletados: Geoma/03 – p.5/41 Exemplo: despejo de poluente E se supormos que o despejo ocorre de forma contínua e suave? F � � � � � � � � � � � � � � � � � � � � � � � � Interpolação Polinomial (linear, Lagrange, diferenças divididas) Splines Aproximação Série de Taylor Mínimos Quadrados Geoma/03 – p.6/41 Interpolação Polinomial calcular um polinômio � que de algum modo aproxima � em um intervalo � � � � � são dados � pontos distintos no plano � � � � � � � � � � � � � � � � � � � � � � � � � � deseja-se determinar um polinômio � que interpola estes pontos, isto é, satisfaz � � � � � � � � � � � � � � � � � � � tem grau � � � � Geoma/03 – p.7/41 Interpolação Polinomial Exemplo: despejo de poluentes com � dados: � � número de horas quantidade de poluentes após as 08:00h (Kg/hora) 0 2 2 3 5 4 9 1 � � � � � � � � � � � � � � � � � � � � Polinômio interpolador (grau � � ) � � � � � � � � � � � � � � � � � � � � � significa obter os oeficientes � � � � � � � � e � � Geoma/03 – p.8/41 Interpolação Polinomial se � � � � � � � � � � � � � � � então � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � sistema de 4 equações lineares em � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.9/41 Interpolação Polinomial pode ser resolvido usando o método de eliminação de Gauss � é único encontrar meio mais simples e barato de determiná-lo Geoma/03 – p.10/41 Interpolação por Polinômios de Lagrange novamente considere � � considere 4 polinômios especiais de grau 3 (Polinômios de Lagrange): � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � satisfazem por construção � � � � � � � e � � � � � � � � � � � � � Geoma/03 – p.11/41 Interpolação por Polinômios de Lagrange Fazendo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Tem duas propriedades: é um polinômio de grau � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � é o polinômio interpolante desejado não é necessário resolver sistema de equações custo decorre da determinação dos polinômios de Lagrange Geoma/03 – p.12/41 Forma de Diferenças Divididas de Newton O polinômio interpolante é � � � � � � � �� � � � � � � � � � � , onde � � são: � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ... � � � � � � � � �� � � � � � � � � � note que � � � � � � � � se � � � Geoma/03 – p.13/41 Forma de Diferenças Divididas de Newton Com � � � � � � � � se � � � � obtém-se � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � então o sistema de equações é: � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.14/41 Forma de Diferenças Divididas de Newton Resolvendo por substituição: � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ... os coeficientes recebem uma denominação especial: � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � é a diferença dividida de � em � � � � � � � � � � � � Geoma/03 – p.15/41 Forma de Diferenças Divididas de Newton o polinômio que interpola � em � � � � � � � � é � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.16/41 Forma de Diferenças Divididas de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.17/41 Forma de Diferenças Divididas de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.18/41 Forma de Diferenças Divididas de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados 2+x/2-x*(x-2)/30-17*x*(x-2)*(x-5)/1260 Geoma/03 – p.19/41 Forma de Diferenças Divididas de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � �� � � � � � � � � � � entre � � e � � � � � � � � � � � � entre � � e � � � � � � � � � � � � � � entre � � e � � � � � � � � � � � � � � � � Geoma/03 – p.20/41 Forma de Diferenças Divididas de Newtonentre � � e � � � � � � � � � � � � entre � � e � � � � � � � � � � � � � � entre � � e � � � � � � � � � � � � � � � � 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados 2+x/2 3+(x-2)/3 4-3*(x-5)/4 Geoma/03 – p.21/41 Interpolante Linear por Partes 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados linear por partes nenhuma restrição de continuidade imposta sobre � ou sobre suas derivadas entre os sub-intervalos Geoma/03 – p.22/41 Erro de Interpolação Teorema do erro para aproximação polinomial: Seja � o polinômio (único) de grau � que interpola � em � � � � � � � � � � é uma função definida num intervalo � � � � que contém os � � � pontos. Se � é � � � � vezes continuamente diferenciável em � � � � , então para � � � � � � o erro é dado por � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.23/41 Interpolação Usando Splines exige-se certa regularidade do interpolante na interface entre os sub-intervalos SPLINES: polinômios de ordem � que interpolam os dados e têm � � � derivadas contínuas em todo o intervalo o spline deve passar nos nós o spline não forma ângulos agudos spline cúbica ( � � �) é a mais comum Geoma/03 – p.24/41 Interpolação Usando Spline Cúbica 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados primeiro intervalo segundo intervalo terceiro intervalo Geoma/03 – p.25/41 Aproximação se conhece a função mais ela é muito complicada se tem um conjunto de dados aproximar por funções simples ou polinômios � � quão boa é a aproximação? aproximações para um conjunto de dados Geoma/03 – p.26/41 Aproximação dados � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � são determinados por um sistema linear � � � � � � � � dependem da natureza dos dados em geral � é muito menor que � Geoma/03 – p.27/41 Aproximação qualidade da aproximação � erro erro ou resíduo � � � � � � � � � � � � � � � � � método dos mínimos quadrados � � � � � �� � é minimizado Geoma/03 – p.28/41 Aproximação Seja o conjunto de dados � � � � � � � � � � � � A função � que melhor se ajusta, no sentido de mínimos quadrados, é a função cujos parâmetros � � são determinados de modo que a soma dos quadrados dos resíduos seja mínima Geoma/03 – p.29/41 Aproximação por Mínimos Quadrados Seja � dado por � � � � � � �� � � � � � � � � � � � � � � � reescrito como � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � passará por um mínimo quando as � derivadas parciais se anularem simultaneamente, ie, � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.30/41 Aproximação por Mínimos Quadrados Como � � � � � � � � � � � � � � � � � � � � � reescrevemos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � sistema de � equações com incógnitas � � � � � � � � Geoma/03 – p.31/41 Aproximação por Mínimos Quadrados Ajuste Polinomial: � � � � � � � Ajuste a uma reta - Regressão Linear Dados � � � � � � � � � � � procura-se a reta � � � � � � � � � � que melhor se ajusta aos dados Geoma/03 – p.32/41 Regressão Linear � � � � � � � � � � � � � � � Pelo critério dos mínimos quadrados para que � � � � � � � � �� seja mínimo � � � � � � � � e � � � � � � � onde � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.33/41 Regressão Linear � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ou � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ou � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � Geoma/03 – p.34/41 Regressão Linear resolver o sistema para determinar � � e � � sistema � � �: regra de Cramer � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � Geoma/03 – p.35/41 Regressão Linear - Exemplo do despejo de poluentes � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.36/41 Regressão Linear - Exemplo do despejo de poluentes � � � � � � � � � � � � � � � � 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados aprox. linear Geoma/03 – p.37/41 Aproximação Quadrática � � � � � � � � � � � � � � � � � � � � � mínimo resíduo � � � � � � � � � � � � � � � � e � � � � � � � onde � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � e � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Geoma/03 – p.38/41 Aproximação Pela Série de Taylor Expansão em série de Taylor de �: � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � necessário conhecer � � � � � � � � � � � � � � aproximar � � � � � � � � � � � � � � se � é suave, então: mais termos �melhor aproximação Geoma/03 – p.39/41 Aproximação Pela Série de Taylor Exemplo do despejo de poluentes Fazendo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � diferença divididas: linear por partes Geoma/03 – p.40/41 Aproximação Pela Série de Taylor Exemplo do despejo de poluentes 0 1 2 3 4 5 0 2 4 6 8 10 K g/ ho ra horas dados 2+x/2 3+(x-2)/3 4-3*(x-5)/4 Geoma/03 – p.41/41 Interpolac {c}~{a}o / Aproximac {c}~{a}o Exemplo: despejo de poluente Exemplo: despejo de poluente Exemplo: despejo de poluente Exemplo: despejo de poluente Exemplo: despejo de poluente Interpolac {c}~{a}o Polinomial Interpolac {c}~{a}o Polinomial Interpolac {c}~{a}o Polinomial Interpolac {c}~{a}o Polinomial {large Interpolac {c}~{a}o por Polin^{o}mios de Lagrange} {large Interpolac {c}~{a}o por Polin^{o}mios de Lagrange} {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} Forma de Diferenc {c}as Divididas de Newton {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} {large Forma de Diferenc {c}as Divididas de Newton} Interpolante Linear por Partes Erro de Interpolac {c}~{a}o Interpolac {c}~{a}o Usando Splines Interpolac {c}~{a}o Usando Spline C'{u}bica Aproximac {c}~{a}o Aproximac {c}~{a}o Aproximac{c}~{a}o Aproximac {c}~{a}o {large Aproximac {c}~{a}o por M'{i}nimos Quadrados} {large Aproximac {c}~{a}o por M'{i}nimos Quadrados} {large Aproximac {c}~{a}o por M'{i}nimos Quadrados} Regress~{a}o Linear Regress~{a}o Linear Regress~{a}o Linear {small Regress~{a}o Linear - Exemplo do despejo de poluentes} {small Regress~{a}o Linear - Exemplo do despejo de poluentes} Aproximac {c}~{a}o Quadr'{a}tica Aproximac {c}~{a}o Pela S'{e}rie de Taylor Aproximac {c}~{a}o Pela S'{e}rie de Taylor Aproximac {c}~{a}o Pela S'{e}rie de Taylor