Calcolo numerico/Metodi del punto fisso

Riformulazione del problema

Data $f:(a,b)\to ℝ$ trovare $\alpha$ tale che $f(\alpha )=0$ equivale a cercare $\alpha$ tale che $\alpha =\varphi (\alpha )$ con $\varphi$ funzione opportuna. Ad esempio, si può considerare

$\varphi =x+f(x)$

oppure

$\varphi (x)=x+\frac{f(x)}{h(x)},h(\alpha )\ne 0$

oppure

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

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

Esistenza di punti fissi

Teorema 4.3

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

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

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

Dimostrazione

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

Unicità del punto fisso: per assurdo, supponiamo che esistano ${\alpha }_1,{\alpha }_2$ tali che $\varphi ({\alpha }_1)={\alpha }_1$ e $\varphi ({\alpha }_2)={\alpha }_2$, allora

$|{\alpha }_2-{\alpha }_1|=|\varphi ({\alpha }_2)-\varphi ({\alpha }_1)|={\varphi }^{\prime }(\eta )\ast ({\alpha }_2-{\alpha }_1),\eta \in [{\alpha }_1,{\alpha }_2].$

Per l'ipotesi ${\varphi }^{\prime }(x)<k$ segue che

$|{\alpha }_2-{\alpha }_1|\le K\ast |{\alpha }_2-{\alpha }_1|<|{\alpha }_2-{\alpha }_1|$

e abbiamo un assurdo.

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

$x_{k+1}-\alpha =\varphi (x_k)-\varphi (\alpha )={\varphi }^{\prime }({\eta }_k)\ast (x_k-\alpha ),\alpha <{\eta }_k<x_k\text{formula }\ast$

e passando al valore assoluto

$|x_{k+1}-\alpha |\le K\ast |x_k-\alpha |\le K^{k+1}\ast |x_0-\alpha |$

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

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

$\underset{k\to \mathrm{\infty }}{lim}\frac{x_{k+1}-\alpha }{x_k-\alpha }=\underset{k\to \mathrm{\infty }}{lim}{\varphi }^{\prime }({\eta }_k)={\varphi }^{\prime }(\alpha )$

Interpretazione geometrica dei metodi di punto fisso

Consideriamo il metodo

