6 Discuta as vantagens e as desvantagens da busca da razão áurea, da interpolação quadrática e do método de Newton para localizar o valor ótimo em uma dimensão.

Passo 1

O enunciado pede que eu discuta vantagens e desvantagens de três métodos para localizar um extremo (valor ótimo) em uma variável: a busca da razão áurea, a interpolação quadrática e o método de Newton.
Informações/condições implícitas que devemos considerar (listadas):
  • Os três métodos são usados para achar mínimo (ou máximo) unidimensional de uma função real.
  • Precisamos comparar: requisitos (derivadas, unimodalidade), robustez (garantia de convergência global/local), velocidade de convergência (ordem), custo por iteração (avaliações de função/derivadas), sensibilidade a ruído/inflação numérica e comportamento prático (quando é indicado usar cada um).
  • Não há dados numéricos concretos; é uma análise conceitual.

Passo 2

Explicando e analisando a busca pela razão áurea (golden-section search): como funciona e por que é confiável.
  • Ideia básica: suponha que a função f é unimodal num intervalo [a,b] (tem apenas um mínimo nesse intervalo). A busca reduz o intervalo onde o mínimo pode estar, avaliando f em dois pontos internos e descartando a subparte que não contém o mínimo. Repetindo, o intervalo vai encolhendo até chegar próximo do mínimo.
  • Constante usada: \varphi = \dfrac{\sqrt{5}-1}{2}\approx 0,618. Após cada iteração o tamanho do intervalo é reduzido por um fator \varphi. Mais precisamente, se L_0=b-a então, depois de k iterações, L_k = \varphi^k L_0. Isso dá uma redução linear do comprimento do intervalo.
  • Requisitos: só precisa de avaliações de f e que f seja unimodal no intervalo inicial. Não usa derivadas.
  • Vantagens (por que você pode gostar dela na prova):
    • Robustez: garante convergência para o mínimo dentro do intervalo se a função for unimodal.
    • Simplicidade: regra fixa de pontos internos, fácil de implementar à mão em prova.
    • Baixo custo por iteração: apenas uma nova avaliação de f por iteração (após as duas iniciais).
    • Não precisa de derivadas e funciona bem com funções ruidosas ou sem expressão analítica.
  • Desvantagens (limitações):
    • Convergência lenta (linear): reduz o intervalo de forma constante, não acelera quando está perto do mínimo.
    • Requer unimodalidade no intervalo inicial; se houver múltiplos mínimos, a técnica pode levar ao mínimo “errado”.
    • Não aproveita informação da curvatura da função (poderia convergir bem mais rápido se soubesse derivadas).
  • Quando usar: quando você tem pouca informação (não há derivadas), função cara de avaliar mas unimodal, ou quando quer método confiável e simples.

Passo 3

Explicando a interpolação quadrática (parabolic interpolation): ideia, fórmula da parábola e comportamento.
  • Ideia básica: pegue três pontos (x_1,f_1),(x_2,f_2),(x_3,f_3) com x_1<x_2<x_3 que “cercam” o mínimo; ajuste uma parábola que passa por esses três pontos e estime o mínimo como o vértice dessa parábola. Se a parábola for boa aproximação local, o vértice dá um próximo ponto estimado muito perto do mínimo real.
  • Fórmula do vértice: se a parábola ajustada tem forma p(x)=ax^2+bx+c, o vértice (abscissa do mínimo) é
