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):
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
é unimodal num intervalo (tem apenas um mínimo nesse intervalo). A busca reduz o intervalo onde o mínimo pode estar, avaliando 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:
. Após cada iteração o tamanho do intervalo é reduzido por um fator . Mais precisamente, se então, depois de iterações, . Isso dá uma redução linear do comprimento do intervalo. - Requisitos: só precisa de avaliações de
e que 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
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
com 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
, o vértice (abscissa do mínimo) é
Na prática, você calcula
a partir dos três pares
(p. ex. via forma de Lagrange) e obtém
.
- 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
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.
- Instabilidade: se os três pontos forem quase colineares ou se os valores
- Em prova: explique o passo de ajustar a parábola e calcular
. Mostre que funciona muito bem quando a função tem formato “quase quadrático” perto do mínimo (ex.: 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
em torno de 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:
O mínimo dessa aproximação é obtido anulando a derivada:
, daí
- Requisitos:
deve ser duas vezes diferenciável; é necessário calcular (ou aproximar) e . - 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
), uma iteração de Newton leva diretamente ao mínimo: aqui , , então .
- Desvantagens:
- Dependência de derivadas: requer
. Se 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
e (analiticamente ou por diferenças finitas) é custoso; diferenças finitas aumentam o ruído e exigem mais avaliações de . - Sensível a ruído: pequenas flutuações nos valores das derivadas podem causar passos ruins.
- Dependência de derivadas: requer
- Prática: usa-se Newton quando se tem fórmulas analíticas das derivadas ou quando se pode calcular
e 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 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
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).
- Busca da razão áurea: convergência linear (fator
- Custo por iteração (avaliações típicas):
- Razão áurea: 1 avaliação de
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
e . Se calculados numericamente por diferenças finitas, cada iteração pode custar várias avaliações de . Se existirem fórmulas analíticas, o custo pode ser menor.
- Razão áurea: 1 avaliação de
- 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
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
e quer garantia: use razão áurea (ou bissecção/variações) — fácil de explicar e implementar. - Se você tem avaliações de
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
e analiticamente (ou pode calculá-las de forma estável) e consegue um chute inicial razoável: Newton é excelente — cite o exemplo para mostrar velocidade. Caso contrário, use Newton com linha de busca ou damped Newton para garantir passos aceitáveis.
- Se você só tem avaliações de
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
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
”). - 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
temos e . Aplicando
ou seja, chega ao mínimo em uma única iteração a partir de qualquer
. Isso demonstra a força da informação de segunda derivada.
- Exemplo para razão áurea: se
, após 5 iterações — 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
; garante redução do intervalo se
é 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 e
existem e o chute inicial é razoável; aproveita curvatura diretamente. Newton — Desvantagens: requer
e
(ou aproximações custosas); pode divergir ou dar passos ruins se iniciado longe do mínimo ou se
for pequeno/ruidoso; sensível a erros numéricos.
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