AP3 - Métodos Computacionais - JORGELUIZ JUNIOR

Prévia do material em texto

NÚCLEO DE EDUCAÇÃO A DISTÂNCIA (NEAD) 
 
 
 
Resolução de Problemas 
APLICAÇÃO PRÁTICA 
REFERENTE AS UNIDADES “5” A “8” 
 
Turma: Métodos Computacionais 
Professor: Jhoab Pessoa de Negreiros 
Semestre: 2021-1 
Nome: JORGE LUIZ MIGUEL DA SILVA JUNIOR 
Matricula: 5804182 
 
PROPOSTA DO TRABALHO 
 
Os métodos computacionais consistem em um conjunto de ferramentas, métodos e algoritmos 
numéricos para a resolução de problemas onde uma abordagem analítica é extremamente complexa 
ou impossível. Dentro desse conjunto de técnicas numéricas, destacamos os métodos usados para 
determinar os zeros, os pontos críticos, a derivada, a integral de uma função. 
Há essencialmente duas abordagens que são muito importantes, quando se necessita obter 
uma aproximação de uma função a partir de um conjunto de pontos, são elas: 
 Interpolação polinomial; 
 Teoria das aproximações. 
Nessas abordagens existem algumas técnicas, por exemplo, para interpolações: polinômios 
de Lagrange, diferenças divididas, interpolação de Hermite, interpolação por spline cúbica e etc. Por 
outro lado, tem-se como exemplo para aproximações por mínimos quadrados, polinômios de 
Chebyshev, etc. 
O trabalho consiste na pesquisa dessas duas técnicas citadas acima (interpolação polinomial 
e teoria das aproximações). No trabalho deverá conter no mínimo duas técnicas para cada 
abordagem incluindo necessariamente as listadas em negrito. Aplique as técnicas estudadas, no 
mínimo, em um problema relevante. 
 
 
 
 
ORIENTAÇÕES SOBRE A ENTREGA 
 
1 – Vocês poderão trabalhar em trio; 
2 – Um único componente do trio deverá enviar o trabalho com os outros nomes; 
3 – Enviar o enviar o arquivo em docx ou pdf. 
 
 
 APROXIMAÇÃO DE FUNÇÕES 
 
 INTERPOLAÇÃO POLINOMIAL 
 
Introdução: A interpolação 
 
Interpolar uma função f(x) consiste em aproximar essa função por uma outra 
função g(x), escolhida entre uma classe de funções definida a priori e que satisfaça algumas 
propriedades. A função g(x) é então usada em substituição à função f(x). 
A necessidade de se efetuar esta substituição surge em várias situações, como por 
exemplo: 
a.) quando são conhecidos somente os valores numéricos da função para um 
conjunto de pontos e é necessário calcular o valor da função em um ponto não 
tabelado; 
b.) quando a função em estudo tem uma expressão tal que operações como a 
diferenciação e a integração são difíceis (ou mesmo impossíveis) de serem 
realizadas. 
 
 Interpretação geométrica 
 
Consideremos (n +1 ) pontos distintos: x0, x1, ... , xn, chamamos nós da 
interpolação, e os valores de f(x) nesses pontos: f(x0), f(x1), ..., f(xn). 
A forma de interpolação de f(x) que veremos a seguir, consiste em se obter uma 
determinada função g(x) tal que: 
Geometricamente, um esboço da interpolante g(x) sobre a função f(x) é visto na 
figura 3.1. 
 
Em particular, se g(x) = Pn(x), onde Pn é um polinômio de grau n, então a 
interpolação é denominada de interpolação polinomial. 
Observamos que: 
i.) existem outras formas de interpolação polinomial como, por exemplo, a 
fórmula de Taylor, a interpolação por polinômios de Hermite e do tipo 
“spline”, para as quais as condições são outras; 
ii.) Assim como g(x) foi escolhida entre as funções polinomiais, poderíamos 
ter escolhido g(x) como função racional, função trigonométrica, etc. Um 
 
 
caso que explora combinaçãoes de funções trigonométricas, em campo real 
ou complexo, é o aproximante definido a partir da série de Fourier; 
iii.) existe também o caso polinomial não interpolante, tal como, o aproximante 
de funções por mínimos quadrados. 
 
