Calcolo numerico/Metodi del punto fisso

Riformulazione del problema

Data $f\colon (a,b)\to \mathbb {R}$ trovare $\alpha$ tale che $f(\alpha )=0$ equivale a cercare $\alpha$ tale che $\alpha =\phi (\alpha )$ con $\phi$ funzione opportuna. Ad esempio, si può considerare

$\phi =x+f(x)$

oppure

$\phi (x)=x+{\frac {f(x)}{h(x)}},\quad h(\alpha )\neq 0$

oppure

$\phi (x)=x+F(f(x))$

con $F$ continua e $F(0)=0$.

Esistenza di punti fissi

Teorema 4.3

Se $\phi$ mappa un intervallo $[a,b]$ in sé stesso, se $\phi \in C^{1}([a,b])$, e se esiste un $K<1$ tale che $|\phi '(x)|\leq K\forall x\in [a,b]$, segue che:

1. $\phi$ ha un unico punto fisso nell'intervallo $[a,b]$;
2. $x_{k}=\phi (x_{k-1})$ tende ad $\alpha$ per qualunque punto d'innesco $x_{0}\in [a,b]$;
3. $\lim _{k\to \infty }{\frac {x_{k+1}-\alpha }{x_{k}-\alpha }}=\phi '(\alpha )$.

Possiamo definire il tasso asintotico di convergenza come $-\log |f'(\alpha )|$. La convergenza è globale nell'intervallo $[a,b]$.

Dimostrazione

Esistenza del punto fisso: per ipotesi, $\phi \colon [a,b]\to [a,b]$ è continua. Data $\psi (x)=\phi (x)-x\colon [a,b]\to [a,b]$, siccome $a<\phi (x)<b$, si ha $\psi (a)=\phi (a)-a\geq 0$ e $\psi (b)=\phi (b)-b<0$. Quindi $\psi$ è una funzione continua con segni opposti agli estremi, allora esiste $\alpha \in [a,b]$ tale che $\psi (\alpha )=\phi (\alpha )-\alpha =0$, cioè $\phi (\alpha )=\alpha$.

Unicità del punto fisso: per assurdo, supponiamo che esistano $\alpha _{1},\alpha _{2}$ tali che $\phi (\alpha _{1})=\alpha _{1}$ e $\phi (\alpha _{2})=\alpha _{2}$, allora

$|\alpha _{2}-\alpha _{1}|=|\phi (\alpha _{2})-\phi (\alpha _{1})|=\phi '(\eta )*(\alpha _{2}-\alpha _{1}),\quad \eta \in [\alpha _{1},\alpha _{2}].$

Per l'ipotesi $\phi '(x)<k$ segue che

$|\alpha _{2}-\alpha _{1}|\leq K*|\alpha _{2}-\alpha _{1}|<|\alpha _{2}-\alpha _{1}|$

e abbiamo un assurdo.

Convergenza della successione delle iterate: per ogni $k\geq 0$, esiste un punto $\eta _{k}\in [\alpha ,x_{k}]$ tale che

$x_{k+1}-\alpha =\phi (x_{k})-\phi (\alpha )=\phi '(\eta _{k})*(x_{k}-\alpha ),\quad \alpha <\eta _{k}<x_{k}\quad {\hbox{formula }}\ast$

e passando al valore assoluto

$|x_{k+1}-\alpha |\leq K*|x_{k}-\alpha |\leq K^{k+1}*|x_{0}-\alpha |$

e siccome $K\leq 1$, la quantità tende a 0 per $k\to \infty$, cioè $\{x_{k}\}\to \alpha$, per ogni $x_{0}\in [a,b]$.

Verifica del limite: per la formula $\ast$:

$\lim _{k\to \infty }{\frac {x_{k+1}-\alpha }{x_{k}-\alpha }}=\lim _{k\to \infty }\phi '(\eta _{k})=\phi '(\alpha )$

Interpretazione geometrica dei metodi di punto fisso

Consideriamo il metodo

$x_{k+1}=\phi (x_{k})$

Nel caso di convergenza, ci sono due situazioni possibili:

1. convergenza monotona: i punti $x_{k}$ si trovano sempre a sinistra o sempre a destra della radice;
2. convergenza alternata: se $x_{k}$ si trova a sinistra della radice, $x_{k+1}$ si trova a destra e così via.

Consideriamo il punto di intersezione di $\phi$ con la bisettrice, che è il punto fisso $\alpha$. Consideriamo $x_{0}$ a sinistra di $\alpha$, e poniamo $\phi (x_{0})=x_{1}$. Per determinare $x_{2}=\phi (x_{1})$ tracciamo a partire da $x_{1}$ il segmento orizzontale che lo congiunge alla bisettrice, e poi risaliamo sulla funzione, trovando $x_{2}=\phi (x_{1})$ e così via. Se $x_{0}<\alpha$ e la funzione è crescente abbiamo una successione monotona crescente, mentre è decrescente nell'altro caso.

Condizione sufficiente di convergenza locale

Teorema 4.4 (teorema di Ostrosky)

Sia $\alpha$ un punto fisso di $\phi$, e supponiamo che $\phi$ sia di classe $C^{1}$ in un intorno del punto fisso. Allora esiste $\delta >0$ tale che $\forall x_{0}t.c.|x_{0}-\alpha |<\delta$, la successione converge e

