```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
```




    0.0



## 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
def newton_list(f,df,x, prec=1e-8, maxiter=100, iterr = 0, lst = [], reti = False):
    if maxiter == iterr:
        return None
    dx = f(x)/df(x)
    newx = x - dx
    xs = lst[:]
    xs.append(x)
    if abs(dx) < prec:
        if reti:
            return xs, iterr
        else:
            return xs
    else:
        return newton_list(f,df,newx, prec,iterr = iterr+1, lst = xs)
```


```python
def newton_sec_list(f,x1,x2, tol=1e-10, maxiter=100, lst = []):
    """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))
    xs = lst[:]
    xs.append(x1)
    if abs(prox - x2) < tol: # Erro pequeno: convergiu
        return xs
    if maxiter == 0: # Não convergiu
        return xs
    
    return newton_sec_list(f,x2,prox,tol, maxiter-1,xs)

```


```python
def f(x): return x**3 -5
def df(x): return 3*x**2

lnewton = newton_list(f,df,100)
lsecante = newton_sec_list(f,100,200)
ans = 5**(1/3)
plt.semilogy(np.abs(np.array(lnewton) - ans), label='Newton')
plt.semilogy(np.abs(np.array(lsecante) - ans), label='Secante')
plt.legend()
plt.show()
```


```python
a = newton_list(np.sin,np.cos,3,prec=1e-14)
a
```




    [3, 3.142546543074278, 3.141592653300477, 3.141592653589793]



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


```python
### Resposta aqui
nwt_lst = newton_list(f,df,100)
nwt_sec_lst = newton_sec_list(f,100,200)
v1 = np.arange(0,len(nwt_lst),1)
v2 = np.arange(0,len(nwt_sec_lst),1)

_, [ax1, ax2] = plt.subplots(ncols=2, figsize=(15,5))
ax1.set_title('Newton')
ax1.semilogy(np.abs(np.array(nwt_lst) - np.pi))
#ax1.plot(v2, nwt_sec_lst)

ax2.set_title('Newton Secante')
ax2.plot(v2, np.abs(np.array(nwt_sec_lst) - np.pi))
plt.show()
```


```python

```

5bc0b83bbf63cc2464dd7eb0f644046cf6207c4d
ipynb
Jupyter Notebook
comp-cientifica-I-2018-2/semana-7/.ipynb_checkpoints/Semana4-Parte2-MetodoSecante-checkpoint.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/Semana4-Parte2-MetodoSecante.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
comp-cientifica-I-2018-2/semana-7/Semana4-Parte2-MetodoSecante.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
Qwen/Qwen-72B
1. YES
2. YES