Em qualquer um dos casos citados, estes encontram-se inseridos em um tópico 
mais geral chamado aproximação de funções. 
A interpolação polinomial que será vistá será a de Lagrange e a de Newton. 
 
 
Figura 4.1 – esboço de uma função f(x) e de sua interpolante g(x), para n = 4 ( 05 
nós). 
 
Definição - Interpolação Polinomial 
 
Dados os pontos (x0, f(x0)), (x1, f(x1)), ..., (xn, f(xn)), portanto (n + 1) pontos, 
queremos aproximar f(x) por um polinômio pn(x), de grau menor ou igual a n, tal que: 
f(xk) = pn(xk) k = 0, 1, 2, ..., n 
 
Surgem aqui as perguntas: existe sempre um polinômio pn(x) que satisfaça estas 
condições? Caso exista, ele é único? 
Representaremos pn(x) por: 
pn(x) = a0 + a1x + a2x
2 + ... + anx
n. 
Portanto, obter pn(x) significa obter os coeficientes a0, a1, ..., an. 
Da condição pn(xk) = f(xk),  k = 0, 1, 2, ..., n, montamos o seguinte sistema 
linear: 
 
x 
x 
1 x 
1 x x
n 
0 
n 
 … 
… 
x … 
 
a 

a
0 
. 

. 
. 


 a1x
0 
 a2 
2
 
2 1 
 
 
 
 2 
 
 … 

an 0 
n 1 
 
 
 
 n 
f x0 
x1
a0 
 a1x
n 

 a2x
n 
 …  anxn  f xn 

com n + 1 equações e n + 1 variáveis: a0, a1, ..., an. 
 
A matriz A dos coeficientes é 
 
 x0
 
1 x1 

2 n 
0 0 
2 xn 
1 1 


A =  .................................  . . . . 
 
 . . . . 
 2 
 n n n 
que é uma matriz de Vandermonde e, portanto, desde que x0, x1, ..., xn sejam pontos 
distintos, temos det (A)  0 e, então, o sistema linear admite solução única. 
Demonstramos assim o seguinte teorema: 
 
Teorema – Existência e unicidade do Polinômio Interpolador 
Existe um único polinômio pn(x), de grau  n, tal que: pn(xk) = f(xk), k = 0, 1, 2, 
..., n, desde que xk  xj, j  k. 
 Forma de Lagrange do Polinômio de Interpolação 
 
Sejam x0, x1, ...,xn, (n + 1) pontos distintos e yi = f(xi), i = 0, ..., n. 
Seja pn(x) o polinômio de grau  n que interpola f em x0, ..., xn. Podemos 
representar pn(x) na forma pn(x) = y0L0(x) + y1L1(x) + ... + ynLn(x), onde os polinômios 
Lk(x) são de grau n. Para cada i, queremos que a condição pn(xi) = yi seja satisfeita, ou seja: 
pn(xi) = y0L0(xi) + y1L1(xi) + ... + ynLn(xi) = yi 
 
A forma mais simples de se satisfazer esta condição é impor: 
L (x) = 
0
 se k  
i 
 e, para isso, definimos L (x) por 
0 
x 
x 
 a1x1  a x2  …  a xn  f 
. . . . . 
. 
. 
. 
. 
. 
. 
. 
. 
 . 
. 
 
 
n 
n 
k i 1se k  i 
k
Lk(x) = 


x  x0 x  x1…x  xk1x  xk1…x  xn  
xk  x0 xk  x1 …xk  xk1 xk  xk1 …xk  xn 

É fácil verificar que realmente 
 
Lk(xk) = 1 e 
Lk(xi) = 0 se i  k. 
Como o numerador de Lk(x) é um produto de n fatores da forma: 
x  xi , i = 0, ..., n, i  k, então Lk é um polinômio de grau n e, assim, pn(x) é 
um polinômio de grau menor ou igual a n. 
Além disso, para x = xi, i = 0, ..., n temos: 
 
p n x i    yk Lk xi   yi Li x i   
yi k 0 
 
