\documentclass[10pt]{elsarticle}

% Copyright (C) 2007 Alvise Sommariva. This is a free document; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% at your option) any later version. This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details. You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}

\input{myprefs.tex}

\begin{document}
\begin{frontmatter}

\title{\bf Equazioni nonlineari \thanks{Ultima revisione: \today}}

\author{A. Sommariva \thanks{Dipartimento di Matematica,
Universit\mya degli Studi di  Padova, stanza 419, via Trieste 63, 35121 Padova, Italia ({\tt 
alvise@math.unipd.it}).} %Telefono: +39-049-8271350.
}

\begin{keyword}
Metodo di bisezione, stima dell'errore col residuo pesato; metodo di 
Newton, convergenza globale, velocit\mya (ordine) di convergenza, cenno alla 
convergenza locale, stima dell'errore, altri metodi di linearizzazione 
(secanti); iterazioni di punto fisso, convergenza e ordine di 
convergenza.
\end{keyword}

\end{frontmatter}

\noindent {\it{Revisione}}: \today

\noindent\rule{12.15cm}{0.4pt}



%------------------------------------------------------------------------------------------------------------------------
% Soluzione numerica di equazioni nonlineari.
%------------------------------------------------------------------------------------------------------------------------

\section{Soluzione numerica di equazioni nonlineari}

