42
Métodos Numéricos Interpolação / Aproximação Renato S. Silva, Regina C. Almeida

Interpol a Cao

  • Upload
    jsilva2

  • View
    27

  • Download
    0

Embed Size (px)

Citation preview

Métodos NuméricosInterpolaçã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 descrevea 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áriode 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 osvalores 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 osvalores 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 modoaproxima

em um intervalo � � � � �são dados � pontos distintos no plano

� � � � � � � � � � � � � � � � � � � � � � � � � �

deseja-se determinar um polinômio � que interpolaestes 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çãode Gauss

� é único

encontrar meio mais simples e barato dedeterminá-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

Kg/

hora

horas

dados2+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 Newton

entre � � e � � � �� � � � � ��� entre � � e � � � �� � � � �� � � ��

entre � � e � � � �� � � � � ��� � � ��

0

1

2

3

4

5

0 2 4 6 8 10

Kg/

hora

horas

dados2+x/2

3+(x-2)/34-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

Kg/

hora

horas

dadoslinear por partes

nenhuma restrição de continuidade imposta sobre � ou sobre suas derivadasentre 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

é

� � � � vezescontinuamente 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 nainterface entre os sub-intervalos

SPLINES: polinômios de ordem

que interpolam osdados e têm

��

derivadas contínuas em todo ointervalo

o spline deve passar nos nóso 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

Kg/

hora

horas

dadosprimeiro intervalosegundo intervaloterceiro 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 demodo que a soma dos quadrados dos resíduos sejamínima

Geoma/03 – p.29/41

Aproximação por Mínimos Quadrados

Seja

dado por

� � ��� �

��� �

��� �

��

� � �

� � � �

reescrito como

� �� �

� � � � � � � � � � � � �� � � �� � �

� ��� � �

� � � �

passará por um mínimo quando as � derivadasparciais 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

Kg/

hora

horas

dadosaprox. 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 �melhoraproximaçã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

Kg/

hora

horas

dados2+x/2

3+(x-2)/34-3*(x-5)/4

Geoma/03 – p.41/41