Exercício 17 (Desafio) - Ordem de convergência

(a) Mostre que se \varphi^{\prime}(\xi)=0 e \varphi^{\prime \prime}(\xi) \neq 0, então o Método do Ponto Fixo converge quadraticamente (ordem 2).
(b) Para f(x)=x^{2}-2 e \varphi(x)=\frac{1}{2}(x+2 / x), verifique que \varphi^{\prime}(\sqrt{2})=0, execute 5 iterações a partir de x_{0}=1 e confirme a convergência quadrática estimando C=\lim \left|e_{k+1}\right| /\left|e_{k}\right|^{2}.
(c) Mostre que o Método de Newton é o caso \varphi(x)=x-f(x) / f^{\prime}(x) e que \varphi^{\prime}(\xi)=0 para qualquer raiz simples \xi.

Passo 1

Vou listar com clareza o que o enunciado pede e quais informações temos:
  • O enunciado tem três partes: (a), (b) e (c). Preciso responder cada uma.
  • Informações dadas:
    • Em (a): existe uma função \varphi com uma raiz fixa \xi (ou seja, \varphi(\xi)=\xi) e sabe-se que \varphi^{\prime}(\xi)=0 e \varphi^{\prime\prime}(\xi)\neq 0. Pede-se mostrar que o Método do Ponto Fixo (iteração x_{k+1}=\varphi(x_k)) converge com ordem 2 (quadraticamente) para \xi.
    • Em (b): f(x)=x^{2}-2 e \varphi(x)=\dfrac{1}{2}\!\left(x+\dfrac{2}{x}\right). Deve-se verificar \varphi^{\prime}(\sqrt{2})=0, executar 5 iterações a partir de x_0=1 e estimar C=\lim \dfrac{|e_{k+1}|}{|e_k|^{2}} para confirmar a convergência quadrática. Aqui \xi=\sqrt{2} é a raiz desejada.
    • Em (c): mostrar que o Método de Newton corresponde a \varphi(x)=x-\dfrac{f(x)}{f^{\prime}(x)} e que para uma raiz simples \xi (ou seja, f(\xi)=0 e f^{\prime}(\xi)\neq0) vale \varphi^{\prime}(\xi)=0.
O que vou fazer: em (a) usarei o desenvolvimento de Taylor de \varphi em torno de \xi e definirei o erro e_k=x_k-\xi. Em (b) calcularei derivadas de \varphi, executarei explicitamente as 5 iterações, computarei os erros e_k e estimarei a constante C. Em (c) mostrarei algebraicamente a forma de \varphi do Método de Newton e calcularei \varphi^{\prime}(\xi).

Passo 2

Conceitos e definições que vamos usar (explicadinho, sem pressa):
  • Ordem de convergência: se x_k\to\xi e existem p>0 e C>0 tais que
\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^{p}}=C,\qquad e_k:=x_k-\xi,
então dizemos que a iteração converge com ordem p e constante assintótica C. No caso quadrático, p=2.
  • Taylor de segunda ordem com resto: se \varphi é C^{2} perto de \xi, então para x próximo a \xi
\varphi(x)=\varphi(\xi)+\varphi^{\prime}(\xi)(x-\xi)+\frac{1}{2}\varphi^{\prime\prime}(\xi)(x-\xi)^{2}+R(x),
onde o resto R(x)=o\big((x-\xi)^{2}\big) quando x\to\xi. Isto significa que \dfrac{R(x)}{(x-\xi)^{2}}\to 0.
  • Aplicação ao ponto fixo: como \varphi(\xi)=\xi, a expansão acima permitirá expressar o erro da iteração em termos de potência do erro anterior.

Passo 3

Prova detalhada de (a): mostrar ordem 2 quando \varphi^{\prime}(\xi)=0 e \varphi^{\prime\prime}(\xi)\neq0.
  1. Escrevemos a expansão de Taylor de \varphi em torno de \xi:
\varphi(x)=\varphi(\xi)+\varphi^{\prime}(\xi)(x-\xi)+\frac{1}{2}\varphi^{\prime\prime}(\xi)(x-\xi)^{2}+R(x).
Como \varphi(\xi)=\xi (fixo) e \varphi^{\prime}(\xi)=0 pelo enunciado, isso reduz para
\varphi(x)=\xi+\frac{1}{2}\varphi^{\prime\prime}(\xi)(x-\xi)^{2}+R(x).
  1. Substitui-se agora x=x_k=\xi+e_k. Então
x_{k+1}=\varphi(x_k)=\xi+\frac{1}{2}\varphi^{\prime\prime}(\xi)e_k^{2}+R(\xi+e_k).
Por definição e_{k+1}=x_{k+1}-\xi. Assim
e_{k+1}=\frac{1}{2}\varphi^{\prime\prime}(\xi)e_k^{2}+R(\xi+e_k).
  1. Pelo comportamento do resto temos R(\xi+e_k)=o(e_k^{2}) quando e_k\to 0. Ou seja,