Então, a forma de Lagrange para o polinômio interpolador é: 
n 
 
 
onde 
 
 
 
L k x 


x 

j0 
jk 
 
 
x j 
. 
pn(x) 
= 
y k Lk x
k 0 
n 

j0 
jk 
x k  x j 

Exemplo : (Interpolação Linear) 
 
Faremos aqui um exemplo teórico para interpolação em dois pontos distintos: (x0, 
f(xo)) e (x1, f(x1)). 
Assim, n é igual a 1 e, por isto, a interpolação por dois pontos é chamada 
interpolação linear. 
 
 
 
2 
-1 
0 
1 
-1 
4 
x 
f(x) 
Usando a forma de Lagrange teremos: 
p1(x) = y0 L0 x  y1L1 x, onde 
L (x) = 
x  x1 
x  x 
, L (x) = . 
 
 0 
x 0  
x1  
1 
x1  x 0  Assim, p (x) = y 
x  x1  
 
 
x  x0 , ou seja,
1 0 x 
 

x
1

 
x
 
0
x1  xy0  x  x 0 y1x1  x 0 que é exatamente a equação da reta que 
passa por (x0, f(x0)) e (x1, f(x1)). 
Exemplo : 
 
Seja a tabela: 
 
 
Pela forma de Lagrange, temos que: 
p2(x) = y0 L0 x  y1L1 x  y 2L 2 x , onde: 
x  x1 x  x 2 
  
 x  0x  2 
 
x 2  2x 
 
 
L0(x) = 
x
 
 x1 x 
0 
 x 2 

1  01  2 3
x  x 0 x  x 2 

x  1x  
2
x 2  x  2
L1(x) = 
x
 
 x 0 x1  x2 
 
 
0  10  2 
 
 2 
x  x0 x  x1 
  
x  1x  0 
 
x 2  x 
 
L2(x) = 
x
 
 x0 x2  x1  2  12  0 6
 
 
 
0 
0 
1 
2 
 
3 

6 
Assim na forma de Lagrange, 
 
 x 2  2x   x 2  x  2   x 2  x 
p2(x) = 4    1     1  
  
  
   
  
 2 
 
Agrupando os termos semelhantes, obtemos que p2(x) = 1  
7 
x  
2 
x 2 . 
3 3 
 
 Forma de Newton do Polinômio de Interpolação 
 
A forma de Newton para o polinômio pn(x) que interpola f(x) em x0, x1, ..., xn, (n 
+ 1) pontos distintos é a seguinte: 
pn(x) = d0  d1x  x0   d2 x  x 0 x  x1   …  d n x  x 0 x  x1 …x  x n1 

No que segue, estudaremos: 
i) o operador diferenças divididas, uma vez que os coeficientes dk, k = 0, 1, 
..., n acima são diferenças divididas de ordem k entre os pontos (xj, f(xj)), j 
= 0, 1, ..., k. 
ii) a dedução da expressão de pn(x) dada por: 
pn(x) = d0  d1x  x0   d2 x  x 0 x  x1   …  d n x  x 0 x  x1 …x  x n1 


 Teoria das Aproximações:

 
 APROXIMAÇÃO POR MÍNIMOS QUADRADOS 
Consideremos a seguinte tabela de 
valores de uma função y = f(x): i 
1 2 3 4 
x
i
 2 4 6 8 
y
i
 2 11 28 40 

Pretende-se estimar valores da função em pontos não tabelados. Poderíamos utilizar o 
polinómio interpolador de Lagrange, de grau  3 (visto termos 4 pontos), ou então um Spline 
cúbico. Em ambos os casos, e designando por P tal função, ela teria de verificar: P(xi) = yi, i= 1, 2, 
3 e 4. 
 
Experimentemos primeiramente, representar em eixos cartesianos o conjunto de pontos da 
tabela dada 
 
x 8 6 4 

2 
10 
20 
y 

30 
40 
 
Verifica-se que os pontos se dispõem quase em linha recta (representação gráfica de um 
polinómio do 1º grau). Se usarmos essa 
1 
 
 
 
