```python
import numpy as np
import matplotlib.pyplot as plt
```

# O método de Newton com aproximação da secante

Podemos modifiar o método de Newton para que,
em vez de usar a reta tangente, e com isso necessitar da derivada (que podemos não saber calcular de forma simples!)
ele use uma secante, e desta forma apenas uma aproximação da derivada.

Como vimos na parte anterior, a equação da reta secante é dada por
$$ S_{f,x1,x2}(t) = f(x_1) + \frac{f(x_2) - f(x_1)}{x_2 - x_1}(t - x_1), $$
daonde vemos que $\frac{f(x_2) - f(x_1)}{x_2 - x_1}$ é, naturalmente, uma aproximação da derivada.

Substituindo diretamente no método de Newton, temos assim uma fórmula que usa dois valores:
$$S_f(x_1,x_2) = x_1 - \frac{f(x_1)}{\frac{f(x_2) - f(x_1)}{x_2 - x_1}}.$$

## Simetria

É claro que a reta secante que passa em $x_1$ e $x_2$ não depende da ordem,
e as fórmulas que obtivemos acima parecem privilegiar $x_1$ face a $x_2$.
Isso é apenas porque não nos demos ao trabalho de explicitar a simetria:

Para a equação da reta secante:
$$\begin{align}
S_{f,x1,x2}(t)
  & = f(x_1) + \frac{f(x_2) - f(x_1)}{x_2 - x_1}(t - x_1) \\
  & = \frac{f(x_1)(x_2 - x_1) + \big[f(x_2) - f(x_1)\big]t - \big[f(x_2) - f(x_1)\big]x_1}{x_2 - x_1} \\
  & = \frac{x_2 f(x_1) - x_1 f(x_2) + t\big[f(x_2) - f(x_1)\big]}{x_2 - x_1}.
\end{align}$$
Para encontrar o zero da secante, podemos agora tanto fazer diretamente da equação acima,
igualando o numerador a zero,
ou então simetrizando $S_f(x_1,x2)$,
o que dá a mesma fórmula (ainda bem!):
$$S_f(x_1,x_2)
  = x_1 - \frac{f(x_1)}{\frac{f(x_2) - f(x_1)}{x_2 - x_1}}
  = x_1 - \frac{f(x_1)\big( x_2 - x_1 \big)}{f(x_2) - f(x_1)}
  = \frac{x_1 f(x_2) - x_2 f(x_1)}{f(x_2) - f(x_1)}.$$

No caso de um método iterativo, podemos usar outros pontos de $f$ já calculados,
para evitar chamar $f$ várias vezes!
Assim, temos a seguinte recorrência:
- Os valores $x_1$ e $x_2$ são tomados ("ao acaso", ou talvez "espertamente", dependendo se podemos ser espertos)
- Iteramos $x_{n+2} = S_f(x_{n+1},x_n)$
Neste caso, como temos uma _ordem_ entre os pontos utilizados,
haverá uma certa assimetria no algoritmo.


```python
def newton_sec(f,x1,x2, tol=1e-10, maxiter=100):
    """Método de Newton com aproximação da secante, para a função $f$, começando em x1 e x2."""
    prox = (x1*f(x2) - x2*f(x1))/(f(x2) - f(x1))
    if abs(prox - x2) < tol: # Erro pequeno: convergiu
        return prox
    if maxiter == 0: # Não convergiu
        return prox
    
    return newton_sec(f,x2,prox,tol, maxiter-1)
```


```python
import numpy as np
```


```python
ans = newton_sec(np.cos, 0,3)
ans - np.pi/2
```

## Performance

O "método da secante", como é conhecido, converge mais lentamente do que o método de Newton:
podemos mostrar que os erros $e_i$ satisfazem uma "recorrência de desigualdade":
$$ e_{n+1} < C (e_n \cdot e_{n-1}). $$
Mas, como este calcula menos vezes a função, ele converge mais rápido por número de chamadas a $f$.

### Exercício: Fazer uma comparação entre as velocidades de Newton e da Secante.

Comece fazendo um gráfico simples, com a precisão da resposta em função do número de passos.
Em seguida, faça o gráfico da precisão em função do número de vezes que a função $f$ é calculada.

Se tiver tempo, faça desenhos indicando os pontos das iterações.
Enfim, se você tiver mais tempo ainda, anime o desenho "ao longo do tempo":
faça aparecer os pontos de Newton e da secante "na ordem em que foram obtidos"
(em função do número de vezes que $f$ foi calculada).


```python
from rootfinding import newton_list
```


```python
def newton_sec_list(f,x1,x2, tol=1e-10, maxiter=100):
    ### Resposta aqui

```

Gráfico em função do andamento da função:


```python
### Resposta aqui

```

e19b6d38408ec20397ff100f5558384f4a9411c5
ipynb
Jupyter Notebook
comp-cientifica-I-2018-2/semana-7/raw_files/Semana4-Parte2-MetodoSecante.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
2019-12-23T16:39:01.000Z
2019-12-23T16:39:01.000Z
comp-cientifica-I-2018-2/semana-7/raw_files/Semana4-Parte2-MetodoSecante.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
comp-cientifica-I-2018-2/semana-7/raw_files/Semana4-Parte2-MetodoSecante.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
Qwen/Qwen-72B
1. YES
2. YES