AP3 - Métodos ComputacionaisFEITO

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
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.
R. polinômios de Lagrange 
Uma vez conhecidas as funcões Ln,k , um polinômio interpolador ´e facilmente determinado. Este polinômio ´e chamado de n-ésimo polinômio interpolador de Lagrange e é definido como descrito no Teorema 1 .
Teorema 1: Se x0, x1, ..., xn são n + 1 números distintos e f é uma funçaoo cujos valores nestes números são dados, então existe um ´único polinômio P(x) de grau no máximo n com f (xk ) = P(xk ), para k = 0, 1, ..., n. Este polinômio é dado por P(x) = f (x0)Ln,0(x) + ... + f (xn)Ln,n(x) = Xn k=0 f (xk )Ln,k (x), (1) onde, para cada k = 0, 1, ..., n, Ln,k (x) = (x − x0)...(x − xk−1)(x − xk+1)...(x − xn) (xk − x0)...(xk − xk−1)(xk − xk+1)...(xk − xn) = Yn i=0,i6=k (x − xi) (xk − xi) . 
Quando não houver dúvida quanto ao grau do polinômio, denotaremos Ln,k (x) por Lk (x). Queremos determinar o segundo polinômio interpolador de Lagrange para a função f (x) = 1 x , usando os pontos x0 = 2, x1 = 2.5 e x2 = 4. Para isto, o primeiro passo ´e determinar L0(x), L1(x) e L2(x). 
Usando a definição vista anteriormente, temos que 
L0(x) = (x − 2.5)(x − 4) (2 − 2.5)(2 − 4) = (x − 2.5)(x − 4), 
L1(x) = (x − 2)(x − 4) (2.5 − 2)(2.5 − 4) = − (x − 2)(x − 4) 0.75 , e 
L2(x) = (x − 2)(x − 2.5) (4 − 2)(4 − 2.5) = (x − 2)(x − 2.5) 3 . 
Como
 f (x0) = f (2) = 0.5, f (x1) = f (2.5) = 0.4, f (x2) = f (4) = 0.25, 
temos que P(x) = X 2 k=0 f (xk )Lk (x) = 
0.5(x − 2.5)(x − 4) − 0.4 (x − 2)(x − 4) 0.75 + 0.25(x − 2)(x − 2.5) 3 = 
0.05x 2 − 0.425x + 1.15 
Usando o polinômio P calculado, podemos estimar o valor da função f (x) = 1 x em um ponto. 
Uma aproximação de f (3) = 1 3 é 
f (3) ≈ P(3) = 0.325. 
R. MINIMOS QUADRADOS
Consideremos a seguinte tabela de valores de uma função 
y = f(x):
 i 1 2 3 4 
