Exercício 23 (Teórico) - Ordem de convergência da Secante

A ordem de convergência do Método da Secante é \varphi=\frac{1+\sqrt{5}}{2} \approx 1,618 (número áureo).
(a) Admitindo que e_{k+1} \approx C e_{k}^{p} e usando a relação da secante com diferenças divididas, mostre que p satisfaz p^{2}-p-1=0 e conclua que p=\varphi.
(b) Verifique numericamente a ordem \varphi para o exercício anterior, estimando \left|e_{k+1}\right| /\left|e_{k}\right|^{\varphi}.
(c) A secante precisa de duas avaliações de f por iteração, enquanto Newton precisa de uma de f e uma de f^{\prime}. Em termos de “avaliações por dígito correto”, qual é mais eficiente? Justifique comparando \varphi / 2 com 2 / 1.

Passo 1

O que o enunciado dá e o que pede:
  • Dá: a afirmação que a ordem de convergência do método da secante é \varphi=\dfrac{1+\sqrt{5}}{2}.
  • Dá a hipótese assintótica que podemos escrever \,e_{k+1}\approx C\,e_k^{p}\, para algum C\neq0 e ordem p.
  • Pede:
    (a) partir da relação da secante com diferenças divididas, mostrar que p satisfaz p^{2}-p-1=0 e concluir p=\varphi;
    (b) verificar numericamente a ordem \varphi estimando \left|e_{k+1}\right|/\left|e_{k}\right|^{\varphi} (isto é, dar a forma de verificação e calcular se houver dados numéricos);
    (c) discutir eficiência em termos de “avaliações por dígito correto”, comparando \varphi/2 com 2/1 e concluir qual método é mais eficiente.

Passo 2

Definições e fórmula da secante (colocando tudo explícito).
  • Seja \alpha uma raiz simples de f (ou seja f(\alpha)=0 e f'(\alpha)\neq0).
  • Defina o erro em cada iteração por \,e_k := x_k-\alpha\,.
  • A iteração da secante escreve-se
x_{k+1}=x_k - f(x_k)\,\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}.
Substituindo x_j=\alpha+e_j convertemos a atualização em uma relação entre e_{k+1},e_k,e_{k-1}. O objetivo é obter a forma assintótica mais baixa ordem de e_{k+1} em termos de e_k,e_{k-1}.

Passo 3

Expansão de Taylor de f perto da raiz \alpha — por que e como usar.
  • Como \alpha é raiz simples, expandimos f em Taylor em torno de \alpha:
f(\alpha+e)=f'(\alpha)e+\tfrac{1}{2}f''(\alpha)e^{2}+O(e^{3})
quando e\to0. Aqui O(e^{3}) significa “termos da ordem de e^{3} ou mais pequenos”.
  • Aplicando isso a x_k=\alpha+e_k e a x_{k-1}=\alpha+e_{k-1} obtemos:
f(x_k)=f'(\alpha)e_k+\tfrac{1}{2}f''(\alpha)e_k^{2}+O(e_k^{3}),
f(x_{k-1})=f'(\alpha)e_{k-1}+\tfrac{1}{2}f''(\alpha)e_{k-1}^{2}+O(e_{k-1}^{3}).

Passo 4

Aproximação da diferença dividida (denominador da secante).
  • A diferença dividida que aparece na secante é
\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}.
  • Substituindo as expansões e lembrando que x_k-x_{k-1}=e_k-e_{k-1}, obtemos, para termos até ordem linear em e,
\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}} = f'(\alpha) + \tfrac{1}{2}f''(\alpha)(e_k+e_{k-1}) + O(e_k^{2}+e_{k-1}^{2}).
Isto é natural: a diferença dividida aproxima a derivada f'(\alpha) mais um pequeno termo proporcional a e_k+e_{k-1}.

Passo 5

Substituir no esquema da secante e expandir para obter a relação entre erros.
  • A fórmula da secante reescrita com as expansões dá
e_{k+1}=e_k - \frac{f(x_k)}{\dfrac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}}.
  • Substituindo f(x_k)=f'(\alpha)e_k+\tfrac{1}{2}f''(\alpha)e_k^{2}+O(e_k^{3}) e a expressão da diferença dividida do passo anterior, e usando a expansão em série para 1/(f'(\alpha)+\delta)=\dfrac{1}{f'(\alpha)}\bigl(1-\dfrac{\delta}{f'(\alpha)}+O(\delta^{2})\bigr), obtemos (mantendo só os termos dominantes):
