Caderno 5

Método de Newton: Sair pela Tangente sem Perder o Rumo¶

O método de Newton, também conhecido como método de Newton-Raphson, é uma técnica iterativa poderosa para encontrar aproximações das raízes de equações não lineares. Sua ideia central é usar a reta tangente à curva da função em um ponto de aproximação inicial para estimar onde essa reta cruza o eixo $x$, fornecendo assim uma nova aproximação. Esse processo é repetido até que a diferença entre iterações sucessivas seja suficientemente pequena, indicando convergência para uma raiz.

Apesar de ser um método rápido e eficiente com convergência quadrática quando a aproximação inicial está suficientemente próxima da raiz, ele também apresenta desafios. Ele exige que a derivada $f'(x)$ esteja disponível e bem comportada. Além disso, se o ponto inicial estiver longe da raiz, ou se a função tiver pontos de inflexão ou derivadas próximas de zero, o método pode divergir ou oscilar. Por isso, é comum combiná-lo com outras técnicas, como a inspeção gráfica ou métodos mais estáveis (como bisseção) para estimar bons pontos iniciais.

Explicação do algoritmo¶

O processo iterativo do método é dado pela seguinte função de iteração:

onde:

• $x^{(k-1)}$ é a aproximação atual.

• $f(x^{(k-1)})$ é o valor atual da função.

• $f'(x^{(k-1)})$ é o valor atual da primeira derivada da função.

A ideia é que a interseção da tangente à curva $f(x)$ no ponto $x^{(k-1)}$ com o eixo $x$ forneça uma nova aproximação $x^{(k)}$. O Método de Newton é uma ferramenta essencial no arsenal de métodos numéricos, oferecendo uma abordagem eficiente e poderosa para a solução de uma ampla variedade de problemas matemáticos.

O algoritmo funciona da seguinte forma:

1. Inicialize $x^{(0)}$ (chute inicial)

2. Para $k$ de 1 até $N$:

   a. Calcule $f(x^{(k)})$

   b. Calcule $f'(x^{(k)})$ (derivada da função no ponto $x^{(k)}$)

   c. Se $f'(x^{(k)}) = 0$, retorne erro (derivada zero, o método falha)

   d. Calcule $x^{(k)} = \phi(x^{(k-1)})$ (como o processo iterativo acima)

   e. Se $ER(x^{(k)}, x^{(k-1)}) < \epsilon$, então a solução foi encontrada com a precisão desejada. Retorne $x^{(k)}$.

3. Se o número máximo de iterações for atingido, retorne a última aproximação $x^{(k-1)}$.

Um caso clássico¶

Considere que desejamos calcular a raiz enésima de um número real positivo $d$, ou seja, $x = \sqrt[n]{d}$. Podemos fazer isto utilizando o método de Newton de uma forma muito simples, mas “diferente”. Em primeiro lugar, note que buscamos a solução da equação $f(x) = 0$, tal que

Calculando derivada, obtemos

Utilizando ambas na função de iteração do método de Newton, chegamos a

que, finalmente, pode ser simplificada no processo iterativo

Se um “palpite” razoável for dado para $x^{(0)}$, a convergência para o valor real será rápida.

Exemplo numérico¶

Vamos calcular $\sqrt[3]{27}$ – claramente, $n = 3$ e $d=27$ – com um chute inicial $x^{(0)} = 5.0$.

1. A função de iteração para este exemplo é dada por $x^{(k)} = \frac{1}{3} \left( 2x^{(k-1)} + \frac{27}{[x^{(k-1)}]^{2}} \right) = \frac{2x^{(k-1)}}{3} + \frac{9}{[x^{(k-1)}]^{2}}$