xi 2 4 6 8 
yi 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 
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 Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 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. 
Designando axi + b o i-ésimo valor dado pela aproximação, o problema consiste em encontrar as constantes a e b que minimizam Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 2 [ ] yi axi b i n − + = ∑ ( ) 2 1 No exemplo apresentado, o problema reduz-se a encontrar as constantes a e b que minimizam [ ] y ax b i i i − + = = ∑ ( ) 2 1 4 = [ 2 - (2a + b )] 2 + [11 - (4a + b)] 2 + [28 - (6a + b )] 2 + [40 - (8a + b)] 2 . Se 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 i i i − + = ∑ ( 2 1 4 )] [ ] ∂ ∂a y ax b i i i −+ = = ∑ ( ) 2 1 4 0 e [ ] ∂ ∂b y ax b i i i −+ = = ∑ ( ) 2 1 4 0 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: Min y ax b [ ] i i i n − + = ∑ ( ) 2 1 Para que o mínimo exista é necessário que [ ] ∂ ∂a y ax b y ax b x i i i n ii i i n − + = − − −= = = ∑ ∑ ( ) ( )( ) 2 1 1 2 0 e [ ] ∂ ∂b y ax b y ax b i i i n i i i n − + = − − −= = = ∑ ∑ ( ) ( )( ) 2 1 1 2 1 0. Estas equações podem ser simplificadas, assumindo a seguinte forma: a x b x xy i i n i i n i i i n 2 =1 11 = = ∑ ∑∑ + = e a x bn y i i n i i n = = ∑ ∑ + = 1 1 . a que se costuma chamar equações normais, e cuja solução é a n xy x y nx x i i i n i i n i i n i i n i i i n i = − − = == = = ∑ ∑∑ ∑ ∑ ( ) ( ).( .( ) ( ) 1 1 1 2 1 2 ) 1 e b x y xy nx x i i n i i i n i i i n i i n i i n i i i n i = − − == = = x = = ∑∑ ∑∑ ∑ ∑ ( ).( ) ( ).( .( ) ( ) 1 2 111 1 2 1 2 ) Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 4 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 P x ax n k k k n ( ) = = ∑ 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 y Px y Px y Px y ax y ax y a yx aa x i i i M i i i i M i M i i M i j i j j n i M i M i j i j j n i M i ji i j i M j n i M j k k n i j k i M j n = − =− + = + = + = = = = − = = == = − = = = = + = = ∑ ∑ ∑ ∑ ∑ ∑ ∑∑ ∑ ∑ ∑ ∑∑ ∑ ( ( )) ( ) ( ). ( ( )) ( ). ( ) .( ) ( ). 2 0 2 0 0 2 0 0 00 2 00 0 0 0 0 0 2 2 2 2 2 ∑ 0 Tal como no caso linear, para que E tenha um mínimo é necessário que ∂ ∂ ∂ ∂ E a j n E a yx a x j j i i j k k n i M i i M j k = = = ⇔− + = = = = + ∑ ∑ ∑ 0 01 02 2 0 0 0 , , ,..., . 0 que constitui um sistema de n+1 incógnitas aj e n+1 equações: Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 5 a x yx j k k n i i M j k i i j i M = = + n = ∑∑ ∑= = 00 0 . , 01, ,..., chamadas equações normais. Estas últimas equações podem escrever-se na forma: a x a x a x a x yx i i M i i nin i M i M i M i i i M 0 0 0 1 1 2 2 0 0 0 0 = = = = =0 ∑ ∑ + + ++ = ∑ ∑ ∑ LL , a x a x a x a x yx i i M i i nin i M i M i M i i i M 0 1 0 1 2 3 1 0 0 0 1 0 2 = + = = = = ∑ ∑ + + ++ = ∑ ∑ ∑LL , M a x a x a x a x yx i n i M i in n i n i M i M i M i in i M n 0 0 1 2 2 2 0 0 0 0 1 = + = = = = ∑ ∑ + + ++ = ∑ ∑ + ∑ LL . 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. Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 6 ∑ xi 0 = 5 ∑ xi 1 = 2.5 ∑ xi 2 = 1.875 ∑xi 3 = 1.5625 ∑ xi 4 =1.3828 ∑yi 1 = 8.768 ∑xi yi = 0.4514 ∑xi 2 yi =4.4015 as equações normais para este problema são: a x a x a x yx i i i i i i i i i 0 0 0 4 1 1 2 2 0 4 0 4 0 0 4 = = = = ∑ ∑ ++ = ∑ ∑ a x a x a x yx i i i i i i i i i 0 1 0 4 1 2 2 3 0 4 0 4 0 4 = = = = ∑ ∑ ++ = ∑ ∑ a x a x a x yx i i i i i i i i i 0 2 0 4 1 3 2 4 0 4 0 4 2 0 4 = = = = ∑ ∑ ++ = ∑ ∑ substituindo valores obtém-se: 5.000 a0 + 2.500 a1 + 1.875 a2 = 8.7680 2.500 a0 + 1.875 a1 + 1.5625 a2 = 5.4514 1.875 a0 + 1.5625 a1 + 1.3828 a2 = 4.4015 cuja solução é a0 = 1.0052, a1 = 0.8641 e a2 = 0.8437. O polinómio de grau dois, que aproxima a função tabelada, utilizando a técnica dos mínimos quadrados é P2(x) = 0.8437 x2 + 0.8641 x + 1.0052 Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 7 Embora a técnica dos mínimos quadrados utilize normalmente funções aproximadoras polinomiais, nalguns casos podem utilizar-se outras funções, como por exemplo a função exponencial. Neste caso a função aproximadora será da forma: y = beax com a e b constantes. Ao aplicar a técnica dos mínimos quadrados, pretende-se minimizar E y be i axi i M = − = ∑( . 2 0 ) as equações normais associadas são: [ ] [ ] ∂ ∂ E b y be e i axi axi i =− − = = 2 0 ∑ 1 4 . [ ] [ ] ∂ ∂ E a y b e b xe i axi i axi i =− − = = 2 0 ∑ 1 4 . . mas não têm solução exacta. O método usualmente seguido para dados que possuam uma relação exponencial consiste em aplicar a função logaritmo à função aproximadora: y = beax ⇔ ln y = ln b + ax Acetatos das aulas teóricas de Cálculo Numérico Cecília Rodrigues 8 surgindo assim uma relação linear para ln b e a. O procedimento aplicado aquando da obtenção de uma função aproximadora linear pode agora ser aplicado, com as devidas adaptações. 
Exemplo : Considere os dados da seguinte tabela: 
i xi yi 
1 1.00 5.10 
2 1.25 5.79 
3 1.50 6.53 
4 1.75 7.45 
5 2.00 8.46 
Se se representar em eixos cartesianos os valores de xi e ln yi, verifica-se a existência de uma relação linear, o que sugere a utilização de uma função aproximadora do tipo: 
y = beax ⇔ ln y = ln b + ax 
i xi ln yi xi 2 xiln yi 
1 1.00 1.629 1.0000 1.629
2 1.25 1.756 1.5625 2.195 
3 1.50 1.876 2.2500 2.814 
4 1.75 2.008 3.0625 3.514 
5 2.00 2.135 4.0000 4.270 
∑ 7.50 9.404 11.875 14.422 
a n xy x y nx x i i i n i i n i i n i i n i i i n i = − − = == = = ∑ ∑∑ ∑ ∑ ( ) ( ).( .( ) ( ) 1 1 1 2 1 2 ) 1 b x y xy nx x i i n i i i n i i i n i i n i i n i i i n i = − − == = = x = = ∑∑ ∑∑ ∑ ∑ ( ).( ) ( ).( .( ) ( ) 1 2 111 1 2 1 2 ) obtém-se a = − − = ( )( . ) ( . )( . ) ( )( . ) ( . ) . 5 14 422 7 5 9 404 5 11875 7 5 2 0 5056 ln ( . )( . ) ( . )( . ) ( )( . ) ( . ) b = . − − = 11875 9 404 14 422 7 5 5 11875 7 5 2 1122 note-se que ln b = 1.122 ⇔ b = e1.122 = 3.071, 
pelo que a função aproximadora pretendida é y = 3.071 e1.122