Buscar

interpolacao_e_aproximacao

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

Mais conteúdos dessa disciplina