2. Partindo de $x^{(0)} = 5$, desenvolvemos as seguintes iterações

   • $k = 1 \Rightarrow x^{(1)} = \frac{2(5)}{3} + \frac{9}{5^2} = \frac{10}{3} + \frac{9}{25} = 3.333 + 0,36 = 3.693$

   • $k = 2 \Rightarrow x^{(2)} = \frac{2(3.693)}{3} + \frac{9}{3.693^2} \approx 2.462 + \frac{9}{13.636} \approx 2.462 + 0.660 = 3.122$

   • $k = 3 \Rightarrow x^{(3)} = \frac{2(3.122)}{3} + \frac{9}{3.122^2} \approx 2.081 + \frac{9}{9.750} \approx 2.081 + 0.923 = 3.004$

   • $k = 4 \Rightarrow x^{(4)} = \frac{2(3.004)}{3} + \frac{9}{3.004^2} \approx 2.0027 + \frac{9}{9.024} \approx 2.0027 + 0.9973 = 3.000$

Com apenas 4 iteradas chegamos à resposta.

Implementação do algoritmo¶

No algoritmo proposto abaixo, a função newton requererá 5 argumentos:

• a estimativa inicial, representada pela variável x0;

• a função $f(x)$ propriamente dita, representada por f;

• a derivada $f'(x)$, representada por df;

• o erro relativo assumido, representado por tol;

• o número máximo de iterações $N$ para tentativa de solução, representado por nmax.

Playground interativo¶

Utilize o playground interativo abaixo para testar o método da bisseção para funções não lineares quaisquer. Como dado de entrada para $f(x)$, utilize funções escritas nos moldes de Python científico como um tipo str. Para os parâmetros do intervalo inicial e de erro, utilize float.

Aplicações¶

Exemplo: Resolva o problema $f(x) = 0$, para $f(x) = -\text{arccos}(x) + 4\text{sen}(x) + 1.7$, no intervalo $-0.2 \le x \le 1.0$ e $\epsilon = 10^{-3}$.

Exemplo: Resolva o problema $h(z) = 0$, para $h(z) = -z(1-2z)^{-1} - \text{tan}(z+1)$, no intervalo $[1,8]$ e $\epsilon = 10^{-5}$.

Como no exemplo anterior, para utilizarmos o método de Newton é preciso saber a derivada da função $h(z)$. Vamos encontrá-la utilizando o módulo de computação simbólica sympy.

A partir daí, utilizamos a expressão normalmente na função.

Compare a quantidade de iterações obtidas com o mesmo exemplo resolvido com o algoritmo da bisseção.

Derivação para otimização¶

O método de Newton, originalmente desenvolvido para encontrar raízes de equações, pode ser adaptado com grande eficácia para problemas de otimização. Nesse contexto, seu objetivo é encontrar os pontos críticos de uma função — ou seja, valores onde a derivada é nula e que podem corresponder a mínimos, máximos ou pontos de sela. A ideia central é usar uma aproximação quadrática da função por meio da série de Taylor de segunda ordem. O processo pode ser resumido nos passos a seguir:

1. Função Objetivo (FO): seja $f(x)$ uma função escalar diferenciável cujo mínimo queremos encontrar.

2. Expansão de Taylor de Segunda Ordem: expandimos $f(x)$ em torno de um ponto $x^{(k)}$ usando a série de Taylor até a segunda ordem:

   $$f(x) \approx f(x^{(k)}) + f'(x^{(k)}) (x - x^{(k)}) + \frac{1}{2} f''(x^{(k)}) (x - x^{(k)})^2,$$

   (6)

   onde $f'(x^{(k)})$ é a primeira derivada (gradiente) de $f$ em $x^{(k)}$ e $f''(x^{(k)})$ é a segunda derivada (Hessiana) de $f$ em $x^{(k)}$.

3. Condição de otimização: para encontrar o ponto $x$ que minimiza $f(x)$, devemos encontrar um ponto onde a derivada da função seja zero. Definimos a direção de descida $t$ como $x - x^{(k)}$:

   $$f(x^{(k+1)}) \approx f(x^{(k)}) + f'(x^{(k)}) t + \frac{1}{2} f''(x^{(k)}) t^2$$

   (7)

