Seja $f:[a,b]\to \mathbb{R}$ uma função
Considere a sequência $\{x_n\}_{n\in \mathbb{N}}$ com $x_0\in (a,b)$ e
$$x_{n+1}=x_n - \frac{f(x_n)}{f^\prime(x_n)}$$Antes de mostrar as condições de convergência, vamos assumir que a sequẽncia converge a $r$, e vamos ver com que rapidez.
Seja $e_n=x_n-r$ o erro de $n$-ésima iteração do método de Newton
$$ r = x_n - e_n \implies f(r)= f(x_n-e_n) = f(x_n)- f^\prime(x_n)e_n + \frac{1}{2}f^{\prime\prime}(\xi_n)e_n^2 = 0$$$$ \frac{f(x_n)}{f^\prime(x_n)} = e_n - \frac{1}{2}\frac{ f^{\prime\prime}(\xi_n)}{f^\prime(x_n)}e_n^2 = x_n - x_{n+1}= e_n - e_{n+1}$$daí
$$ e_{n+1} = \frac{1}{2}\frac{ f^{\prime\prime}(\xi_n)}{f^\prime(x_n)}e_n^2 $$$$ \lim_{n \to \infty} \frac{e_{n+1}}{e_n^2} = \frac{1}{2}\frac{f^{\prime\prime}(r)}{f^\prime(r)} = C $$Esta é a definição de convergência de ordem 2 (ou convergência quadrática)
A convergência depende da escolha de um $x_0$ bem próximo de $r$. Em primeiro lugar, tomemos um número $\delta > 0$ tal que a derivada $f^\prime(x) \neq 0$ no intervalo $ I= |x-r|\lt \delta$ ($I=(r-\delta, r+\delta)$). Definimos: $$ c(\delta) = \frac{1}{2} \frac{\max_{x\in I}f^{\prime\prime}(x)}{\min_{x\in I}f^\prime{x}} $$ Note que $\lim_{\delta \to 0}\delta c(\delta)=0$ então podemos tomar um $\delta$ talque $\delta c(\delta)=\alpha < 1$.
Deste modo temos que:
$$|x_1-r|=|e_1|=\frac{1}{2}\frac{ |f^{\prime\prime}(\xi_0)|}{|f^\prime(x_0)|}e_0^2 \leq c(\delta)|e_0||e_0| \lt \alpha|e_0|$$e por recorrência $$ |e_n| \lt \alpha^n|e_0| $$ O que mostra a convergência $\square$
Esta é uma variação do método de Newton. Fazemos a aproximação da derivada por $$ f^\prime(x_n) = \frac{f(x_n) - f(x_{n-1})}{x_n-x_{n-1}}$$ o que nos dá a iteração de segunda ordem:
$$ x_{n+1} = \frac{x_{n-1}f(x_n)-x_nf(x_{n-1})}{f(x_n) - f(x_{n-1})}$$def secante(f,x0,x1,epsilon):
""" Método da secante para a encontrar a raiz de f(x)=0 """
x= (x0*f(x1) - x1*f(x0))/(f(x1) - f(x0))
while abs(x1-x0) > epsilon:
x0,x1 = x1, x
x= (x0*f(x1) - x1*f(x0))/(f(x1) - f(x0))
return x
Para testar vamos usar a função $f(x) =x^6 -x -1$.
%matplotlib inline
from matplotlib.pyplot import plot
x= arange(-1,1.3,0.01)
f = lambda x: x**6-x-1
plot(x,f(x))
grid()
secante(f,1,1.3,0.001)
1.1347241385131241
secante(f,-1.0,-0.5,0.001)
-0.7780895986591118