Baixe o app para aproveitar ainda mais
Prévia do material em texto
Universidade Federal do Maranhão - UFMA Bacharelado Interdisciplinar em Ciência e Tecnologia Camila Ferreira dos Santos Mariana Andressa Luna Pinheiro Professor Dr Kênio Cálculo Numérico Segundo Trabalho Prático São Luís - MA 2016 2 RESUMO Neste trabalho buscou-se confirmar o fenômeno de Runge na função 𝑓(𝑥) = 1 1 + 25 𝑥2 mostrando graficamente a divergência nos extremos da aproximação por polinômio de Lagrange. Aplicou- se o método de splines tanto linear quanto cúbica para diferentes quantidades de partições do intervalo. 3 SUMÁRIO 1. Introdução………………………………………………………………………………….......4 2. Referencial Teórico……………………………………………………………………….........5 2.1 Polinômio de Lagrange………………………………………………………………..5 2.2 Spline Linear………………………………………………………………………......5 2.3 Splines Cúbicas………………………………………………………………………..5 3. Algoritmos………………………………………………………………………………….......5 3.1 Algoritmo para polinômio de Langrange………………………………………...……5 3.2 Algoritmo para Spline Linear…………………………………………………………8 3.3 Algoritmo para Spline Cúbica…………………………………………………….…10 3.4 Função Erro………………………………………………………………………..…17 4. Resultados e discussões…………………………………………………………………….....17 4.1 Para k = 5………………………………………………………………………….…18 4.1.1 Lagrange…………………………………………………………………...18 4.1.2 Spline Linear………………………………………………………….……19 4.1.3 Spline Cúbica………………………………………………………………20 4.2 Para k = 10……………………………………………………………………...……21 4.2.1 Lagrange…………………………………………………………..……….21 4.2.2 Spline Linear……………………………………………………………….22 4.2.3 Spline Cúbica……………………………………………………………....23 4.3 Para k = 20…………………………………………………………………..……….24 4.3.1 Lagrange…………………………………………………………………...24 4.3.2 Spline Linear……………………………………………………….………25 4.3.3 Spline Cúbica………………………………………………………..……..26 5. Conclusão……………………………………………………………………………...……...27 6. Bibliografia…………………………………………………………………………...……....27 4 1. Introdução Ao estudar erros de interpolação por funções polinomiais, Carle D. T. Runge propôs a seguinte função 𝑓(𝑥) = 1 1 + 25 𝑥2 , 𝑥 ∈ [−1, 1] verificando que uma sequência de polinômios interpolantes obtida a partir de pontos de interpolação igualmente espaçados não converge quando 𝑥está nos extremos de seu intervalo, mais precisamente quando 𝑥 ∈ (−1, −0.727) ⋃(0.727, 1) De fato, é possível demonstrar que 𝑙𝑖𝑚 𝑛→+∞ 𝑚𝑎𝑥|𝑓(𝑥) − 𝑝𝑛(𝑥)| = +∞ para −1 ≤ 𝑥 ≤ 1 Já que, supondo 𝑓 uma função contínua e 𝑛 vezes diferenciável no intervalo (𝑎, 𝑏), no qual estão contidos os pontos 𝑥𝑖, com 𝑖 = 1, 2, . . . , 𝑛 e seja 𝑝 o polinômio de grau 𝑛 − 1 que interpola a função nestes pontos, então existe 𝜁(𝑥) ∈ (𝑎, 𝑏) tal que 𝑓(𝑥) − 𝑝(𝑥) = 1 𝑛! 𝑓(𝑛)(𝜁) ∏(𝑥 − 𝑥𝑖) 𝑛 𝑖 = 1 o comportamento irregular é proveniente do produtório, que apresenta valores flutuantes quando 𝑥 está próximo à fronteira do intervalo (−1, 1), aumentando à medida que se amplia a quantidade de pontos, caso estes sejam igualmente espaçados. 5 2. Referencial Teórico 2.1 Polinômio de Lagrange No que diz respeito à interpolação de funções com polinômios, o polinômio de Lagrange é amplamente empregado. Estes polinômios fazem ajuste de um conjunto tabelado de pontos da seguinte maneira 𝑝(𝑥) = ∑ 𝑦𝑖 𝑛 𝑖 = 1 ∏ (𝑥 − 𝑥𝑗) (𝑥𝑖 − 𝑥𝑗) 𝑛 𝑗 = 1 𝑗 ≠ 𝑖 onde 𝑦𝑖 é o valor da função em 𝑥𝑖. Este tipo de interpolação, que não requer nenhum cálculo preliminar para os coeficientes, e que pode ser implementado facilmente em programas de computador é bastante útil e eficiente. Entretanto, quando ocorre o fenômeno de Runge, a aproximação por este método se mostra precária nos extremos, sendo necessário recorrer a outras técnicas de aproximação. 2.2 Spline Linear Interpolação de pontos por métodos como de Newton ou Lagrange fornecem polinômios com grau 𝑛 − 1 quando são fornecidos 𝑛 pontos. E aproximam bem quando 𝑛 é pequeno, e assim, a ordem do polinômio interpolador é baixa. No entanto, quando 𝑛 aumenta, é mais preciso aproximar a função por diversos polinômios de grau baixo que por um polinômio de grau alto. Esta é a ideia geral das funções spline, ou interpolação por partes. A função spline linear aproxima a função por diversas retas: a cada dois pontos tabelados há uma reta que os liga. Assim, para diversos pontos a aproximação é razoável. 2.3 Splines Cúbicas Seguindo o mesmo princípio da spline linear, a versão cúbica liga três pontos por uma função de terceiro grau. Por ser um conjunto de funções de grau mais elevado, as exigências são também mais rigorosas. É exigido que as derivadas de até segunda ordem sejam contínuas, para que formem uma curva suave. Para maior simplicidade, pode-se adotar a aproximação nos pontos extremos por funções lineares, assim, suas segundas derivadas são nulas e o sistema a ser resolvido é de ordem 𝑛 − 2. Este caso é chamado spline natural. 3. Algoritmos 3.1 Algoritmo para o polinômio de Lagrange Inicialmente pedimos que o usuário insira o grau do polinômio a ser estudado ( nesse trabalho foram utilizados 5, 10 e 20) e calculamos os valores de x, x é o ponto nos intervalos 6 dados (n = m+1), os valores de alpha, alpha é a segmentção no intervalo dado na questão (m=51) e os valores de f(x). Em seguida com os conceitos mostrados anteriormente de Polinômio de Lagrange, calculamos a função polinomial e encontramos o erro máximo entre os pontos com relação a função dada. fprintf('Fenomeno de Runge \n') fprintf('Considere a funçao f(x) = 1/( 1 + 25x^2) e o intervalo[a,b] = [-5,5], igualmente espaçados.\n') k = input('Informe o grau do polinomio a ser estudado: '); n = k + 1; x = zeros(1,n); aux = 0; % Segmentaçao dos valores de x de acordo com o grau do poliniomio informado. for i = 1:1:n x(i) = -5 + (10*aux)/k; aux = aux +1; end %Avaliação dos valores da função f(x) no intervalo x. f = (1)./( 1 + 25*x.^2); %Utilização do polinômio de Lagrange. L = zeros(n,n); % A matriz L armazena os valores da forma de Lagrange for i=1: 1: n v = 1; for j=1 :1 :n if i ~= j v = conv(v,poly(x(j)))/(x(i) - x(j)); 7 end end L(i,:) = v; end %Cálculo dos coficientes do polinomio de grau (n-1) %O vetor C é o vetor de coeficientes do polinomio de lagrange C = f*L; %Segementação do intervalo alpha = zeros(1,51); aux = 0; for i=1:1:51 alpha(i) = -5 + 0.2*aux; aux = aux +1; end %Avaliação dos valores da função no intervalo alpha. q = (1)./(1 + 25*alpha.^2); %Avaliação dos valores do polinômio no intervalo alpha. p = polyval(C,alpha); fprintf('Os valores de x utilizados na interpolação é: \n'); disp(x); fprintf('E os valores da função utilizados: \n'); disp(f); 8 fprintf('Os coeficientes do polinomio de Lagrange interpoladoré: \n'); disp(C); %Chamada da funçao erro. [w,i] = funcaoerro(q,p); fprintf('O maior erro cometido é de aproximadamente: %.4f \n',w); %Plotagem dos pontos da função, do polinômio interpolador e do ponto onde o erro é máximo. plot(alpha,q,'b:p',alpha,p,'r:p',alpha(i),p(i),'mO'); 3.2 Algoritmo para a Spline Linear Aqui, semelhante ao caso anterior calculamos inicialmente o alpha (m = 51), os pontos x e os valores de f(x). Em seguida utilizamos os conceitos aprendidos no tópico anterior para Spline Linear e encontrar os coeficientes do polinômio. % Spline Linear fprintf('Considere a funçao f(x) = 1/( 1 + 25x^2) e o intervalo[a,b] = [-5,5], igualmente espaçados.\n') k = input('Informe o grau do polinomio a ser estudado: '); n = k + 1; x = zeros(1,n); aux = 0; % Segmentaçao dos valores de x de acordo com o grau do poliniomio informado. for i = 1:1:n x(i) = -5 + (10*aux)/k; aux = aux +1; end alpha = zeros(1,51); 9 aux = 0; for i=1:1:51 alpha(i) = -5 + 0.2*aux; aux = aux +1; end %O vetor x sao os valores do intervalo %O vetor y sao os valores da funçao tabela %Alpha é o valor, ou conjunto de valores, a serem interpolados y = (1)./( 1 + 25*x.^2); n = length(x); L = zeros(2,n-1); %Matriz dos coeficientes das (n-1) splines for i=1:1:n-1 L(1,i) = ( ( y(i+1) - y(i) ) / ( x(i+1) - x(i))); L(2,i) = ( ( y(i)*x(i+1) - y(i+1)*x(i)) / ( x(i+1) - x(i))); end % Interpolação do valor a ser fornecido m = length(alpha); Beta = zeros(1,51); for i=2:1:n for j=1:1:51 if ( alpha(j) >= x(i-1) ) if (alpha(j) <= x(i)) Beta(j) = L(1,i-1)*alpha(j) + L(2,i-1); 10 end end end end %Avaliação dos valores da função no intervalo alpha. q = (1)./(1 + 25*alpha.^2); %Avaliação dos valores do polinômio no intervalo alpha. fprintf('Os valores de x utilizados na interpolação é: \n'); disp(x); fprintf('E os valores da função utilizados: \n'); disp(y); fprintf('Os coeficientes do polinomio de L spline é: \n'); disp(Beta); %Chamada da funçao erro. [w,i] = funcaoerro(q,Beta); fprintf('O maior erro cometido é de aproximadamente: %.4f \n',w); %Plotagem dos pontos da função, do polinômio interpolador e do ponto onde o erro é máximo. plot(alpha,q,'b:p',alpha,Beta,'r:p',alpha(i),Beta(j),'mO'); 3.3 Algoritmo para a Spline Cúbica Inicialmente foi obtido o alpha, o x e o f(x) semelhante aos algorítmos anteriores. Para resolver as matrizes da spline cúbica foi utilizado o Algorítmo de Thomas (ou Algoritmo de matriz tridiagonal), um método algébrico que consiste numa simplificação da Eliminação Gaussiana para resolução de sistemas de equações tridiagonais. Finalizando com o cálculo do erro e a plotagem dos pontos. % Spline cúbica 11 fprintf('Considere a funçao f(x) = 1/( 1 + 25x^2) e o intervalo[a,b] = [-5,5], igualmente espaçados.\n') k = input('Informe o grau do polinomio a ser estudado: '); n = k + 1; x = zeros(1,n); aux = 0; % Segmentaçao dos valores de x de acordo com o grau do poliniomio informado. for i = 1:1:n x(i) = -5 + (10*aux)/k; aux = aux +1; end alpha = zeros(1,51); aux = 0; for i=1:1:51 alpha(i) = -5 + 0.2*aux; aux = aux +1; end y = (1)./( 1 + 25*x.^2); %function Beta = Spline_Cubica(x,y,alpha) % Os parametros da função Spline Cúbica são: % Vetor x e y dos valores %Valor/ ou conjunto de valores alpha apara serem aproximados %Beta é a matriz de valores a ser retornado 12 n = length(x); %Determinação do vetor de espaçamento h h = zeros(1,n-1); for i=1:1:n-1 h(i) = x(i+1)-x(i); end %Determinação da matriz A dos coeficientes L = zeros(n-2,n-2); for i=1:1:n-2 for j=1:1:n-2 if ( i == j) L(i,i) = 2*( h(i) + h(i+1)); elseif ( i > j) L(i,i-1) = h(i); else L(i,i+1) = h(i+1); end end end %Determinaçao da matriz de valores b d = zeros(n-2,1); for i=1:1:n-2 phi = ( y(i+2) - y(i+1))/h(i+1); 13 gama = ( y(i+1) - y(i))/h(i); d(i) = 6*( phi - gama); end %Algoritmo de matriz tridiagonal %Separação das três diagonais principais em três vetores colunas. a = zeros(n-2,1); for i=2:1:n-2 a(i) = L(i,i-1); end b = zeros(n-2,1); for i=1:1:n-2 b(i) = L(i,i); end c = zeros(n-2,1); for i=1:1:n-3 c(i) = L(i,i+1); end %Eliminaçao da matriz for i=1:1:n-2 if (i==1) c(i) = c(i)/b(i); d(i) = d(i)/b(i); 14 else zeta = b(i) - c(i-1)*a(i); c(i) = c(i)/zeta; d(i) = ( d(i) - d(i-1)*a(i))/zeta; end end %Retro- Substituição u = zeros(n-2,1); u(n-2) = d(n-2); for i=(n-3) : -1 :1 u(i) = d(i) - c(i)*u(i+1); end % Passagem dos valores da soluçao para um vetor com n colunas(ao invés de % n-2), pois os coeficientes dos extremos são nulos g = zeros(n,1); for i=1:1:n if i==1 g(i) = 0; elseif i == n g(i) = 0; else g(i) = u(i-1); 15 end end %Considerando uma funçao cúbica da forma: f(x) = (k(1))*x^3 + (k(2))*x^2 + %(k(3))*x + k(4) k = zeros(4,n-1); for i=1:1:n-1 k(1,i) = ( g(i+1) - g(i))/(6*h(i)); k(2,i) = g(i+1)/2; phi =(y(i+1) - y(i))/h(i); gama = (h(i)*(2*g(i+1) + g(i)))/6; k(3,i) = phi + gama; k(4,i) = y(i+1); end %Aproximação dos valores pela Spline Cúbica %Aplha é o valor a ser aproximado m = length(alpha); %Uma boa ídeia :) (51) Beta = zeros(1,m); 16 for i=2:1:n for j=1 :1:m if alpha(j) >= x(i-1) if alpha(j) <= x(i) Beta(1,j) = k(1,i-1)*(alpha(j)-x(i)).^3 + k(2,i-1)*(alpha(j)-x(i)).^2 + k(3,i-1)*(alpha(j)-x(i)) + k(4,i-1); end end end end %Avaliação dos valores da função no intervalo alpha. q = (1)./(1 + 25*alpha.^2); %Avaliação dos valores do polinômio no intervalo alpha. fprintf('Os valores de x utilizados na interpolação é: \n'); disp(x); fprintf('E os valores da função utilizados: \n'); disp(y); fprintf('Os coeficientes do polinomio de L spline é: \n'); disp(Beta); %Chamada da funçao erro. [w,i] = funcaoerro(q,Beta); fprintf('O maior erro cometido é de aproximadamente: %.4f \n',w); %Plotagem dos pontos da função, do polinômio interpolador e do ponto onde o erro é máximo. plot(alpha,q,'b:p',alpha,Beta,'r:p',alpha(i),Beta(j),'mO'); 17 3.4 Função erro Aqui o algoritmo mostrado abaixo foi utilizado nostrês casos anteriores para encontrar o erro máximo entre a função polinomial e a função dada. function [delta,I] = Erro(q,p) % O vetor q contem os valores da função. %O vetor p contem os valores do polinômio. %M é a quantidade de dados a serem comparados. m = length(q); delta = 0; for i=1:1:m aux = abs(q(i) - p(i)); if aux > delta delta = aux; I = i; end end end 4.Resultados e discursões Considerando a função 𝑓(𝑥) = 1 1+25𝑥² e o intervalo [a,b] = [-5,5]. O objetivo deste trabalho foi constatar o fenômeno de Runge e usar spline linear e spline cúbica para comparar com o polinômio de Lagrange. Foram considerados: Pn(x): polinômio de grau k que interpola 𝑓(𝑥) em 𝑥0, 𝑥1, . . . , 𝑥𝑘 S1(x): spline linear interpolante em 𝑥0, 𝑥1, . . . , 𝑥𝑘 S3(x): spline cúbica interpolante em 𝑥0, 𝑥1, . . . , 𝑥𝑘 18 onde 𝑥0, 𝑥1, . . . , 𝑥𝑘 são (k+1) pontos igualmente espaçados no intervalo [-5,5]. realizou-se 3 conjuntos de testes, fez-se k assumir os valores 5, 10 e 20, em cada teste e calculou-se: De acordo com os resultados obtidos apartir dos algoritmos (MATLAB), foi permitido fazer uma análise gráfica, onde as estrelas em vermelho representa o polinômio interpolador e as estrelas em azul representa a função em 𝑓(𝑥). 4.1 Para k = 5 4.1.1 Polinômio de Lagrange A figura abaixo representa o comand windows do MATLAB retornada pelo código em questão, onde é mostrado os valores de x (x = 𝑧𝑖= -5 + 0.2i) e os valores de 𝑝(𝑥) e 𝑓(𝑥), calculados com os valores de x obtidos. O valor máximo de erro obtido, de acordo com o solicitado em questão, foi de 0.9558 Figura 1 Resultados obtidos pelo algoritmo para Lagrange Fonte: MATLAB 19 Figura 2 Gráfico de Lagrange dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.1.2 Spline Linear Os resultados obtidos para spline linear não foram satisfatórios visto que a diferença entre este erro com o erro obtido em Lagrange foi muito pequeno. Figura 3 Resultados obtidos pelo algoritmo para Spline Linear Fonte: MATLAB 20 Figura 4 Gráfico de Spline Linear dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.1.3 Spline Cúbica Ainda nesse método como no anterior não observou-se vantagem comparada a forma de Lagrange. Em todos os métodos houve divergência entre os pontos [-1,1] Figura 5 Resultados obtidos pelo algoritmo para Spline Cúbica Fonte: MATLAB 21 Figura 6 Gráfico de Spline Cúbica dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.2 Para k = 10 4.2.1 Polinômio de Lagrange Para o k = 10 o erro obtido pelo código aumentou significamente para este método. Figura 7 Resultados obtidos pelo algoritmo para Lagrange Fonte: MATLAB Abaixo podemos ver que a função polinômio interpoladora não se comportou próxima a f(x). 22 Figura 8 Gráfico de Lagrange dos valores da função 𝑓(𝑥) 4.2.2 Spline Linear Podemos observar aqui que o erro diminui bastante em relação ao anterior. Figura 9 Resultados obtidos pelo algoritmo para Spline Linear. Fonte: MATLAB 23 Figura 10 Gráfico de Spline Linear dos valores da função 𝑓(𝑥) Fonte: MATLAB A plotagem dos pontos também apresenta uma aproximação visual, mostrando o porque do erro ter diminuido. 4.2.3 Spline cúbica O erro aqui também apresentou uma diminuição em relação ao anterior. O maior erro é visto entre o intervalo [-2,2]. O gráfico apresentou uma aproximação visivél. Figura 11 Resultados obtidos pelo algoritmo para Spline Cúbica Fonte: MATLAB 24 Figura 12 Gráfico de Spline Cúbica dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.3 Para k = 20 4.3.1 Polinômio de Lagrange Para k igual à 20, o polinômio de Lagrange apresentou um erro super elevado em relação aos anteriores e o seu comportamento no gráfico não se aproximou da função, divergindo bastante. Figura 13 Resultados obtidos pelo algoritmo para Lagrange Fonte: MATLAB 25 Figura 14 Gráfico de Lagrange dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.3.2 Spline Linear O erro cometido foi ainda menor neste caso. O intervalo onde apresentava um maior erro, ocorreu uma melhor aproximação, com um erro quase homogêneo perto da origem. Figura 15 Resultados obtidos pelo algoritmo para Spline Linear Fonte: MATLAB 26 Figura 16 Gráfico de Spline Linear dos valores da função 𝑓(𝑥) Fonte: MATLAB 4.3.3 Spline Cúbica Na cúbica o erro diminiu um pouco em relação ao anterior. Figura 17 Resultados obtidos pelo algoritmo para Spline Cúbica Fonte: MATLAB 27 Figura 18 Gráfico de Spline Cúbica dos valores da função 𝑓(𝑥) Fonte: MATLAB 5. Conclusão De acordo com o gráfico apresentado para o polinômio interpolador de Lagrange, temos comprovado o fenômeno de Runge, já que à medida que aumenta a quantidade de pontos num intervalo [a, b], aumenta o erro nos pontos extremos do intervalo e melhora a aproximação nos pontos centrais. Isto é justificado pela fórmula do erro, em que os pontos extremos do intervalo faz com que o fator (𝑥 − 𝑥0)· · ·(𝑥 − 𝑥𝑛) seja grande. Desta forma, o polinômio interpolador não é indicado para extrapolar valores, isto é aproximar valores que não pertencem ao intervalo [𝑥0, 𝑥𝑛]. Mais ainda, observa-se que o emprego da interpolação por partes se fez bastante útil neste caso, de ordem cúbica e especialmente linear, que apresentou uma melhor aproximação visível em relação a cúbica e também um menor erro. 6. Bibliografia RUGGIERO, M. A. G., LOPES, V. L. R., Cálculo númerico: aspectos teóricos e computacionais. 2ª Ed. Pearson, São Paulo, 1996. GILAT, A. e SUBRAMANIAM, V. “Métodos Numéricos para Engenheiros e Cientistas – Uma introdução com aplicações usando o MATLAB”, 1a Ed. , Editora Bookman, 2008.
Compartilhar