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 \mathrm{f}(\mathrm{x}).
  • Minimizar o número de cálculos do valor da função.
Fórmulas
\begin{aligned} d & =\frac{\sqrt{5}-1}{2}\left(x_{u}-x_{l}\right) \\\ x_{1} & =x_{l}+d \\\ x_{2} & =x_{u}-d \\\ & \quad x^{\#}=\frac{1}{2} \frac{\left(x_{2}^{2}-x_{3}^{2}\right) S\left(x_{1}\right)+\left(x_{3}^{2}-x_{1}^{2}\right) S\left(x_{2}\right)+\left(x_{1}^{2}-x_{2}^{2}\right) S\left(x_{3}\right)}{\left(x_{2}-x_{3}\right) S\left(x_{1}\right)+\left(x_{3}-x_{1}\right) S\left(x_{2}\right)+\left(x_{1}-x_{2}\right) S\left(x_{3}\right)} \\\ x^{k+1} & =x^{k}-\frac{f^{\prime}\left(x^{k}\right)}{f^{\prime \prime}\left(x^{k}\right)} \cong x^{k}-\frac{[f(x+h)-f(x-h)] / 2 h}{[f(x+h)-2 f(x)+f(x-h)] / h^{2}} \end{aligned}

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 x quanto o valor de f(x).
  • 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):
d = \frac{\sqrt{5}-1}{2}\left(x_u-x_l\right)
x_1 = x_l + d
x_2 = x_u - d
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 [x_l,x_u];
  • usa o fator \tau = \dfrac{\sqrt{5}-1}{2} (o mesmo que aparece na fórmula do d);
  • reutiliza avaliações de f 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 (x_{\text{opt}}, f(x_{\text{opt}})).

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 [x_l,x_u] mantendo dois pontos internos x_2 e x_1 de modo que a razão dos segmentos siga a constante \tau. O valor de \tau é
\tau = \frac{\sqrt{5}-1}{2}\approx 0{,}6180339887.
  • Com a convenção que vou usar (a mesma que aparece no enunciado):
x_1 = x_l + d,\qquad x_2 = x_u - d,\qquad d = \tau (x_u-x_l).
Note que com essa escolha temos x_l < x_2 < x_1 < x_u.
  • Em cada iteração comparamos f(x_1) e f(x_2). Como queremos localizar um máximo:
    • Se f(x_1)>f(x_2), o máximo está entre x_2 e x_u. Logo descartamos o intervalo [x_l,x_2] atual e atualizamos x_l\leftarrow x_2.
    • Se f(x_1)<f(x_2), o máximo está entre x_l e x_1. Logo descartamos [x_1,x_u] e atualizamos x_u\leftarrow x_1.
    • Se f(x_1)=f(x_2) (caso raro com precisão finita), podemos reduzir o intervalo por ambos os lados ou escolher uma convenção (por exemplo, atualizar x_l\leftarrow x_2,\;x_u\leftarrow x_1).
  • 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 f(x_1)>f(x_2) e descartamos [x_l,x_2], então o antigo x_1 passa a ser o novo x_2 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:
\text{erro\_rel} \equiv \frac{x_u-x_l}{\max(1,|x_{\text{est}}|)}
onde x_{\text{est}} é a estimativa atual do ótimo (por exemplo, o ponto com maior valor entre x_1 e x_2). A razão para dividir por \max(1,|x_{\text{est}}|) é evitar divisão por números muito pequenos quando a solução está perto de zero — isso faz o critério ser relativo quando |x_{\text{est}}| é grande e absoluto (com denominação 1) quando |x_{\text{est}}| é pequeno. Paramos quando
\text{erro\_rel} < \text{tol}
ou quando o número de iterações excede \text{maxiter}.
  • Alternativa comum é usar (x_u-x_l)/|x_{\text{est}}|, mas prefiro a forma com \max(1,|x_{\text{est}}|) 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 \tau=\dfrac{\sqrt{5}-1}{2}.
  • Calcule d=\tau (x_u-x_l).
  • Calcule x_1=x_l+d e x_2=x_u-d.
  • Avalie f_1=f(x_1) e f_2=f(x_2). (São as duas avaliações iniciais.)
Iteração (um ciclo):
  1. Compare f_1 e f_2.
  2. Caso f_1>f_2 (o lado direito interior é melhor):
    • Atualize x_l \leftarrow x_2.
    • Mova x_2 \leftarrow x_1 e f_2 \leftarrow f_1 (reuso da avaliação).
    • Recalcule d=\tau (x_u-x_l), depois x_1 = x_l + d.
    • Avalie f_1 = f(x_1) (apenas uma nova avaliação nesta ramificação).
  3. Caso f_1<f_2 (o lado esquerdo interior é melhor):
    • Atualize x_u \leftarrow x_1.
    • Mova x_1 \leftarrow x_2 e f_1 \leftarrow f_2.
    • Recalcule d=\tau (x_u-x_l), depois x_2 = x_u - d.
    • Avalie f_2 = f(x_2).
  4. Caso f_1=f_2 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 f_1>f_2 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 f. 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 x_1\) e \(x_2\): \[x_{\text{est}} = \begin{cases} x_1 & \text{se } f_1 \ge f_2,\\\ x_2 & \text{caso contrário.} \end{cases}
  • Quando o critério de parada for satisfeito, retornamos (x_{\text{est}}, f(x_{\text{est}}))\]. No código vamos retornar explicitamente ambos. - Também é útil, para diagnóstico, retornar o número de avaliações de \(f 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 [x_l,x_u] já tiver x_u\le x_l, é erro de entrada; na prova explique que é necessário garantir x_u>x_l.
  • 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:
    • f: função a ser maximizada (callable).
    • x_l, x_u: limites do intervalo.
    • tol: tolerância do erro relativo (por exemplo 1\mathrm{e}{-6}).
    • maxiter: número máximo de iterações.
  • Saída:
    • x_{\text{opt}}: ponto estimado para o máximo.
    • f_{\text{opt}}: valor f(x_{\text{opt}}).
  • Propriedades implementacionais para economizar chamadas:
    • Reuso de f_1 e f_2 conforme descrito.
    • Evitar cópias desnecessárias.
    • Contabilizar número de avaliações de f (útil na prova para mostrar economia).

Passo 8

Explicação do que o código faz (linha a linha, sem repetir o código-fonte na íntegra):
  • Calcula \tau e inicializa x_1,x_2 e f_1,f_2.
  • Entra em loop até que o erro relativo definido em Passo 3 satisfaça a tolerância ou até atingir \text{maxiter}.
  • Em cada iteração, faz a comparação f_1 vs f_2 e aplica as atualizações descritas em Passo 4, fazendo apenas uma avaliação nova de f.
  • Ao final retorna o melhor ponto entre x_1 e x_2 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].
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

Exercícios relacionados