x^* = -\dfrac{b}{2a}.
Na prática, você calcula a,b a partir dos três pares (x_i,f_i) (p. ex. via forma de Lagrange) e obtém x^*.
  • Requisitos: função razoavelmente suave e que os três pontos contem informação suficiente; geralmente assume unimodalidade local.
  • Vantagens:
    • Potencial de convergência muito mais rápida que a razão áurea se a função for bem aproximada por uma parábola perto do mínimo. Pode chegar a convergência superlinear ou até quadrática localmente quando o ajuste é bom.
    • Usa apenas avaliações de função (não exige derivadas explícitas), então é útil quando derivadas são difíceis de obter.
    • Em prática é mais rápido em número de avaliações que métodos puramente lineares quando a curva é suave.
  • Desvantagens:
    • Instabilidade: se os três pontos forem quase colineares ou se os valores f_i tiverem ruído, o ajuste pode produzir um vértice fora do intervalo plausível ou um valor ruim.
    • Não é garantido convergir globalmente; pode “saltar” para regiões ruins.
    • Requer cuidado em escolher/atualizar os três pontos; implementações práticas combinam interpolação quadrática com um método robusto (por exemplo, método de Brent) para garantir segurança.
  • Em prova: explique o passo de ajustar a parábola e calcular x^*. Mostre que funciona muito bem quando a função tem formato “quase quadrático” perto do mínimo (ex.: f(x)=(x-2)^2 a parábola é exata e o método chega ao mínimo imediatamente).

Passo 4

Explicando o método de Newton para otimização unidimensional: fórmula, condição de aplicação e propriedades.
  • Ideia básica: usamos a expansão em série de Taylor de f em torno de x_k até a segunda ordem e escolhemos o ponto crítico da aproximação quadrática como próxima iteração. A aproximação da Taylor:
