Funções: Zeros, Máximos e Mínimos
Jorge Cruz
DI/FCT/UNL
Introdução aos Computadores e à Programação
1º Semestre 2005/2006
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
1
Generalização do Problema
• Um projéctil é lançado de uma altura de y0 metros, com um
ângulo inicial de lançamento de  radianos e com uma
velocidade inicial de v0 metros por segundo.
y
hmax
f(a)
v0

y0
(0,0)
a
dmax
• A trajectória do projéctil em coordenadas (x,y)xmodelada por:
y  f ( x )  x tan(θ ) 
g
x 2  y0
2
2
2v0 cos ( θ )
• Problema: determinar a distância máxima (dmax) e a altura
máxima (hmax) atingidas pelo projéctil.
• Equivalente: determinar o zero e o máximo de f(x) para x>0
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
2
Zero de uma Função
• O método de pesquisa dicotómica é um método
simples para determinar um zero de uma função f
num intervalo [xmin, xmax] sempre que o seu valor nos
extremos do intervalo tenha sinais contrários, isto é:
– f(xmin) * f(xmax) < 0.
• A ideia consiste em:
– dividir o intervalo no seu ponto médio xmed;
– verificar se este ponto é aproximadamente um zero de f:
|f(xmed)| 
(em que  é uma tolerância aceitável)
– caso xmed não seja zero de f, aplicar o método de pesquisa
dicotómica ao subintervalo:
[xmin,xmed] se f(xmin)*f(xmed)<0 ou [xmed,xmax] se f(xmed)*f(xmax)<0
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
3
Zero de uma Função
• O método de pesquisa dicotómica assume que se conhece
inicialmente o intervalo [xmin, xmax] onde:
– f(xmin) * f(xmax) < 0.
• Se f tiver mais que um zero nesse intervalo, o método apenas
calcula um dos zeros.
• Por cada iteração o intervalo de pesquisa é reduzido a metade.
• É necessário indicar um valor de tolerância
que o algoritmo termina.
 para garantir