\lim_{k\to\infty}\frac{R(\xi+e_k)}{e_k^{2}}=0.
  1. Dividindo a expressão de e_{k+1} por e_k^{2} obtemos
\frac{e_{k+1}}{e_k^{2}}=\frac{1}{2}\varphi^{\prime\prime}(\xi)+\frac{R(\xi+e_k)}{e_k^{2}}.
Tomando limite quando k\to\infty (isto é, e_k\to 0), pela propriedade do resto,
\lim_{k\to\infty}\frac{e_{k+1}}{e_k^{2}}=\frac{1}{2}\varphi^{\prime\prime}(\xi).
  1. Conclusão: o limite existe finito e não nulo (porque \varphi^{\prime\prime}(\xi)\neq0). Portanto a ordem de convergência é p=2 (quadrática) e a constante assintótica é C=\dfrac{1}{2}\varphi^{\prime\prime}(\xi). Observação prática: isso vale localmente, ou seja, para x_0 suficientemente próximo de \xi, a iteração converge e com ordem 2.

Passo 4

Agora parte (b): verificação de \varphi^{\prime}(\sqrt{2})=0 e execução de 5 iterações a partir de x_0=1.
  1. Primeiro calculemos \varphi^{\prime}(x) e \varphi^{\prime\prime}(x) para a dada \varphi:
\varphi(x)=\frac{1}{2}\!\left(x+\frac{2}{x}\right).
Derivando:
\varphi^{\prime}(x)=\frac{1}{2}\left(1-\frac{2}{x^{2}}\right)=\frac{1}{2}-\frac{1}{x^{2}}.
Derivando de novo:
\varphi^{\prime\prime}(x)=\frac{d}{dx}\!\left(-\frac{1}{x^{2}}\right)=\frac{2}{x^{3}}.
  1. Avaliando em \xi=\sqrt{2}:
\varphi^{\prime}(\sqrt{2})=\frac{1}{2}-\frac{1}{(\sqrt{2})^{2}}=\frac{1}{2}-\frac{1}{2}=0,
\varphi^{\prime\prime}(\sqrt{2})=\frac{2}{(\sqrt{2})^{3}}=\frac{2}{2\sqrt{2}}=\frac{1}{\sqrt{2}}\neq0.
Portanto a hipótese de (a) está verificada: \varphi^{\prime}(\sqrt{2})=0 e \varphi^{\prime\prime}(\sqrt{2})\neq0.
  1. Agora executamos as iterações. Lembre que x_{k+1}=\varphi(x_k)=\dfrac{1}{2}\!\left(x_k+\dfrac{2}{x_k}\right). Tomando x_0=1:
  • x_0=1.
  • Calcule x_1:
x_1=\frac{1}{2}\!\left(1+\frac{2}{1}\right)=\frac{1}{2}\cdot 3= \frac{3}{2}=1{,}5.
  • Calcule x_2:
x_2=\frac{1}{2}\!\left(1{,}5+\frac{2}{1{,}5}\right)=\frac{1}{2}\!\left(\frac{3}{2}+\frac{4}{3}\right)=\frac{1}{2}\!\left(\frac{9+8}{6}\right)=\frac{17}{12}\approx 1{,}4166666666666667.
  • Calcule x_3:
x_3=\frac{1}{2}\!\left(x_2+\frac{2}{x_2}\right)\approx \frac{1}{2}\!\left(1{,}4166666666666667+\frac{2}{1{,}4166666666666667}\right).
Calculando numericamente \dfrac{2}{1{,}4166666666666667}\approx 1{,}4117647058823528. Assim
x_3\approx\frac{1}{2}\cdot 2{,}8284313725490194\approx 1{,}4142156862745097.
  • Calcule x_4:
x_4=\frac{1}{2}\!\left(x_3+\frac{2}{x_3}\right).
Numéricamente \dfrac{2}{1{,}4142156862745097}\approx 1{,}41421143847487. Então
x_4\approx\frac{1}{2}\cdot 2{,}8284271247493797\approx 1{,}4142135623746899.
  • Calcule x_5:
x_5=\frac{1}{2}\!\left(x_4+\frac{2}{x_4}\right).
Numéricamente \dfrac{2}{1{,}4142135623746899}\approx 1{,}414213562372, (valores arredondados) e
x_5\approx 1{,}4142135623730951\\ \text{(próximo de }\sqrt{2}\text{)}.ó
  1. Agora calculamos os erros e_k=x_k-\sqrt{2}. Usaremos \sqrt{2}\approx 1{,}4142135623730951.
  • e_0=1-\sqrt{2}\approx -0{,}4142135623730951.
  • e_1=1{,}5-\sqrt{2}\approx 0{,}0857864376269049.
  • e_2\approx 1{,}4166666666666667-\sqrt{2}\approx 0{,}0024531042935716.
  • e_3\approx 1{,}4142156862745097-\sqrt{2}\approx 0{,}0000021239014146.
  • e_4\approx 1{,}4142135623746899-\sqrt{2}\approx 1{,}5949\times 10^{-12}.
  • e_5\approx 1{,}4142135623730951-\sqrt{2}\approx 0\\ \text{(na precisão mostrada, ordem de }10^{-16}\text{)}.ã
  1. Estimativa da constante C. Pelo item (a) esperamos
C=\frac{1}{2}\varphi^{\prime\prime}(\sqrt{2})=\frac{1}{2}\cdot\frac{1}{\sqrt{2}}=\frac{1}{2\sqrt{2}}\approx 0{,}3535533905932738.
Vamos estimar numericamente C_k:=\dfrac{|e_{k+1}|}{|e_k|^{2}} para alguns k grandes o suficiente (onde o comportamento assintótico já aparece):
  • Para k=2:
C_2\approx\frac{|e_3|}{|e_2|^{2}}\approx\frac{2{,}1239014146\times 10^{-6}}{(2{,}4531042936\times 10^{-3})^{2}} \approx 0{,}3535533905932738.
  • Para k=3:
C_3\approx\frac{|e_4|}{|e_3|^{2}}\approx\frac{1{,}5949\times10^{-12}}{(2{,}1239014146\times10^{-6})^{2}} \approx 0{,}3535533905932738.
Ambos os valores aproximam muito bem C=\dfrac{1}{2\sqrt{2}}. Isso confirma a convergência quadrática e a constante esperada.

Passo 5

Parte (c): mostrar que o Método de Newton é o caso \varphi(x)=x-\dfrac{f(x)}{f^{\prime}(x)} e que \varphi^{\prime}(\xi)=0 para raiz simples \xi.
  1. Definição do Método de Newton: dada f com derivada não nula perto da raiz, a iteração é
x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}.
Portanto toma-se \varphi(x)=x-\dfrac{f(x)}{f^{\prime}(x)}. Assim Newton é um caso particular do Método do Ponto Fixo com essa \varphi.
  1. Calculemos \varphi^{\prime}(x) explicitamente. Escrevemos \varphi(x)=x-g(x) com g(x)=\dfrac{f(x)}{f^{\prime}(x)}. Então
\varphi^{\prime}(x)=1-g^{\prime}(x).
Calcule g^{\prime}(x) usando a regra do quociente:
g^{\prime}(x)=\frac{f^{\prime}(x)\cdot f^{\prime}(x)-f(x)\cdot f^{\prime\prime}(x)}{[f^{\prime}(x)]^{2}} =\frac{[f^{\prime}(x)]^{2}-f(x)f^{\prime\prime}(x)}{[f^{\prime}(x)]^{2}}.
Logo
\varphi^{\prime}(x)=1-\frac{[f^{\prime}(x)]^{2}-f(x)f^{\prime\prime}(x)}{[f^{\prime}(x)]^{2}} =\frac{f(x)f^{\prime\prime}(x)}{[f^{\prime}(x)]^{2}}.
  1. Agora avaliamos em \xi que é uma raiz simples: f(\xi)=0 e f^{\prime}(\xi)\neq0. Substituindo:
\varphi^{\prime}(\xi)=\frac{f(\xi)f^{\prime\prime}(\xi)}{[f^{\prime}(\xi)]^{2}}=\frac{0\cdot f^{\prime\prime}(\xi)}{[f^{\prime}(\xi)]^{2}}=0.
Portanto \varphi^{\prime}(\xi)=0 sempre que \xi é raiz simples. Pelo item (a) isso explica por que o Método de Newton costuma ter convergência quadrática localmente (de fato, Newton tem ordem 2 sob hipóteses standard).

Resposta

(a) A iteração converge com ordem 2 (quadraticamente) e a constante assintótica é C=\dfrac{1}{2}\varphi^{\prime\prime}(\xi).\n
(b) \varphi^{\prime}(\sqrt{2})=0. As iterações a partir de x_0=1 dão aproximadamente x_1=1{,}5,\\ x_2\approx1{,}4166666666666667,\\ x_3\approx1{,}4142156862745097,\\ x_4\approx1{,}4142135623746899,\\ x_5\approx1{,}4142135623730951. Estimando C obtemos C\approx\dfrac{1}{2\sqrt{2}}\approx 0{,}3535533905932738, confirmando convergência quadrática.\n
(c) O Método de Newton corresponde a \varphi(x)=x-\dfrac{f(x)}{f^{\prime}(x)} e para qualquer raiz simples \xi vale \varphi^{\prime}(\xi)=0.

Exercícios relacionados