Métodos quase-Newton

Métodos para aproximar zeros de função, mais baratos que o método de Newton

Vamos lá?

Os métodos quase-Newton são tentativas de tornar o método de Newton mais barato, evitando o cálculo da derivada. Só que essa economia também tem seu preço.

A aplicação do método de Newton, além do cálculo da função, depende da avaliação da derivada em cada iterando. Isso pode ser uma complicação em casos onde, a derivada da função não é conhecida explicitamente, ou quando, mesmo conhecida, seu cálculo é caro do ponto de vista computacional.

Uma classe de métodos, conhecidos como métodos quase-Newton, tenta superar essas dificuldades, evitando computar a derivada da função, que é trocada por uma aproximação. Os métodos diferem entre si pela forma como a derivada é aproximada.

Por exemplo, um método muito simples, é o método das cordas, onde a derivada é computada uma única vez, na aproximação inicial, e depois mantida constante durante todas as iterações. Sua iteração é dada por $$ x_{k+1} = x_k - {f(x_k) \over f'(x_0)}.$$

Uma alternativa melhor nos leva ao método da secante. Neste método, a derivada em $x_k$ é aproximada por uma fórmula de diferenças que, geometricamente, corresponde à inclinação da reta secante que intersepta a função nos pontos das últimas duas iterações, como ilustrado na figura abaixo.

Desta forma, a iteração fica $$ x_{k+1} = x_k - {f(x_k) \over g_k},$$ onde $$g_k = \frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}.$$ Este método tem convergência superlinear e precisa de dois pontos para ser inicializado. Seu algoritmo pode esquematizado como

  • Sejam $x_0$ e $x_1$ duas aproximações iniciais para $x_*$, zero de $f$.
  • Para $k=1,2,\ldots$
    • $g_k \leftarrow \left[f(x_k) - f(x_{k-1})\right] / \left(x_k- x_{k-1}\right)$
    • $x_{k+1} \leftarrow x_k - f(x_k) / g_k,$ desde que $g_k \neq 0$

Uma implementação cuidadosa do algoritmo acima deve se preocupar em preservar cálculos feitos em uma iteração, que sejam necessários para a iteração seguinte.

Observe que se $x_k\to x_*,$ então $|x_k - x_{k-1}| \to 0$, ou seja, a medida que os iterandos obtidos pelo método da secante se aproximam do zero da função, a diferença entre eles vai e zero e portanto $g_k \to f'(x_*)$ (por quê?). Isto significa que a iteração do método da secante fica cada vez mais próxima da iteração do método de Newton. O resultado disto é a convergência superlinear do método da secante.

Até agora discutimos o problema de resolver uma única equação não linear. Na próxima aula iniciaremos a discussão sobre várias equações não lineares em simultâneo, para poder depois definir métodos para sistemas de equações não lineares.

1. Aplique o método da secante para determinar um zero de $f(x) = 2\ln(x)-x+3.$ Em cada iteração, exiba a diferença $|g_k - f'(x_k)|.$

2. Pesquise por outros métodos quase-Newton. Tente aplicar ao problema acima um dos métodos que você tenha descoberto.