[03] Dizemos que um método iterativo apresenta convergência quadrática se:
\lim _{n \rightarrow \infty} \frac{e_{n+1}}{e_{n}^{2}}=k
onde k é chamada de constante assintótica de proporcionalidade, e_{n}=\left|x_{n}-x^{*}\right| e e_{n+1}=\left|x_{n+1}-x^{*}\right| são os erros cometidos nas iterações n e n+1, respectivamente, e x^{*} é a raiz exata da função.
Mostre que o método de Newton-Raphson apresenta convergência quadrática, desde que f^{\prime}\left(x^{*}\right) \neq 0 , onde f^{\prime}\left(x^{*}\right) é a derivada da função no ponto x^{*}.

Passo 1

O enunciado pede para mostrar que o método de Newton-Raphson tem convergência quadrática, ou seja, que
\lim_{n\to\infty}\frac{e_{n+1}}{e_n^2}=k
com k finito, onde e_n=\left|x_n-x^*\right| e x^* é a raiz exata de f. As informações relevantes são:
  • A definição do erro e_n=\left|x_n-x^*\right|.
  • A condição necessária que devemos usar: f'(x^*)\neq 0.
  • A iteração de Newton-Raphson (que vamos usar):
x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.
Não se resolve nada neste passo; só organizamos o que foi dado e o que se quer demonstrar.

Passo 2

Vamos aproximar f(x_n) e f'(x_n) por séries de Taylor centradas em x^*. Para isso defino s=x_n-x^*, então s\to 0 quando n\to\infty e e_n=|s|. Como f(x^*)=0 (porque x^* é raiz), a expansão de Taylor de f em torno de x^* até termos de ordem s^2 é:
f(x_n)=f(x^*+s)=f(x^*)+f'(x^*)s+\frac{f''(x^*)}{2}s^2+O(s^3).
Como f(x^*)=0, isso vira
f(x_n)=f'(x^*)s+\frac{f''(x^*)}{2}s^2+O(s^3).
Analogamente, a expansão de f' é
f'(x_n)=f'(x^*)+f''(x^*)s+O(s^2).
Aqui explico rápido os símbolos: O(s^3) significa “termos cujo módulo é menor ou igual a C|s|^3 para algum constante C quando s é pequeno” — ou seja, são termos de ordem no mínimo s^3.

Passo 3

Para simplificar a escrita, chamo
A=f'(x^*)\quad\text{e}\quad C=f''(x^*).
Assim as expansões ficam
f(x_n)=A s+\frac{C}{2}s^2+O(s^3),
f'(x_n)=A + C s + O(s^2).
Como A=f'(x^*)\neq 0 pela hipótese, podemos dividir por A. Escrevo a fração que aparece em Newton:
\frac{f(x_n)}{f'(x_n)}=\frac{A s+\frac{C}{2}s^2+O(s^3)}{A+ C s + O(s^2)}.
Fatorando A no numerador e denominador:
\frac{f(x_n)}{f'(x_n)}=s\cdot\frac{1+\frac{C}{2A}s+O(s^2)}{1+\frac{C}{A}s+O(s^2)}.
Agora usamos a expansão \dfrac{1+u_1}{1+u_2}=(1+u_1)(1-u_2+O(u_2^2))=1+(u_1-u_2)+O(u_2^2,u_1u_2) válida para pequenos u_1,u_2. Tomando u_1=\dfrac{C}{2A}s+O(s^2) e u_2=\dfrac{C}{A}s+O(s^2) obtemos, até ordem s^2,
\frac{f(x_n)}{f'(x_n)}=s\left[1+\left(\frac{C}{2A}-\frac{C}{A}\right)s+O(s^2)\right] = s\left[1-\frac{C}{2A}s+O(s^2)\right].

Passo 4

Usando a fórmula de Newton x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)} e lembrando x_n=x^*+s, temos
x_{n+1}=x^*+s - s\left[1-\frac{C}{2A}s+O(s^2)\right] = x^* + \frac{C}{2A}s^2 + O(s^3).
Portanto o erro na iteração n+1 é
e_{n+1}=|x_{n+1}-x^*|=\left|\frac{C}{2A}\right|\,|s|^2 + O(|s|^3).
Mas |s|=e_n, logo
e_{n+1}=\left|\frac{f''(x^*)}{2f'(x^*)}\right| e_n^2 + O(e_n^3).

Passo 5

Dividindo ambos os lados por e_n^2 e tomando o limite n\to\infty (ou seja, e_n\to 0), o termo de ordem O(e_n^3)/e_n^2=O(e_n) tende a zero. Assim
\lim_{n\to\infty}\frac{e_{n+1}}{e_n^2}=\left|\frac{f''(x^*)}{2f'(x^*)}\right|.
Portanto a convergência é quadrática (expoente 2) e a constante assintótica de proporcionalidade é k=\left|\dfrac{f''(x^*)}{2f'(x^*)}\right|. Note que a hipótese f'(x^*)\neq 0 foi essencial para podermos dividir por A e garantir que o método seja bem definido localmente; se f''(x^*)=0 a constante k pode ser zero e a ordem de convergência pode ser maior que 2.

Passo 6

Um exemplo rápido para fixar: tome f(x)=x^2-2. A raiz positiva é x^*=\sqrt{2}. Temos f'(x)=2x, f''(x)=2. Então
k=\left|\frac{f''(x^*)}{2f'(x^*)}\right|=\left|\frac{2}{2\cdot 2\sqrt{2}}\right|=\frac{1}{2\sqrt{2}}.
Isto significa que, para x_n perto de \sqrt{2}, o erro seguinte é aproximadamente \dfrac{1}{2\sqrt{2}}e_n^2, ilustrando a convergência quadrática.

Resposta

O método de Newton-Raphson apresenta convergência quadrática e
\lim_{n\to\infty}\frac{e_{n+1}}{e_n^2}=\left|\frac{f''(x^*)}{2f'(x^*)}\right|.

Exercícios relacionados