• É possível definir como critério de paragem
alternativo/complementar um valor mínimo para o tamanho
do intervalo de pesquisa.
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
4
Zero de uma Função
• A pesquisa dicotómica pode ser definida recursivamente em
Octave pela função seguinte onde xmin e xmax representam os
extremos do intervalo de pesquisa inicial e epsilon a tolerância:
• Assume-se que a função f está definida no ficheiro f.m
function z=zerof(xmin,xmax,epsilon)
xmed=(xmin+xmax)/2;
ymed=f(xmed);
if abs(ymed)<=epsilon
% cláusula base
z=xmed;
else
% definição recursiva
if f(xmin)*ymed<0
z=zerof(xmin,xmed,epsilon);
else
z=zerof(xmed,xmax,epsilon);
endif;
endif;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
5
Zero de uma Função
• Para obter uma versão iterativa teria que se substituir a
chamada recursiva por um ciclo while que apenas termine
quando a aproximação estiver dentro da tolerância epsilon.
function z=zerof(xmin,xmax,epsilon)
xmed=(xmin+xmax)/2;
ymed=f(xmed);
while abs(ymed)>epsilon
if f(xmin)*ymed<0
xmax=xmed;
else
xmin=xmed;
endif;
xmed=(xmin+xmax)/2;
ymed=f(xmed);
endwhile;
z=xmed;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
6
Zero de uma Função
• Uma versão um pouco mais optimizada evitaria calcular
repetidamente f(xmin) para determinar o subintervalo a escolher.
• Para isso bastará manter a condição de que f(xmin) é sempre
negativo e f(xmax) sempre positivo. Assume-se que a condição é
satisfeita inicialmente.
function z=zerof(xmin,xmax,epsilon)
xmed=(xmin+xmax)/2;
ymed=f(xmed);
while abs(ymed)>epsilon
if ymed>0
xmax=xmed;
else
xmin=xmed;
endif;
xmed=(xmin+xmax)/2;
ymed=f(xmed);
endwhile;
z=xmed;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
7
Aplicação ao Programa: trajectoria
O programa principal, guardado no ficheiro “trajectoria.m”,
chama a função maximos para calcular a distância e a altura
máxima da trajectória.
A distância máxima da trajectória corresponde ao zero de f.
% Inicialização de Variáveis
y0 = input(" Qual a altura inicial (m)? ");
v0 = input(" Qual a velocidade inicial (m/s)? ");
tet = input(" Qual o angulo inicial (rad)? ");
dx = input(" Qual a precisao (m)? ");
% Cálculo dos máximos
[dmax, hmax]=maximos(y0,v0,tet,dx);
% Apresentação de Resultados
disp("Distância maxima da trajectoria (m):"); disp(dmax);
disp("Altura maxima da trajectoria (m):"); disp(hmax);
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
8
Funções: maximos e f
A função maximos detecta que o zero de f está entre os dois
últimos pontos da trajectória testados e usa a função zerof para
calcular o seu valor exacto (com uma tolerância de 0.0001).
function [dmax, hmax]=maximos(y0,v0,tet,dx);
X = [0]; Y = [y0]; i = 1;
while Y(i) > 0
i = i+1;
X(i) = X(i-1) + dx;
Y(i) = f(X(i),y0,v0,tet);
endwhile
hmax = max(Y);
dmax = zerof(X(i),X(i-1),0.0001,y0,v0,tet);
plot(X,Y);
endfunction
A função f , guardada no ficheiro “f.m”, fica igual.
function y=f(x,y0,v0,tet);
g = 9.8;
y = x*tan(tet)-(g*x^2)/(2*v0^2*cos(tet)^2)+y0;
endfunction
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
9
Função: zerof
A função zerof, que chama a função f, é alterada de modo a
considerar os parâmetros adicionais y0, v0 e tet.
function z=zerof(xmin,xmax,epsilon,y0,v0,tet)
xmed=(xmin+xmax)/2;
ymed=f(xmed,y0,v0,tet);
while abs(ymed)>epsilon
if ymed>0
xmax=xmed;
else
xmin=xmed;
endif;
xmed=(xmin+xmax)/2;
ymed=f(xmed,y0,v0,tet);
endwhile;
z=xmed;
endfunction
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
10
Máximo de uma Função
• Uma variante do método de pesquisa dicotómica também
pode ser usada para procurar o máximo de uma função f num
determinado intervalo.
• Considere o intervalo [xmin< xinter< xmax] com:
– f(xinter) > f(xmin) e
f(xinter) > f(xmax)
• O seguinte método permite encontrar no intervalo anterior um
máximo local (numa pequena vizinhança):
– escolher o maior intervalo: [xmin,xinter] ou [xinter,xmax];
– dividir o intervalo no seu ponto médio xmed;
– Se xmin<xmed<xinter aplicar o método de pesquisa ao subintervalo:
[xmin<xmed<xinter] se f(xmed)>f(xinter) ou [xmed<xinter<xmax] se f(xmed)<f(xinter)
– Se xinter<xmed<xmax aplicar o método de pesquisa ao subintervalo:
[xinter<xmed<xmax] se f(xmed)>f(xinter) ou [xmin<xinter<xmed] se f(xmed)<f(xinter)
– O algoritmo termina quando o intervalo de pesquisa
suficientemente pequeno:
xmax  xmin 
(em que  é uma tolerância aceitável)
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
é
11
Máximo de uma Função
• O método de pesquisa dicotómica assume que se conhece
inicialmente o intervalo [xmin< xinter< xmax] onde:
– f(xinter) > f(xmin) e f(xinter) > f(xmax)
• Se f tiver mais que um máximo local nesse intervalo, o
método apenas calcula um deles.
• Não há garantias que o máximo local seja um máximo
absoluto, mesmo que este exista no intervalo inicial.
• Se os três pontos forem equidistantes, por cada 2 iterações o
intervalo de pesquisa é reduzido pelo menos a metade.
• É necessário indicar um valor de tolerância  para garantir
que o algoritmo termina.
• Um método semelhante pode ser usado para calcular um
mínimo local de f.
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
12
Máximo de uma Função
•
•
A pesquisa dicotómica pode ser definida recursivamente em Octave pela
função seguinte onde xmin e xmax representam os extremos do intervalo de
pesquisa inicial, xinter o valor intermédio e epsilon a tolerância:
Assume-se que a função f está definida no ficheiro f.m
function y=maximof(xmin,xinter,xmax,epsilon)
if (xmax-xmin)<=epsilon
% cláusula base
y=f(xinter);
else
% definição recursiva
if (xinter-xmin)>(xmax-xinter)
x1=(xmin+xmax)/2; x2=xinter;
else
x1=xinter; x2=(xmin+xmax)/2;
endif
if f(x1)>f(x2)
y=maximof(xmin,x1,x2,epsilon);
else
y=maximof(x1,x2,xmax,epsilon);
endif;
endif;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
13
Máximo de uma Função
•
Para obter uma versão iterativa teria que se substituir a chamada recursiva
por um ciclo while que apenas termine quando a aproximação estiver dentro
da tolerância epsilon.
function y=maximof(xmin,xinter,xmax,epsilon)
while (xmax-xmin)>epsilon
if (xinter-xmin)>(xmax-xinter)
x1=(xmin+xmax)/2; x2=xinter;
else
x1=xinter; x2=(xmin+xmax)/2;
endif
if f(x1)>f(x2)
xinter=x1; xmax=x2;
else
xmin=x1; xinter=x2;
endif;
endwhile;
y=f(xinter);
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
14
•
•
Máximo de uma Função
Uma versão um pouco mais optimizada evitaria calcular repetidamente o
valor de f nos pontos intermédios.
Para isso bastará acrescentar um parâmetro com o valor de f no ponto
intermédio. Assume-se que o valor desse parâmetro é passado inicialmente.
function y=maximof(xmin,xinter,xmax,finter,epsilon)
while (xmax-xmin)>epsilon
if (xinter-xmin)>(xmax-xinter)
x1=(xmin+xmax)/2; x2=xinter;
f1=f(x1); f2=finter;
else
x1=xinter; x2=(xmin+xmax)/2;
f1=finter; f2=f(x2);
endif
if f1>f2
xinter=x1; xmax=x2;
else
xmin=x1; xinter=x2;
endif;
endwhile;
y=finter;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
15
Aplicação ao Programa: trajectoria
O programa principal, guardado no ficheiro “trajectoria.m”,
chama a função maximos para calcular a distância e a altura
máxima da trajectória.
A altura máxima da trajectória corresponde ao máximo de f.
% Inicialização de Variáveis
y0 = input(" Qual a altura inicial (m)? ");
v0 = input(" Qual a velocidade inicial (m/s)? ");
tet = input(" Qual o angulo inicial (rad)? ");
dx = input(" Qual a precisao (m)? ");
% Cálculo dos máximos
[dmax, hmax]=maximos(y0,v0,tet,dx);
% Apresentação de Resultados
disp("Distância maxima da trajectoria (m):"); disp(dmax);
disp("Altura maxima da trajectoria (m):"); disp(hmax);
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
16
Funções: maximos e f
A função maximos detecta que o máximo de f está entre o primeiro e o último
ponto da trajectória (sendo o 2º ponto maior que ambos) e usa a função
maximof para calcular o seu valor exacto (com uma tolerância de 0.0001).
function [dmax, hmax]=maximos(y0,v0,tet,dx);
X = [0]; Y = [y0]; i = 1;
while Y(i) > 0
i = i+1;
X(i) = X(i-1) + dx;
Y(i) = f(X(i),y0,v0,tet);
endwhile
hmax = maximof(X(1),X(2),X(i),Y(2),0.0001,y0,v0,tet);
dmax = zerof(X(i-1),X(i),0.0001,y0,v0,tet);
plot(X,Y);
endfunction
A função f , guardada no ficheiro “f.m”, fica igual.
function y=f(x,y0,v0,tet);
g = 9.8;
y = x*tan(tet)-(g*x^2)/(2*v0^2*cos(tet)^2)+y0;
endfunction
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
17
Função: maximof
A função maximof, que chama a função f, é alterada de modo a
considerar os parâmetros adicionais y0, v0 e tet.
function y=maximof(xmin,xinter,xmax,finter,epsilon,y0,v0,tet)
while (xmax-xmin)>epsilon
if (xinter-xmin)>(xmax-xinter)
x1=(xmin+xmax)/2; x2=xinter;
f1=f(x1,y0,v0,tet); f2=finter;
else
x1=xinter; x2=(xmin+xmax)/2;
f1=finter; f2=f(x2,y0,v0,tet);
endif
if f1>f2
xinter=x1; xmax=x2;
else
xmin=x1; xinter=x2;
endif;
endwhile;
y=finter;
endfunction;
3 Novembro 2005
Funções: Zeros, Máximos e Mínimos
18