Confronto con il metodo di bisezione

Se il metodo di Newton converge, ovvero $\{x_n\} \to 0$ è triviale che:

$\displaystyle \exists \bar{n} : C\,e_n \leq \Theta,\quad \forall n \geq \bar{n},\,\Theta > 0$

Fissato un $\Theta \in [0,\,1]$ , si ha:

$\displaystyle e_{n+1}$	$\displaystyle \leq C\,e_n^2$
$\displaystyle C\,e_{\bar{n}+1}$	$\displaystyle \leq C^2\,e_{\bar{n}}^2$
$\displaystyle C\,e_{\bar{n}+1}$	$\displaystyle \leq (C\,e_{\bar{n}})^2 = \Theta^2$
$\displaystyle C\,e_{\bar{n}+2}$	$\displaystyle \leq (C\,e_{\bar{n}+1})^2 = \Theta^4$
$\displaystyle C\,e_{\bar{n}+k}$	$\displaystyle \leq \Theta^{2^k}$

Ponendo $\Theta = 1/2$ è possibile confrontare il metodo di Newton con il metodo di bisezione:

$\displaystyle C\,e_{\bar{n}+k}$	$\displaystyle \leq \left(\frac{1}{2}\right)^{2^k}$	Newton
$\displaystyle C\,e_{\bar{n}+k}$	$\displaystyle \leq \left(\frac{1}{2}\right)^k$	Bisezione

Matteo Lisotto, Tobia Tesan - CC-BY 2.0