$\lim _{k\to \infty }x_{k}=\alpha .$

Si sa che il $\delta$ esiste, ma non si sa come costruirlo.

Proposizione 4.1

Sia $\phi$ di classe $C^{p+1}$ in un opportuno intorno di $\alpha$, e supponiamo che $\phi ^{s}(\alpha )=0$ con $s=1,\dots ,p$, mentre $\phi ^{s+1}(\alpha )\neq 0$, allora il metodo di punto fisso ha ordine di convergenza $p+1$, e

$\lim _{k\to \infty }{\frac {x_{k+1}-\alpha }{(x_{k}-\alpha )^{p+1}}}={\frac {\phi ^{p+1}(\alpha )}{(p+1)!}}$

Osservazione sul metodo di Newton

Il metodo di Newton è un metodo di punto fisso, dove si pone:

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}$

quindi $\phi$ è della forma $\phi (x)=x-{\frac {f(x)}{h(x)}}$.

Se $f'(\alpha )\neq 0$ e quindi se $\alpha$ è una radice semplice, allora per la proposizione sopra $\gamma =1/2!\phi ''(\alpha )$, e si ha

$\phi '(x)=1-{\frac {f'(x)^{2}-f(x)*f''(x)}{f'(x)^{2}}}$

$\phi '(x)=1-1+{\frac {f(x)*f''(x)}{f'(x)^{2}}}={\frac {f(x)*f''(x)}{f'(x)^{2}}}$

e vale 0 se valutato in $\alpha$.

$\phi ''(x)={\frac {f'(x)^{2}*(f(x)*f^{(3)}(x)+f'(x)*f''(x))-2*f'(x)*f''(x)*f(x)*f''(x)}{f'(x)^{4}}}$

e valutando in $\alpha$, tenendo conto che $f(\alpha )=0$:

$\phi ''(x)={\frac {f'(\alpha )^{3}*f''(\alpha )}{f'(\alpha )^{4}}}={\frac {f''(\alpha )}{f'(\alpha )}}$

quindi

$\lim _{k\to \infty }{\frac {x_{k+1}-\alpha }{(x_{k}-\alpha )^{2}}}=1/2{\frac {f''(\alpha )}{f'(\alpha )}}$

Se $\alpha$ è una radice multipla di molteplicità $s$, si può scrivere $f(x)=(x-\alpha )^{s}*\nu (x)$. Ripetendo i conti precedenti,

$\phi '(x)={\frac {f(x)*f''(x)}{f'(x)^{2}}}$

$f'(x)=s(x-\alpha )^{s-1}*\nu (x)+(x-\alpha )^{s}*\nu '(x)=(x-\alpha )^{s-1}*[s*\nu (x)+(x-\alpha )*\nu '(x)]$

$f''(x)=(x-\alpha )^{s-1}*[s*\nu '(x)++(-\alpha )*\nu '(x)+(x-\alpha )*\nu ''(x)]+(s-1)*(x-\alpha )^{s-2}*[s*\nu (x)+(x-\alpha )*\nu '(x)]$

$f''(x)=(x-\alpha )^{s-2}*[(x-\alpha )*[s*\nu '(x)-\alpha *\nu '(x)+(x-\alpha )*\nu ''(x)+(s-1)*[s*\nu (x)+(x-\alpha )*\nu '(x)]]$

$f''(x)=(x-\alpha )^{s-2}*[(x-\alpha )*[(s-\alpha )*\nu '(x)+(x-\alpha )*\nu ''(x)+(s-1)*s*\nu (x)+(s-1)(x-\alpha )*\nu '(x)]]$

$\phi ''(x)={\frac {(x-\alpha )^{s}*\nu (x)*(x-\alpha )^{s-2}*\theta }{((x-\alpha )^{s-1})^{2}*\eta ^{2}}}={\frac {\theta }{\eta ^{2}}}$

con

$\eta =s*\nu (x)+(x-\alpha )*\nu '(x)$

$\eta (\alpha )=s*\nu (\alpha )$

$\theta =[(x-\alpha )*[(s-\alpha )*\nu '(x)+(x-\alpha )*\nu ''(x)+(s-1)*s*\nu (x)+(s-1)(x-\alpha )*\nu '(x)]]$

$\theta (\alpha )=(s-1)*s*\nu (\alpha )$

quindi

$\phi ''(\alpha )={\frac {\theta (\alpha )}{\eta ^{2}(\alpha )}}={\frac {(s-1)s*\nu (\alpha )}{s^{2}*\nu ^{2}(\alpha )}}$

$=(s-1)/s*\nu (\alpha )$

e quindi $f'(\alpha )=0$ solo se $s=1$, e quindi se $\alpha$ è una radice semplice.

Nel caso di radici multiple, per recuperare l'ordine di convergenza, costruisco la funzione $\phi (x)=x-s{\frac {f(x)}{f'(x)}}$, per ripristinare la convergenza superlineare, infatti si ottiene:

$\phi '(\alpha )=1-s+s{\frac {f(\alpha )f''(\alpha )}{f'(\alpha )^{2}}}$

e sostituendo il valore $\phi '(\alpha )=(s-1)/s$ trovato prima:

$\phi ''(\alpha )=1-s+s*\phi '(\alpha )=1-s+s(s-1)/s=0$