Cálculo Numérico ( apostila 1, 2, 3 )

Prévia do material em texto

Apostila de Introdução
Aos Métodos Numéricos
PARTE III
2o Semestre - 2002
Profa. Salete Souza de Oliveira Buffoni
2
Índice
INTERPOLAÇÃO POLINOMIAL ....................................................................................3
INTRODUÇÃO ....................................................................................................................3
FORMA DE LAGRANGE .................................................................................................... 4
Interpolação para 2 pontos (n+1=2) - ajuste de retas (n=1).......................................... 5
Interpolação para 3 pontos (n+1=3) - ajuste de parábolas (n=2) ................................. 6
SÉTIMA LISTA DE EXERCÍCIOS...................................................................................9
FORMA DE NEWTON........................................................................................................10
Tabela de Diferenças Divididas..................................................................................... 10
Forma de Newton para o Polinômio Interpolador ........................................................ 11
OITAVA LISTA DE EXERCÍCIOS.................................................................................15
3
Interpolação Polinomial
 Introdução
Vamos supor que temos um conjunto de dados {xi,f(xi)} tal como na tabela abaixo:
xi 0 1,5 3,0 4,5 6,0
f(xi) 0,001 0,016 0,028 0,046 0,057
Nosso problema é obter o valor de f(x) para um valor de x que não tenha sido medido, como
por exemplo, x=2.0.
Por exemplo, quando não temos muitos dados (que levaria a um mau ajuste de uma função)
e só queremos saber o valor de f(x) para um x intermediário entre duas medidas, isto é, xi<x<xi+1,
podemos usar as técnicas da interpolação.
Portanto, interpolar um ponto x a um conjunto de n+1 dados {xi,f(xi)}, significa
simplesmente, calcular o valor de f(x), sem conhecer a forma analítica de f(x) ou ajustar uma função
analítica aos dados.
A interpolação polinomial consiste em se obter um polinômio p(x) que passe por todos os
pontos do conjunto de (n+1) dados {xi,f(xi)}, isto é:
p(x0)=f(x0) (1)
p(x1)=f(x1)
...
p(xn)=f(xn)
(note que a contagem começa em zero, portanto temos n+1 pontos na expressão acima).
O polinômio p(x) é chamado de polinômio interpolador. É possível se demonstrar que
existe um único polinômio p(x) de grau menor ou igual a n que passa por todos os (n+1) pontos do
conjunto {xi,f(xi)}
Portanto, podemos escrever:
( ) ( )p x a a x a x a x f xn n n0 0 1 0 2 02 0 0= + ⋅ + ⋅ + + ⋅ =L
( ) ( )p x a a x a x a x f xn n n1 0 1 1 2 12 1 1= + ⋅ + ⋅ + + ⋅ =L
...
( ) ( )p x a a x a x a x f xn n n n n nn n= + ⋅ + ⋅ + + ⋅ =0 1 2 2 L
4
Esse conjunto de equações corresponde a um sistema linear de n+1 equações e n+1
variáveis. Portanto, ele poderia ser resolvido diretamente. Essa é uma das formas de se obter o
polinômio interpolador.
Entretanto, existem outras formas, como a forma de Lagrange e a forma de Newton, que
veremos a seguir.
 Forma de Lagrange
Introdução :
 Sendo conhecidos os valores de uma função apenas em determinados pontos, a
INTERPOLAÇÃO é um procedimento que possibilita a estimativa de valores desconhecidos da
função, bem como auxilia na integraçãode uma função desconhecida ou de difícil integração.
Seja um conjunto de n+1 dados {xi,f(xi)}. Queremos encontrar um polinômio interpolador
p(x) que satisfaça a condição (1), isto é, passe por todos os pontos.
Uma possível forma para p(x) que satisfaça (1) é:
p x L x f x L x f x L x f xn n( ) ( ) ( ) ( ) ( ) ( ) ( )= ⋅ + ⋅ + + ⋅0 0 1 1 L (2)
onde os Lk(x) são polinômios tais que:
( )L xk i ki= δ (3)
sendo que:
δki
se k i
se k i
= ≠=