$x_{k+1}=\varphi (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 $\varphi$ con la bisettrice, che è il punto fisso $\alpha$. Consideriamo $x_0$ a sinistra di $\alpha$, e poniamo $\varphi (x_0)=x_1$. Per determinare $x_2=\varphi (x_1)$ tracciamo a partire da $x_1$ il segmento orizzontale che lo congiunge alla bisettrice, e poi risaliamo sulla funzione, trovando $x_2=\varphi (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 $\varphi$, e supponiamo che $\varphi$ sia di classe $C^1$ in un intorno del punto fisso. Allora esiste $\delta >0$ tale che $\mathrm{\forall }{x}_{0}t.c.|x_0-\alpha |<\delta$, la successione converge e

$\underset{k\to \mathrm{\infty }}{lim}{x}_k=\alpha .$

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

Proposizione 4.1

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

$\underset{k\to \mathrm{\infty }}{lim}\frac{x_{k+1}-\alpha }{(x_k-\alpha {)}^{p+1}}=\frac{{\varphi }^{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^{\prime }(x_k)}$

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

Se $f^{\prime }(\alpha )\ne 0$ e quindi se $\alpha$ è una radice semplice, allora per la proposizione sopra $\gamma =1/2!{\varphi }^{″}(\alpha )$, e si ha

${\varphi }^{\prime }(x)=1-\frac{f^{\prime }(x{)}^2-f(x)\ast f^{″}(x)}{f^{\prime }(x{)}^2}$

${\varphi }^{\prime }(x)=1-1+\frac{f(x)\ast f^{″}(x)}{f^{\prime }(x{)}^2}=\frac{f(x)\ast f^{″}(x)}{f^{\prime }(x{)}^2}$

e vale 0 se valutato in $\alpha$.

${\varphi }^{″}(x)=\frac{f^{\prime }(x{)}^2\ast (f(x)\ast f^{(3)}(x)+f^{\prime }(x)\ast f^{″}(x))-2\ast f^{\prime }(x)\ast f^{″}(x)\ast f(x)\ast f^{″}(x)}{f^{\prime }(x{)}^4}$

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

${\varphi }^{″}(x)=\frac{f^{\prime }(\alpha {)}^3\ast f^{″}(\alpha )}{f^{\prime }(\alpha {)}^4}=\frac{f^{″}(\alpha )}{f^{\prime }(\alpha )}$

quindi

$\underset{k\to \mathrm{\infty }}{lim}\frac{x_{k+1}-\alpha }{(x_k-\alpha {)}^2}=1/2\frac{f^{″}(\alpha )}{f^{\prime }(\alpha )}$

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

${\varphi }^{\prime }(x)=\frac{f(x)\ast f^{″}(x)}{f^{\prime }(x{)}^2}$

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

$f^{″}(x)=(x-\alpha {)}^{s-1}\ast [s\ast {\nu }^{\prime }(x)++(-\alpha )\ast {\nu }^{\prime }(x)+(x-\alpha )\ast {\nu }^{″}(x)]+(s-1)\ast (x-\alpha {)}^{s-2}\ast [s\ast \nu (x)+(x-\alpha )\ast {\nu }^{\prime }(x)]$

$f^{″}(x)=(x-\alpha {)}^{s-2}\ast [(x-\alpha )\ast [s\ast {\nu }^{\prime }(x)-\alpha \ast {\nu }^{\prime }(x)+(x-\alpha )\ast {\nu }^{″}(x)+(s-1)\ast [s\ast \nu (x)+(x-\alpha )\ast {\nu }^{\prime }(x)]]$

$f^{″}(x)=(x-\alpha {)}^{s-2}\ast [(x-\alpha )\ast [(s-\alpha )\ast {\nu }^{\prime }(x)+(x-\alpha )\ast {\nu }^{″}(x)+(s-1)\ast s\ast \nu (x)+(s-1)(x-\alpha )\ast {\nu }^{\prime }(x)]]$

${\varphi }^{″}(x)=\frac{(x-\alpha {)}^s\ast \nu (x)\ast (x-\alpha {)}^{s-2}\ast \theta }{((x-\alpha {)}^{s-1}{)}^2\ast {\eta }^2}=\frac{\theta }{{\eta }^2}$

con

$\eta =s\ast \nu (x)+(x-\alpha )\ast {\nu }^{\prime }(x)$

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

$\theta =[(x-\alpha )\ast [(s-\alpha )\ast {\nu }^{\prime }(x)+(x-\alpha )\ast {\nu }^{″}(x)+(s-1)\ast s\ast \nu (x)+(s-1)(x-\alpha )\ast {\nu }^{\prime }(x)]]$

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

quindi

${\varphi }^{″}(\alpha )=\frac{\theta (\alpha )}{{\eta }^2(\alpha )}=\frac{(s-1)s\ast \nu (\alpha )}{s^2\ast {\nu }^2(\alpha )}$

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

e quindi $f^{\prime }(\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 $\varphi (x)=x-s\frac{f(x)}{f^{\prime }(x)}$, per ripristinare la convergenza superlineare, infatti si ottiene:

${\varphi }^{\prime }(\alpha )=1-s+s\frac{f(\alpha )f^{″}(\alpha )}{f^{\prime }(\alpha {)}^2}$

e sostituendo il valore ${\varphi }^{\prime }(\alpha )=(s-1)/s$ trovato prima:

${\varphi }^{″}(\alpha )=1-s+s\ast {\varphi }^{\prime }(\alpha )=1-s+s(s-1)/s=0$