Questão 4 (3.0 pontos) - Desenvolva um programa usando uma linguagem de programação (python) para implementar o algoritmo da busca da razão áurea. Faça o programa de modo que ele seja expressamente projetado para localizar um máximo. A sub-rotina deve ter as seguintes propriedades:
- Iterar até que o erro relativo fique abaixo do critério de parada ou exceda um número máximo de iterações.
- Retornar tanto o ponto ótimo x quanto o valor de
.
- Minimizar o número de cálculos do valor da função.
Fórmulas
Passo 1
O enunciado pede que eu desenvolva um programa em Python que implemente o algoritmo da busca da razão áurea (golden‑section search), projetado para localizar um máximo. As exigências explícitas são:
- Iterar até que o erro relativo fique abaixo de um critério de parada ou até atingir um número máximo de iterações.
- Retornar tanto o ponto ótimo
quanto o valor de . - Minimizar o número de cálculos do valor da função (ou seja, reutilizar avaliações quando possível).
As informações / fórmulas dadas no enunciado que vou usar (peguei do enunciado):
Também há no enunciado fórmulas relacionadas a interpolação parabólica e atualização de Newton aproximada. Entretanto, a tarefa principal é implementar a busca da razão áurea para encontrar um máximo, por isso vou focar nessa técnica e mencionar como essas fórmulas poderiam complementar o método se desejado (em passos posteriores).
Vou implementar um código bem documentado que:
- encontra um máximo dentro de um intervalo
; - usa o fator
(o mesmo que aparece na fórmula do ); - reutiliza avaliações de
para economizar chamadas; - para quando o erro relativo ficar abaixo de uma tolerância dada ou quando o número máximo de iterações for excedido;
- retorna
.
Passo 2
Entendendo a ideia por trás da busca da razão áurea (intuição passo a passo, sem pular etapas):
- A busca da razão áurea é um algoritmo de busca unidimensional que reduz iterativamente o intervalo de busca
mantendo dois pontos internos e de modo que a razão dos segmentos siga a constante . O valor de é
- Com a convenção que vou usar (a mesma que aparece no enunciado):
Note que com essa escolha temos
.
- Em cada iteração comparamos
e . Como queremos localizar um máximo: - Se
, o máximo está entre e . Logo descartamos o intervalo atual e atualizamos . - Se
, o máximo está entre e . Logo descartamos e atualizamos . - Se
(caso raro com precisão finita), podemos reduzir o intervalo por ambos os lados ou escolher uma convenção (por exemplo, atualizar ).
- Se
- O truque para minimizar avaliações de função: quando movemos os extremos, um dos pontos internos passa a ser o outro ponto interno da próxima iteração. Assim podemos reusar a avaliação correspondente. Por exemplo, se
e descartamos , então o antigo passa a ser o novo e sua avaliação é reutilizada.
Passo 3
Critério de parada (erro relativo) — definição prática e robusta:
- O enunciado pede para parar quando o erro relativo for menor que um critério. Vou usar uma definição prática e estável numericamente:
onde
é a estimativa atual do ótimo (por exemplo, o ponto com maior valor entre
e
). A razão para dividir por
é evitar divisão por números muito pequenos quando a solução está perto de zero — isso faz o critério ser relativo quando
é grande e absoluto (com denominação 1) quando
é pequeno. Paramos quando
ou quando o número de iterações excede
.
- Alternativa comum é usar
, mas prefiro a forma com para maior robustez sem pedir que você pense em normalização extra na prova.
Passo 4
Atualizações e reuso de avaliações (explicação detalhada, para você poder aplicar na prova passo a passo):
Inicializações:
- Calcule
. - Calcule
. - Calcule
e . - Avalie
e . (São as duas avaliações iniciais.)
Iteração (um ciclo):
- Compare
e . - Caso
(o lado direito interior é melhor): - Atualize
. - Mova
e (reuso da avaliação). - Recalcule
, depois . - Avalie
(apenas uma nova avaliação nesta ramificação).
- Atualize
- Caso
(o lado esquerdo interior é melhor): - Atualize
. - Mova
e . - Recalcule
, depois . - Avalie
.
- Atualize
- Caso
num sentido de igualdade com precisão finita, podemos fazer qualquer uma das atualizações acima ou reduzir ambos os lados — na implementação eu trato como só para ter comportamento determinístico, mas explico que outra convenção é aceitável.
Observações sobre mínimos de chamadas:
- Em cada iteração típica fazemos apenas UMA nova avaliação de
. As outras duas informações são preservadas por movimentação de pontos. Isso é o melhor que podemos fazer com esse método clássico.
Passo 5
Escolha da estimativa do ótimo e retorno:
- Em cada iteração podemos tomar como estimativa do ótimo o ponto com maior função entre
- Quando o critério de parada for satisfeito, retornamos feitas; eu incluo isso internamente no código (mas não é obrigatório pelo enunciado).
Passo 6
Tratamento de casos especiais e dicas práticas para a prova:
- Se o intervalo inicial
já tiver , é erro de entrada; na prova explique que é necessário garantir . - Se a função não for unimodal no intervalo, o método pode convergir para um ponto local que não seja global. Em provas normalmente assumem que a função é unimodal no intervalo dado.
- Se quiser acelerar e tiver derivadas ou puder usar interpolação parabólica, pode-se combinar golden section com um passo de interpolação parabólica (método de Brent). O enunciado incluiu a fórmula do vértice de uma parábola (uma forma de interpolação a três pontos) e a atualização de Newton aproximada. Esses podem ser usados como complemento, mas são técnicas adicionais — o golden section é estável e simples.
Passo 7
Formato da sub-rotina e parâmetros (o que entregar na prova / no programa):
- Assinatura sugerida em Python:
def golden_section_max(f, xl, xu, tol=1e-6, maxiter=100) - Entrada:
-
: função a ser maximizada (callable). -
, : limites do intervalo. - tol: tolerância do erro relativo (por exemplo
). - maxiter: número máximo de iterações.
-
- Saída:
-
: ponto estimado para o máximo. -
: valor .
-
- Propriedades implementacionais para economizar chamadas:
- Reuso de
e conforme descrito. - Evitar cópias desnecessárias.
- Contabilizar número de avaliações de
(útil na prova para mostrar economia).
- Reuso de
Passo 8
Explicação do que o código faz (linha a linha, sem repetir o código-fonte na íntegra):
- Calcula
e inicializa e . - Entra em loop até que o erro relativo definido em Passo 3 satisfaça a tolerância ou até atingir
. - Em cada iteração, faz a comparação
vs e aplica as atualizações descritas em Passo 4, fazendo apenas uma avaliação nova de . - Ao final retorna o melhor ponto entre
e e o valor da função correspondente.
Resposta
def golden_section_max(f, xl, xu, tol=1e-6, maxiter=100):
“”"
Busca da razão áurea (golden-section) para MAXIMIZAR f em [xl, xu].
“”"
Busca da razão áurea (golden-section) para MAXIMIZAR f em [xl, xu].
Parâmetros:
- f: função unidimensional (callable) que recebe um float e retorna float
- xl, xu: limites do intervalo (xl < xu)
- tol: tolerância para o erro relativo (default 1e-6)
- maxiter: número máximo de iterações (default 100)
Retorna:
- x_opt: ponto estimado do máximo
- f_opt: valor f(x_opt)
"""
import math
if xu <= xl:
raise ValueError("Necessário xu > xl")
tau = (math.sqrt(5) - 1) / 2.0 # ~0.618...
# primeiro par de pontos internos
d = tau * (xu - xl)
x1 = xl + d
x2 = xu - d
f1 = f(x1)
f2 = f(x2)
nfev = 2 # contagem de avaliações de f
# escolha inicial do estimador do ótimo
if f1 >= f2:
x_est = x1
f_est = f1
else:
x_est = x2
f_est = f2
for k in range(1, maxiter + 1):
# critério de erro relativo (robusto quando x_est perto de zero)
err_rel = (xu - xl) / max(1.0, abs(x_est))
if err_rel < tol:
break
if f1 > f2:
# máximo está no intervalo (x2, xu)
xl = x2
# desloca pontos: x2 <- x1 (reuso de f1)
x2 = x1
f2 = f1
# novo x1
d = tau * (xu - xl)
x1 = xl + d
f1 = f(x1)
nfev += 1
else:
# f1 <= f2: máximo está em (xl, x1)
xu = x1
# desloca pontos: x1 <- x2 (reuso de f2)
x1 = x2
f1 = f2
# novo x2
d = tau * (xu - xl)
x2 = xu - d
f2 = f(x2)
nfev += 1
# atualiza estimador do ótimo
if f1 >= f2:
x_est = x1
f_est = f1
else:
x_est = x2
f_est = f2
# retorno final: ponto e valor da função
return x_est, f_est