Funções: Zeros, Máximos e Mínimos

3 Novembro 2005 Funções: Zeros, Máximos e Mínimos 1

Funções: Zeros, Máximos e Mínimos

Jorge CruzDI/FCT/UNL

Introdução aos Computadores e à Programação1º Semestre 2005/2006


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.

• A trajectória do projéctil em coordenadas (x,y) modelada por:0

222

02yx

)θ(cosv

g)θtan(x)x(fy

• 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

v0

(0,0)x

y

y0

a

f(a)

dmax

hmax


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


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 para garantir que o algoritmo termina.

• É possível definir como critério de paragem alternativo/complementar um valor mínimo para o tamanho do intervalo de pesquisa.


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;


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;


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;


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 Resultadosdisp("Distância maxima da trajectoria (m):"); disp(dmax);disp("Altura maxima da trajectoria (m):"); disp(hmax);


Funções: maximos e fA 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


Função: zerofA 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


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)


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.


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;


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;


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;


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 Resultadosdisp("Distância maxima da trajectoria (m):"); disp(dmax);disp("Altura maxima da trajectoria (m):"); disp(hmax);


Funções: maximos e fA 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


Função: maximofA 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;

Documents

Funções: Zeros, Máximos e Mínimos