linha recta para aproximar os valores de f(x), essa função “não passará” pelos pontos tabelados, ou 
melhor dizendo, não será interpoladora de f(x), nesses mesmos pontos. 
Em vez de um polinómio interpolador de f(x), pode usar-se a recta que “passe mais 
próximo” dos pontos tabelados, ou seja que minimize a soma das distâncias dos pontos tabelados 
à recta. Mas minimizar a soma das distâncias dos pontos tabelados à recta é equivalente a 
minimizar a soma dos quadrados das distâncias dos pontos tabelados à recta. 
A aproximação por mínimos quadrados consiste em encontrar a 
função que “melhor se ajuste”, ao conjunto de pontos dado, minimizando 
o erro resultante do ajustamento, ou seja, pretende-se minimizar a 
soma dos quadrados das diferenças entre os valores tabelados e 
os valores obtidos pela aproximação. 
y 
 
 
40 


30 

20 
 
 
10 

2 4 6 8 x 
 
 
Designando axi + b o i-ésimo valor dado pela aproximação, o problema 
consiste em encontrar as constantes a e b que minimizam 
2 
 
 
 
4 
4 
4 4 

2 
2  2 
 
 
n 
yi  (axi  b)2 
i  1 
 
No exemplo apresentado, o problema reduz-se a encontrar as constantes a e b que 
minimizam 
 
 yi  (axi  b) 
i1 
=  2 - (2a + b ) 2 + 11 - (4a + b) 2 + 28 - (6a + b ) 2 + 40 - (8a + b)2. 
 
 
Se yi  (axi  b)
i1 
 
se considerar uma função de duas variáveis, 
para que um par ordenado (a,b) seja um mínimo local é condição necessária (não suficiente) que 
as derivadas parciais da função em ordem a a e b se anulem em (a,b), ou seja 
 
 
y  (ax  b)  0 e y  (ax  b)  0 
i i i i 
a i1 b i1 
 
 
das quais resultam, para este exemplo, 30a + 5b = 134 e 20a + 4b = 
81. A solução deste sistema de equações lineares é a = 6.55 e b = - 12.5, logo a função 
aproximadora pretendida é 
 
P(x) = 6.55x - 12.5 
 
 
 
O problema de encontrar a recta que “melhor se ajuste” a um conjunto de pontos dado, 
pode então ser formulado como: 
2 
3 
 
 
 
n 
n n 
n n 
2 
2 
 
 
Minyi  (axi  b)
i1 
 
 
Para que o mínimo exista é necessário que 
 
 
 yi  (axi  b)  2(yi  axi  b)(xi)  0 
 
a i1 
e 
i1 
 
 yi  (axi  b)  2(yi  axi  b)(1)  0. 
 
b i1 i1 
 
 
Estas equações podem ser simplificadas, assumindo a seguinte forma: 
 
 
n n n 
axi 
2 
 bxi  xiyi 
i1 
 
e 
i1 i1 
 
n n 
axi  b. n  yi 
i1 i1 
 
 
a que se costuma chamar equações normais, e cuja solução é 
 
 
n n n 
n(xiyi)  (xi).(yi) 
a i1 i1 i1 e n n 
n.(xii 
2 )  (xii)2
 
i1 i1 
 
n n n n 
(xii
2 ).(yi)  (xiyi).(xi) 
b  i1 i1 i1 i1 n n 
n.(xii
2 )  (xii)2
 
i1 i1 
2 


4 
 
 
 
n 
j i 0 k 0 i 0 
Consideremos agora o problema mais geral que consiste em aproximar um conjunto de 
pares ordenados { (xi, yi), i=0, 1, 2,..., M }, por um polinómio 
Pn(x) akxk
 
k0 
 
 
de grau n < M, usando a técnica dos mínimos quadrados. 
O procedimento é análogo ao descrito aquando da utilização de um polinómio de grau 1 
(cuja representação gráfica é uma recta) e consiste em encontrar as constantes a0, a1, a2, ..., an que 
minimizam: 
 
E  (yi  P(xi))2 
i0 
 
M M M 
 (yi)2  2P(xi). yi (P(xi))2
 
