Métodos quase-Newton

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 esboço de algoritmo pode esquematizado como

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. Além disso, da mesma forma que para o método de Newton, é necessário estabelecer um critério de parada.

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.

3. Considere a implementação abaixo para o método da secante.

function [x,fx,k] = secante(f,x0,x1,tol,K)

# [x, fx, k] = secante(f,x0,x1,tol,K)
#
# Aproxima um zero da função f, partindo do ponto x1,
# calculando a primeira aproximação para a reta tangente
# usando o ponto x0, até que uma aproximação x com
# |f(x)| ≤ tol seja obtida ou até que K iterações sejam
# realizadas.
#
# Esta função retorna:
# x  - aproximação para o zero de f (ou NaN em caso de erro)
# fx - o valor de f em x
# k  - quantidade de iterações realizadas
   
   f0 = f(x0);
   f1 = f(x1);

   k = 0;
   while (abs(f1) > tol) && (k < K)

      g = (f1-f0) / (x1-x0);
      x = x1 - f1 / g;

      x0 = x1;
      x1 = x;

      f0 = f1;
      f1 = f(x1);

      k = k + 1;
   endwhile

   fx = f1;
endfunction 

1. Proponha uma alteração na implementação acima, na qual apenas um ponto inicial é fornecido, de modo que o segundo ponto necessário para o método da secante seja construído automaticamente.
2. Inclua na implementação proteção para que não haja divisão por zero. O que pode ser feito caso isto ocorra?
3. Experimente alterar a condição de parada da implementação.