0
1
,
,
(4)
Portanto,
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
= ⋅ + ⋅ + + ⋅
= ⋅ + ⋅ + + ⋅
=
L
L
e,
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
= ⋅ + ⋅ + + ⋅
= ⋅ + ⋅ + + ⋅
=
L
L
ou seja:
p x f xi i( ) ( )=
o que mostra que o polinômio interpolador p(x) passa exatamente sobre os pontos {xi,f(xi)} da tabela
dada.
5
Temos agora que encontrar os polinômios Lk(x), que satisfaçam (3). Uma função que
satisfaz a condição (3) é:
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )nxkx1kxkx1kxkx1xkx0xkx
nxx1kxx1kxx1xx0xx)x(kL −⋅⋅+−⋅−−⋅⋅−⋅−
−⋅⋅+−⋅−−⋅⋅−⋅−= LL
LL
que é fácil verificar, pois:
( )
( )
L x e
L x se i k
k k
k i
=
= ≠
1
0 ,
De maneira compacta, podemos escrever o polinômio interpolador na Forma de Lagrange,
como:
( ) ( ) ( )p x L x f xn i i
i
n
= ⋅
=
∑
0
(5)
e,
( )
( )
( )L x
x x
x x
i
j
j
j i
n
i j
j
j i
n=
−
−
=≠
=≠
∏
∏
0
0
 Interpolação para 2 pontos (n+1=2) - ajuste de retas (n=1)
 xi x0 x1
f(xi) f(x0) f(x1)
De (5) :
(6)
As funções Li (x) devem satisfazer (3), ou seja:
L0 (x0) =1 L1 (x0) =0
L0 (x1) =0 L1 (x1) =1 (7)
∑
=
+==
1
0
1100 )().()().()().()(
i
ii xfxLxfxLxfxLxp
6
É fácil verificar que, as seguintes funções, satisfazem (7) :
(8)
De (8) em (6) :
( ) ( ) ( )1
01
0
0
10
1 xf
xx
xx
xf
xx
xx
xp ⋅



−
−+⋅



−
−=
 Interpolação para 3 pontos (n+1=3) - ajuste de parábolas (n=2)
xi x0 x1 x2
f(xi) f(x0) f(x1) f(x2)
De (5):
( ) ( ) ( ) ( ) ( )2211002
0
xfLxfLxfLxfLxp
i
ii ⋅+⋅+⋅=⋅= ∑
=
(9)
onde:
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
Por construção:
( ) ( )
( ) ( )2010
21
0 xxxx
xxxx
L −⋅−
−⋅−=
( ) ( )
( ) ( )2101
20
1 xxxx
xxxx
L −⋅−
−⋅−=
( ) ( )
( ) ( )1202
10
2 xxxx
xxxx
L −⋅−
−⋅−=
10
1
0 )( xx
xx
xL −
−=
01
0
1 )( xx
xx
xL −
−=
7
Portanto:
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( )21202
10
1
2101
20
0
2010
21)( xf
xxxx
xxxx
xf
xxxx
xxxx
xf
xxxx
xxxx
xp ⋅−⋅−
−⋅−+⋅−⋅−
−⋅−+⋅−⋅−
−⋅−=
 Exemplo:
Ajuste uma reta aos seguintes pontos:
x 2 4
f(x) 3,1 5,6
( ) ( ) ( )1
01
0
0
10
1 xf
xx
xx
xf
xx
xx
xp ⋅



−
−+⋅



−
−=
( ) ( ) ( )28.2455.16.5
24
2
1.3
42
4 −⋅+−⋅−=⋅


−
−+⋅


−
−= xxxxxp
( ) 6.025.1 +⋅= xxp
Ex.: Interpolação linear
 Tabela
 ————————————
 x | y
 —————+——————
 10 | 250 Qual o valor de y para x = 15?
 20 | 432
 30 | 500
 ————————————
 +-
8
 Interpolação linear entre 2 pontos conhecidos |(x , y )
 | 1 1
 | (x , y )
 | 2 2
 x - x +-
 1
 y = y + ———————— ( y - y )
 1 x - x 2 1
 2 1
 15 - 10
 y = 250 + ——————— (432 - 250) = 341
 20 - 10
9
Sétima Lista de Exercícios
1 ) Qual a relação entre o número de pontos usados na interpolação e o grau do polinômio
interpolador que pode ser calculado?
2 ) Se você tiver um conjunto de 5 dados {(x0,f(x0), (x1,f(x1), (x2,f(x2), (x3,f(x3), (x4,f(x4),}, e deseja
fazer uma interpolação linear, isto é, encontraruma reta que lhe permita obter o valor de f(x′), onde
x1<x′<x2:
a) Qual seria o grau do polinômio que você calcularia, isto é, quantos pontos você utilizaria?
b) E quais pontos da tabela você usaria?
3 ) A seguinte tabela informa o número de carros que passam por um determinado pedágio em um
determinado dia:
Horário 10:00 10:30 11:00 11:30 12:00 12:30
Número (em mil) 2.69 1.64 1.09 1.04 1.49 2.44
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 11:10, usando a forma de
Lagrange para encontrar um polinômio interpolador p(x) que estima o número de carros em
função do tempo. Use uma reta como função interpoladora.
c) Agora, faça a mesma estimativa, mas utilizando uma parábola como polinômio interpolador.
10
 Forma de Newton
 Tabela de Diferenças Divididas.
O próximo a método de interpolação a ser estudado é a “Forma de Newton”. No entanto, para que
possamos discutir este método temos que antes nos familiarizar com a construção da chamada
“Tabela de Diferenças Divididas”
Seja a tabela de valores:
x x0 x1 x2 x3
f(x) f(x0) f(x1) f(x2) f(x3)
Podemos construir a seguinte tabela:
x f(xi) f[xi, xi+1] f[xi, xi+1, xi+2] f[xi, xi+1, xi+2, xi+3]
x0 f(x0)
f[x0,x1]
f[x0,x1,x2]
x1 f(x1)
f[x1,x2] f[x0,x1,x2,x3]
x2 f(x2) f[x1,x2,x3]
f[x2,x3]
x3 f(x3)
onde:
[ ] ( ) ( )f x x f x f x
x x0 1
1 0
1 0
, = −−
[ ] ( ) ( )f x x f x f x
x x1 2
2 1
2 1
, = −−
[ ] ( ) ( )f x x f x f x
x x2 3
3 2
3 2
, = −−
[ ] [ ] [ ]f x x x f x x f x x
x x0 1 2
1 2 0 1
2 0
, ,
, ,= −−
11
[ ] [ ] [ ]f x x x f x x f x x
x x1 2 3
2 3 1 2
3 1
, ,
, ,= −−
[ ] [ ] [ ]f x x x x f x x x f x x x
x x0 1 2 3
1 2 3 0 1 2
3 0
, , ,
, , , ,= −−
 Exemplo:
xi 0,1 0,4 0,7 1 1,2
f(xi) 0,813 0,536 0,682 1,25 1,864
A tabela de diferenças divididas é:
 xi f(xi) f[xi , xi+1] f[xi , xi+1, xi+2] f[xi , xi+1 , xi+2 ,xi+3]
0,1 0,813
0,4 0,536
0,7 0,682
1 1,250
1,2 1,864
f[xi , xi+1 , xi+2 , xi+3 , xi+4 ] =
 Forma de Newton para o Polinômio Interpolador
Para calcular a Forma de Newton do polinômio interpolador, vamos começar com o caso mais
simples: encontrar um polinômio de grau 0, p0(x), que interpola f(x) no ponto x0. Vamos partir da
diferença dividida f[x0,x], que é dada por:
[ ] ( ) ( )f x x f x f x
x x0
0
0
, = −− (1)
Isolando-se f(x) da expressão acima, tem-se:
923,0
1,04,0
813,0536,0 −=−
−
487,0
4,07,0
536,0682,0 =−
−
893,1
7,01
682,025,1 =−
−
07,3
12,1
25,1864,1 =−
−
( )
 350,2
1,07,0
 923,0487,0 =−
−−
354,2
7,02,1
893,107,3 =−
−
343,2
4,01
487,0893,1 =−
−
 008,0
1,01
350,2343,2 −=−
−
 014,0
4,02,1
343,2354,2 =−
−
02,0
1,02,1
) 008,0(014,0 =−
−−
12
( ) ( ) [ ] ( )f x f x f x x x x− = ⋅ −0 0 0,
( ) ( ) [ ] ( )f x f x f x x x x= + ⋅ −0 0 0, (2)
Da própria definição de polinômio interpolador, sabe-se que (ver expressão 1 da aula
anterior):
p0(x)=f(x0)
Portanto, a expressão (2) pode ser escrita como:
( ) ( ) [ ] ( )f x p x f x x x x= + ⋅ −0 0 0, (3)
A expressão acima não pode ser usada diretamente, pois não podemos calcular o valor
f[x0,x], já que não conhecemos o valor de f(x) em qualquer ponto x (veja expressão (1) acima). Fora
do ponto x0, sabemos que o polinômio interpolador é apenas uma aproximação de f(x), caso
contrário teríamos uma resposta exata e não precisaríamos da interpolação. Em outras palavras,
tem-se que:
p0(x)≈f(x), para x≠x0
Portanto, da expressão (3), concluímos que f[x,x0]⋅(x-x0) é simplesmente a diferença entre o
valor de f(x) (valor real da função) e o valor p0(x) que obtivemos com a interpolação. Em outras
palavras, esse termo é o erro no processo de interpolação, isto é:
( ) ( ) ( ) [ ] ( )0000 , xxxxfxpxfxE −⋅=−= (4)
Podemos realizar o mesmo exercício, partindo de uma diferença dividia de ordem maior, ou
seja f[x0,x1,x], que é dada por:
[ ] [ ] [ ] [ ]
( ) ( ) [ ]
( ) ( ) ( ) [ ]
( ) ( )01
0100
1
01
0
0
1
010
0110
,
,
,,
,,,,
xxxx
xxfxxxfxf
xx
xxf
xx
xfxf
xx
xxfxxf
xxxfxxxf
−⋅−
⋅−−−=
=−
−−
−
=−
−==
Portanto, tem-se que:
( ) ( ) ( ) [ ] ( ) ( ) [ ]xxxfxxxxxxfxxxfxf ,,, 10010100 ⋅−⋅−=⋅−−−
e
( ) ( ) ( ) [ ] ( ) ( ) [ ]xxxfxxxxxxfxxxfxf ,,, 10011000 ⋅−⋅−+⋅−+=
Podemos verificar que o polinômio interpolador de ordem 1, p1(x), é dado por:
( ) ( ) ( ) [ ]10001 , xxfxxxfxp ⋅−+=
pois,
( ) ( ) ( ) [ ] ( )01000001 , xfxxfxxxfxp =⋅−+=
e
13
( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) ( )1
01
01
0101001011 , xfxx
xfxf
xxxfxxfxxxfxp =−
−⋅−+=⋅−+=
que são as condições fundamentais para se encontrar tal polinômio.
Portanto, o erro cometido ao se aproximar f(x) por p1(x) é:
( ) ( ) ( ) [ ]xxxfxxxxxE ,, 10101 ⋅−⋅−=
Podemos continuar indefinidamente, até encontrarmos o polinômio interpolador de uma
ordem n qualquer, aplicando sempre o mesmo raciocínio. A expressão geral para um polinômio
interpolador de ordem n será então:
( ) ( ) ( ) [ ] ( ) ( ) [ ]
( ) ( ) ( ) [ ]nn
n
xxxfxxxxxx
xxxfxxxxxxfxxxfxp
,,,
,,,
10110
210101000
KK
L
⋅−⋅⋅−⋅−+
++⋅−⋅−+⋅−+=
−
e o erro é dado por:
( ) ( ) ( ) ( ) [ ]xxxxfxxxxxxxE nnn ,,,, 1010 KK ⋅−⋅⋅−⋅−=
 Exemplo:
x 0,2 0,5 0,9 1,5 2,0
f(x) 4,88 5,00 5,72 8,00 11,00
Encontre o polinômio interpolador p(x) usando a forma de Newton:
 xi f(xi) f[xi , xi+1] f[xi , xi+1, xi+2]
0,2 4,88
0,5 5,00
0,9 5,72
 1,5 8,00
 2,0 11,00
Usando (11):
4,0
2,05,0
88,400,5 =−
−
8,1
5,09,0
00,572,5 =−
−
8,3
9,05,1
72,500,8 =−
−
0,6
5,10,2
00,800,11 =−
−
2
2,09,0
4,08,1 =−
−
2
5,05,1
8,18,3 =−
−
0
2
9,00,2
8,30,6 =−
− 0
14
Note que usando a forma de Newton, p(xi) = f(xi)
52)(
2,04,0208,04,088,4)(
2).1,02,05,0(08,04,088,4)(
2).5,0).(2,0(04).2,0(88,4)(
2
2
2
+−=
+−−+−+=
+−−+−+=
−−+−+=
xxxp
xxxxxp
xxxxxp
xxxxp
15
Oitava Lista de Exercícios
1 ) Qual é a condição básica para se obter o polinômio interpolador?
2 ) Na fabricação de determinadas cerâmicas é muito importante saber as condições de temperatura
em que o produto foi assado no forno. Como não é possível medir a temperatura do forno a todo
instante, ela é medida em intervalos periódicos de tempo e esses dados são interpolados para o
instante em que cada peça foi “queimada” a fim de se conhecer a temperatura do forno nesse
instante. Em um dia de funcionamento do forno, os seguintes dados foram coletados:
Horário 7:00 10:00 13:00 16:00 19:00 21:00
Temperatura (102 oC) 2.32 2.51 2.63 2.55 2.41 2.28
a) Construa a tabela de diferenças divididas para esses pontos.
b) Estime a temperatura do forno ás 14:30 usando a forma de Newton para apenas dois
pontos.
c) Faça essa estimativa novamente, desta vez usando 3 pontos.
3 ) Dado o seguinte conjunto de dados,
xi -2.0 -1.4 0.5 1.8 3.3
f(xi) 0.4±0.1 2.9±0.2 4.2±0.2 1.4±0.3 -7.5±0.4
encontre o valor de f(x) para x=2.0, usando:
a) uma parábola do tipo g(x)=ax2+b ajustada aos dados;
b) um polinômio interpolador de ordem igual a 2, na forma de Lagrange;
c) um polinômio interpolador de ordem igual a 2, na forma de Newton;
16
Referências Bibliográficas
RUGGIERO/LOPES - Cálculo Numérico. Makron Books
CHAPRA/CARRALE - Numerical Methods for Engineers. Ed. McGrawHill
CONTE - Elementos de Análise Numérica. Ed. Globo
BARROSO - Cálculo Numérico - Ed. Harper & How do Brasil
MARCELO G. MUNHOZ- Apostila de Cálculo Numérico - FACENS