i0 
M 
i0 
M n 
i0 
M n 
  yi 
2 
 2(ajxi 
j ). yi  (ajxi 
j )2
 
i0 
M 
i0 
n 
j0 
M 
i0 
n 
j0 
n M 
  yi 
2 
 2aj.( yixi 
j )  ajak( xi 
jk ). 
i0 j0 i0 j0 k0 i0 
 
 
Tal como no caso linear, para que E tenha um mínimo é 
necessário que 
 
 
E 
aj 
 
E 
 0, j  0,1,...,n. 
 
M 
 
 
 
 
 
n M jk 
a 
 0  2 yixi 
j  2akxi  0 
 
 
que constitui um sistema de n+1 incógnitas aj e n+1 equações: 
M 
5 
 
 
 
n M jk M 
ak.  xi   yixi 
j , j  0,1,...,n 
k0 i0 i0 
 
 
chamadas equações normais. 
 
 
Estas últimas equações podem escrever-se na forma: 
 
 
M M M M M 
a0 xi 
0 
 a1 xi
1 
 a2 xi 
2 
LLan xi
n 
 yixi 
0 , 
i0 i0 i0 i0 i0 
 
M M M M M 
a0  xi
1 
 a1 xi 
2 
 a2  xi 
3 
LLan xi
n1 
  yixi
1, 
i0 
 
M 
M 
i0 
 
 
 
M 
i0 
 
 
 
M 
i0 
 
 
 
M 
i0 
 
 
 
M 
a0  xi
n  a1 xi
n1  a2 xi
n2 LLan xi 
2n
   yixi
n. 
i0 i0 i0 i0 i0 
6 
 
 
 
n=0 
∈ ∈ { } 
− − − 
− 
− 
− 
 
 
Prova-se que as equações normais têm solução única se os valores xi (i=0, 1, 2,..., M) forem distintos. 
 
Exemplo: Considere a seguinte tabela da função y = f(x): 
 
 
 
i 0 1 2 3 4 
xi 0.00 0.25 0.50 0.75 1.00 
yi 1.0000 1.2840 1.6487 2.1170 2.7183 
 
determine a expressão analítica do polinómio de grau dois, que aproxima a função tabelada, utilizando a 
técnica dos mínimos quadrados. 
 
Resolução: Neste problema n = 2 e M = 4, logo teremos 3 equações normais. 
 
 Polinómios de Chebyshev 
 
Paridade, zeros e extremos 
Paridade 
. Σ∞ 
Definição 1.2. Uma sucessão de 
polinómios 
simétrica se e somente se: 
Pn(x) 
n=0 
, tal que, o grau de Pn(x) é igual a n, diz-se 
Pn(−x) = (−1)n
Pn(x), ∀x ∈ R. (1.19) 
Isto significa que, se n for par Pn(−x) = Pn(x), ∀x ∈ R, ou seja, Pn(x) é uma função par, e se n 
for ímpar Pn(−x) = −Pn(x), ∀x ∈ R,ou seja, Pn(x) é uma função ímpar. 
Proposição 1.1.3. A sucessão {Tn(x)}∞ é simétrica. 
Demonstração. Façamos a demonstração usando o método de indução finita. 
Seja n = 0, então, pela Definição 1.2, T0(x) = 1 é par, visto que T0( x) = 1 = T0(x). 
Seja n = 1, então, pela Definição 1.2, T1(x) = x é ímpar, visto que T1( x) = x = T1(x). 
Seja n N, vamos supor que, para cada k 0, 1, 2, . . . , n , Tk(x) é par se k for par e Tk(x) é ímpar se k 
for ímpar. Vamos provar que Tn+1(x) tem a mesma propriedade. 
Sabe-se que 
 
Há agora dois casos a considerar: 
Tn+1(x) = 2xTn(x) − Tn−1(x). 
i) Se n + 1 for par, então n é ímpar e n 1 é par. Aplicando a hipótese de indução, podemos afirmar 
que Tn(x) é uma função ímpar e Tn−1(x) é uma função par. Uma vez que x é uma função ímpar, 
então xTn(x) é uma função par, por ser produto de duasfunções ímpares. Assim sendo, Tn+1(x) é 
par por ser a soma de duas funções pares. 
ii) Se n + 1 foi ímpar, então n é par e n 1 é ímpar. Aplicando a hipótese de indução, podemos 
7 
 
 
 