Data una funzione continua $f: I \rightarrow \R$ (dove al solito $I$ \mye un intervallo di $\R$), si desidera calcolare $x^{\ast}$ tale
che $f(x^{\ast})=0$. Questo problema \`e assai diffuso nel calcolo
numerico e richiede in generale l'utilizzo di un {\sl{metodo iterativo}}
per approssimare tali {\sl{soluzioni}} $x^{\ast}$. In altri termini, partendo da un valore
iniziale $x_{0}$ si
genera una sequenza di valori $x_{1},x_{2},x_{3},\ldots$ che si desidera
convergano, magari velocemente, ad una opportuna soluzione $x^{\ast}$, o perfino la determinino in un numero finito di passi.

\begin{example}
Per un teorema di Galois (a volte detto di Abel-Ruffini \cite{WIKGAL}), per $n \geq 5$, {{non esistono formule risolutive mediante le 4 operazioni e estrazione di radici}} per il
calcolo degli zeri di una generica equazione polinomiale $p_{n}(x)=0$ che richiedano un numero finito di operazioni. 

Ci\myo non vieta di approssimare tali radici
con un metodo numerico
compiendo un errore assoluto e/o relativo inferiore a un valore
prestabilito detto {\sl{tolleranza}}.

\smsp

Equazioni di questo tipo possono 
\begin{itemize}
\item non avere soluzioni reali, si pensi ad esempio $x^2+2=0$ in cui il discriminante \mye negativo; 
\item avere pi\myu di una soluzione come nel caso di $x^2-5x+6=0$ che ha per soluzioni $x=2$, $x=3$;
\item avere $x^{\ast}$ semplici ovvero tali $f^{\prime}(x^{\ast}) \neq 0$, come nel caso di $f(x)=x^2-3x+2=0$ che ha per soluzioni $x=1$, $x=2$, in cui non si annulla $f^{\prime}(x)=2x-3$ (vale rispettivamente $-1$ e $1$);
\item averne $x^{\ast}$ multiple ovvero tali $f^{\prime}(x^{\ast}) = 0$, come nel caso di $(x^2-1)^2=0$ in cui $1$ \mye soluzione multipla in quanto $f^{\prime}(x)=2(x^2-1)$ ha zero in $1$ tanto per $f$ che per $f^{\prime}$.
\end{itemize}
Queste differenti situazioni hanno causato varie difficolt\mya nella soluzione delle equazioni polinomiali, per cui usualmente si applicano metodi ad hoc.
\end{example}

\begin{example}
Si consideri il problema
di calcolare gli zeri della funzione continua $f(x)=\sin x -x$, cio\mye quei valori $ x^{\ast}
$ per cui $\sin x^{\ast}-x^{\ast}=0$. Visto che
$$\sin x^{\ast}-x^{\ast}=0 \, \Leftrightarrow \, \sin x^{\ast}= x^{\ast} $$
e
$$|\sin x| \leq 1$$
risulta evidente che se esiste un tale zero, necessariamente
$$x^{\ast} \in [-1,1].$$
Inoltre da 
$$
f(1)=\sin(1)-1 \approx -0.1585
$$
$$
f(-1)=\sin(.1)-(-1) \approx 0.1585
$$
per il teorema degli zeri di una funziona continua, possiamo asserire che un tale zero esiste. In effetti la funzione \mye decrescente in $[-1,1]$ in quanto $f^{\prime}(x)=\cos x -1 \leq 0$ per ogni $x \in [-1,1]$ e quindi tale zero \mye unico (e si vede subito essere $x^{\ast}=0$).
\end{example}

La prima tentazione che sorge per studiare gli zeri di una funzione continua $f$ \'e di farne il grafico. Purtroppo questa strategia non \mye sempre efficace, e usualmente richiede troppi calcoli dovuti alla valutazione della funzione in molti punti.

\smsp

Tipicamente 
\begin{itemize}
\item si valuta $f$ in molti punti campione $x_1,x_2,\ldots,x_k, \ldots, x_N$ (con $x_{k} < x_{x_k+1}$), 
\item si disegnano le coppie $(x_k,f(x_k))$ nel piano cartesiano,
\item si approssima il grafico, unendo con segmenti tutte le coppie $P_j=(x_j,f(x_j))$ $P_{j+1}=(x_{j+1},f(x_{j+1}))$, $j=1,\ldots,N-1$.
\end{itemize}

Se il numero $N$ di campioni \mye piccolo, allora tra certi $x_k$ e $x_{k+1}$, il grafico di $f$ potrebbe essere molto diverso da quello della versione numerica, e alcuni zeri potrebbero non essere individuati. 

Si pensi ad esempio di studiare $f(x)=10^6 (x-1/1000)(x+1/1000)$ che ovviamente ha zeri $-1/1000$, $1/1000$. Se campioniamo la funzione nei punti equispaziati $x_{k}=-1+k/100$, con $k=0,\ldots,100$ gli zeri non vengono individuati anche dopo zoom successivi, per mancanza di dati.

 \begin{figure}[!ht]\label{tangenti}
 \centering
   {\includegraphics[scale=0.25,clip]{gr_I.eps}}
      {\includegraphics[scale=0.25,clip]{gr_II.eps}}
 \caption{Problemi con grafici e zoom per lo studio di $f(x)=0$ per $f(x)=10^6 \cdot (x-1/1000)(x+1/1000)$, qualora eseguito via campionamento nei punti $x_{k}=-1+k/100$, con $k=0,\ldots,100$. Se non si esegue lo zoom, si direbbe che esiste un unico zero, verosimilmente uguale a $0$.}
 \end{figure}

Si potrebbe ovviare aumentando il numero di punti equispaziati, ma da una parte non si avrebbe ancora la garanzia di fedelt\mya del grafico, e dall'altra il numero di valutazioni diventerebbe eccessivo.

A dispetto di questa analisi pessimistica, avere un'idea del grafico della funzione, ottenuto anche per mezzi analitici tramite il classico {\sl{studio di funzione}}, nella maggior parte dei casi pu\myo permettere la localizzazione di alcuni zeri, problema potenzialmente non banale dal punto di vista algoritmico.


\section{Metodi iterativi e convergenza}
Introduciamo di seguito dei metodi iterativi che permettano l'approssimazione di zeri di funzioni continue.

Un metodo iterativo \mye un tipo di metodo numerico nel quale l'approssimazione $x_n$ della soluzione al problema matematico esaminato \mye ottenuta partendo dalle precedenti $x_0,\ldots,x_{n-1}$. 

Usualmente si fornisce un punto di partenza $x_0$ per tale processo, dopo una qualche analisi teorica, altrimenti lo si sceglie casualmente.

\smsp

Nel caso della soluzione di equazioni non lineari, ci sono due aspetti specifici di cui \`e opportuno tenere conto
\smsp
\begin{enumerate}
\item Garanzia della convergenza alla soluzione: se $\{x_{n}\}$ \`e la
soluzione generata dal metodo e $x^{\ast}$ \`e uno zero per $f$, si
cercano delle condizioni per cui $x_{n} \rightarrow x^{\ast}$.\smsp
\item Se $x_{n} \rightarrow x^{\ast}$ si cerca la velocit\mya con cui
ci\myo accade. In tal senso, \`e importante calcolare il cosidetto
{\sl{ordine di convergenza}}. 
\begin{definition}
Supponiamo un metodo per la soluzione di equazioni nonlineari, generi una successione
$\{x_{k}\}$ convergente allo zero $x^*$ del problema $f(x^*)=0$. Si ponga $e_k=|x_k-x^*|$.
Il metodo ha {\sl{ordine di convergenza}} almeno $p \geq 1$ se esiste $C >0$ tale che 
$$
e_{n+1} \leq e_n^p
$$
e ordine esattamente $p$ se vale 
$$
\lim_{n \rightarrow \infty}{ \frac {|e_{k+1}|} {|e_{k}|^{p}} }=L \neq 0
$$
In particolare, $L$ \`e la {\sl{costante asintotica di errore}}.
\end{definition}

\begin{remark}
Si noti che per $p=1$, necessariamente $L \leq 1$ e che $L < 1$ oppure $C < 1$ sono condizioni sufficienti per la convergenza.
\end{remark}

Se 
\begin{itemize}
\item $p=1$ la convergenza \mye detta {\sl{lineare}};
\item $p>1$  la convergenza \mye detta {\sl{superlineare}}; in particolare per $p=2$ si dice {\sl{quadratica}}, per $p=3$ si dice {\sl{cubica}}.
\end{itemize}

\smsp
\begin{example}
Vediamo con un semplice esempio il caso in cui sia per $k=0,1,2,\ldots$
$${ \frac {|e_{k+1}|} {|e_{k}|^{p}} }={ \frac {1} {10} }, \,\, {|e_{0}|=1 }$$
\noindent
cio\mye
$${ {|e_{k+1}|}  }={ \frac {1} {10} } \, {|e_{k}|^{p}}, \,\, {|e_{0}|=1 }.$$
\smsp
Evidentemente
$$\lim_{n \rightarrow \infty}{ \frac {|e_{k+1}|} {|e_{k}|^{p}} }={ \frac {1} {10} },$$
\noindent e il metodo ha ordine di convergenza $p$.
\smsp
Se abbiamo $p=1$ la successione prodotta sar\mya:
$$e_0=1, \, e_1=1/10, \, e_2=1/100, \, e_3=1/1000, \, \ldots $$
mentre per $p=2$ abbiamo facilmente
$$e_0=1, \, e_1=1/10, \, e_2=1/1000, \, e_3=1/10^6, \ldots,$$
per cui si vede che a parit\mya di $C$, maggiore \mye $p$ allora minore \mye l'errore $e_k$ compiuto a parit\mya di $k$.

Si ottiene in scala semilogaritmica, il grafico \ref{tangenti} che evidenzia come {\sl{asintoticamente}}, ovvero per $n$ sufficientemente grande, sia da preferire un metodo con $p$ maggiore possibile. 
\end{example}

 \begin{figure}[!ht]\label{conv}
 \centering
   {\includegraphics[scale=0.35,clip]{velocita.eps}}
 \caption{Grafico che illustra l'errore di un metodo con convergenza $p=1$ (in rosso a rombi) e $p=2$ (in nero a cerchietti), per $C=1/10$ ed $e_0=1$.}
 \end{figure}

L'utilizzo di tale scala offre alcuni suggerimenti. Se appare asintoticamente come
\begin{itemize}
\item una retta decrescente vuol dire che la (possibile) convergenza {\sl{verosimilmente}} ha ordine
$1$;
\item una parabola decrescente, al di sotto di una qualsiasi retta, vuol dire che la (possibile) convergenza {\sl{verosimilmente}} ha ordine
$>1$.
\end{itemize}

\end{enumerate}



%------------------------------------------------------------------------------------------------------------------------
% Metodo di bisezione.
%------------------------------------------------------------------------------------------------------------------------

\section{Metodo di bisezione (o dicotomico)}
Sia $f:[a,b] \rightarrow {\mathbb R}$ una funzione continua e
supponiamo $f(a)\cdot f(b)<0$, ovvero la funzione $f$ non si annulla agli estremi e assume in $a$ e $b$ valori di segno opposto. 

Di conseguenza, per il {\sl{teorema
degli zeri di una funzione continua}}, l'intervallo $(a,b)$ contiene
{\sl{almeno}} uno zero $x^*$ di $f$. 

\smsp

Il metodo di bisezione pu\myo essere definito in forma algoritmica come segue (cf. {\cite[p.408]{COM}}, {\cite{WIK2}}):

\begin{enumerate}
\item si fissa un intervallo $(a_k,b_k)$, $k \in \{0,1,\ldots\}$ in cui il segno di $f(a_k)$ \mye diverso da quello di $f(b_k)$, ovvero
$$
f(a_k) \cdot f(b_k) < 0;
$$
%Se $f(a_0) \cdot f(b_0) = 0$ allora o $a_0$ o $b_0$ sono zeri di $f$ altrimenti
dal teorema degli zeri di una funzione continua, si sa che esiste almeno un certo $x^{\ast} \in (a_k,b_k)$ che \mye zero di $f$;
\item si calcola il punto medio $x_k$ dell'intervallo $(a_k,b_k)$ ovvero
$$
x_{k}=\frac{a_k+b_k}{2};
$$
\item se $f(x_{k})=0$ si conclude il processo in quanto $x_{k}$ \mye lo zero cercato;
\item se pi\myu in generale un certo criterio di arresto \mye applicabile ed \mye verificato allora si conclude il processo perch\mye si reputa che $x_{k}$ sia un'approssimazione di uno zero;
\item altrimenti, 
\begin{itemize}
\item se $f(a_k) \cdot f(x_{k}) < 0$ si pone $a_{k+1}=a_{k}$, $b_{k+1}=x_{k}$;
\item se $f(x_{k}) \cdot f(b_k) < 0$ si pone $a_{k+1}=x_{k}$, $b_{k+1}=b_k$;
\end{itemize}
e si continua il processo relativamente al nuovo intervallo $(a_{k+1},b_{k+1})$, ripartendo dal punto 1.
\end{enumerate}

\begin{remark}
Si osservi che alla $k$-sima iterazione, il metodo di bisezione utilizza esclusivamente il segno di $f(x_k)$ e non il suo valore effettivo. 
\end{remark}

 \subsection{Convergenza del metodo di bisezione}

Prima di citare un teorema di convergenza del metodo di bisezione, introduciamo la funzione $\lceil x \rceil$ che arrotonda il numero reale $x$ al minore intero non minore di $x$.

Ad esempio,
$$
\lceil 3.14 \rceil =4, \,\,\, \lceil -2.13 \rceil =-2, \,\,\,  \lceil 8 \rceil =8, \,\,\,  \lceil -4 \rceil =-4.
$$
 
 Sussiste il seguente teorema.

\begin{theorem}
Sia $f:[a,b] \rightarrow \R$ una funzione continua e $f(a)\cdot f(b) < 0$. Allora se $x_k$ \mye la $k$-sima iterazione del metodo di bisezione, esiste uno zero $x^*$ di $f$ tale che 
$$
|x_k-x^*| \leq 2^{-(k-1)} (b-a).
$$

Inoltre affinch\mye per un certo $\epsilon > 0 $ si abbia $|x^*-x_k| \leq \epsilon$, necessitano al pi\myu
$$k^*(\epsilon) = \lceil  \log_2 \left(   {(b-a)}/{\epsilon }  \right) \rceil  -1$$
iterazioni.
\end{theorem}

\begin{proof}
Osserviamo che ad ogni iterazione il metodo di bisezione dimezza l'ampiezza dell'intervallo $[a_k,b_k]$ e quindi essendo $a_0=a$, $b_0=b$
\begin{eqnarray}
b_{k}-a_{k}&=&(1/2) (b_{k-1}-a_{k-1})=(1/2)^2 (b_{k-2}-a_{k-2})=\nonumber \\
&\ldots&=(1/2)^{k} (b_{0}-a_{0})=2^{-k}(b-a). \nonumber
\end{eqnarray}
Ricordiamo che $x^{\ast} \in (a_k,b_k)$ per ogni $k=0,1,\ldots$ per cui essendo $x_{k}$ il punto medio di $(a_k,b_k)$, e $x^*$ sta in $[a_k,x_k]$ o $[x_k,b_k]$, abbiamo  
$$|x_{k}-x^{\ast}| \leq (b_k-a_k)/2.$$
Di conseguenza
\begin{eqnarray}
|x_{k}-x^{\ast}| &\leq& (b_k-a_k)/2 = (1/2)^{k} (b-a) \cdot (1/2) \nonumber \\
&=&(1/2)^{k+1} (b-a)=2^{-(k+1)}(b-a). \nonumber
\end{eqnarray}

Se $2^{-(k+1)} (b-a) \leq \epsilon$ necessariamente 
$$|x_{k}-x^{\ast}| \leq 2^{-(k+1)} (b-a) \leq \epsilon.$$

Vediamo qual'\'e il primo indice $k^*(\epsilon)$ per cui $2^{-(k+1)} (b-a) \leq \epsilon$ e di conseguenza otterremo $|x_{k^*(\epsilon)}-x^{\ast}| \leq \epsilon.$.

Essendo il logaritmo in base 2 una funzione continua e crescente in $(0,+\infty)$, applicandolo ad ambo i membri della prima disuguaglianza $$2^{-(k+1)}  \leq \frac{\epsilon}{b-a}$$
ricaviamo
$$-(k+1)=\log_2(2^{-(k+1)})  \leq \log_2\left(\frac{\epsilon}{b-a}\right)$$
ovvero $k+1 \geq - \log_2(\frac{\epsilon}{b-a})$ e il primo intero per cui ci\myo accade \mye
$$k^*(\epsilon) = \lceil  - \log_2 (   \frac{\epsilon}{b-a}   ) \rceil  -1= \lceil  \log_2 (  {(b-a)}/{\epsilon }  ) \rceil  -1.$$
Si osservi che tipicamente $\frac{\epsilon}{b-a}  \ll 1 $ e quindi $ \log_2(\frac{\epsilon}{b-a}) < 0$, per cui il numero di iterazioni $k(\epsilon)$ \mye effettivamente un numero naturale.

\end{proof}

\begin{remark}
Il teorema precedente implica che, se $f(a) \cdot f(b) <0$ allora il metodo di bisezione converge a una soluzione $x^{\ast} \in (a,b)$ perch\mye per ogni $\epsilon > 0$ esiste $k^*(\epsilon)$ tale che se $k \geq k^*(\epsilon)$ allora $|x_k-x^{\ast}| \leq \epsilon$. 

D'altra parte non ha un ordine di convergenza vero e proprio, ma in {\sl{media}} converge linearmente. 
\end{remark}

 \subsection{Bisezione: alcuni esempi}

\begin{example}
Come primo esempio, calcoliamo la soluzione dell'equazione $$f(x)=\sin(x)-x=0.$$ Per quanto detto in precedenza \mye unica e vale $x^*=0$.

\smsp

Visto che $f(-2)=1.090\ldots$, $f(3)=-2.858\ldots$, utilizziamo l'algoritmo di bisezione con $a_0=-2$ e $b_0=3$. Interrompiamo il processo alla iterazione $n$-sima se $f(x_n)=0$ oppure $(b_n-a_n)/2 \leq \epsilon$, con $ \epsilon=10^{-5}$. Come detto, il fatto che $(b_k-a_k)/2 \leq \epsilon$ implica
$$|x_k-x^*| \leq (b_k-a_k)/2 \leq \epsilon.$$

Osserviamo che
$$k^*(\epsilon) = \lceil  - \log_2 (   \frac{\epsilon}{b_{0}-a_{0}}   ) \rceil  -1 = \lceil  - \log_2 (  10^{-5}/5   ) \rceil  -1 =\lceil 18.9316\ldots \rceil  -1=18.
$$

Dal grafico dell'errore assoluto in scala semilogaritmica, si vede che non si pu\myo affermare che la convergenza sia lineare (non \mye approssimativamente una retta).

\begin{table}[h!]
\begin{tabular}{c c c c c c}
\hline
$k$& $a_k$ & $b_k$ & $x_{k}$ & $(b_{k}-a_{k})/2$ & ${\mbox{sgn}}_{k}$ \\
\hline
 	 $   0$ & $-2.00000000e+00$ & $3.00000000e+00$ & $5.00000000e-01$ &$2.5e+00$ &$-$ \\
 	 $   1$ & $-2.00000000e+00$ & $5.00000000e-01$ & $-7.50000000e-01$ &$1.2e+00$ &$+$\\
 	 $   2$ & $-7.50000000e-01$ & $5.00000000e-01$ & $-1.25000000e-01$ &$6.2e-01$ &$+$\\
 	 $   3$ & $-1.25000000e-01$ & $5.00000000e-01$ & $1.87500000e-01$ &$3.1e-01$ &$-$\\
 	 $   4$ & $-1.25000000e-01$ & $1.87500000e-01$ & $3.12500000e-02$ &$1.6e-01$ &$-$\\
 	 $   5$ & $-1.25000000e-01$ & $3.12500000e-02$ & $-4.68750000e-02$ &$7.8e-02$ &$+$\\
 	 $   6$ & $-4.68750000e-02$ & $3.12500000e-02$ & $-7.81250000e-03$ &$3.9e-02$ &$+$\\
 	 $   7$ & $-7.81250000e-03$ & $3.12500000e-02$ & $1.17187500e-02$ &$2.0e-02$ &$-$\\
 	 $   8$ & $-7.81250000e-03$ & $1.17187500e-02$ & $1.95312500e-03$ &$9.8e-03$ &$-$\\
 	 $   9$ & $-7.81250000e-03$ & $1.95312500e-03$ & $-2.92968750e-03$ &$4.9e-03$ &$+$\\
 	 $  10$ & $-2.92968750e-03$ & $1.95312500e-03$ & $-4.88281250e-04$ &$2.4e-03$ &$+$\\
 	 $  11$ & $-4.88281250e-04$ & $1.95312500e-03$ & $7.32421875e-04$ &$1.2e-03$ &$-$\\
 	 $  12$ & $-4.88281250e-04$ & $7.32421875e-04$ & $1.22070312e-04$ &$6.1e-04$ &$-$\\
 	 $  13$ & $-4.88281250e-04$ & $1.22070312e-04$ & $-1.83105469e-04$ &$3.1e-04$ &$+$\\
 	 $  14$ & $-1.83105469e-04$ & $1.22070312e-04$ & $-3.05175781e-05$ &$1.5e-04$ &$+$\\
 	 $  15$ & $-3.05175781e-05$ & $1.22070312e-04$ & $4.57763672e-05$ &$7.6e-05$ &$-$\\
 	 $  16$ & $-3.05175781e-05$ & $4.57763672e-05$ & $7.62939453e-06$ &$3.8e-05$ &$-$\\
 	 $  17$ & $-3.05175781e-05$ & $7.62939453e-06$ & $-1.14440918e-05$ &$1.9e-05$ &$+$\\
 	 $  18$ & $-1.14440918e-05$ & $7.62939453e-06$ & $-1.90734863e-06$ &$9.5e-06$ &$+$\\
\hline
\end{tabular}
\caption{Studio dell'equazione $\sin(x)-x=0$, in $(0,1)$ con $ {\mbox{\tt{toll}}}=10^{-5}$. Si osservi che $f(a_k) > 0$, $f(b_k) < 0$ per ogni $k$. E' interessante guardare come si passi da $(a_k,b_k)$ a $(a_{k+1},b_{k+1})$, al variare di ${\mbox{sgn}}_{k} ={\mbox{sgn}}(f(x_{k}))$ }
\end{table}

 \begin{figure}[h!]\label{bisae}
 \centering
   {\includegraphics[scale=0.25,clip]{bis_ex0.eps}}
    {\includegraphics[scale=0.25,clip]{bis_ex0_ae.eps}}
 \caption{A sinistra, grafico della funzione  $\sin(x)-x=0$, in $[-2,3]$. A destra errore assoluto $|x_k-x^*|$ in scala semilogaritmica.}
 \end{figure}
 
 Una particolarit\mya di quest'esempio \mye che posto $e_{k}=|x_k-x^{\ast}|$, il rapporto $ \frac {|e_{k+1}|} {|e_{k}|}$ assume alternativamente valori $0.6$ e $0.{\overline{6}}=0.666\ldots$ e quindi non esiste il limite 
 $\lim_k \frac {|e_{k+1}|} {|e_{k}|}.$
Conseguentemente, il metodo di bisezione non ha convergenza lineare.
\end{example}

\begin{example}
Quale esempio, vogliamo calcolare la soluzione dell'equazione $f(x)=\exp(x)-2+x=0$. Osserviamo che $f$ \mye una funzione continua e crescente, che $f(0)=-2$, $f(1)=\exp(1)-2+1 = 1.7182\ldots$, e di conseguenza ha un unico zero e questo sta in $(0,1)$.

Quindi utilizziamo l'algoritmo di bisezione con $a_0=0$ e $b_0=1$. Interrompiamo il processo alla iterazione $n$-sima se $f(x_n)=0$ oppure $(b_n-a_n)/2 \leq \epsilon$, con $ \epsilon=10^{-5}$.

La soluzione \mye $x^{\ast} \approx 0.4428544010023885$. Osserviamo che
$$k^*(\epsilon) = \lceil  - \log_2 (   \frac{\epsilon}{b_{0}-a_{0}}   ) \rceil  -1 = \lceil  - \log_2 (  10^{-5}   ) \rceil  -1 =\lceil16.6096\rceil  -1=16.
$$

Dal grafico dell'errore assoluto in scala semilogaritmica, si vede che non si pu\myo affermare che la convergenza sia lineare (non \mye approssimativamente una retta).

\begin{table}[h!]
\begin{tabular}{c c c c c c}
\hline
$k$& $a_k$ & $b_k$ & $x_{k}$ & $(b_{k}-a_{k})/2$ & ${\mbox{sgn}}_{k}$ \\
\hline

 	 $   0$ & $0.00000000e+00$ & $1.00000000e+00$ & $5.00000000e-01$ &$5.0e-01$ &$+$ \\
 	 $   1$ & $0.00000000e+00$ & $5.00000000e-01$ & $2.50000000e-01$ &$2.5e-01$ &$-$\\
 	 $   2$ & $2.50000000e-01$ & $5.00000000e-01$ & $3.75000000e-01$ &$1.2e-01$ &$-$\\
 	 $   3$ & $3.75000000e-01$ & $5.00000000e-01$ & $4.37500000e-01$ &$6.2e-02$ &$-$\\
 	 $   4$ & $4.37500000e-01$ & $5.00000000e-01$ & $4.68750000e-01$ &$3.1e-02$ &$+$\\
 	 $   5$ & $4.37500000e-01$ & $4.68750000e-01$ & $4.53125000e-01$ &$1.6e-02$ &$+$\\
 	 $   6$ & $4.37500000e-01$ & $4.53125000e-01$ & $4.45312500e-01$ &$7.8e-03$ &$+$\\
 	 $   7$ & $4.37500000e-01$ & $4.45312500e-01$ & $4.41406250e-01$ &$3.9e-03$ &$-$\\
 	 $   8$ & $4.41406250e-01$ & $4.45312500e-01$ & $4.43359375e-01$ &$2.0e-03$ &$+$\\
 	 $   9$ & $4.41406250e-01$ & $4.43359375e-01$ & $4.42382812e-01$ &$9.8e-04$ &$-$\\
 	 $  10$ & $4.42382812e-01$ & $4.43359375e-01$ & $4.42871094e-01$ &$4.9e-04$ &$+$\\
 	 $  11$ & $4.42382812e-01$ & $4.42871094e-01$ & $4.42626953e-01$ &$2.4e-04$ &$-$\\
 	 $  12$ & $4.42626953e-01$ & $4.42871094e-01$ & $4.42749023e-01$ &$1.2e-04$ &$-$\\
 	 $  13$ & $4.42749023e-01$ & $4.42871094e-01$ & $4.42810059e-01$ &$6.1e-05$ &$-$\\
 	 $  14$ & $4.42810059e-01$ & $4.42871094e-01$ & $4.42840576e-01$ &$3.1e-05$ &$-$\\
 	 $  15$ & $4.42840576e-01$ & $4.42871094e-01$ & $4.42855835e-01$ &$1.5e-05$ &$+$\\
 	 $  16$ & $4.42840576e-01$ & $4.42855835e-01$ & $4.42848206e-01$ &$7.6e-06$ &$-$\\
\hline
\end{tabular}
\caption{Studio dell'equazione $\exp(x)-2+x=0$, in $(0,1)$ con $ \epsilon=10^{-5}$. Si osservi che $f(a_k) < 0$, $f(b_k)>0$, e si guardi al variare di ${\mbox{sgn}}_{k} ={\mbox{sgn}}(f(x_{k}))$ come si passi da $(a_k,b_k)$ a $(a_{k+1},b_{k+1})$}
\end{table}

 \begin{figure}[h!]\label{bisae2}
 \centering
   {\includegraphics[scale=0.25,clip]{bis_exI.eps}}
    {\includegraphics[scale=0.25,clip]{bis_exI_ae.eps}}
 \caption{A sinistra, grafico della funzione  $\exp(x)-2+x=0$, in $[0,1]$. A destra errore assoluto $|x_k-x^*|$ in scala semilogaritmica.}
 \end{figure}
 
\end{example}




\subsection{Alcuni criteri di arresto per il metodo di bisezione}
Esistono vari criteri di arresto per il metodo di bisezione. Fissata una tolleranza {\tt{toll}} dall'utente, ad esempio {\tt{toll}}=$10^{-6}$, si pu\myo terminare il processo qualora
\begin{itemize}
\item $|x_{k+1}-x_k| \leq \epsilon$ (criterio dello step); 
\item $|f(x_k)| \leq \epsilon$ (criterio del residuo); 
\item $\frac{|f(x_k)|}{w_k} \leq \epsilon$ ove $w_k=\frac{|f(b_k)-f(a_k)|}{b_k-a_k}  \approx |f^{\prime}(x^*)|$,  (criterio del residuo pesato); vedremo poi un esempio.
\end{itemize}

\begin{remark}
Supponiamo sia $(a_0,b_0)$ l'intervallo iniziale. Dopo la prima iterazione \mye noto esclusivamente $x_0$ e quindi
\begin{itemize}
\item non \mye applicabile il criterio dello step in quanto necessita pure di $x_1$, che \mye quindi utilizzabile a partire solo dalla seconda iterazione;
\item i criteri del residuo e del residuo pesato sono applicabili in quanto richiedono esclusivamente il calcolo di $f(x_0)$ e possibilmente di $w_0$ che dipende esclusivamente da $f(a_0)$, $f(b_0)$.
\end{itemize} 
\end{remark}



\begin{example}
Come esempio, consideriamo tre funzioni:
\begin{eqnarray}
f_1(x)&=&x^2-2 \nonumber \\
f_2(x)&=&10^{-8} \cdot (x^2-2) \nonumber \\
f_2(x)&=&10^8 \cdot (x^2-2) \nonumber \\
\end{eqnarray}

Non \mye difficile vedere che hanno tutte quali zeri $\pm \sqrt{2}$, ma che in termini di grafico, 
\begin{enumerate}
\item la prima non ha un grafico molto ripido vicino alla soluzione (in effetti la derivata in $\sqrt{2}$ vale $2\sqrt{2}$), 
\item la seconda \mye molto piatta vicino alla soluzione (la derivata  in $\sqrt{2}$ vale $2\sqrt{2}\cdot 10^{-8}$), 
\item la terza \mye molto piatta vicino alla soluzione (la derivata  in $\sqrt{2}$ vale $2\sqrt{2}\cdot 10^{+8}$). 
\end{enumerate}

Il metodo di bisezione, implementato con ognuno dei test di arresto porge i seguenti risultati, in cui 
\begin{itemize}
\item {\tt{res}} indica il test del residuo,
\item {\tt{wres}} indica il test del residuo pesato,
\item {\tt{step}} indica il criterio dello step.
\end{itemize} 

Abbiamo interrotto il processo se il metodo aveva fatto $10000$ iterazioni, o si fosse verificato il criterio di arresto con tolleranza {\tt{toll}}=$10^{-10}$.

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
{\mbox{test}} & $x_n$ & $|x_n-x^*|$ & $|f(x_n)|$ & $n$ \\
\hline
{\mbox{res}} & $1.414213562384248e+00$ & $1.115e-11$ & $3.154e-11$ & $  29$ \\
{\mbox{wres}} &  $1.414213562384248e+00$ & $1.115e-11$ & $3.154e-11$ & $  29$ \\
{\mbox{step}} &  $1.414213562326040e+00$ & $4.706e-11$ & $1.331e-10$ & $  34$ \\
\hline
\end{tabular}
\caption{La funzione $f_1$ non \mye piatta o ripida nei pressi dello zero $x^{\ast}$ e i test di arresto sono circa equivalenti.}
\end{table}

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
{\mbox{test}} & $x_n$ & $|x_n-x^*|$ & $|f(x_n)|$ & $n$ \\
\hline
{\mbox{res}} &  $1.414062500000000e+00$ & $1.511e-04$ & $4.272e-12$ & $   7$ \\
{\mbox{wres}} &  $1.414213562384248e+00$ & $1.115e-11$ & $3.154e-19$ & $  29$ \\
{\mbox{step}} &  $1.414213562326040e+00$ & $4.706e-11$ & $1.331e-18$ & $  34$ \\
\hline
\end{tabular}
\caption{La funzione $f_2$ \mye molto piatta nei pressi dello zero $x^{\ast}$ e il test del residuo risulta molto impreciso, effettuando poche iterazioni, offrendo per\myo una scarsa approssimazione di $x^{\ast}$. Gli altri due test d'arresto risultano appropriati.}
\end{table}

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
{\mbox{test}} & $x_n$ & $|x_n-x^*|$ & $|f(x_n)|$ & $n$ \\
\hline
{\mbox{res}} &  $1.414213562373095e+00$ & $2.220e-16$ & $4.441e-08$ & $10000$ \\
{\mbox{wres}} &  $1.414213562384248e+00$ & $1.115e-11$ & $3.154e-03$ & $  29$ \\
{\mbox{step}} &  $1.414213562326040e+00$ & $4.706e-11$ & $1.331e-02$ & $  34$ \\
\hline
\end{tabular}
\caption{La funzione $f_3$ \mye molto ripida nei pressi dello zero $x^{\ast}$ e il test del residuo risulta molto conservativo, superando il numero massimo di iterazioni concesse, nonostante abbia calcolato una ottima approssimazione di $x^{\ast}$. Gli altri due test d'arresto risultano appropriati.}
\end{table}

I risultati mostrano 
\begin{enumerate}
\item la superiorit\mya del test basato sul residuo pesato, rispetto al test del residuo, qualora la funzione abbia derivate molto grandi o molto piccole in prossimit\mya della soluzione;
\item l'invarianza rispetto alla pendenza del metodo dello step, che in effetti non ha a che fare con valutazioni delle funzioni $f_1$, $f_2$, $f_3$ (rifletterci su).
\end{enumerate}

\end{example}


%------------------------------------------------------------------------------------------------------------------------
% Metodo di Newton per la risoluzione di equazioni nonlineari.
%------------------------------------------------------------------------------------------------------------------------

\section{Metodo di Newton per la risoluzione di equazioni nonlineari}

Supponiamo che 
\begin{itemize}
\item $x^{\ast}$ sia uno zero di $f$ in $[a,b]$,
\item $f$ sia derivabile due volte con continuit\mya in $[a,b]$.
\end{itemize}

\smsp

Dalla formula di Taylor centrata in $x_k \in [a,b]$, per un certo $\xi_k$ che sta nel pi\myu piccolo intervallo aperto contentente $x_k$, $x^{\ast}$, abbiamo
{{
$$0=f(x^{\ast})=f(x_k)+f^{\prime}(x_k)(x^{\ast}-x_k)+f^{\prime \prime}(\xi_k)(x^{\ast}-x_k)^2/2.$$
}}


Di conseguenza, tralasciando il termini di ordine superiore $f^{\prime \prime}(\xi_k)(x^{\ast}-x_k)^2/2$ (che si ritiene molto piccolo qualora $x^* \approx x_k$), ricaviamo
$$0 \approx f(x_k)+f^{\prime}(x_k)(x^{\ast}-x_k)$$
\noindent 
e quindi se $f^{\prime}(x_{k}) \neq 0$, dopo facili conti
$$x^{\ast} \approx x_{k}-f(x_{k})/f^{\prime}(x_{k}).$$

\smsp

Il {\sl{metodo di Newton}} genera la successione
\begin{equation}\label{newton}
x_{k+1}=x_{k}+h_{k}, \, \, h_{k}=-f(x_{k})/f^{\prime}(x_{k}), \,\,
k=0,1,\ldots
\end{equation}
supposto che sia $f^{\prime}(x_{k}) \neq 0$ per $k=0,1,\ldots$ (cf. \cite[p.58]{ATK}, \cite{WIK3}).

 

\begin{remark}
\begin{figure}[!ht]\label{ign}
 \centering
 %{\includegraphics[scale=0.25,clip]{new_ig.eps}}
 % {\includegraphics[scale=0.05,clip]{ntan.png}}
  {\includegraphics[scale=0.40,clip]{tangenti.eps}}
 \caption{Interpretazione geometrica del metodo di Newton, alla iterazione $n$-sima, $n=1,2,3,4$, per calcolare uno zero di una funzione convessa.}
 \end{figure}
Il metodo ha una interpretazione geometrica. Alla $k$-sima iterazione:
\begin{enumerate}
\item si calcola $f(x_{k-1})$;
\item si disegna la retta tangente $\gamma_k$ alla curva definita dalle coppie $(x,f(x))$, nel punto $(x_{k-1},f(x_{k-1}))$;
\item si pone $x_k$ l'intersezione di $\gamma_k$ con l'asse delle ascisse.
\end{enumerate}


\end{remark}



 \subsection{Metodo di Newton: criteri di arresto}
Le iterazioni del metodo di Newton terminano tipicamente secondo due criteri di arresto, quello dello step ovvero in cui, fissata una tolleranza {\tt{toll}} si ferma il processo qualora
$$
|x_{k+1}-x_k| < {\mbox{\tt{toll}}}
$$
e quello del residuo, in cui ci\myo accade qualora
$$
|f(x_k)| < {\mbox{\tt{toll}}}.
$$
E' importante notare che per il metodo di Newton si ha che il criterio dello step \mye molto simile a un residuo pesato, in quanto per $w_k=\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}} \approx f^{\prime} (x_k)$
$$
x_{k+1}-x_k=-\frac{f(x_k)}{f^{\prime}(x_k)} \approx -\frac{f(x_k)}{w_k}.
$$



 \subsection{Metodo di Newton: un teorema di convergenza locale}
Per quanto riguarda la velocit\mya di convergenza proveremo un teorema di {\sl{convergenza locale}} (cf. {\cite{ATK}}, p. 60).

Un tale asserto mostra come sia possibile risolvere numericamente l'equazione $f(x)=0$, partendo da un punto $x_0$ appartenente a un certo intervallo $I$ contenente la radice $x^*$. In questi teoremi, a differenza di quelli detti di {\sl{convergenza globale}}, si sa solo che tale $I$ esiste, ma in generale non \mye noto esplicitamente.

\smsp

\begin{theorem}\label{conv1}
Si supponga
\begin{enumerate}
\item $f \in C^{2}([a,b])$;
\item $x^{\ast}\in (a,b)$ sia uno zero semplice di $f$, ovvero $f(x^*)=0$, $f^{\prime}(x^*) \neq 0$.
\end{enumerate}
 Allora per $x_0 \in [a,b]$ sufficientemente vicino a $x^{\ast}$ le iterazioni del metodo di Newton
$$x_{k+1}=x_k-f(x_k)/f^{\prime}(x_k), \,\,\, k=0,1,2,\ldots$$
sono ben definite e convergono almeno quadraticamente a $x^{\ast}$. Se $f^{\prime \prime}(x^{\ast}) \neq 0$, allora la convergenza \mye esattamente quadratica.
\end{theorem}

\smsp

\begin{proof}
La dimostrazione consiste nel
\begin{enumerate}
\item trovare un intervallo ${\cal{I}}_1$ contenente lo zero in cui la derivata non si annulla;
\item determinare un sottointervallo ${\cal{I}}_2 \subseteq {\cal{I}}_1$ per cui se $x_n \in {\cal{I}}_2$ allora l'iterazione $x_{n+1}$ del metodo di Newton fa ancora parte di ${\cal{I}}_2$;
\item dedurre la convergenza quadratica da stime dell'errore in quest'intervallo. 
\end{enumerate}
Vediamo i dettagli della dimostrazione.

\smsp

Essendo lo zero semplice, per definizione $f^{\prime}(x^{\ast}) \neq 0$. Di conseguenza, per il teorema di permanenza del segno, esiste un intorno simmetrico chiuso di $x^{\ast}$ $${\cal{I}}_1=[x^{\ast}-\delta,x^{\ast}+\delta]$$ con la propriet\mya che $f^{\prime}(x) \neq 0$ per ogni $x \in {\cal{I}}_1$. 

\smsp

Osserviamo che dalla formula di Taylor centrata in $x_n$ e dalla definizione della successione del metodo di Newton, se $x_n \in {\cal{I}}_1$, allora per un certo $\xi_n \in {\cal{I}}_1$ (che in effetti sta nel pi\myu piccolo intervallo aperto contenente $x^{\ast}$ e $x_n$ e di conseguenza pure in ${\cal{I}}_1$)
$$0=f(x^{\ast})=f(x_n)+f^{\prime}(x_n) (x^{\ast}-x_n)+f^{\prime \prime}(\xi_n) (x^{\ast}-x_n)^2/2$$
e quindi dividendo ambo i membri per $f^{\prime}(x_n) \neq 0$ (poich\mye se $x_n \in {\cal{I}}_1$ allora $f^{\prime}(x) \neq 0$), ricordando la definizione del metodo di Newton
\begin{eqnarray}\label{loc1}
0 &=& {\frac{f(x_n)}{f^{\prime}(x_n)}} + (x^{\ast}-x_n)+{\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}}     (x^{\ast}-x_n)^2 \nonumber \\
&=& x^{\ast} - x_{n+1} + {\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}}     (x^{\ast}-x_n)^2.
\end{eqnarray}
Di conseguenza, posto $e_n=x_n-x^{\ast}$, da ({\ref{loc1}}) abbiamo
$$
e_{n+1}=x_{n+1}-x^{\ast}={\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}}     (x^{\ast}-x_n)^2=  {\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}}     e_n^2
$$
e quindi
$$|e_{n+1}|=\left| {\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}} \right|    |e_n|^2.$$
Per il teorema di Weierstrass, essendo $f^{\prime}$ e $f^{\prime\prime}$ funzioni continue, esistono finiti 
$${ \max_{x \in {\cal{I}}_1} {|f^{\prime \prime}(x)|} } $$ $$ { \min_{y \in {\cal{I}}_1} {|f^{\prime}(y)|} } $$ per cui \mye pure finito
$$C :=  \frac{ { \max_{x \in {\cal{I}}_1} {|f^{\prime \prime}(x)|} } }{ { 2 \min_{y \in {\cal{I}}_1} {|f^{\prime}(y)|} } } $$
e ovviamente, visto che $\xi_n, x_n \in {\cal{I}}_1$
$$C \geq {\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}}.$$
Possiamo quindi affermare che se $x_n \in I_1$ allora
$$|e_{n+1}| \leq C |e_n|^2.$$
Di conseguenza, per definizione, l'ordine di convergenza \mye almeno $p=2$, ovvero almeno quadratica.

\vspace{0.35cm}
Se $f^{\prime \prime}(x^*) \neq 0$, allora $C :=  \frac{ { \max_{x \in {\cal{I}}_1} {|f^{\prime \prime}(x)|} } }{ { 2 \min_{y \in {\cal{I}}_1} {|f^{\prime}(y)|} } }  > 0$.


Ricordiamo ora che nell'intorno ${\cal{I}}_1=[x^{\ast}-\delta,x^{\ast}+\delta]$ di $x^{\ast}$ si ha $f^{\prime} \neq 0$ (cio\mye $f^{\prime}$ ha segno costante).

Poniamo per un qualsiasi $\epsilon \in (0,1)$ $$\gamma=\min{(\delta,(1-\epsilon)/C)}>0.$$ Se $x_0 \in {\cal{I}}_2 \equiv [x^{\ast}-\gamma,x^{\ast}+\gamma] \subseteq {\cal{I}}_1$ (si osservi che $\gamma < \delta$) allora essendo $$0 \leq C \gamma = C \cdot \min{(\delta,(1-\epsilon)/C)}=\min{(C\delta,1-\epsilon)} < 1$$ 
e dal fatto che se $x_0 \in [x^{\ast}-\gamma,x^{\ast}+\gamma] \subseteq {\cal{I}}_1$ necessariamente
$$
|e_0|=|x_0-x^*| \leq \gamma
$$
ricaviamo
$$|e_1| \leq C |e_0|^2 =(C|e_0|) \cdot |e_0| \leq \underbrace{(C \gamma)}_{<1} \gamma < \gamma$$
per cui tutte le iterazioni $x_n$ del metodo di Newton stanno nell'intervallo ${\cal{I}}_2=[x^{\ast}-\gamma,x^{\ast}+\gamma]$ ed essendo ${\cal{I}}_2 \subseteq {\cal{I}}_1$ la successione descritta dal metodo di Newton \mye ben definita (in quanto ci\myo implica che per ogni $n$, $f^{\prime}(x_n) \neq 0$.

Anzi, da $x_0 \in {\cal {I}}_2$ ricaviamo $|e_0| \leq \gamma < 1$, ed essendo $$0 \leq C|e_{n+1}| \leq (C^2 |e_n|^2)= (C |e_n|)^2 \leq \ldots \leq (C |e_0|)^{2^{n+1}}$$ visto che $C|e_0| \leq C \gamma \leq 1-\epsilon <1$,
implica $$ (C |e_0|)^{2^{n+1}} \rightarrow 0$$ per il teorema del confronto tra limiti, $|e_{n+1}| \rightarrow 0$ cio\mye $x_{n+1} \rightarrow x^{\ast}$.
Inoltre si ha che per un certo $n^{\ast}$, se $n \geq n^{\ast}$, \mye $x_n=x^{\ast}$ oppure dalla continuit\mya di $f^{\prime}$ e $f^{\prime \prime}$ nell'intervallo ${\cal{I}}_2=[x^{\ast}-\gamma,x^{\ast}+\gamma]$
$$\lim_n {\frac {|e_{n+1}|}{|e_n|^2}}=\lim_n \left| {\frac{f^{\prime \prime}(\xi_n)}{2 \cdot f^{\prime}(x_n)}} \right|={\frac{|f^{\prime \prime}(x^{\ast})|}{2 \cdot |f^{\prime}(x^{\ast})|}} \neq 0   $$
\noindent cio\mye la convergenza \mye esattamente quadratica.



\end{proof}



 \subsection{Metodo di Newton: un teorema di convergenza globale}
\noindent Dimostriamo un teorema di convergenza globale, che permette di risolvere numericamente l'equazione $f(x)=0$, partendo da un punto $x_0$ appartenente a un ben determinato intervallo $I$ contenente la radice $x^*$. In questi teoremi, a differenza di quelli detti di {\sl{convergenza locale}}, $I$ \mye noto esplicitamente.

\smsp

\begin{theorem}\label{LT1}
Sia $f: [a,b] \rightarrow \R$ una funzione che gode delle seguenti propriet\mya
\begin{enumerate}
\item $f(a)<0$ e $f(b)>0$;
\item $f^{\prime \prime}(x) > 0$ per ogni $x \in [a,b]$.
\end{enumerate}
Allora
\begin{enumerate}
\item esiste uno ed un solo $x^{\ast} \in (a,b)$ tale che $f(x^{\ast})=0$. e tale zero \mye semplice;
\item per $x_0 \in [x^{\ast},b]$ il metodo di Newton
$$x_{n+1}=x_n- {\frac{f(x_n)}{f^{\prime} (x_n) }}$$
\mye ben definito;
\item la successione $\{x_n\}$ \mye decrescente e converge a $x^{\ast}$.
\end{enumerate}
\end{theorem}

\smsp

\begin{proof}

$\\$
\vspace{-0.2cm}

\begin{enumerate}
\item Essendo $f^{\prime \prime}(x) > 0$ per ogni $x \in [a,b]$, allora la funzione $f^{\prime}$ \mye continua e monotona crescente in $[a,b]$. Di conseguenza,
\begin{itemize}
\item se $f^{\prime}$ non ha segno costante in $[a,b]$, si ha che pure $f$ \mye monotona e quindi in $(a,b)$ c'\mye un unico zero $x^{\ast}$ poich\mye $f(a) <0$ e $f(b)>0$;
\item se $f^{\prime}$ non ha segno costante in $[a,b]$ essendo monotona crescente ha un unico zero. Di conseguenza, per la sua convessit\mya, $f$ ha un unico minimo $x_{\mbox{\tiny{min}}} \in [a,b]$. Quindi dalla monotonia crescente di $f^{\prime}$ in $[x_{\mbox{\tiny{min}}},b]$ e dal fatto che $f(x_{\mbox{\tiny{min}}} ) \leq f(a)$ e $f(x_{\mbox{\tiny{min}}} )  \leq 0 < f(b)$ abbiamo che vi \mye un unico zero in $x^{\ast} \in [a,b]$.
\end{itemize}
Osserviamo che per quanto appena visto, $f^{\prime}(x) > 0$ per ogni $x \in [x^{\ast},b]$ e quindi in particolare che lo zero $x^{\ast}$ \mye semplice.

\item Questo risultato segue dal fatto che la funzione $f^{\prime}$ \mye strettamente positiva in $[x^{\ast},b]$.

\item Sia $n \geq 0$ e $x_n \geq x^{\ast}$. Dalla formula di Taylor, essendo $f^{\prime \prime}(x) > 0$, per ogni $x \in [a,b]$, deduciamo che per $\xi_n$ nel pi\myu piccolo intervallo aperto contenente
$x_n$ e $x_{n+1}=x_n- {\frac{f(x_n)}{f^{\prime} (x_n) }}$ si ha
\begin{eqnarray}
f(x_{n+1})&=&f(x_n)+f^{\prime}(x_n) \cdot (x_{n+1}-x_n) +f^{\prime \prime}(\xi_n) \cdot {\frac{(\xi-x_n)^2}{2}} \nonumber \\
&>& f(x_n)+f^{\prime}(x_n) \cdot (x_{n+1}-x_n)=0=f(x^{\ast}).
\end{eqnarray}
Poich\mye per $x < x^{\ast}$ la funzione $f$ \mye negativa, necessariamente ci\myo implica che $x_{n+1} > x^{\ast}$
Inoltre la successione $\{x_n\}$ \mye strettamente decrescente perch\mye da $f(x_n) > 0$ e $f^{\prime} (x_n) >0$ abbiamo $$x_{n+1}=x_n- {\frac{f(x_n)}{f^{\prime} (x_n) }} \leq x_n.$$
Poich\mye la successione $\{x_n\}$ \mye decrescente e limitata inferiormente da $x^{\ast}$, essa ammette limite $\xi^{\ast}$. Ma allora per la continuit\mya di $f$ e $f^{\prime}$
$$\xi^{\ast}=
 \lim_n {x_{n+1}}=  \lim_n {x_n}-\lim_n  {\frac {f(x_n)} {f^{\prime} (x_n)} }= \xi^{\ast} - { \frac {f(\xi^{\ast})}   {f^{\prime} (\xi^{\ast})}      }$$
ed essendo $f^{\prime} (\xi^{\ast}) \neq 0$ poich\mye tale zero \mye semplice abbiamo $f(\xi^{\ast})=0$. Ma $x^{\ast}$ \mye l'unico zero di $f$ e quindi $\xi^{\ast}=x^{\ast}$ cio\mye il metodo di Newton converge decrescentemente a $x^{\ast}$.
\end{enumerate}

\end{proof}



\begin{theorem}\label{LT2}
Sia $f: [a,b] \rightarrow \R$ una funzione che gode delle seguenti propriet\mya
\begin{enumerate}
\item $f(a)>0$ e $f(b)<0$;
\item $f^{\prime \prime}(x) > 0$ per ogni $x \in [a,b]$.
\end{enumerate}
Allora
\begin{enumerate}
\item esiste uno ed un solo $x^{\ast} \in (a,b)$ tale che $f(x^{\ast})=0$. Tale zero \mye semplice.
\item per $x_0 \in [x^{\ast},b]$ il metodo di Newton
$$x_{n+1}=x_n- {\frac{f(x_n)}{f^{\prime} (x_n) }}$$
\mye ben definito.
\item La successione $\{x_n\}$ \mye crescente e converge a $x^{\ast}$.
\end{enumerate}
\end{theorem}

\smsp

\begin{proof}
Si consideri 
$$
g(y)=f(-y), \,\,\, y \in [-b,-a].
$$
Poniamo quindi ${\tilde{a}}=-b$,  ${\tilde{b}}=-a$ e osserviamo che 
\begin{itemize}
\item $g({\tilde{a}})=g(-b)=f(-(-b))=f(b) <0$;
\item $g({\tilde{b}})=g(-a)=f(-(-a))=f(a) >0$;
\item se $y \in [{\tilde{a}},{\tilde{b}}]$ allora derivando due volte $g(y)=f(-y)$ abbiamo
$$g^{\prime \prime}(y)=f^{\prime \prime}(-y)$$
e siccome $y \in [{\tilde{a}},{\tilde{b}}] \equiv [-b,-a]$, necessariamente $-y \in [a,b]$, per cui
$$g^{\prime \prime}(y) > 0, \,\,\, y \in [{\tilde{a}},{\tilde{b}}].$$

Per il teorema precedente, l'equazione $g(y)=0$ ha un'unica soluzione $y^* \in [{\tilde{a}},{\tilde{b}}]=[-b,-a]$. Ma allora, se poniamo $x^*=-y^*$ ricaviamo
$$
f(x^*)=f(-(-x^*))=f(-y^*)=g(y^*)=0
$$
cio\mye $x^*$ \mye uno zero di $f$.

Ed \mye pure l'unico zero, perch\mye se ce ne fosse un'altro diverso da $x^*$, diciamo $\overline{x} \in [a,b]$, allora $-\overline{x} \in [-b,-a] \equiv [{\tilde{a}},{\tilde{b}}]$ sarebbe un altro zero di $g$ in $ [{\tilde{a}},{\tilde{b}}]$ distinto da $y^*=-x^*$ mentre sappiamo che $y^*$ \mye l'unico.

Il teorema precedente dice che, partendo da $y_0 \in [y^{\ast},{\tilde{b}}]$, la successione determinata dal metodo di Newton 
$$
y_{k+1}=y_k-\frac{g(y_k)}{g^{\prime}(y_k)}=y_k-\frac{f(-y_k)}{f^{\prime}(-y_k)}, \,\,\, k=0,1,\ldots
$$
\mye decrescente e converge all'unico zero $y^*$ di $g$. 

Poniamo $x_k=-y_k$ e ricaviamo da $f^{\prime}(x)=-g^{\prime}(-x)$
$$
-x_{k+1}=-x_k-\frac{f(-(-x_k))}{-f^{\prime}(-(-x_k))}, \,\,\, k=0,1,\ldots
$$
ovvero
$$
x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}, \,\,\, k=0,1,\ldots
$$
cio\mye la successione del metodo di Newton applicata a $f$. Poich\mye $x_k=-y_k$ e $y_k$ \mye decrescente, si ha che $x_k$ \mye crescente e converge a $x^*=-y^*$, visto che
$$
\lim_k x_k=\lim_k -y_k=-\lim_k y_k= -y^*.
$$

\end{itemize}

\end{proof}


\begin{theorem}\label{LT3}
Sia $f: [a,b] \rightarrow \R$ una funzione che gode delle seguenti propriet\mya
\begin{enumerate}
\item $f(a) \cdot f(b)<0$;
\item $f^{\prime \prime}(x) < 0$ per ogni $x \in [a,b]$.
\end{enumerate}
Allora
\begin{enumerate}
\item esiste uno ed un solo $x^{\ast} \in (a,b)$ tale che $f(x^{\ast})=0$. Tale zero \mye semplice.
\item se  $f(a) <0$, $f(b) > 0$, per $x_0 \in [a,x^*]$, la successione $\{x_k\}$ generata dal metodo di Newton \mye ben definita, crescente e converge a $x^*$,  
\item se  $f(a) >0$, $f(b) < 0$, per $x_0 \in [x^*,b]$, la successione $\{x_k\}$ generata dal metodo di Newton \mye ben definita, decrescente e converge a $x^*$.
\end{enumerate}
\end{theorem}

\begin{prooftrace}
 Basta applicare la tecnica utilizzata nella dimostrazione precedente, per $g(x)=-f(x)$. Infatti, $g^{\prime \prime}(x)=-f^{\prime \prime}(x)$, e se $g(a) >0$, $g(b) <0$ si applica il Teorema \ref{LT1}, altrimenti il Teorema \ref{LT2}.
In particolare si prova che $f$ ha un unico zero $x^* \in [a,b]$ e che qualora
\begin{itemize}
\item si abbia  $f(a) <0$, $f(b) > 0$, si vede che per $x_0 \in [a,x^*]$, la successione $\{x_k\}$ generata dal metodo di Newton \mye crescente e converge a $x^*$,  
\item si abbia  $f(a) > 0$, $f(b) < 0$, si vede che per $x_0 \in [x^*,b]$, la successione $\{x_k\}$ generata dal metodo di Newton \mye decrescente  e converge a $x^*$.
\end{itemize}
\end{prooftrace}
\smsp

\begin{remark}
I teoremi precedenti si possono mostrare geometricamente, caso per caso, osservando che le tangenti alla curva $y=f(x)$ stanno sempre sopra o sotto il grafico, e che la successione $\{x_k\}$ \mye monotona e limitata e quindi ha limite finito che si vede facilmente coincidere proprio con lo zero $x^*$ di $f$.
\end{remark}


\begin{remark}
Esistono molti teoremi di convergenza globale per il metodo di Newton, oltre a quelli citati (cf. \cite{DSC}, \cite{KEL}, \cite{ZEI}).  Ad esempio, in {\cite[p. 419]{COM}}, si mostra che
\smsp
\begin{theorem}\label{convglob}
Sia $f \in C^{2}([a,b])$, con $[a,b]$ intervallo chiuso e limitato. Se
\smsp
\begin{enumerate}
\item $f(a) \cdot f(b) < 0$; \smsp
\item $f^{\prime}(x) \neq 0$, per ogni $x \in [a,b]$; \smsp
\item $f^{\prime \prime}(x) \geq 0$ o $f^{\prime \prime}(x) \leq 0$, per ogni $x \in [a,b]$; \smsp
\item $|f(a)/f^{\prime}(a)|<b-a$ e $|f(b)/f^{\prime}(b)|<b-a$, \smsp
\end{enumerate}
allora il metodo di Newton converge all'unica soluzione $x^{\ast}$
in $[a,b]$, per ogni $x_{0} \in [a,b]$.
\end{theorem}
\end{remark}

\begin{remark}
Osserviamo che il metodo di Newton non ha sempre convergenza
quadratica, come nel caso del problema $f(x)=0$ in cui $x^{\ast}$ sia uno zero avente molteplicit\mya $p > 1$ cio\mye tale che
$$f(x^{\ast})=f^{\prime}(x^{\ast})=\ldots=f^{(p-1)}(x^{\ast})=0.$$ \noindent
Quale esempio si ponga $$f(x)=(x-2) {\log{(x-1)}}.$$

Si verifica facilmente che $x^*=2$ \mye un suo zero e visto che 
\begin{itemize}
\item $f^{(1)}(x)=\log(x - 1) + (x - 2)/(x - 1)$,
\item $f^{(2)}(x)=2/(x - 1) - (x - 2)/(x - 1)^2$,
\end{itemize}
ha molteplicit\mya $2$, visto che $f^{(1)}(2)=0$ ma $f^{(2)}(2)\neq 0$. Si vede che il metodo di Newton non converge quadraticamente a tale radice.
\smsp
\end{remark}




%------------------------------------------------------------------------------------------------------------------------
% Facoltativo. Nota storica.
%------------------------------------------------------------------------------------------------------------------------

\begin{remarkh}
Il metodo di Newton \mye anche noto come metodo di Newton-Raphson, in quanto sviluppato da Newton nell'opera {\sl{Analysis Aequationes Numero Terminorum Infinitas}} (1666, scritto nel 1671 e quindi pubblicato nel 1711 da William Jones) per calcolare la radice $2.09455148154233\ldots$ di $x^3-2 \, x-5$. Il metodo forse derivava da alcune idee di Francois Viete che a sua volta si rifaceva al lavoro del matematico persiano Sharaf al-Din al-Tusi. 

Erone di Alexandria utilizzava idee in qualche modo simili.

La questione venne ripresa nel {\sl{De metodis fluxionum et serierum infinitarum}} (scritto nel 1671, tradotto e pubblicato come {\sl{Method of Fluxions}} nel 1736 da John Colson). Il metodo descritto era molto differente
da quello attuale, e veniva sostanzialmente applicato a polinomi {\cite[p. 413]{COM}}, {\cite{WIK4}}.

Il metodo di Newton venne pure pubblicato nel {\sl{A Treatise of Algebra both Historical and Practical}} (1685) di John Wallis.

Nel 1690, Joseph Raphson pubblic\myo nel {\sl{Analysis aequationum universalis}} una versione maggiormente algoritmica, iterativa e meno complicata di quella di Newton. Quindi Simpson, nel 1740, generalizz\myo queste idee per equazioni nonlineari e sistemi nonlineari di piccole dimensioni (cf. \cite{TRE}).

Nel 1768, Jean-Raymond Mourraille nel {\sl{Trait\myer de la r{\myer}solution des {\myer}quation num{\myer}riques}} cominci\myo a discutere la convergenza del metodo di Newton, sottolineando il legame con l'aspetto geometrico delle tangenti.

Pure Fourier diede impulso a questi studi nel {\sl{Question d'analyse algebrique}} (1818).
\end{remarkh}


 \subsection{Metodo di Newton: alcuni esempi}
\begin{example}
Consideriamo il problema $f(x)=\sin(x)-x=0$ che abbiamo visto avere quale unica soluzione $x^*=0$.
Visto che $f^{\prime}(x)=\cos(x)-1$, le iterate del metodo di Newton saranno
$$
x_{k+1}=x_{k}-\frac {\sin(x_k)-x_k}  {\cos(x_k)-1}
$$
Osserviamo che il processo non \mye ben definito se $\cos(x_k)-1=0$, ovvero $x_k=m\pi$ con $m \in \Z$.
Interrompiamo il metodo quando $|x_{k+1}-x_{k}| \leq 10^{-6}$ e quale punto iniziale poniamo $x_0=3$.

Si noti che $x^*=0$ \mye uno zero multiplo in quanto $f(x^*)=f^{\prime}(x^*)=0$. Questo, per un teorema che vedremo successivamente causer\mya una povera performance da parte del metodo.

Sperimentalmente $|e_{k+1}|/|e_k| \approx 0.667$ per $k > 1$ e quindi almeno empiricamente possiamo affermare che il metodo di Newton, relativamente a questo esempio, ha convergenza lineare.

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 	 $   0$ & $3.000000000000000e+00$ & $3.00e+00$ & $-$ & $-2.86e+00$ \\
 	 $   1$ & $1.563371471588948e+00$ & $1.56e+00$ & $1.44e+00$ & $-5.63e-01$\\
 	 $   2$ & $9.957580269725619e-01$ & $9.96e-01$ & $5.68e-01$ & $-1.57e-01$\\
 	 $   3$ & $6.524666397563195e-01$ & $6.52e-01$ & $3.43e-01$ & $-4.53e-02$\\
 	 $   4$ & $4.318439019482230e-01$ & $4.32e-01$ & $2.21e-01$ & $-1.33e-02$\\
 	 $   5$ & $2.869951130449173e-01$ & $2.87e-01$ & $1.45e-01$ & $-3.92e-03$\\
 	 $   6$ & $1.910666484344176e-01$ & $1.91e-01$ & $9.59e-02$ & $-1.16e-03$\\
 	 $   7$ & $1.273001625888427e-01$ & $1.27e-01$ & $6.38e-02$ & $-3.44e-04$\\
 	 $   8$ & $8.484384021569123e-02$ & $8.48e-02$ & $4.25e-02$ & $-1.02e-04$\\
 	 $   9$ & $5.655577232707287e-02$ & $5.66e-02$ & $2.83e-02$ & $-3.01e-05$\\
 	 $  10$ & $3.770183802430618e-02$ & $3.77e-02$ & $1.89e-02$ & $-8.93e-06$\\
 	 $  11$ & $2.513396320297106e-02$ & $2.51e-02$ & $1.26e-02$ & $-2.65e-06$\\
 	 $  12$ & $1.675579904767051e-02$ & $1.68e-02$ & $8.38e-03$ & $-7.84e-07$\\
 	 $  13$ & $1.117048042787600e-02$ & $1.12e-02$ & $5.59e-03$ & $-2.32e-07$\\
 	 $  14$ & $7.446971464636467e-03$ & $7.45e-03$ & $3.72e-03$ & $-6.88e-08$\\
 	 $  15$ & $4.964643054317002e-03$ & $4.96e-03$ & $2.48e-03$ & $-2.04e-08$\\
 	 % $  16$ & $3.309760676548749e-03$ & $3.31e-03$ & $1.65e-03$ & $-6.04e-09$\\
 	 % $  17$ & $2.206506714829620e-03$ & $2.21e-03$ & $1.10e-03$ & $-1.79e-09$\\
 	 % $  18$ & $1.471004357126464e-03$ & $1.47e-03$ & $7.36e-04$ & $-5.31e-10$\\
 	 % $  19$ & $9.806695361152210e-04$ & $9.81e-04$ & $4.90e-04$ & $-1.57e-10$\\
 	 % $  20$ & $6.537796801480609e-04$ & $6.54e-04$ & $3.27e-04$ & $-4.66e-11$\\
 	 % $  21$ & $4.358531167794926e-04$ & $4.36e-04$ & $2.18e-04$ & $-1.38e-11$\\
 	 % $  22$ & $2.905687437519249e-04$ & $2.91e-04$ & $1.45e-04$ & $-4.09e-12$\\
 	% $  23$ & $1.937124954552415e-04$ & $1.94e-04$ & $9.69e-05$ & $-1.21e-12$\\
 	% $  24$ & $1.291416629567679e-04$ & $1.29e-04$ & $6.46e-05$ & $-3.59e-13$\\
 	% $  25$ & $8.609444163136152e-05$ & $8.61e-05$ & $4.30e-05$ & $-1.06e-13$\\
 	% $  26$ & $5.739629495784966e-05$ & $5.74e-05$ & $2.87e-05$ & $-3.15e-14$\\
 	 %$  27$ & $3.826419702314216e-05$ & $3.83e-05$ & $1.91e-05$ & $-9.34e-15$\\
 	% $  28$ & $2.550946421224401e-05$ & $2.55e-05$ & $1.28e-05$ & $-2.77e-15$\\
 	 %$  29$ & $1.700631209039519e-05$ & $1.70e-05$ & $8.50e-06$ & $-8.20e-16$\\
 	% $  30$ & $1.133754719544165e-05$ & $1.13e-05$ & $5.67e-06$ & $-2.43e-16$\\
 	% $  31$ & $7.558361507197022e-06$ & $7.56e-06$ & $3.78e-06$ & $-7.20e-17$\\
 	% $  32$ & $5.038913239483810e-06$ & $5.04e-06$ & $2.52e-06$ & $-2.13e-17$\\
 	$\ldots$ & $\ldots$ & $\ldots$ & $\ldots$ & $\ldots$\\
 	$  33$ & $3.359297519803817e-06$ & $3.36e-06$ & $1.68e-06$ & $-6.32e-18$\\
 	 $  34$ & $2.239575075072224e-06$ & $2.24e-06$ & $1.12e-06$ & $-1.87e-18$\\
\hline
\end{tabular}
\caption{La convergenza del metodo di Newton alla soluzione $x^*=0$ di $f(x)=\sin(x)-x=0$ \mye molto lenta, ed \mye causata dal fatto che la soluzione \mye multipla ovvero $f(x^*)=f^{\prime}(x^*)=0$. Il test del residuo non assicura che $|x_n-x^{*}|$ sia piccolo, e questo \mye dovuto al fatto che la funzione, nei pressi della soluzione \mye molto piatta (la derivata \mye nulla!).}
\end{table}


 \begin{figure}[h!]\label{figN1}
 \centering
 {\includegraphics[scale=0.25,clip]{new_exII.eps}}

 \caption{Errore assoluto $|x_k-x^*|$ dove $x_k$ \mye la $k$-sima iterata del metodo di Newton per la soluzione di $f(x)=\sin(x)-x=0$, in scala semilogaritmica.}
 \end{figure}

\end{example}







\begin{example}
Consideriamo il problema $f(x)=\exp(x)-2+x=0$ che sappiamo avere un'unica soluzione $x^* \approx 0.4428544010023885$.
Da $f^{\prime}(x)=\exp(x)-1$, il metodo di Newton definisce la successione
$$
x_{k+1}=x_{k}-\frac {\exp(x_k)-2+x_k}  {\exp(x_k)-1}
$$
Osserviamo che il processo non \mye ben definito se $\exp(x_k)-1=0$, ovvero $x_k=0$.
Essendo $f^{\prime}(x)=\exp(x^*)-1=0.557145598997611\ldots$ lo zero \mye semplice.

Relazioniamo il test in tabella a quanto noto per la convergenza. 
\begin{enumerate}
\item $ x^* = 0.4428544010023885 \ldots$ \mye uno zero semplice;
\item $f^{\prime }(x) = \exp(x)+1> 0$.
\item $f^{\prime \prime}(x) = \exp(x) > 0$.
\end{enumerate}

La funzione \mye quindi convessa, strettamente crescente e $\lim_{x \rightarrow +\infty} f(x)=+\infty$ mentre $\lim_{x \rightarrow -\infty} f(x)=-\infty$. Di conseguenza, di sicuro esistono $a$ e $b$ nel dominio per cui $f(a) < 0$ e $f(b) > 0$. Ad esempio, possiamo porre come nel caso di bisezione $a=0$, $b=1$ in quanto $f(0)=-2$, $f(1)=\exp(1)-2+1 = 1.7182\ldots$.

Il teorema di convergenza globale \ref{LT1} dice che partendo da $x_0=b=1$ otterremo una successione decrescente, convergente a $x^*$ che per il teorema di convergenza locale avr\'a convergenza quadratica, come si pu\myo verificare dal relativo grafico e dalla sua tabella.



\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 $   0$ & $1.000000000000000e+00$ & $5.57e-01$ & $-$ & $1.72e+00$ \\
 	 $   1$ & $5.378828427399902e-01$ & $9.50e-02$ & $4.62e-01$ & $2.50e-01$\\
 	 $   2$ & $4.456167485265452e-01$ & $2.76e-03$ & $9.23e-02$ & $7.07e-03$\\
 	 $   3$ & $4.428567246451099e-01$ & $2.32e-06$ & $2.76e-03$ & $5.94e-06$\\
 	 $   4$ & $4.428544010040325e-01$ & $1.64e-12$ & $2.32e-06$ & $4.20e-12$\\
 	 $   5$ & $4.428544010023886e-01$ & $1.11e-16$ & $1.64e-12$ & $1.11e-16$\\
\hline
\end{tabular}
\caption{La convergenza del metodo di Newton alla soluzione $x^*=0$ di $f(x)=\exp(x)-2+x=0$  \mye molto rapida ovvero $f(x^*)=f^{\prime}(x^*)=0$. Il test del residuo \mye molto accurato, mentre quello dello step individua correttamente a posteriori l'errore dell'iterata precedente. Ad esempio, alla quinta iterata dice correttamente che l'errore alla quarta era $1.64e-12$. Si osservi che la successione $\{x_n\}$ \mye in effetti decrescente per $n=0,1,\ldots,5$.}
\end{table}

 \begin{figure}[h!]\label{figN2}
 \centering
 {\includegraphics[scale=0.25,clip]{new_exI.eps}}

 \caption{Errore assoluto $|x_k-x^*|$ dove $x_k$ \mye la $k$-sima iterata del metodo di Newton per la soluzione di $f(x)=\exp(x)-2+x=0$, in scala semilogaritmica.}
 \end{figure}

\end{example}


\begin{example}
Quale terzo esempio calcoliamo la radice quadrata di $2$, ovvero la soluzione positiva di $f(x)=x^2-2$, che risulta essere $x^{\ast}=1.414213562373095\ldots$. Visto che $f^{\prime}(x)=2x$, le iterazioni del metodo di Newton saranno
$$
x_{k+1}=x_k-\frac{x_k^2-2}{x_k}, \,\,\,\, k=0,1,\ldots
$$
che saranno indefinite qualora per qualche $k$ si abbia $x_k=0$. Ovviamente $f^{\prime}(x^{\ast})=2 \sqrt{2} \neq 0$ e quindi lo zero \mye semplice.

Osserviamo che il metodo calcola la radice di $2$ utilizzando esclusivamente il prodotto $x_k^2=x_k \cdot x_k$, la sottrazione e la divisione, ed era un metodo comune per calcolare pi\myu in generale, con semplici modifiche, le radici quadrate di numeri non negativi.

Dal punto di vista della convergenza
\begin{enumerate}
\item la funzione $f(x)=x^2-2$ assume valori negativi per $x \in [0,\sqrt{2})$, e positivi per  $x \in (\sqrt{2},+\infty)$,
\item si ha che $f^{\prime}(x)=2x$, $f^{\prime \prime}(x)=2 >0$ per ogni $x \in [0,+\infty)$.
\end{enumerate}


Nell'esperimento, sapendo che $\sqrt{2} \in (1,2)$, siamo partiti da $x_0=2 > x^*=\sqrt{2}$, con tolleranza $\epsilon=10^{-15}$. In questo test le iterazioni si interrompono perch\'e $x_5=\sqrt{2}$ e non perc\mye un criterio di arresto \mye verificato (si veda la terza colonna della tabella).

Per il teorema \ref{LT1} possiamo affermare che il metodo di Newton determina una successione $\{x_k\}$ decrescente e convergente a $x^*$. Per il teorema di convergenza locale, la convergenza \mye quadratica.

Osserviamo che numericamente, per $k=1,2,3$, $|e_{k+1}|/|e_k|^2 \approx 3.54e-01$, suggerendo una convergenza quadratica del metodo di Newton, applicato a questo esempio. Come visto, la successione \mye decrescente.

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 	 $   0$ & $2.000000000000000e+00$ & $5.86e-01$ & $-$ & $2.00e+00$ \\
 	 $   1$ & $1.500000000000000e+00$ & $8.58e-02$ & $5.00e-01$ & $2.50e-01$\\
 	 $   2$ & $1.416666666666667e+00$ & $2.45e-03$ & $8.33e-02$ & $6.94e-03$\\
 	 $   3$ & $1.414215686274510e+00$ & $2.12e-06$ & $2.45e-03$ & $6.01e-06$\\
 	 $   4$ & $1.414213562374690e+00$ & $1.59e-12$ & $2.12e-06$ & $4.51e-12$\\
 	 $   5$ & $1.414213562373095e+00$ & $0.00e+00$ & $1.59e-12$ & $4.44e-16$\\
\hline
\end{tabular}
\caption{La convergenza del metodo di Newton alla soluzione $x^*=\sqrt{2}=1.414213562373095\ldots$ di $f(x)=x^2-2=0$  \mye molto rapida ovvero $f(x^*)=f^{\prime}(x^*)=0$. Il test del residuo \mye molto accurato, mentre quello dello step individua correttamente a posteriori l'errore dell'iterata precedente. Ad esempio, alla quinta iterata dice correttamente che l'errore alla quarta era $1.59e-12$.}
\end{table}

 \begin{figure}[h!]\label{figN3}
 \centering
 {\includegraphics[scale=0.25,clip]{new_exIII.eps}}

 \caption{Errore assoluto $|x_k-x^*|$ dove $x_k$ \mye la $k$-sima iterata del metodo di Newton per la soluzione di $f(x)=x^2-2=0$, in scala semilogaritmica.}
 \end{figure}



\begin{remark}
Si osservi che pi\myu in generale per calcolare la radice $n$-sima di $\alpha$ basta risolvere 
$$
f(x)=x^n-\alpha=0
$$ 
dove $x^* \in I$, con $I$ dipendente da $n$. Ad esempio, se $n$ \mye dispari si pu\myo supporre $I=\R$, mentre se $n$ \mye pari $I=[0,+\infty)$.

In questo caso, visto che $f^{\prime}(x)=nx^{n-1}$ e quindi il metodo di Newton genera la successione
$$
x_{k+1}=x_k-\frac{x_k^n-\alpha}{nx_k^{n-1}}=\frac{n-1}{n} x_k + \frac {\alpha}{n x_k^{n-1}}.
$$

In virt\myu del teorema di convergenza globale, per dedurre la convergenza basta scegliere $x_0$ cosicch\mye $x_0^n \geq \alpha$ e tale convergenza \mye quadratica per il teorema di convergenza locale.
\end{remark}




\end{example}






\begin{example}[Facoltativo]
Uno dei problemi sorti con i primi processori era quello di calcolare la divisione utilizzando esclusivamente somme, sottrazioni o moltiplicazioni.

Supponiamo di dover calcolare $a/b=a\cdot {\frac{1}{b}}$ e quindi, visto che il processore era capace di calcolare moltiplicazioni, bastava calcolare $1/b$ e moltiplicare il risultato ottenuto per $a$.

% DETTAGLI ACCURATI DOPO END DOCUMENT.

Dopo una complicata analisi sui numeri macchina normalizzati, si osserva che ci si pu\myo ricondurre al calcolare il reciproco di numeri in $\alpha \in [1/2,1)$ ovvero risolvere l'equazione
$$
f(x)=\frac{1}{x}-\alpha=0, \,\, \alpha \in [1/2,1).
$$
Visto che $f^{\prime}(x)=-1/x^2$, il metodo di Newton genera la successione
$$
x_{k+1}=x_{k}-\frac {\frac{1}{x_k}-\alpha} {-\frac{1}{x_k^2}}=x_{k}+x_k^2 \left( {\frac{1}{x_k}-\alpha} \right)=2x_k^2-\alpha x_k^2=(2 -\alpha \cdot x_k) \cdot x_k
$$
che pu\myo essere valutata solo con 1 sottrazione e due prodotto.

Di conseguenza, il metodo di Newton permette di calcolare la divisione di due numeri usando solo sottrazioni e moltiplicazioni.


\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
$   0$ & $2.000000000000000e+00$ & $8.24e-01$ & $-$ & $-3.50e-01$ \\
$   1$ & $6.000000000000001e-01$ & $5.76e-01$ & $1.40e+00$ & $8.17e-01$\\
$   2$ & $8.940000000000001e-01$ & $2.82e-01$ & $2.94e-01$ & $2.69e-01$\\
$   3$ & $1.108649400000000e+00$ & $6.78e-02$ & $2.15e-01$ & $5.20e-02$\\
$   4$ & $1.172560831697694e+00$ & $3.91e-03$ & $6.39e-02$ & $2.83e-03$\\
$   5$ & $1.176457594968538e+00$ & $1.30e-05$ & $3.90e-03$ & $9.39e-06$\\
$   6$ & $1.176470588091793e+00$ & $1.44e-10$ & $1.30e-05$ & $1.04e-10$\\
$   7$ & $1.176470588235294e+00$ & $0.00e+00$ & $1.44e-10$ & $0.00e+00$\\
\hline
\end{tabular}
\caption{La convergenza del metodo di Newton alla soluzione $x^*=1/0.85 \approx 1.176470588235294$ di $f(x)=\frac{1}{x}-0.85$, partendo da $x_0=2$  \mye molto rapida. Il test del residuo \mye molto accurato, mentre quello dello step individua correttamente a posteriori l'errore dell'iterata precedente. Si osservi che il calcolo ha necessitato, viste le $7$ iterazioni di $7$ somme e $14$ prodotti.}
\end{table}





\end{example}







%------------------------------------------------------------------------------------------------------------------------
% Facoltativo: Metodo delle secanti.
%------------------------------------------------------------------------------------------------------------------------

\section{Metodo delle secanti}
Uno dei metodi pi\myu comunemente utilizzati per la risoluzione di equazioni nonlineari \mye quello delle secanti, che nel caso di sistemi di equazioni nonlineari porta (non banalmente) al molto noto metodo di Broyden (1965).

Se $f:(a,b) \rightarrow \R$ \mye una funzione continua, il metodo delle secanti definisce la successione (cf. \cite[p.65]{ATK}) 

\begin{equation}
x_{n+1}=x_{n}-f(x_{n}) \cdot {  \frac {x_n-x_{n-1}} {f(x_n)-f(x_{n-1})}  }
\end{equation}

\noindent
ottenuta dal metodo di Newton sostituendo $f^{\prime}(x_n)$ col rapporto incrementale
$${  \frac {f(x_n)-f(x_{n-1})} {x_n-x_{n-1}} }.$$

\noindent
Si nota subito che a differenza del metodo di Newton, quello delle secanti richiede due punti iniziali $x_0$, $x_1$ e non necessita ovviamente del calcolo della derivata $f^{\prime}$.

Si dimostra che
\smsp
\begin{theorem}[Jeeves, 1958]
Se $f \in C^2([a,b])$ con la radice $\alpha \in [a,b]$ e $f^{\prime}(\alpha) \neq 0$ allora se $x_0$, $x_1$ sono sufficientemente vicine ad $\alpha$ le iterate del metodo delle secanti convergono ad $\alpha$, con ordine di convergenza pari alla {\sl{sezione aurea}}, ovvero $$p=  \frac {(1+\sqrt{5})} {2} \approx 1.62.$$
\end{theorem}

\begin{example}
 L'intento di questa sezione \mye di vedere la performance del metodo delle secanti, per valutare gli zeri di 
\begin{enumerate}
\item $f(x)=\exp(x)-1+x=0$, con $x_1=0$, $x_2=1$;
\item $f(x)=\sin(x)-x=0$, con $x_1=-2$, $x_2=3$;
\item $f(x)=x^2-2=0$, con $x_1=1$, $x_2=2$.
\end{enumerate}

\begin{remarkh}
Un primitivo utilizzo del metodo delle secanti si trova in una tavoletta babilonese del 1800 A.C.. Noto anche come {\sl{Regola della doppia falsa posizione}}, fu perfezionato da Cardano nel 1545, che lo utilizz\myo come metodo iterativo. Pare che il nome {\sl{metodo delle secanti}}, sia stato proposto da Jeeves nel 1958, che per primo prov\myo l'ordine di convergenza di tale metodo. Per ulteriori ragguagli storici si veda \cite{ORIGSEC}.
\end{remarkh}

Si vede che in linea di massima sono paragonabili a quelle del metodo di Newton, richiedendo per\myo due dati iniziali, ma non la derivata di $f$ che viene stimata tramite un rapporto incrementale.

\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 	 $   0$ & $0.000000000000000e+00$ & $4.43e-01$ & $-$ & $-1.00e+00$ \\
 	 $   1$ & $1.000000000000000e+00$ & $5.57e-01$ & $1.00e+00$ & $1.72e+00$ \\
 	 $   2$ & $3.678794411714423e-01$ & $7.50e-02$ & $6.32e-01$ & $-1.87e-01$\\
 	 $   3$ & $4.300563616528947e-01$ & $1.28e-02$ & $6.22e-02$ & $-3.26e-02$\\
 	 $   4$ & $4.431457539835317e-01$ & $2.91e-04$ & $1.31e-02$ & $7.45e-04$\\
 	 $   5$ & $4.428532661274237e-01$ & $1.13e-06$ & $2.92e-04$ & $-2.90e-06$\\
 	 $   6$ & $4.428544009017152e-01$ & $1.01e-10$ & $1.13e-06$ & $-2.57e-10$\\
 	 $   7$ & $4.428544010023887e-01$ & $1.67e-16$ & $1.01e-10$ & $1.67e-16$\\
 \hline
\end{tabular}
\caption{La convergenza del metodo delle secanti alla soluzione $x^* =0.4428544010023887\ldots$ di $f(x)=\exp(x)-1+x=0$ \mye molto rapida, paragonabile in termini di iterazioni a quella del metodo di Newton. Quali dati iniziali abbiamo scelto $x_0=0$ e $x_1=1$. Lo step fornisce buone stime a posteriori dell'errore compiuto all'iterazione precedente.}
\end{table}
 	 
 	 
 	 
\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 $   0$ & $-2.000000000000000e+00$ & $2.00e+00$ & $-$ & $1.09e+00$ \\
 	 $   1$ & $3.000000000000000e+00$ & $3.00e+00$ & $5.00e+00$ & $-2.86e+00$\\
 	 $   2$ & $-6.192179107632967e-01$ & $6.19e-01$ & $3.62e+00$ & $3.88e-02$\\
 	 $   3$ & $-5.707325299195892e-01$ & $5.71e-01$ & $4.85e-02$ & $3.05e-02$\\
 	 $   4$ & $-3.934167222042483e-01$ & $3.93e-01$ & $1.77e-01$ & $1.01e-02$\\
 	 $   5$ & $-3.059435414661084e-01$ & $3.06e-01$ & $8.75e-02$ & $4.75e-03$ \\
 	 $   6$ & $-2.278322477580405e-01$ & $2.28e-01$ & $7.81e-02$ & $1.97e-03$ \\
 	 $   7$ & $-1.726853342973921e-01$ & $1.73e-01$ & $5.51e-02$ & $8.57e-04$ \\
 	 $   8$ & $-1.300690036608595e-01$ & $1.30e-01$ & $4.26e-02$ & $3.66e-04$ \\
 	 $   9$ & $-9.823363631520615e-02$ & $9.82e-02$ & $3.18e-02$ & $1.58e-04$ \\
 	 $  10$ & $-7.412520006397208e-02$ & $7.41e-02$ & $2.41e-02$ & $6.79e-05$ \\
 	 % ﻿$  11$ & $-5.595731332049650e-02$ & $5.60e-02$ & $1.82e-02$ & $2.92e-05$
%  	 $  12$ & $-4.223754204611702e-02$ & $4.22e-02$ & $1.37e-02$ & $1.26e-05$
%  	 $  13$ & $-3.188393645808658e-02$ & $3.19e-02$ & $1.04e-02$ & $5.40e-06$
%  	 $  14$ & $-2.406801518306406e-02$ & $2.41e-02$ & $7.82e-03$ & $2.32e-06$
%  	 $  15$ & $-1.816831332345191e-02$ & $1.82e-02$ & $5.90e-03$ & $1.00e-06$
%  	 $  16$ & $-1.371478383961675e-02$ & $1.37e-02$ & $4.45e-03$ & $4.30e-07$
%  	 $  17$ & $-1.035296250253680e-02$ & $1.04e-02$ & $3.36e-03$ & $1.85e-07$
%  	 $  18$ & $-7.815208405763049e-03$ & $7.82e-03$ & $2.54e-03$ & $7.96e-08$
%  	 $  19$ & $-5.899521950661010e-03$ & $5.90e-03$ & $1.92e-03$ & $3.42e-08$
 	 $  20$ & $-4.453415286714068e-03$ & $4.45e-03$ & $1.45e-03$ & $1.47e-08$ \\
%  	 $  21$ & $-3.361782907290553e-03$ & $3.36e-03$ & $1.09e-03$ & $6.33e-09$
%  	 $  22$ & $-2.537734460004233e-03$ & $2.54e-03$ & $8.24e-04$ & $2.72e-09$
%  	 $  23$ & $-1.915678910550476e-03$ & $1.92e-03$ & $6.22e-04$ & $1.17e-09$
%  	 $  24$ & $-1.446103156378638e-03$ & $1.45e-03$ & $4.70e-04$ & $5.04e-10$
%  	 $  25$ & $-1.091630946734480e-03$ & $1.09e-03$ & $3.54e-04$ & $2.17e-10$
%  	 $  26$ & $-8.240478088038679e-04$ & $8.24e-04$ & $2.68e-04$ & $9.33e-11$
%  	 $  27$ & $-6.220552813584801e-04$ & $6.22e-04$ & $2.02e-04$ & $4.01e-11$
%  	 $  28$ & $-4.695756364523789e-04$ & $4.70e-04$ & $1.52e-04$ & $1.73e-11$
%  	 $  29$ & $-3.544721601689286e-04$ & $3.54e-04$ & $1.15e-04$ & $7.42e-12$
 	 $  30$ & $-2.675831159495087e-04$ & $2.68e-04$ & $8.69e-05$ & $3.19e-12$ \\
%  	 $  31$ & $-2.019925188876338e-04$ & $2.02e-04$ & $6.56e-05$ & $1.37e-12$
%  	 $  32$ & $-1.524796399399942e-04$ & $1.52e-04$ & $4.95e-05$ & $5.91e-13$
%  	 $  33$ & $-1.151034753583298e-04$ & $1.15e-04$ & $3.74e-05$ & $2.54e-13$
%  	 $  34$ & $-8.688904275943952e-05$ & $8.69e-05$ & $2.82e-05$ & $1.09e-13$
%  	 $  35$ & $-6.559059587918703e-05$ & $6.56e-05$ & $2.13e-05$ & $4.70e-14$
%  	 $  36$ & $-4.951287397538464e-05$ & $4.95e-05$ & $1.61e-05$ & $2.02e-14$
%  	 $  37$ & $-3.737616678695961e-05$ & $3.74e-05$ & $1.21e-05$ & $8.70e-15$
%  	 $  38$ & $-2.821442928322494e-05$ & $2.82e-05$ & $9.16e-06$ & $3.74e-15$
%  	 $  39$ & $-2.129844931052127e-05$ & $2.13e-05$ & $6.92e-06$ & $1.61e-15$
 	 $  40$ & $-1.607772401198045e-05$ & $1.61e-05$ & $5.22e-06$ & $6.93e-16$ \\
%  	 $  41$ & $-1.213671959735139e-05$ & $1.21e-05$ & $3.94e-06$ & $2.98e-16$
%  	 $  42$ & $-9.161742823469699e-06$ & $9.16e-06$ & $2.97e-06$ & $1.28e-16$
%  	 $  43$ & $-6.915965437231466e-06$ & $6.92e-06$ & $2.25e-06$ & $5.51e-17$
%  	 $  44$ & $-5.220726077253034e-06$ & $5.22e-06$ & $1.70e-06$ & $2.37e-17$
%  	 $  45$ & $-3.941000899576136e-06$ & $3.94e-06$ & $1.28e-06$ & $1.02e-17$
%  	 $  46$ & $-2.974970812459836e-06$ & $2.97e-06$ & $9.66e-07$ & $4.39e-18$
%  	 $  47$ & $-2.245697625610128e-06$ & $2.25e-06$ & $7.29e-07$ & $1.89e-18$
%  	 $  48$ & $-1.695253833266496e-06$ & $1.70e-06$ & $5.50e-07$ & $8.12e-19$
%  	 $  49$ & $-1.279630296421087e-06$ & $1.28e-06$ & $4.16e-07$ & $3.49e-19$
 	 $  50$ & $-9.661064115820756e-07$ & $9.66e-07$ & $3.14e-07$ & $1.50e-19$ \\
%  	 $  51$ & $-7.290436232586484e-07$ & $7.29e-07$ & $2.37e-07$ & $6.46e-20$
%  	 $  52$ & $-5.505148567434749e-07$ & $5.51e-07$ & $1.79e-07$ & $2.78e-20$
%  	 $  53$ & $-4.152034285201589e-07$ & $4.15e-07$ & $1.35e-07$ & $1.19e-20$
%  	 $  54$ & $-3.140570120741586e-07$ & $3.14e-07$ & $1.01e-07$ & $5.19e-21$
%  	 $  55$ & $-2.360070214307883e-07$ & $2.36e-07$ & $7.80e-08$ & $2.20e-21$
%  	 $  56$ & $-1.786782672414100e-07$ & $1.79e-07$ & $5.73e-08$ & $9.53e-22$
%  	 $  57$ & $-1.347668810538012e-07$ & $1.35e-07$ & $4.39e-08$ & $3.97e-22$
%  	 $  58$ & $-1.034016052055091e-07$ & $1.03e-07$ & $3.14e-08$ & $1.85e-22$
%  	 $  59$ & $-7.595698883825359e-08$ & $7.60e-08$ & $2.74e-08$ & $7.94e-23$
 	 $  60$ & $-5.537352656281193e-08$ & $5.54e-08$ & $2.06e-08$ & $2.65e-23$ \\
%  	 $  61$ & $-4.508179542509111e-08$ & $4.51e-08$ & $1.03e-08$ & $1.32e-23$
%  	 $  62$ & $-3.479006428737028e-08$ & $3.48e-08$ & $1.03e-08$ & $6.62e-24$
%  	 $  63$ & $-2.449833314964945e-08$ & $2.45e-08$ & $1.03e-08$ & $3.31e-24$
%  	 $  64$ & $-1.420660201192862e-08$ & $1.42e-08$ & $1.03e-08$ & $0.00e+00$
 	 $  65$ & $-1.420660201192862e-08$ & $1.42e-08$ & $0.00e+00$ & $0.00e+00$ \\
\hline
\end{tabular}
\caption{La convergenza del metodo delle secanti alla soluzione $x^*=0$ di $f(x)=\sin(x)-x=0$ \mye molto lenta, ed \mye causata dal fatto che la soluzione \mye multipla ovvero $f(x^*)=f^{\prime}(x^*)=0$. Il test del residuo non assicura che $|x_n-x^{*}|$ sia piccolo, e questo \mye dovuto al fatto che la funzione, nei pressi della soluzione \mye molto piatta (la derivata \mye nulla!).}
\end{table}




\begin{table}[h!]
\begin{tabular}{c c c c c}
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$ & $|f(x_n)|$  \\
\hline
 	 $   0$ & $1.000000000000000e+00$ & $4.14e-01$ & $-$ & $-1.00e+00$ \\
 	 $   1$ & $2.000000000000000e+00$ & $5.86e-01$ & $1.00e+00$ & $2.00e+00$\\
 	 $   2$ & $1.333333333333333e+00$ & $8.09e-02$ & $6.67e-01$ & $-2.22e-01$\\
 	 $   3$ & $1.400000000000000e+00$ & $1.42e-02$ & $6.67e-02$ & $-4.00e-02$\\
 	 $   4$ & $1.414634146341463e+00$ & $4.21e-04$ & $1.46e-02$ & $1.19e-03$\\
 	 $   5$ & $1.414211438474870e+00$ & $2.12e-06$ & $4.23e-04$ & $-6.01e-06$\\
 	 $   6$ & $1.414213562057320e+00$ & $3.16e-10$ & $2.12e-06$ & $-8.93e-10$\\
 	 $   7$ & $1.414213562373095e+00$ & $2.22e-16$ & $3.16e-10$ & $8.88e-16$\\
\hline
\end{tabular}
\caption{La convergenza del metodo delle secanti alla soluzione $x^* =\sqrt{2}=1.414213562373095\ldots$ di $f(x)=x^2-2=0$ \mye molto rapida, paragonabile in termini di iterazioni a quella del metodo di Newton. Quali dati iniziali abbiamo scelto $x_0=1$ e $x_1=2$. Lo step fornisce buone stime a posteriori dell'errore compiuto all'iterazione precedente.}
\end{table}


 	 
 	 
\end{example}

%------------------------------------------------------------------------------------------------------------------------
% Metodo di punto fisso.
%------------------------------------------------------------------------------------------------------------------------

\section{Metodo di punto fisso (o di Picard)}

Consideriamo i problemi di {\it{punto fisso}}
$$x=\phi(x)$$
in cui supponiamo che $\phi: [a,b] \rightarrow [a,b]$ sia una funzione continua. Notiamo subito che ogni problema di tipo $f(x)=0$ si pu\myo ovviamente riscrivere in questa forma, posto $\phi(x)=f(x)+x$. 

Dal punto di visto geometrico, coincide col calcolare l'intersezione tra la bisettrice $y=x$ con il grafico della curva $y=\phi(x)$.

Nel metodo di punto fisso, si definisce la successione
$$x_{k+1}=\phi(x_k)$$
che si desidera convergere ad $\alpha$ tale che $\phi(\alpha)=\alpha$. La funzione $\phi$ \mye talvolta detta di {\sl{iterazione}} perch\mye a partire da $x_k$ determina $x_{k+1}$.

Si dimostra che (cf. {\cite[p.80]{ATK}})
\smsp
\begin{theorem} {\label{BAN}}
Si assuma che 
\begin{enumerate}
\item $\phi$ sia derivabile con continuit\mya in $[a,b]$, 
\item $\phi([a,b]) \subseteq [a,b]$ 
\item se $x \in [a,b]$ allora
$$|\phi^{\prime}(x)| \leq \theta < 1$$
con $\theta$ indipendente da $x$.
\end{enumerate}

Allora 
\begin{enumerate}
\item $x=\phi(x)$ ha un'unica soluzione $\alpha$ in $[a,b]$;
\item per qualsiasi scelta di $x_0 \in [a,b]$, posto $$x_{n+1}=\phi(x_n)$$ \noindent la successione converge ad $\alpha$;
\item posto $e_n=|x_n-\alpha|$ si ha $\lim_n \frac{e_{n+1}}{e_n}=|\phi^{\prime}(\alpha)|$ (convergenza almeno lineare);
\item si ha $$|\alpha - x_n| \leq {\frac{\theta^n}{1-\theta}}|x_1-x_0|;$$
\item vale la {\sl{stima a priori}} $$|x_n-\alpha| \leq \theta^n |x_0-\alpha|;$$
\item vale la {\sl{stima a posteriori}} 
$$|x_n-\alpha|= \frac {|x_{n+1}-x_n|}   {1-\phi^{\prime}(\xi_n)} \leq \frac{1}{1-\theta} |x_{n+1}-x_n|,$$
con $x_n$ nel pi\myu piccolo intervallo aperto contenente $x_n$ e $\alpha$.
\end{enumerate}
\end{theorem}

\smsp

Si osservi che questo teorema 
\begin{itemize}
\item stabilisce l'esistenza e unicit\mya della soluzione del problema di punto fisso,
\item offre un metodo iterativo $x_{k+1}=\phi(x_k)$ per poterla approssimare, con convergenza almeno lineare (potrebbe essere $\phi^{\prime}(\alpha) = 0$ ed avere effettivamente ordine $p >1$),
\item offre una maggiorazione dell'errore $|\alpha - x_n|$ dipendentemente dalla distanza delle prime due iterazioni,
\item suggerisce stime dell'errore compiuto; in particolare il punto 6. fa capire che per $\theta \approx 1$ lo step pu\myo non essere un buon criterio di arresto, perch\mye in tal caso $1/(1-\theta)$ pu\myo essere cos\myi grande, che nonostante $|x_{n+1}-x_n|$ sia piccolo, pu\myo accadere che $|x_n-\alpha|$ sia grande.
\end{itemize}

\smsp
Per semplificare l'applicazione del precedente teorema (cf. {\cite[p.81]{ATK}})

\begin{theorem}[Convergenza locale]{\label{BAN2}}
Si assuma che 
\begin{enumerate}
\item $\alpha$ sia la soluzione di $x=\phi(x)$
\item $\phi$ sia derivabile con continuit\mya in un intervallo centrato in $\alpha$,
\item $|\phi^{\prime}(\alpha)| < 1$.
\end{enumerate}

Allora esiste un intorno $I$ di $\alpha$ per cui
\begin{enumerate}
\item $x=\phi(x)$ ha un'unica soluzione $\alpha$ in $I$;
\item per qualsiasi scelta di $x_0 \in I$, posto $$x_{n+1}=\phi(x_n)$$ \noindent la successione converge ad $\alpha$ almeno linearmente;
\item posto $e_n=|x_n-\alpha|$ si ha $\lim_n \frac{e_{n+1}}{e_n}=|\phi^{\prime}(\alpha)|$ (convergenza almeno lineare).
\end{enumerate}


\end{theorem}

Notiamo come si possa utilizzare tale teorema per determinare la convergenza quadratica di un metodo di punto fisso. 

Vale il seguente teorema, molto utile per determinare l'ordine di convergenza del metodo di punto fisso (cf. {\cite[p.82]{ATK}}).
\begin{theorem}\label{CPF}
Si supponga che partendo da un certo $x_0 \in [a,b]$, la successione $\{x_k\}$ sia tale che 
$x_{k+1}=\phi(x_k)$. Inoltre che 
\begin{enumerate}
\item $\phi \in C^{p}([a,b])$, 
\item $\phi(\alpha)=\alpha$, 
\item $\phi^{(j)}(\alpha)=0$, per $j=0,\ldots,p-1$ e $\phi^{(p)}(\alpha) \neq 0$,
\item se $p=1$ allora $|\phi(\alpha)| <1$.
\end{enumerate}
Se il punto iniziale $x_0$ \mye sufficientemente vicino ad $\alpha$, allora $x_k \rightarrow \alpha$ e l'ordine di convergenza del metodo \mye uguale a $p$, essendo
$$
\lim \frac{e_{n+1}} {e_n^p}= \frac{|\phi^{(p)}(\alpha)|} {p!}.
$$
\end{theorem}

\begin{proof}
Osserviamo che se 
\begin{itemize}
\item $p=1$ abbiamo per ipotesi $|\phi(\alpha)| <1$,
\item $p > 1$ allora $|\phi^{(1)}(\alpha)|=0 < 1$,
\end{itemize}
e quindi $x_k \rightarrow \alpha$ dal teorema {\ref{BAN2}}.

Per un certo $\xi_k \in {\cal{I}}(\alpha,x_k)$, ovvero appartenente al pi\myu piccolo intervallo aperto contenente $\alpha$ e $x_k$, abbiamo dalla formula di Taylor
\begin{eqnarray}
x_{k+1}=\phi(x_k)&=&\phi(\alpha)+\sum_{j=1}^{p-1} \phi^{(j)}{(\alpha)}\frac {(x_k-\alpha)^j}{j!}+\phi^{(p)}{(\xi_k)}\frac {(x_k-\alpha)^p}{p!} \nonumber \\
&=&\alpha+\phi^{(p)}{(\xi_k)}\frac {(x_k-\alpha)^p}{p!} \nonumber
\end{eqnarray}
Essendo 
$$
x_{k+1}=\alpha+\phi^{(p)}{(\xi_k)}\frac {(x_k-\alpha)^p}{p!} 
$$
sottraendo $\alpha$ ad ambo i membri, posto $e_k=|x_k-\alpha|$,
\begin{equation}\label{23423}
x_{k+1}-\alpha=\phi^{(p)}{(\xi_k)}\frac {(x_k-\alpha)^p}{p!} \Rightarrow
e_{k+1}=|\phi^{(p)}{(\xi_k)}| \frac{e_k^p}{p!}
\end{equation}
da cui
\begin{itemize}
\item per qualche $k^*$ si ha $e_{k^*}=0$ e quindi da (\ref{23423}) \mye $e_k=0$ per $k \geq k^*$, o
\item \mye ben definita per ogni $k \in {\mathbb{N}}$ la frazione $\frac{e_{k+1}}{e_k^p}$ ed \mye $$ \lim_{k \rightarrow \infty} \frac{e_{k+1}}{e_k^p}=\lim_{k \rightarrow \infty} \frac{|\phi^{(p)}{(\xi_k)}|}{p!} =\frac{|\phi^{(p)}(\alpha)|}{p!} \neq 0  $$
\end{itemize}
cio\mye l'ordine di convergenza \mye uguale a $p$. 

L'ultimo passaggio necessita una spiegazione. Sappiamo che $\xi_k \in {\cal{I}}(x_k,\alpha)$, ovvero al pi\myu piccolo intervallo aperto contentente $x_k$ e $\alpha$ e poich\mye $x_k \rightarrow \alpha$, per il teorema del confronto, $\xi_k \rightarrow \alpha$. Quindi, essendo $\phi \in C^{p}([a,b])$, ricaviamo $\phi^{(p)}{(\xi_k)} \rightarrow \phi^{(p)}(\alpha)$ e quindi visto che il valore assoluto \mye una funzione continua, pure $|\phi^{(p)}{(\xi_k)}| \rightarrow |\phi^{(p)}(\alpha)|$.
\end{proof}

\begin{example}
Quello di Newton \mye un particolare metodo di punto fisso. Infatti per 
$$
\phi(x):=x-\frac{f(x)}{f^{\prime}(x)}
$$
abbiamo
$$x_{k+1}=\phi(x_k)=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}.$$ 

Supponiamo 
\begin{enumerate}
\item $x^*$ sia uno zero semplice di $f(x)=0$ tale che $f^{\prime \prime}(x^*)\neq 0$,
\item $x_n \rightarrow x^*$,
\item $f:([a,b]) \rightarrow \R$ sia sufficientemente differenziabile con continuit\mya. % $f^{\prime}$ non si annulli in $[a,b]$.
\end{enumerate}

Dopo qualche calcolo, 
$$
\phi^{\prime}(x)=1-\frac{(f^{\prime}(x))^2-f(x)f^{\prime \prime}(x)}{(f^{\prime}(x))^2}=\frac{f(x)f^{\prime \prime}(x)}{(f^{\prime}(x))^2}
$$
e
$$
\phi^{\prime \prime}(x)=
\frac{f^{(2)}(x)}{f^{(1)}(x)} + \frac{f(x)f^{(3)}(x)}{(f^{(1)}(x))^2} - \frac{2 f(x)(f^{(2)}(x))^2}{(f^{(1)}(x))^3}.
$$



Visto che $f^{\prime}(x^*) \neq 0$, ma $f(x^*)=0$
$$
\phi^{\prime}(x^*)=\frac{f(x)f^{\prime \prime}(x^*)}{(f^{\prime}(x^*))^2}=0
$$
e se supponiamo $f^{\prime \prime}(x^*) \neq 0$, allora essendo $f(x^*)=0$,
$$
\phi^{\prime \prime}(x^*)=\frac{f^{(2)}(x^*)}{f^{(1)}(x^*)} + 
\frac{f(x^*)f^{(3)}(x^*)}{(f^{(1)}(x^*))^2} - \frac{2 f(x^*)(f^{(2)}(x^*))^2}{(f^{(1)}(x^*))^3} \neq 0
$$
da cui deduciamo che il metodo di Newton ha convergenza locale quadratica in virt\myu del teorema \ref{CPF}.

\begin{remark}
Si osservi che i teoremi \ref{BAN} e \ref{BAN2} comportano che sotto opportune ipotesi, se la radice \mye multipla allora la convergenza \mye almeno lineare.
\end{remark}

\begin{remark}
Il metodo delle secanti, a differenza del metodo di Newton, non determina una successione del tipo $x_{k+1}=\phi(x_k)$ perch\mye ogni iterazione dipende da 2 iterate precedenti (e non una sola!).
\end{remark}
\end{example}

\begin{example}
Desideriamo studiare $f(x)=\exp(x)-2+x=0$ mediante un metodo di punto fisso. Ricordiamo che esiste una sola soluzione in $[0,1]$, visto che $f(0)=-1$, $f(1)=\exp(1)-2+1 >0$ e si pu\myo applicare il teorema degli zeri di una funzione continua. Avevamo visto che la unica soluzione \mye $x^*=0.4428544010023887\ldots$.

La prima idea \mye di studiare il problema
$$
x=\phi(x):=2-\exp(x)
$$
ma purtroppo, essendo $\phi^{\prime}(x)=-\exp(x)$ e $x^* \in (0,1)$, abbiamo $|\phi^{\prime}(\alpha)|=|-\exp(\alpha)| > 1$ e i teoremi di punto fisso sopra indicati non possono essere utilizzati.

Osserviamo che $\exp(x)-2+x=0$ se e solo se $\exp(x)=2-x$ ovvero applicando il logaritmo ad ambo i membri $x=\ln(2-x)$ che \mye un'equazione in forma di punto fisso.

La funzione $\phi(x)=\ln(2-x)$ ha derivata 
$$
\phi^{\prime}(x)=\frac{1}{2-x}
$$
che \mye una funzione strettamente crescente, ed essendo $\phi^{\prime}(0)=1/2$, $\phi^{\prime}(1)=1$, visto che il punto fisso $\alpha=x^* \in (0,1)$, sicuramente \mye tale che
$$
1/2 < \phi^{\prime}(\alpha)=\frac{1}{2-\alpha}  < 1.
$$
e quindi 
$$
|\phi^{\prime}(\alpha)|< 1.
$$
Di conseguenza il metodo di punto fisso converge alla soluzione almeno localmente.

Testiamo numericamente la convergenza se scegliamo $x_0=0$ oppure $x_0=1$. In entrambi i casi il metodo converge linearmente, come si pu\myo evincere dai grafici dell'errore in scala semilogaritmica.

Confrontando con il numero di iterazioni del metodo di Newton o delle secanti per raggiungere la stessa precisione si capisce che nonostante il basso costo di ogni iterazione, il metodo di punto fisso utilizzato non sia in questo caso da suggerire.


\begin{table}[h!]
\begin{center}
\begin{tabular}{c c c c }
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$   \\
\hline
$   0$ & $0.000000000000000e+00$ & $4.43e-01$ & $-$ \\
 	 $   1$ & $6.931471805599453e-01$ & $2.50e-01$ & $6.93e-01$\\
 	 $   2$ & $2.676218188444345e-01$ & $1.75e-01$ & $4.26e-01$\\
 	 $   3$ & $5.494951357024610e-01$ & $1.07e-01$ & $2.82e-01$\\
 	 $   4$ & $3.719116781052663e-01$ & $7.09e-02$ & $1.78e-01$\\
 	 $   5$ & $4.874065178868661e-01$ & $4.46e-02$ & $1.15e-01$\\
 	 $   6$ & $4.138257153687164e-01$ & $2.90e-02$ & $7.36e-02$\\
 	 $   7$ & $4.613250066022943e-01$ & $1.85e-02$ & $4.75e-02$\\
 	 $   8$ & $4.309216521766674e-01$ & $1.19e-02$ & $3.04e-02$\\
 	 $   9$ & $4.504884073820321e-01$ & $7.63e-03$ & $1.96e-02$\\
 	 $  10$ & $4.379397797394399e-01$ & $4.91e-03$ & $1.25e-02$\\
%  	 $  11$ & $4.460056039781504e-01$ & $3.15e-03$ & $8.07e-03$
%  	 $  12$ & $4.408286457754075e-01$ & $2.03e-03$ & $5.18e-03$
%  	 $  13$ & $4.441544969443129e-01$ & $1.30e-03$ & $3.33e-03$
%  	 $  14$ & $4.420191297311959e-01$ & $8.35e-04$ & $2.14e-03$
%  	 $  15$ & $4.433906689834486e-01$ & $5.36e-04$ & $1.37e-03$
%  	 $  16$ & $4.425099500109551e-01$ & $3.44e-04$ & $8.81e-04$
%  	 $  17$ & $4.430755832090135e-01$ & $2.21e-04$ & $5.66e-04$
%  	 $  18$ & $4.427123475444539e-01$ & $1.42e-04$ & $3.63e-04$
%  	 $  19$ & $4.429456236721741e-01$ & $9.12e-05$ & $2.33e-04$
  	 $  20$ & $4.427958160235598e-01$ & $5.86e-05$ & $1.50e-04$\\
%  	 $  21$ & $4.428920236093007e-01$ & $3.76e-05$ & $9.62e-05$
%  	 $  22$ & $4.428302394458529e-01$ & $2.42e-05$ & $6.18e-05$
%  	 $  23$ & $4.428699174506262e-01$ & $1.55e-05$ & $3.97e-05$
%  	 $  24$ & $4.428444362787582e-01$ & $9.96e-06$ & $2.55e-05$
%  	 $  25$ & $4.428608003344440e-01$ & $6.40e-06$ & $1.64e-05$
%  	 $  26$ & $4.428502913383924e-01$ & $4.11e-06$ & $1.05e-05$
%  	 $  27$ & $4.428570402280176e-01$ & $2.64e-06$ & $6.75e-06$
%  	 $  28$ & $4.428527060883951e-01$ & $1.69e-06$ & $4.33e-06$
%  	 $  29$ & $4.428554894767561e-01$ & $1.09e-06$ & $2.78e-06$
  	 $  30$ & $4.428537019831390e-01$ & $6.99e-07$ & $1.79e-06$ \\
%  	 $  31$ & $4.428548499129420e-01$ & $4.49e-07$ & $1.15e-06$
%  	 $  32$ & $4.428541127116736e-01$ & $2.88e-07$ & $7.37e-07$
%  	 $  33$ & $4.428545861428715e-01$ & $1.85e-07$ & $4.73e-07$
%  	 $  34$ & $4.428542821050329e-01$ & $1.19e-07$ & $3.04e-07$
%  	 $  35$ & $4.428544773583512e-01$ & $7.64e-08$ & $1.95e-07$
%  	 $  36$ & $4.428543519665344e-01$ & $4.90e-08$ & $1.25e-07$
%  	 $  37$ & $4.428544324932481e-01$ & $3.15e-08$ & $8.05e-08$
%  	 $  38$ & $4.428543807789362e-01$ & $2.02e-08$ & $5.17e-08$
%  	 $  39$ & $4.428544139899038e-01$ & $1.30e-08$ & $3.32e-08$
  	 $  40$ & $4.428543926617972e-01$ & $8.34e-09$ & $2.13e-08$ \\
%  	 $  41$ & $4.428544063587223e-01$ & $5.36e-09$ & $1.37e-08$
%  	 $  42$ & $4.428543975625473e-01$ & $3.44e-09$ & $8.80e-09$
%  	 $  43$ & $4.428544032114570e-01$ & $2.21e-09$ & $5.65e-09$
%  	 $  44$ & $4.428543995837233e-01$ & $1.42e-09$ & $3.63e-09$
%  	 $  45$ & $4.428544019134564e-01$ & $9.11e-10$ & $2.33e-09$
%  	 $  46$ & $4.428544004173002e-01$ & $5.85e-10$ & $1.50e-09$
%  	 $  47$ & $4.428544013781327e-01$ & $3.76e-10$ & $9.61e-10$
%  	 $  48$ & $4.428544007610855e-01$ & $2.41e-10$ & $6.17e-10$
%  	 $  49$ & $4.428544011573536e-01$ & $1.55e-10$ & $3.96e-10$
  	 $  50$ & $4.428544009028699e-01$ & $9.95e-11$ & $2.54e-10$ \\
%  	 $  51$ & $4.428544010662996e-01$ & $6.39e-11$ & $1.63e-10$
%  	 $  52$ & $4.428544009613449e-01$ & $4.10e-11$ & $1.05e-10$
%  	 $  53$ & $4.428544010287469e-01$ & $2.64e-11$ & $6.74e-11$
%  	 $  54$ & $4.428544009854612e-01$ & $1.69e-11$ & $4.33e-11$
%  	 $  55$ & $4.428544010132594e-01$ & $1.09e-11$ & $2.78e-11$
%  	 $  56$ & $4.428544009954073e-01$ & $6.98e-12$ & $1.79e-11$
%  	 $  57$ & $4.428544010068719e-01$ & $4.48e-12$ & $1.15e-11$
%  	 $  58$ & $4.428544009995095e-01$ & $2.88e-12$ & $7.36e-12$
%  	 $  59$ & $4.428544010042376e-01$ & $1.85e-12$ & $4.73e-12$
  	 $  60$ & $4.428544010012012e-01$ & $1.19e-12$ & $3.04e-12$ \\
%  	 $  61$ & $4.428544010031511e-01$ & $7.63e-13$ & $1.95e-12$
%  	 $  62$ & $4.428544010018988e-01$ & $4.90e-13$ & $1.25e-12$
%  	 $  63$ & $4.428544010027031e-01$ & $3.15e-13$ & $8.04e-13$
%  	 $  64$ & $4.428544010021866e-01$ & $2.02e-13$ & $5.16e-13$
%  	 $  65$ & $4.428544010025183e-01$ & $1.30e-13$ & $3.32e-13$
%  	 $  66$ & $4.428544010023052e-01$ & $8.33e-14$ & $2.13e-13$
%  	 $  67$ & $4.428544010024421e-01$ & $5.36e-14$ & $1.37e-13$
%  	 $  68$ & $4.428544010023543e-01$ & $3.42e-14$ & $8.78e-14$
%  	 $  69$ & $4.428544010024106e-01$ & $2.21e-14$ & $5.63e-14$
  	 $  70$ & $4.428544010023746e-01$ & $1.39e-14$ & $3.60e-14$ \\
%  	 $  71$ & $4.428544010023976e-01$ & $9.16e-15$ & $2.31e-14$
%  	 $  72$ & $4.428544010023828e-01$ & $5.66e-15$ & $1.48e-14$
%  	 $  73$ & $4.428544010023922e-01$ & $3.72e-15$ & $9.38e-15$
%  	 $  74$ & $4.428544010023862e-01$ & $2.28e-15$ & $6.00e-15$
%  	 $  75$ & $4.428544010023900e-01$ & $1.55e-15$ & $3.83e-15$
%  	 $  76$ & $4.428544010023877e-01$ & $8.33e-16$ & $2.39e-15$
%  	 $  77$ & $4.428544010023892e-01$ & $7.22e-16$ & $1.55e-15$
  	 $  78$ & $4.428544010023882e-01$ & $2.78e-16$ & $9.99e-16$ \\
\hline
\end{tabular}
\end{center}
\caption{La convergenza del metodo di punto fisso alla soluzione $x^*\approx 0.4428544010023885$ di $f(x)=\exp(x)-2+x=0$  non \mye molto rapida (risulta lineare). Abbiamo studiato il problema di punto fisso equivalente e quindi con soluzione $\alpha=x^*$, della forma $x=\phi(x)$ ove $\phi(x)=\ln(2-x)$. In questo caso $x_0=0$.}
\end{table}


\begin{table}[h!]
\begin{center}
\begin{tabular}{c c c c }
\hline
$n$ & $x_n$ & $|x_n-x^{*}|$ & $|x_n-x_{n-1}|$   \\
\hline
 $   0$ & $1.000000000000000e+00$ & $5.57e-01$ & $-$   \\
 	 $   1$ & $0.000000000000000e+00$ & $4.43e-01$ & $1.00e+00$\\
 	 $   2$ & $6.931471805599453e-01$ & $2.50e-01$ & $6.93e-01$\\
 	 $   3$ & $2.676218188444345e-01$ & $1.75e-01$ & $4.26e-01$\\
 	 $   4$ & $5.494951357024610e-01$ & $1.07e-01$ & $2.82e-01$\\
 	 $   5$ & $3.719116781052663e-01$ & $7.09e-02$ & $1.78e-01$\\
 	 $   6$ & $4.874065178868661e-01$ & $4.46e-02$ & $1.15e-01$\\
 	 $   7$ & $4.138257153687164e-01$ & $2.90e-02$ & $7.36e-02$\\
 	 $   8$ & $4.613250066022943e-01$ & $1.85e-02$ & $4.75e-02$\\
 	 $   9$ & $4.309216521766674e-01$ & $1.19e-02$ & $3.04e-02$\\
 	 $  10$ & $4.504884073820321e-01$ & $7.63e-03$ & $1.96e-02$\\
%  	 $  11$ & $4.379397797394399e-01$ & $4.91e-03$ & $1.25e-02$
%  	 $  12$ & $4.460056039781504e-01$ & $3.15e-03$ & $8.07e-03$
%  	 $  13$ & $4.408286457754075e-01$ & $2.03e-03$ & $5.18e-03$
%  	 $  14$ & $4.441544969443129e-01$ & $1.30e-03$ & $3.33e-03$
%  	 $  15$ & $4.420191297311959e-01$ & $8.35e-04$ & $2.14e-03$
%  	 $  16$ & $4.433906689834486e-01$ & $5.36e-04$ & $1.37e-03$
%  	 $  17$ & $4.425099500109551e-01$ & $3.44e-04$ & $8.81e-04$
%  	 $  18$ & $4.430755832090135e-01$ & $2.21e-04$ & $5.66e-04$
%  	 $  19$ & $4.427123475444539e-01$ & $1.42e-04$ & $3.63e-04$
  	 $  20$ & $4.429456236721741e-01$ & $9.12e-05$ & $2.33e-04$ \\
%  	 $  21$ & $4.427958160235598e-01$ & $5.86e-05$ & $1.50e-04$
%  	 $  22$ & $4.428920236093007e-01$ & $3.76e-05$ & $9.62e-05$
%  	 $  23$ & $4.428302394458529e-01$ & $2.42e-05$ & $6.18e-05$
%  	 $  24$ & $4.428699174506262e-01$ & $1.55e-05$ & $3.97e-05$
%  	 $  25$ & $4.428444362787582e-01$ & $9.96e-06$ & $2.55e-05$
%  	 $  26$ & $4.428608003344440e-01$ & $6.40e-06$ & $1.64e-05$
%  	 $  27$ & $4.428502913383924e-01$ & $4.11e-06$ & $1.05e-05$
%  	 $  28$ & $4.428570402280176e-01$ & $2.64e-06$ & $6.75e-06$
%  	 $  29$ & $4.428527060883951e-01$ & $1.69e-06$ & $4.33e-06$
  	 $  30$ & $4.428554894767561e-01$ & $1.09e-06$ & $2.78e-06$ \\
%  	 $  31$ & $4.428537019831390e-01$ & $6.99e-07$ & $1.79e-06$
%  	 $  32$ & $4.428548499129420e-01$ & $4.49e-07$ & $1.15e-06$
%  	 $  33$ & $4.428541127116736e-01$ & $2.88e-07$ & $7.37e-07$
%  	 $  34$ & $4.428545861428715e-01$ & $1.85e-07$ & $4.73e-07$
%  	 $  35$ & $4.428542821050329e-01$ & $1.19e-07$ & $3.04e-07$
%  	 $  36$ & $4.428544773583512e-01$ & $7.64e-08$ & $1.95e-07$
%  	 $  37$ & $4.428543519665344e-01$ & $4.90e-08$ & $1.25e-07$
%  	 $  38$ & $4.428544324932481e-01$ & $3.15e-08$ & $8.05e-08$
%  	 $  39$ & $4.428543807789362e-01$ & $2.02e-08$ & $5.17e-08$
  	 $  40$ & $4.428544139899038e-01$ & $1.30e-08$ & $3.32e-08$ \\
%  	 $  41$ & $4.428543926617972e-01$ & $8.34e-09$ & $2.13e-08$
%  	 $  42$ & $4.428544063587223e-01$ & $5.36e-09$ & $1.37e-08$
%  	 $  43$ & $4.428543975625473e-01$ & $3.44e-09$ & $8.80e-09$
%  	 $  44$ & $4.428544032114570e-01$ & $2.21e-09$ & $5.65e-09$
%  	 $  45$ & $4.428543995837233e-01$ & $1.42e-09$ & $3.63e-09$
%  	 $  46$ & $4.428544019134564e-01$ & $9.11e-10$ & $2.33e-09$
%  	 $  47$ & $4.428544004173002e-01$ & $5.85e-10$ & $1.50e-09$
%  	 $  48$ & $4.428544013781327e-01$ & $3.76e-10$ & $9.61e-10$
%  	 $  49$ & $4.428544007610855e-01$ & $2.41e-10$ & $6.17e-10$
  	 $  50$ & $4.428544011573536e-01$ & $1.55e-10$ & $3.96e-10$ \\
%  	 $  51$ & $4.428544009028699e-01$ & $9.95e-11$ & $2.54e-10$
%  	 $  52$ & $4.428544010662996e-01$ & $6.39e-11$ & $1.63e-10$
%  	 $  53$ & $4.428544009613449e-01$ & $4.10e-11$ & $1.05e-10$
%  	 $  54$ & $4.428544010287469e-01$ & $2.64e-11$ & $6.74e-11$
%  	 $  55$ & $4.428544009854612e-01$ & $1.69e-11$ & $4.33e-11$
%  	 $  56$ & $4.428544010132594e-01$ & $1.09e-11$ & $2.78e-11$
%  	 $  57$ & $4.428544009954073e-01$ & $6.98e-12$ & $1.79e-11$
%  	 $  58$ & $4.428544010068719e-01$ & $4.48e-12$ & $1.15e-11$
%  	 $  59$ & $4.428544009995095e-01$ & $2.88e-12$ & $7.36e-12$
  	 $  60$ & $4.428544010042376e-01$ & $1.85e-12$ & $4.73e-12$ \\
%  	 $  61$ & $4.428544010012012e-01$ & $1.19e-12$ & $3.04e-12$
%  	 $  62$ & $4.428544010031511e-01$ & $7.63e-13$ & $1.95e-12$
%  	 $  63$ & $4.428544010018988e-01$ & $4.90e-13$ & $1.25e-12$
%  	 $  64$ & $4.428544010027031e-01$ & $3.15e-13$ & $8.04e-13$
%  	 $  65$ & $4.428544010021866e-01$ & $2.02e-13$ & $5.16e-13$
%  	 $  66$ & $4.428544010025183e-01$ & $1.30e-13$ & $3.32e-13$
%  	 $  67$ & $4.428544010023052e-01$ & $8.33e-14$ & $2.13e-13$
%  	 $  68$ & $4.428544010024421e-01$ & $5.36e-14$ & $1.37e-13$
%  	 $  69$ & $4.428544010023543e-01$ & $3.42e-14$ & $8.78e-14$
  	 $  70$ & $4.428544010024106e-01$ & $2.21e-14$ & $5.63e-14$ \\
%  	 $  71$ & $4.428544010023746e-01$ & $1.39e-14$ & $3.60e-14$
%  	 $  72$ & $4.428544010023976e-01$ & $9.16e-15$ & $2.31e-14$
%  	 $  73$ & $4.428544010023828e-01$ & $5.66e-15$ & $1.48e-14$
%  	 $  74$ & $4.428544010023922e-01$ & $3.72e-15$ & $9.38e-15$
%  	 $  75$ & $4.428544010023862e-01$ & $2.28e-15$ & $6.00e-15$
%  	 $  76$ & $4.428544010023900e-01$ & $1.55e-15$ & $3.83e-15$
%  	 $  77$ & $4.428544010023877e-01$ & $8.33e-16$ & $2.39e-15$
%  	 $  78$ & $4.428544010023892e-01$ & $7.22e-16$ & $1.55e-15$
  	 $  79$ & $4.428544010023882e-01$ & $2.78e-16$ & $9.99e-16$ \\
\hline
\end{tabular}
\end{center}
\caption{La convergenza del metodo di punto fisso alla soluzione $x^* \approx 0.4428544010023885$ di $f(x)=\exp(x)-2+x=0$  non \mye molto rapida (risulta lineare). Abbiamo studiato il problema di punto fisso equivalente e quindi con soluzione $\alpha=x^*$, della forma $x=\phi(x)$ ove $\phi(x)=\ln(2-x)$. In questo caso $x_0=1$.}
\end{table}


\begin{center}
 \begin{figure}[h!]\label{cpfl}
 \centering
   {\includegraphics[scale=0.25,clip]{fp0.eps}}
    {\includegraphics[scale=0.25,clip]{fp1.eps}}
 \caption{Convergenza lineare delle approssimazioni di punto fisso, partendo da $x_0=0$ (a sinistra) e $x_0=1$ (a destra).}
 \end{figure}
\end{center}

\end{example}

%------------------------------------------------------------------------------------------------------------------------
% Facoltativo: il metodo di Halley.
%------------------------------------------------------------------------------------------------------------------------

\section{Facoltativo: il metodo di Halley}
Il metodo di Halley \cite{WIK31} approssima uno zero $x^\ast$ dell'equazione $f(x)=0$ con la sequenza di iterazioni
$$x_{n+1} = x_n - \frac {2 f(x_n) f'(x_n)} {2 {[f'(x_n)]}^2 - f(x_n) f''(x_n)}$$
a partire da un punto iniziale $x_0$. Ovviamente, si richiede l'esistenza della derivata seconda.

Se $f$ \mye differenziabile tre volte con continuit\mya e $x^\ast$ non \mye uno zero delle sue derivate, allora si pu\myo dimostrare (non immediato!) che in un certo intorno di $x^\ast$ le iterate $x_n$ soddisfano

$$| x_{n+1} - x^\ast | \le K \cdot {| x_n - x^\ast |}^3, \text{ per qualche }K > 0.\!$$

\noindent
cio\mye con convergenza almeno cubica.

\noindent
Quale esercizio si
\smsp
\begin{enumerate}
\item approssimi col metodo di Halley lo zero di $$f_2(x):=x-6.28-\sin(x),$$ partendo da $x_0=4$; \smsp
\item approssimi col metodo di Halley la radice quadrata di $2$ partendo da $x_0=1$; \smsp
\item approssimi col metodo di Halley la radice cubica di $2$ partendo da $x_0=1$. \smsp
\end{enumerate}

\noindent
interrompendo il processo quando lo step $|x_{n+1}-x_{n}|$ \mye inferiore di $10^{-14}$.
Si paragoni quindi il metodo di Halley con quello di Newton, sugli stessi problemi: quale dei due sembra convergere pi\myu velocemente?












\smsp

{\bf{Bibliografia.}}



\begin{thebibliography}{99}
\bibitem{ATK} K. Atkinson, {\em An Introduction to Numerical Analysis\/},
Wiley, (1989).

\bibitem{COM} V. Comincioli, {\em Analisi Numerica, metodi modelli
applicazioni\/}, McGraw-Hill, (1990).


\bibitem{DSC} J.E. Dennis, Jr. e R.B. Schnabel, {\em Numerical Methods for Unconstrained Optimization and Nonlinear Equations\/}, SIAM, (1996).

\bibitem{KEL} C.T. Kelley, {\em Iterative Methods for Linear and Nonlinear Equations\/}, SIAM Frontiers in Applied Mathematics. SIAM, Philadelphia, (1995).
\bibitem{QUA} A. Quarteroni, F. Saleri {\em Introduzione al Calcolo
Scientifico\/}, Springer, (2002).

\bibitem{MTAN} Mac Tutor (Newton), \\   {\href{http://www-history.mcs.st-andrews.ac.uk/Biographies/Newton.html}{http://www-history.mcs.st-andrews.ac.uk/Biographies/Newton.html}}.
\bibitem{MTAR} Mac Tutor (Raphson), \\   {\href{http://www-history.mcs.st-andrews.ac.uk/Biographies/Raphson.html}{http://www-history.mcs.st-andrews.ac.uk/Biographies/Raphson.html}}.
Origin and Evolution of the Secant Method in One Dimension
\bibitem{ORIGSEC} J-M. Papakonstantinou, R- A. Tapia, {\sl{Origin and Evolution of the Secant Method in One Dimension}},
The American Mathematical Monthly, Vol. 120, No. 6 (June–July 2013), pp. 500-518.
\bibitem{ROD} G. Rodriguez, {\em Algoritmi Numerici\/}, Pitagora Editrice, (2008).

\bibitem{TRE} L.N. Trefethen, {\sl{Numerical Analysis}}, Branches of Mathematics.

\bibitem{WIK1} Wikipedia (Calcolo dello zero di una funzione), \\   {\href{http://it.wikipedia.org/wiki/Calcolo\_dello\_zero\_di\_una\_funzione}{http://it.wikipedia.org/wiki/Calcolo\_dello\_zero\_di\_una\_funzione}}.

\bibitem{WIK2} Wikipedia (Metodo della bisezione), \\   {\href{http://it.wikipedia.org/wiki/Metodo\_della\_bisezione}{http://it.wikipedia.org/wiki/Metodo\_della\_bisezione}}.

\bibitem{WIK3} Wikipedia (Metodo delle tangenti), \\   {\href{http://it.wikipedia.org/wiki/Metodo\_delle\_tangenti}{http://it.wikipedia.org/wiki/Metodo\_delle\_tangenti}}.

\bibitem{WIK31} Wikipedia (Halley's method), \\
{\href{http://en.wikipedia.org/wiki/Halley's\_method}{http://en.wikipedia.org/wiki/Halley's\_method}}.

\bibitem{WIK4} Wikipedia (Newton's method), \\   {\href{http://en.wikipedia.org/wiki/Newton's\_method}{http://en.wikipedia.org/wiki/Newton's\_method}}.

\bibitem{WIKGAL} Wikipedia (Teorema di Abel-Ruffini), \\   {\href{
https://it.wikipedia.org/wiki/Teorema\_di\_Abel-Ruffini}{https://it.wikipedia.org/wiki/Teorema\_di\_Abel-Ruffini}}.

\bibitem{ZEI} E. Zeidler, {\em Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems\/}, Springer, (1998).

\end{thebibliography}

\end{document}

