title: Iterazione di punto fisso
text: # Iterazione di punto fisso
  
  In analisi numerica, l'iterazione di punto fisso o iterazione funzionale è un metodo per trovare le radici di una funzione, ovvero per risolvere un'equazione nella forma $f(x)=0$.
  
  Se $f,g:\mathbb {R} \to \mathbb {R}$ sono due funzioni tali che $g(x)=x-f(x)$, allora si ha $f(\alpha )=0$ se e solo se $g(\alpha )=\alpha$, cioè $\alpha$ è radice di $f$ se e solo se è punto fisso di $g$. Il metodo consiste nel risolvere l'equazione $g(x)=x$ dove la generica espressione di $g$ è:
  
      $g(x)=x-f(x)+F(f(x))\qquad F(0)=0$
  
  Si vede quindi che $g$, ovvero la funzione di iterazione, può essere scelta in vari modi. Ad esempio se $f(x)=x^{2}+x+1$ si può scegliere:
  
      $g(x)=-x^{2}-1\qquad g(x)=-1-{\frac {1}{x}}\dots$
  
  La soluzione si approssima (scelto un punto $x_{0}$ iniziale) con la successione:
  
      $x_{n+1}=g(x_{n})$
  
  ## Proprietà
  
  La convergenza del metodo è garantita sotto determinate ipotesi da alcuni risultati teorici.
  
  In primo luogo, se esiste un intervallo $[a,b]$ tale che:
  
  * $g:[a,b]\rightarrow [a,b]$
  * $g\in C^{1}([a,b])$
  * $|g'(x)|<1\;\forall x\in [a,b]$
  
  allora $g$ ha un unico punto fisso in $[a,b]$ (è una contrazione) e se $x_{0}\in [a,b]$ la successione sopra definita converge ad esso linearmente.
  
  Tuttavia non è sempre facile determinare un intervallo siffatto. Se però si conosce bene il comportamento di $g$ nei pressi del punto fisso, si può sfruttare il teorema di Ostrowski. Se:
  
  * $g\in C^{1}(I)$, dove $I$ è un intorno del punto fisso $\alpha$
  * $|g'(\alpha )|<1$
  
  allora $\exists \delta >0$ tale che se $|x_{0}-\alpha |<\delta$ la successione converge ad $\alpha$. Si noti che se la seconda ipotesi non è verificata, o c'è divergenza o non si può dir nulla (nel caso dell'uguaglianza). La velocità di convergenza aumenta con l'ordine di derivabilità.
  
  ## Altri metodi
  
  Il metodo delle corde e quello di Newton si possono vedere come casi particolari dell'iterazione di punto fisso, usando come funzioni di iterazione rispettivamente:
  
      $g(x)=x-{\frac {b-a}{f(b)-f(a)}}f(x)$
      $g(x)=x-{\frac {f(x)}{f'(x)}}$
  