4. Derivada da expansão: para minimizar $f(x)$, tomamos a derivada da expressão acima em relação a $t$ e igualamos a zero:

   $$\frac{d}{dt}\left[ f(x^{(k)}) + f'(x^{(k)}) t + \frac{1}{2} f''(x^{(k)}) t^2 \right] = 0$$

   (8)

   Uma vez que $f(x^{(k)})$ não depende de $t$, é uma constante. Assim obtemos:

   $$f'(x^{(k)}) + f''(x^{(k)}) t = 0$$

   (9)

5. _solução para a direção $t$: resolvendo para $t$, temos:

   $$t = -\frac{f'(x^{(k)})}{f''(x^{(k)})}$$

   (10)

6. Atualização da Iteração: a próxima aproximação $x^{(k+1)}$ é obtida somando $t$ ao ponto atual $x^{(k)}$:

   $$x^{(k+1)} = x^{(k)} + t = x^{(k)} - \frac{f'(x^{(k)})}{f''(x^{(k)})}$$

   (11)

A derivada $f'(x^{(k)})$ indica a inclinação da função em $x^{(k)}$. A segunda derivada $f''(x^{(k)})$ fornece informações sobre a curvatura da função. Se $f''(x^{(k)}) > 0$, estamos em um ponto onde a função está curvando para cima (mínimo local), enquanto $f''(x^{(k)}) < 0$ indica um ponto onde a função está curvando para baixo (máximo local). O passo $t$ determina a magnitude e a direção do ajuste necessário para aproximar-se do ponto de mínimo (ou máximo).

Método de Halley¶

O método de Halley é uma extensão do método de Newton e utiliza até a terceira derivada da função. Enquanto o método de Newton tem convergência quadrática, o método de Halley converge mais rapidamente e alcança convergência cúbica, pois usa mais informações sobre a curvatura da função. De maneira similar ao que já fizemos, vamos derivar a fórmula partindo diretamente da expansão de Taylor:

1. Expansão de Taylor: expandimos a função $f(x)$ em torno de um ponto $x^{(k)}$:

   $$f(x) \approx f(x^{(k)}) + f'(x^{(k)}) (x - x^{(k)}) + \frac{1}{2} f''(x^{(k)}) (x - x^{(k)})^2 + \frac{1}{6} f'''(x^{(k)})(x - x^{(k)})^3,$$

   (12)

2. Estimativa da raiz: supondo que $x^{(k+1)} = x^{(k)} + \Delta x$ é a nova estimativa da raiz, então queremos $f(x^{(k+1)}) = 0$. Substituindo $\Delta x = x^{(k+1)} - x^{(k)}$ na expansão de Taylor e igualando a zero, temos:

   $$f(x^{(k)}) + f'(x^{(k)})\Delta x + \frac{1}{2} f''(x^{(k)})(\Delta x)^2 + \frac{1}{6} f'''(x^{(k)})(\Delta x)^3 = 0$$

   (13)

3. Isolamento do passo: a solução para $\Delta x$ (que nos dá a atualização para $x$) é dada pela fórmula:

   $$\Delta x = -\frac{f(x^{(k)})}{f'(x^{(k)})} \left( \frac{2}{2 - \frac{f(x^{(k)}) f''(x^{(k)})}{f'(x^{(k)})^2}} \right)$$

   (14)

4. Iteração do Método de Halley: a fórmula iterativa do método de Halley é então:

   $$x^{(k+1)} = x^{(k)} - \frac{f(x^{(k)})}{f'(x^{(k)})} \left( \frac{2}{2 - \frac{f(x^{(k)}) f''(x^{(k)})}{f'(x^{(k)})^2}} \right)$$

   (15)

As vantagens do método de Halley sobre o método de Newton são a taxa de convergência e o alcance de uma solução mais precisa com menos iterações em comparação. Por outro lado, o cálculo das derivadas de ordem superior pode ser computacionalmente custoso e complexo, especialmente para funções complicadas. A precisão do método também depende da precisão das derivadas de segunda e terceira ordem. Portanto, erros nessas derivadas podem afetar a convergência e a precisão da solução.

Problemas propostos¶

• Crie um código genérico que implemente o algoritmo do método de Newton de modo que a derivada seja calculada diretamenta por computação simbólica, sem intervenção manual, quando for possível. Dica: use sympy.lambdify.

• Faça uma implementação do método de Newton para otimização e uma para o método de Halley. Em seguida, incorpore a capacidade de cálculo das derivadas de maneira automática.