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)}}

Bibliografia

(EN) Richard L. Burden, J. Douglas Faires, Numerical Analysis, 3rd, PWS Publishers, 1985, ISBN 0-87150-857-5.

Voci correlate

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica