aula13 interpolacao

Prévia do material em texto

Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Interpolac¸a˜o Polinomial
3 Forma de Lagrange
4 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Me´todos Iterativos
◮ Me´todo de Jacobi
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k−1)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
◮ Me´todo de Gauss-Seidel
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
◮ Convergeˆncia dos Me´todos
◮ Crite´rio das Linhas e Crite´rio de Sassenfeld
◮ Me´todos de Relaxac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Suponha que se tenha um conjunto de n+ 1 pontos
x0, x1, . . . , xn
e seus respectivos valores em relac¸a˜o a uma func¸a˜o f(x), ou seja,
y0 = f(x0), y1 = f(x1), . . . , yn = f(xn)
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Interpolar os pontos
(x0, y0) , (x1, y0) , . . . , (xn, y0)
consiste em obter uma func¸a˜o g(x) tal que
g(x0) = y0, g(x1) = y1, . . . , g(xn) = yn
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Polinoˆmios sera˜o adotados aqui como interpoladores
◮ Sa˜o computados facilmente
◮ Suas derivadas e integrais tambe´m sa˜o polinoˆmios
◮ A interpolac¸a˜o polinomial e´ utilizada principalmente quando
◮ A expressa˜o de f(x) na˜o e´ conhecida
◮ A func¸a˜o f(x) e´ complexa
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial – Definic¸a˜o
◮ O problema geral da interpolac¸a˜o por meio de polinoˆmios consiste
em, dados n+ 1 pontos distintos
x0, x1, . . . , xn
e seus respectivos pares
y0, y1, . . . , yn
determinar um Polinoˆmio Pn(x) de grau ma´ximo n tal que
Pn(x0) = y0, Pn(x1) = y1, . . . , Pn(xn) = yn
◮ Em geral, yi = f(xi)
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Deseja-se obter um polinoˆmio na forma
Pn(x) = a0 + a1x+ a2x
2 + · · ·+ anx
n
◮ Para esse fim, deve-se determinar os coeficientes a0, a1, . . . , an de
modo que
Pn(x0) = a0 + a1x0 + a2x
2
0 + · · ·+ anx
n
0 = y0
Pn(x1) = a0 + a1x1 + a2x
2
1 + · · ·+ anx
n
1 = y1
...
Pn(xn) = a0 + a1xn + a2x
2
n + · · ·+ anx
n
n = yn
◮ Assim, verifica-se que uma forma de determinar o polinoˆmio
interpolador e´ resolvendo um sistema de equac¸o˜es lineares com n+ 1
inco´gnitas
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Em forma matricial o sistema linear fica como

1 x0 x
2
0 . . . x
n
0
1 x1 x
2
1 . . . x
n
1
...
...
...
. . .
...
1 xn x
2
n . . . x
n
n




a0
a1
...
an

 =


y0
y1
...
yn


◮ A matriz de coeficientes e´ chamada de Matriz de Vandermonde
◮ Sabe-se que det(A) 6= 0 desde que os pontos x0, x1, . . . , xn sejam
distintos
◮ Teorema Dados n+ 1 pontos distintos x0, x1, . . . , xn e seus
respectivos valores y0, y1, . . . , yn, enta˜o existe um u´nico polinoˆmio
Pn(x), de grau ma´ximo n, tal que
Pn(xi) = yi, i = 0, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Exemplo
◮ Exemplo 1
Encontre o polinoˆmio de grau ≤ 2 que interpola os pontos que
seguem.
x −1 0 1
f(x) 0,54 1 0,54
◮ Soluc¸a˜o: P2(x) = 1− 0,46x
2
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial – Exemplo em Python
1 from pylab import *
2
3 def polyinterp(x,y):
4 n = len(x)
5 A = zeros((n,n))
6 for i in range(n):
7 for j in range(n):
8 A[i,j] = x[i]**j
9 c = gauss(A,np.matrix(y).transpose())
10 return c
11
12 def polyhorner(c,z):
13 n = len(c)
14 b = c[n-1]
15 for i in range(n-2,-1,-1):
16 b = c[i] + b * z
17 return b
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial – Exemplo em Python
1 # pares (xi, yi) observados
2 x = [-1.0, 0.0, 1.0]
3 y = [0.54, 1.0, 0.54]
4
5 # valor z para o qual deseja-se uma aproximacao de f(z)
6 z = 0.5
7
8 # determina os coeficientes do polinomio interpolador
9 c = polyinterp( x, y )
10
11 # calculo da aproximacao de f(z)
12 fz = polyhorner( c, z )
13 print fz
Heder S. Bernardino Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Interpolac¸a˜o Polinomial
◮ Observac¸o˜es
◮ Outras formas de se determinar o polinoˆmio interpolante sera˜o vistas
◮ sem a necessidade de resolver um sistema de equac¸o˜es lineares
◮ complexidade computacional O(n3)
◮ A matriz de Vandermonde costuma ser mal condicionada
◮ leva a` perda de precisa˜o da soluc¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
◮ Um exemplo sera´ utilizado para ilustrar a ideia
◮ Dados os treˆs pontos distintos (x0, y0), (x1, y1), (x2, y2)
◮ Deseja-se encontrar o polinoˆmio
P2(x) = a0 + a1x+ a2x
2
tal que
P2(xi) = yi, i = 0, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
◮ Uma fo´rmula para encontrar tal polinoˆmio e´ a seguinte
P2(x) = y0L0(x) + y1L1(x) + y2L2(x)
onde
L0(x) =
(x− x1)(x− x2)
(x0 − x1)(x0 − x2)
L1(x) =
(x− x0)(x− x2)
(x1 − x0)(x1 − x2)
L2(x) =
(x− x0)(x− x1)
(x2 − x0)(x2 − x1)
◮ As func¸o˜es L0(x), L1(x) e L2(x) sa˜o chamadas de func¸o˜es de base de
Lagrange
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
◮ Ale´m de serem polinoˆmios de grau n, essas func¸o˜es sa˜o definidas de
modo que
Li(xj) =
{
1, se i = j
0, se i 6= j
onde i, j = 0, 1, . . . , n
◮ Consequentemente P2(x) tem grau ≤ 2
◮ E´ fa´cil ver que o polinoˆmio interpola os dados, pois
P2(x0) = y0 L0(x0)︸ ︷︷ ︸
=1
+y1 L1(x0)︸ ︷︷ ︸
=0
+y2 L2(x0)︸ ︷︷ ︸
=0
= y0
P2(x1) = y0L0(x1) + y1L1(x1) + y2L2(x1) = y1
P2(x2) = y0L0(x2) + y1L1(x2) + y2L2(x2) = y2
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
◮ Considerando n+ 1 pontos distintos
(x0, y0), (x1, y1), . . . , (xn, yn)
◮ O polinoˆmio interpolador na forma de Lagrange e´ dado por
Pn(x) = y0L0(x) + y1L1(x) + · · ·+ ynLn(x) =
n∑
i=0
yiLi(x)
onde
Li(x) =
(x− x0)(x− x1) . . . (x− xi−1)(x− xi+1) . . . (x− xn)
(xi − x0)(xi − x1) . . . (xi − xi−1)(xi − xi+1) . . . (xi − xn)
Li(x) =
n∏
j=0,j 6=i
(x− xj)
(xi − xj)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
Entrada: nu´mero de pontos n, vetores x e y de dados, valor a ser
interpolado z
1 inicio
2 r ←− 0;
3 para i = 0, . . . , n− 1 fac¸a
4 c ←− 1;
5 d ←− 1;
6 para j = 0, . . . , n− 1 fac¸a
7 c ←− c ∗ (z − xj);
8 d ←− d ∗ (xi − xj);
9 r ←− r + yi ∗ (c/d);
10 retorna r
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Exemplo
◮ Exemplo 2
Encontre o polinoˆmio de grau ≤ 2 na Forma de Lagrange que
interpola os pontos que seguem. Simplifique o polinoˆmio.
x −1 0 1
f(x) 0,54 1 0,54
◮ Soluc¸a˜o: P2(x) = 1− 0,46x
2
◮ Nota-se que o polinoˆmio e´ o mesmo que aquele obtido anteriormente
pois, como foi visto, este polinoˆmio e´ u´nico
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange
◮ Observac¸o˜es
◮ O algoritmo executa um total de operac¸o˜es aritme´ticas na ordem de n2
◮ A complexidadecomputacional e´ menor do que resolver um sistema de
equac¸o˜es lineares (O(n3))
◮ Embora simples, avaliar um novo ponto z e´ computacionalmente
custoso na Forma de Lagrange para o polinoˆmio interpolador
◮ Ale´m disso, aumentar o grau do polinoˆmio interpolador requer que as
bases Li(x) sejam computadas novamente
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange – Exemplo em Python
1 from pylab import *
2
3 def lagrange(x,y,z):
4 z = array( z )
5 r = 0.0
6 for i in range(len(x)):
7 c = 1.0
8 d = 1.0
9 for j in range(len(x)):
10 if (i != j):
11 c = c * (z - x[j])
12 d = d * (x[i] - x[j])
13 r = r + y[i] * (c/d)
14 return r
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Forma de Lagrange – Exemplo em Python
1 # pares (xi, yi) observados
2 x = [-1.0, 0.0, 1.0]
3 y = [0.54, 1.0, 0.54]
4
5 # valor z para o qual deseja-se uma aproximacao de f(z)
6 z = 0.5
7
8 # calculo da aproximacao utilizando a Forma de Lagrange
9 fz = lagrange( x, y, z )
10 print fz
11
12 # exemplo de calculos de aproximacao para varios pontos
13 zs = [0.5, 0.6, 0.7]
14 fzs = lagrange( x, y, zs )
15 print fzs
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Interpolac¸a˜o Polinomial
◮ Sejam os pontos da tabela que segue
x 1 1,1 1,2 1,3
tan(x) 1,5574 1,9648 2,5722 3,6021
◮ Construindo polinoˆmios interpoladores de grau n = 1, 2, 3, enta˜o
n 1 2 3
pontos x0,x1 x0,x1,x2 x0,x1,x2,x3
Pn(x) 2,2685 2,2435 2,2296
|erro| 0,0340 0,0090 0,0049
◮ Adotando tan(1,15) = 2,2345 como base da comparac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Lagrange
Interpolac¸a˜o Polinomial
◮ Observa-se que
◮ A aproximac¸a˜o tende a melhorar quando aumenta-se n
◮ Sera´ visto que o erro aumenta quando n assume valores muito grandes
◮ Problemas podem aparecer quando n ≥ 10
◮ Outras formas de interpolac¸a˜o sera˜o vistas para evitar esse tipo de
situac¸a˜o
◮ Utilizar interpolac¸a˜o com polinoˆmios de grau menor em partes do
intervalo original
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Interpolac¸a˜o Polinomial
◮ Encontrar Pn(x) que interpolem os n+ 1 pontos dados
◮ Soluc¸a˜o u´nica se os pontos forem distintos
◮ Pode ser determinado resolvendo um sistema de equac¸o˜es lineares
◮ Forma de Lagrange
Pn(x) =
n∑
i=0
yiLi(x) com Li(x) =
n∏
j=0,j 6=i
(x− xj)
(xi − xj)
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Interpolação Polinomial
	Forma de Lagrange
	Revisão