k 
π 
∈ 
afirmar que Tn(x) é uma função par e Tn−1(x) é uma função ímpar. Uma vez que x é uma função 
ímpar, então xTn(x) é uma função ímpar, por ser produto de uma função ímpar e outra par. 
Assim sendo, Tn+1(x) é ímpar por ser a soma de duas funções ímpares. 
□ 
 
Zeros 
Proposição Tn(x) tem n zeros reais em [−1, 1] dados pela seguinte fórmula 
 
xn,k = cos θ 
 
 
n,k 
, onde θ 
 
 
n,k 
=
 2(n − k) + 1 
π, k=1(1)n. (1.20) 
2n 
Notemos que os ângulos θn,k são decrescentes em k e satisfazem a condição π > θn,k > θn,k+1 > θ
n
 > 
0 
pelo que, xn,k é crescente em k e satisfaz −1 < xn,k < xn,k+1 < 1. 
Demonstração. Os zeros da função Tn(x), para x ∈ [−1, 1], que correspondem aos zeros da função cos nθ, para 
θ ∈ [0, π], podem ser calculados pela equação trigonométrica, 
Tn(x) = 0 
π 
⇐⇒ cos nθ = cos 
2
 
⇐⇒ nθ = 
⇐⇒ θn,k = 
2 
+ kπ, k ∈ Z 
(2k + 1)π 
2n 
, k ∈ Z 
⇐⇒ θ 
 
n,k = 
 2(n − k) + 1π
, k Z.
 
2n 
Polinómios de Chebyshev Primeira espécie 
14 
 
 
Σ Σ 
 
 
 
Figura 1.1: Variação da variável dependente x em função da variação da variável independente θ, na função x = 
cos θ, para θ ∈ [0, π] e x ∈ [−1, 1]. 
 
Dado que a função cosseno é periódica de período positivo mínimo 2π, os zeros da função Tn(x) são dados por 
 
xn,k 
 
= cos θ 
 
 
n,k 
= cos 
( 2k − 1)π
, k = 1(1)n. (1.21) 
2n 
Como os intervalos das variáveis x e θ são percorridos em sentidos contrários a fórmula (1.21) vai gerar uma 
sucessão de zeros decrescentes para a variável x, para se evitar esta organização vamos usar a formula 
 
xn,k 
= cos 
2 (n − k) + 1 
π , k = 1(1)n. 
2n 
□ 
Polinómios de Chebyshev Primeira espécie 
11 
 
 
− 
Na Figura 1.2 estão representados os zeros das funções T31(x) e T32(x). Note que 
quanto maior for o grau do polinómio, mais próximo dos extremos x = 1 e x = 1 se 
localizarão os seus zeros e, por consequência da paridade, estes zeros são simétricos 
em relação a origem. 
 
 
 
 
 
 
BIBLIOGRAFIA : 
 
http://wwwp.fc.unesp.br/~arbalbo/Iniciacao_Cientifica/interpolacao/teoria/1_Interpol_
polinomial_Met_Lagrange_Newton.pdf 
 
https://www1.univap.br/spilling/CN/ExRes_MMQ.pdf 
 
 
https://sigarra.up.pt › fmup › pub_geral.show_file 
 
 
 
 
 
http://wwwp.fc.unesp.br/~arbalbo/Iniciacao_Cientifica/interpolacao/teoria/1_Interpol_polinomial_Met_Lagrange_Newton.pdf
http://wwwp.fc.unesp.br/~arbalbo/Iniciacao_Cientifica/interpolacao/teoria/1_Interpol_polinomial_Met_Lagrange_Newton.pdf
https://www1.univap.br/spilling/CN/ExRes_MMQ.pdf
https://sigarra.up.pt/fmup/pt/pub_geral.show_file?pi_doc_id=178259
https://sigarra.up.pt/fmup/pt/pub_geral.show_file?pi_doc_id=178259