\begin{aligned} e_{k+1} &\approx e_k - \bigl(f'(\alpha)e_k+\tfrac{1}{2}f''(\alpha)e_k^{2}\bigr)\cdot \frac{1}{f'(\alpha)}\Bigl(1 - \frac{\tfrac{1}{2}f''(\alpha)(e_k+e_{k-1})}{f'(\alpha)}\Bigr)\\[4pt] &= e_k - e_k - \tfrac{1}{2}\frac{f''(\alpha)}{f'(\alpha)}e_k^{2} + e_k\cdot \tfrac{1}{2}\frac{f''(\alpha)}{f'(\alpha)}(e_k+e_{k-1}) + \text{termos de ordem superior}. \end{aligned}
  • Observe que os termos em e_k^{2} se cancelam: -\tfrac{1}{2}\frac{f''}{f'}e_k^{2}+ \tfrac{1}{2}\frac{f''}{f'}e_k^{2}=0. O termo remanescente de menor ordem é
e_{k+1}\approx \tfrac{1}{2}\frac{f''(\alpha)}{f'(\alpha)}\,e_k e_{k-1}.
  • Defina a constante
M := \tfrac{1}{2}\frac{f''(\alpha)}{f'(\alpha)}.
Assim a relação assintótica principal é
\boxed{\,e_{k+1}\approx M\,e_k e_{k-1}\,}
quando k é grande (regime assintótico).]

Passo 6

Usar a hipótese e_{k+1}\approx C e_k^{p} para obter a equação para p.
  • A hipótese nos dá também, deslocando índices,
e_k\approx C e_{k-1}^{p}.
  • Da segunda equação isolamos e_{k-1} em termos de e_k:
e_{k-1}\approx\biggl(\frac{e_k}{C}\biggr)^{1/p}.
  • Substituindo e_{k-1} na relação do passo anterior e_{k+1}\approx M e_k e_{k-1} obtemos
e_{k+1}\approx M\,e_k\left(\frac{e_k}{C}\right)^{1/p} = M C^{-1/p}\, e_k^{1+1/p}.
  • Mas pela hipótese também e_{k+1}\approx C e_k^{p}. Igualando as potências de e_k (ou seja, os expoentes dominantes) dá
p = 1+\frac{1}{p}.
  • Multiplicando por p obtemos a equação quadrática
p^{2}-p-1=0.

Passo 7

Resolver a quadrática e concluir p=\varphi.
  • A solução positiva da equação p^{2}-p-1=0 é
p=\frac{1+\sqrt{5}}{2}.
  • Portanto a ordem de convergência assintótica do método da secante é
\boxed{\,p=\varphi=\dfrac{1+\sqrt{5}}{2}\approx 1{,}618\,}.

Passo 8

Como verificar numericamente a ordem \varphi (resposta ao item (b)) — procedimento e observações.
  • Procedimento prático, supondo que se tenha os iterados x_0,x_1,\dots,x_N e uma boa aproximação da raiz \alpha:
    1. Calcule os erros \,e_k = x_k-\alpha para k suficientemente grandes (regime assintótico).
    2. Para cada k compute a razão
    r_k := \frac{|e_{k+1}|}{|e_k|^{\varphi}}.
    1. Se o método tem ordem \varphi, então r_k tende para uma constante não nula quando k\to\infty. Numericamente espera-se ver r_k estabilizando para valores próximos entre iterações.
  • Observação importante: para executar isso são necessários os valores numéricos dos iterados (ou dos erros) do “exercício anterior”. Sem esses dados não há como produzir os números pedidos. Portanto, sem os x_k ou sem \alpha (ou sem as diferenças e_k) não é possível calcular as razões numéricas pedidas.
  • Exemplo ilustrativo (independente do seu enunciado anterior): se se quisesse testar em um caso concreto, escolheria uma função simples com raiz conhecida (por exemplo \,f(x)=x^{2}-2, raiz \sqrt{2}), rodaria a secante com chutes iniciais, recolheria os x_k, computaria e_k e depois os r_k. Uma estabilização de r_k confirma numericamente a ordem \varphi.

Passo 9

Discussão de eficiência em termos de “avaliações por dígito correto” (item (c)).
  • Definição prática usada aqui: a ordem p indica a “potência” com que o erro diminui por iteração (erro reduz como e_{k+1}\approx\text{const}\cdot e_k^{p}). Uma métrica de eficiência é comparar essa ordem com o custo por iteração, medido em número de avaliações caras (tipicamente chamadas de "avaliações de f" e também contando a avaliação de f' se custosa).
  • Custos por iteração:
    • Secante: precisa de duas avaliações de f por iteração (em x_k e em x_{k-1}), portanto custo ≈ 2 avaliações por iteração; ordem p=\varphi. Eficiência aproximada: \dfrac{\varphi}{2}.
    • Newton: precisa de uma avaliação de f e de f' por iteração. Se considerarmos avaliação de f' com custo semelhante ao de f, então o custo por iteração é aproximadamente 2 avaliações e a ordem é 2, portanto eficiência aproximada: \dfrac{2}{2}=1.
    • Se, alternativamente, a avaliação de f' for considerada desprezível (ou já disponível a baixo custo), pode-se ver Newton como tendo custo 1 caro por iteração e então a razão mostrada no enunciado \dfrac{2}{1}=2 seria usada — isto só é válido quando realmente o custo de f' é desprezível.
  • Numericamente: \frac{\varphi}{2}\approx\frac{1{,}618}{2}\approx 0{,}809, \qquad \frac{2}{2}=1, \qquad \frac{2}{1}=2\\ (\text{caso especial: }f'\text{ "gratuito"}).
  • Conclusão: em termos práticos e razoáveis (contando avaliação de f' com custo similar ao de f), a eficiência de Newton ( 1 unidade de ordem por avaliação) é maior que a da secante ( \approx0{,}809). Mesmo no cenário otimista para Newton em que f' é “gratuito”, Newton fica ainda mais vantajoso. Logo, em termos de “avaliações por dígito correto” o método de Newton é, de modo geral, mais eficiente que a secante.

Resposta

(a) p satisfaz p^{2}-p-1=0, portanto p=\dfrac{1+\sqrt{5}}{2}=\varphi.
(b) Não é possível verificar numericamente pois os iterados (ou os erros e_k) do exercício anterior não foram fornecidos; o procedimento é calcular r_k=\dfrac{|e_{k+1}|}{|e_k|^{\varphi}} e observar a estabilização de r_k.
(c) \dfrac{\varphi}{2}\approx0{,}809 (secante) é menor que \dfrac{2}{2}=1 (Newton contando f' com custo igual a f); portanto Newton é mais eficiente em avaliações por dígito correto (e, se f' fosse “gratuito”, Newton seria ainda mais vantajoso: \tfrac{2}{1}=2).

Exercícios relacionados