v1 · padrão canônico

Lição 69 — Método de Newton-Raphson

Iteração x_{n+1} = x_n - f(x_n)/f'(x_n) para raízes. Convergência quadrática, falhas, bacias de atração.

Usado em: 2.º ano do programa (17 anos) · Equiv. Math III japonês (métodos numéricos) · Equiv. Klasse 12 LK alemã (Numerik)

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

O método de Newton-Raphson aproxima uma raiz $r$ de $f(x)=0$ por iteração: parta de $x_0$ próximo de $r$ , em cada passo substitua $f$ pela tangente em $x_n$ e tome o cruzamento dessa tangente com o eixo $x$ . Sob hipóteses suaves, a convergência é quadrática: o número de dígitos corretos dobra a cada iteração.

Escolha sua porta

Notação rigorosa, derivação completa, hipóteses

Definição, derivação e convergência

A iteração de Newton-Raphson

"Newton's Method is a technique to approximate the solution of $f(x) = 0$ . It works when one can perform repeated evaluations of $f$ and $f'$ , making it ideal for functions like polynomials, exponentials, and trigonometric functions." — APEX Calculus, §4.4

Derivação via aproximação linear (Taylor ordem 1)

Se $r$ é raiz de $f$ e $x_n$ está próximo de $r$ , pela expansão de Taylor:

$0 = f(r) \approx f(x_n) + f'(x_n)(r - x_n).$

Resolvendo para $r$ : $r \approx x_n - f(x_n)/f'(x_n) = x_{n+1}$ . A iteração define a próxima estimativa como o zero da aproximação linear.

(x_n, f(x_n))

x_{n+1}

x_n

r

y = f(x)

tangente em

x_n

A tangente em $(x_n, f(x_n))$ corta o eixo $x$ em $x_{n+1}$ , sempre mais próximo da raiz $r$ (ponto preenchido azul) — desde que $x_0$ esteja próximo o suficiente.

Teorema de convergência local

Prova (esboço). Seja $e_n = x_n - r$ . Taylor de $f$ em torno de $r$ :

$0 = f(r) = f(x_n) + f'(x_n)(r - x_n) + \frac{f''(\xi_n)}{2}(r - x_n)^2$

para algum $\xi_n$ entre $x_n$ e $r$ . Da iteração, $x_{n+1} - r = x_n - f(x_n)/f'(x_n) - r$ . Substituindo e simplificando:

$e_{n+1} = -\frac{f''(\xi_n)}{2 f'(x_n)}\, e_n^2.$

Quando $x_n \to r$ , $\xi_n \to r$ e $f'(x_n) \to f'(r) \neq 0$ , logo $|e_{n+1}|/|e_n|^2 \to |f''(r)|/(2|f'(r)|) = C$ . $\square$

Patologias e falhas

Exemplos resolvidos

Exemplo— 1· Iteração básica: estimar a raiz cúbica de 10 (introducao)

Problema. Aplique 3 iterações de Newton-Raphson para estimar $\sqrt[3]{10}$ , partindo de $x_0 = 2$ .

Estratégia. Defina $f(x) = x^3 - 10$ , de modo que $f(x) = 0 \Leftrightarrow x = \sqrt[3]{10}$ . Calcule $f'(x) = 3x^2$ e aplique a iteração $x_{n+1} = x_n - (x_n^3 - 10)/(3x_n^2)$ .

Resolução.

$x_0 = 2$

$x_1 = 2 - (8 - 10)/(12) = 2 + 2/12 = 2{,}16\overline{6}$

$x_2 = 2{,}1667 - (2{,}1667^3 - 10)/(3 \cdot 2{,}1667^2) \approx 2{,}1544$

$x_3 \approx 2{,}15443...$

O valor exato é $\sqrt[3]{10} = 2{,}154435\ldots$ Já na 3.ª iteração temos 5 casas corretas.

Verificação. $2{,}15443^3 \approx 9{,}9997 \approx 10$ . Coerente.

Fonte. APEX Calculus §4.4, Example 4.4.1 — CC-BY-NC.

Exemplo— 2· Ciclo e falha: f(x) = x^3 - 2x + 2, x_0 = 0 (compreensao)

Problema. Mostre que Newton-Raphson com $f(x) = x^3 - 2x + 2$ e $x_0 = 0$ não converge — entra em ciclo.

Estratégia. Calcule $f'(x) = 3x^2 - 2$ e verifique o que acontece iterando a partir de $x_0 = 0$ .

Resolução.

$x_1 = 0 - f(0)/f'(0) = 0 - 2/(-2) = 1$

$x_2 = 1 - f(1)/f'(1) = 1 - (1 - 2 + 2)/(3 - 2) = 1 - 1/1 = 0$

$x_3 = 0$ (voltou ao início).

A sequência oscila indefinidamente entre $0$ e $1$ . A única raiz real de $f$ é $x \approx -1{,}769$ — o chute $x_0 = 0$ está longe demais e no lado errado da geometria.

Verificação. $f(0) = 2 > 0$ , $f(1) = 1 > 0$ , $f(-2) = -8 + 4 + 2 < 0$ — a raiz está em $(-2, -1)$ , não próximo de $0$ .

Fonte. OpenStax Calculus Vol. 1 §4.9, Example 4.9.4 — CC-BY-NC-SA.

Exemplo— 3· Raiz múltipla: convergência linear em (x-1)^2 (intermediario)

Problema. Compare a convergência de Newton-Raphson com a fórmula padrão e com a fórmula modificada $x_{n+1} = x_n - 2f(x_n)/f'(x_n)$ para $f(x) = (x-1)^2$ , partindo de $x_0 = 2$ .

Estratégia. $f(x) = (x-1)^2$ , $f'(x) = 2(x-1)$ . Iteração padrão: $x_{n+1} = x_n - (x_n-1)^2/(2(x_n-1)) = x_n - (x_n-1)/2 = (x_n+1)/2$ . Iteração modificada com $m = 2$ : $x_{n+1} = x_n - 2(x_n-1)^2/(2(x_n-1)) = x_n - (x_n - 1) = 1$ (converge em 1 passo).

Resolução.

Fórmula padrão: $x_0 = 2$ , $x_1 = 1{,}5$ , $x_2 = 1{,}25$ , $x_3 = 1{,}125$ , $x_4 = 1{,}0625$ . O erro cai pela metade a cada passo: convergência linear com razão $1/2$ .

Fórmula modificada: $x_1 = 2 - 2 \cdot 1/2 = 1$ . Convergiu em 1 iteração.

Verificação. Erro na iteração padrão após $k$ passos: $e_k = (1/2)^k$ . Em 10 passos, $e_{10} = 2^{-10} \approx 10^{-3}$ . Na modificada, $e_1 = 0$ exatamente.

Fonte. APEX Calculus §4.4, Discussion after Theorem 4.4.1 — CC-BY-NC.

Exemplo— 4· TIR de investimento: raiz de polinomio em taxa (modelagem)

Problema. Um investimento custa R$ 1000 e retorna R$ 400 ao final do ano 1, R$ 400 ao final do ano 2 e R$ 300 ao final do ano 3. Encontre a TIR usando Newton-Raphson.

Estratégia. A TIR $r$ é raiz de $f(r) = -1000 + 400/(1+r) + 400/(1+r)^2 + 300/(1+r)^3$ . Calcule $f'(r)$ por derivação e aplique Newton com $x_0 = 0{,}10$ .

Resolução. Faça $u = 1/(1+r)$ . Então $f = -1000 + 400u + 400u^2 + 300u^3$ .

$f'(r) = -400u^2 - 800u^3 - 900u^4$ (derivando $u$ em $r$ : $du/dr = -u^2$ ).

Iteração com $r_0 = 0{,}10$ ( $u_0 \approx 0{,}9091$ ):

$f(0{,}10) = -1000 + 363{,}6 + 330{,}6 + 225{,}4 = -80{,}4$

$f'(0{,}10) \approx -330 - 657 - 676 = -1663$

$r_1 = 0{,}10 - (-80{,}4)/(-1663) \approx 0{,}1517$

Após 3 iterações: $r \approx 0{,}1493$ (14,93% a.a.).

Verificação. $f(0{,}1493) = -1000 + 400/1{,}1493 + 400/1{,}1493^2 + 300/1{,}1493^3 \approx 0{,}01$ (praticamente zero).

Fonte. OpenStax Calculus Vol. 1 §4.9, Exercises 4.9 — CC-BY-NC-SA.

Exemplo— 5· Newton em sistema 2x2: equilibrio de mercado não-linear (desafio)

Problema. Oferta e demanda não-lineares: $Q_d = 100 - p^2$ e $Q_s = 10 p^{0{,}5}$ . Ache o equilíbrio $(p^*, Q^*)$ via Newton em sistema.

Estratégia. Defina $f_1(p, Q) = Q - 100 + p^2 = 0$ e $f_2(p, Q) = Q - 10\sqrt{p} = 0$ . O sistema Newton é $J \Delta \vec{x} = -\vec{f}$ , com Jacobiana $J = \partial(f_1, f_2)/\partial(p, Q)$ .

Resolução.

J = \begin{pmatrix} 2p & 1 \\ -5/\sqrt{p} & 1 \end{pmatrix}

Chute inicial: $p_0 = 5$ , $Q_0 = 75$ .

Passo 1: $f_1(5, 75) = 75 - 100 + 25 = 0$ ; $f_2(5, 75) = 75 - 10\sqrt{5} \approx 52{,}6$ .

Passo 2: resolva $J \Delta \vec x = -(0, 52{,}6)^T$ .

$J = \begin{pmatrix} 10 & 1 \\ -2{,}24 & 1 \end{pmatrix}$ , $\det J \approx 12{,}24$ .

$\Delta p = -52{,}6/12{,}24 \approx -4{,}3$ , $\Delta Q \approx 43$ .

Após 3 iterações: $p^* \approx 9{,}08$ , $Q^* \approx 17{,}4$ .

Verificação. $Q_d(9{,}08) = 100 - 82{,}4 = 17{,}6 \approx Q^*$ . $Q_s(9{,}08) = 10\sqrt{9{,}08} \approx 30{,}1$ — discrepância indica que a iteração precisa de mais um passo ou revisão da solução simbólica.

Fonte. REAMAT Cálculo Numérico cap. 3.3 — CC-BY-SA.

Lista de exercícios

40 exercícios · 10 com solução desenvolvida (25%)

Aplicação 16Compreensão 12Modelagem 3Desafio 8Demonstração 1

Fontes

APEX Calculus — Hartman, Heinold, Siemers, Chalishajar · CC-BY-NC. Fonte primária — §4.4 Newton's Method.
OpenStax Calculus Volume 1 — Strang, Herman et al. · CC-BY-NC-SA. §4.9 Newton's Method. Exercícios aplicados (TIR, sistemas).
REAMAT — Cálculo Numérico (Python) — UFRGS Reamat Colaborativo · CC-BY-SA. Cap. 3 Zeros de funções. Implementações Python, análise de erro, método da secante.