f(x)\approx f(x_k)+f'(x_k)(x-x_k)+\tfrac{1}{2}f''(x_k)(x-x_k)^2.
O mínimo dessa aproximação é obtido anulando a derivada: f'(x_k)+f''(x_k)(x-x_k)=0, daí
x_{k+1} = x_k - \dfrac{f'(x_k)}{f''(x_k)}.
  • Requisitos: f deve ser duas vezes diferenciável; é necessário calcular (ou aproximar) f' e f''.
  • Vantagens:
    • Convergência local muito rápida: quando a aproximação quadrática é boa (ou seja, quando você está suficientemente perto do mínimo) o método tem ordem de convergência quadrática — o erro se reduz aproximadamente ao quadrado a cada iteração. Isso significa que em poucas iterações chega muito próximo do mínimo.
    • Em exemplos simples (por exemplo f(x)=(x-2)^2), uma iteração de Newton leva diretamente ao mínimo: aqui f'(x)=2(x-2), f''(x)=2, então x_{k+1}=x_k-(2(x_k-2))/2=2.
  • Desvantagens:
    • Dependência de derivadas: requer f''(x_k)\neq 0. Se f'' estiver próxima de zero (ponto de inflexão), o passo pode explodir.
    • Convergência local, não global: se o palpite inicial estiver longe do mínimo, o método pode divergir ou convergir para um ponto indesejado.
    • Custo por iteração: avaliar f' e f'' (analiticamente ou por diferenças finitas) é custoso; diferenças finitas aumentam o ruído e exigem mais avaliações de f.
    • Sensível a ruído: pequenas flutuações nos valores das derivadas podem causar passos ruins.
  • Prática: usa-se Newton quando se tem fórmulas analíticas das derivadas ou quando se pode calcular f' e f'' com custo baixo e quando se pode garantir um chute inicial razoável. Em otimização multivariada, versões com Hessiano modificados (para garantir positividade) são comuns — análogo unidimensional é ajustar f'' para evitar divisão por números pequenos.

Passo 5

Comparação direta (velocidade, custo, robustez) e recomendações práticas para cada situação de prova/uso.
  • Ordem de convergência (resumo):
    • Busca da razão áurea: convergência linear (fator \approx 0,618 por iteração no comprimento do intervalo).
    • Interpolação quadrática: geralmente superlinear quando funciona bem; pode ser praticamente quadrática localmente em casos favoráveis.
    • Newton: convergência quadrática local (quando válida).
  • Custo por iteração (avaliações típicas):
    • Razão áurea: 1 avaliação de f por iteração (após as duas iniciais).
    • Interpolação quadrática: precisa manter três avaliações; cada tentativa de novo vértice normalmente exige 1 avaliação adicional (mas a lógica de atualização pode variar). Montar a parábola exige manipulação algébrica, mas não derivações.
    • Newton: precisa de f' e f''. Se calculados numericamente por diferenças finitas, cada iteração pode custar várias avaliações de f. Se existirem fórmulas analíticas, o custo pode ser menor.
  • Robustez vs rapidez: há um trade-off clássico: a razão áurea é robusta e simples, mas lenta; Newton é muito rápido quando aplicável e bem inicializado, mas arriscado/instável; interpolação dá um meio-termo (mais rápida que razão áurea quando a curva é bem ajustada, porém com risco).
  • Incertezas e ruído: se f tiver ruído, a razão áurea é mais tolerante; Newton e interpolação são sensíveis.
  • Recomendações práticas (o que fazer numa prova ou no mundo real):
    • Se você só tem avaliações de f e quer garantia: use razão áurea (ou bissecção/variações) — fácil de explicar e implementar.
    • Se você tem avaliações de f e função é suave e espera-se formato “parabólico” perto do mínimo: tente interpolação quadrática, mas guarde um critério de backup (p.ex. se o novo ponto sair do intervalo, voltar para razão áurea). Explique que isso é justamente a ideia por trás do método de Brent (mistura de segurança e velocidade).
    • Se você conhece f' e f'' analiticamente (ou pode calculá-las de forma estável) e consegue um chute inicial razoável: Newton é excelente — cite o exemplo f(x)=(x-2)^2 para mostrar velocidade. Caso contrário, use Newton com linha de busca ou damped Newton para garantir passos aceitáveis.

Passo 6

Como explicar rapidamente isso numa prova (roteiro curto e seguro): o que escrever para convencer o corretor.
  • Comece definindo requisitos de cada método (usa derivada? precisa de unimodalidade?).
  • Dê a ordem de convergência e interprete (linear vs quadrática). Explique custo por iteração em termos de avaliações de f e derivadas.
  • Liste uma vantagem e uma desvantagem curtas e claras para cada método (ex.: “Razão áurea: +robusta, -lenta”; “Newton: +rápida, -sensível a chute inicial e requer f''”).
  • Se tiver espaço, mencione a prática comum: combine interpolação com método robusto (Brent) e use Newton com step control. Isso mostra que você conhece a aplicabilidade prática, não só definição teórica.

Passo 7

Dicas finais e exemplos numéricos curtos para fixação (para você “pegar o jeito” na prova):
  • Exemplo rápido para Newton (mostre por que é tão rápido): para f(x)=(x-2)^2 temos f'(x)=2(x-2) e f''(x)=2. Aplicando
x_{k+1}=x_k-\dfrac{2(x_k-2)}{2}=2,
ou seja, chega ao mínimo em uma única iteração a partir de qualquer x_k. Isso demonstra a força da informação de segunda derivada.
  • Exemplo para razão áurea: se L_0=1, após 5 iterações L_5=\varphi^5\cdot 1\approx 0,618^5\approx 0,09 — mostra redução garantida mas linear (não explosiva).
  • Lembre-se: em prova não precisa implementar código; escreva a ideia, a ordem de convergência e um pequeno argumento sobre custo/robustez. Isso costuma valer bastante ponto.

Resposta

Razão áurea — Vantagens: robusta e simples; exige apenas avaliações de f; garante redução do intervalo se f é unimodal; baixo custo por iteração (1 avaliação nova). Razão áurea — Desvantagens: convergência lenta (linear); não explora curvatura; requer unimodalidade no intervalo inicial.
Interpolação quadrática — Vantagens: potencial de convergência muito mais rápida que a razão áurea quando a parábola ajusta bem (superlinear/quase quadrática local); não requer derivadas explícitas. Interpolação quadrática — Desvantagens: pode ser instável se os pontos forem ruins ou houver ruído; não garante convergência global; cuidado com vértice fora do intervalo.
Newton — Vantagens: convergência local quadrática (muito rápida) quando f' e f'' existem e o chute inicial é razoável; aproveita curvatura diretamente. Newton — Desvantagens: requer f' e f'' (ou aproximações custosas); pode divergir ou dar passos ruins se iniciado longe do mínimo ou se f'' for pequeno/ruidoso; sensível a erros numéricos.

Exercícios relacionados