Metodi del punto fisso

Riformulazione del problema

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

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

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

oppure

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

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

oppure

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

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

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

Esistenza di punti fissi

Teorema 4.3

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

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

   $$\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 )|$$-\log |f'(\alpha )|$. La convergenza è globale nell'intervallo $[a,b]$$[a,b]$.)

Dimostrazione

ESISTENZA DEL PUNTO FISSO: Per ipotesi, $\phi \colon [a,b]\to [a,b]$$\phi \colon [a,b]\to [a,b]$ è continua. Data $\psi (x)=\phi (x)-x\colon [a,b]\to [a,b]$$\psi (x)=\phi (x)-x\colon [a,b]\to [a,b]$, siccome $a<\phi (x)<b$$a<\phi (x)<b$, si ha $\psi (a)=\phi (a)-a\geq 0$$\psi (a)=\phi (a)-a\geq 0$ e $\psi (b)=\phi (b)-b<0$$\psi (b)=\phi (b)-b<0$. Quindi $\psi$$\psi$ è una funzione continua con segni opposti agli estremi, allora esiste $\alpha \in [a,b]$$\alpha \in [a,b]$ tale che $\psi (\alpha )=\phi (\alpha )-\alpha =0$$\psi (\alpha )=\phi (\alpha )-\alpha =0$, cioè $\phi (\alpha )=\alpha$$\phi (\alpha )=\alpha$. UNICITÀ DEL PUNTO FISSO: Per assurdo, supponiamo che esistano $\alpha _{1},\alpha _{2}$$\alpha _{1},\alpha _{2}$ tali che $\phi (\alpha _{1})=\alpha _{1}$$\phi (\alpha _{1})=\alpha _{1}$ e $\phi (\alpha _{2})=\alpha _{2}$$\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}].$$

$$|\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$$\phi '(x)<k$ segue che

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

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

e ho un assurdo.

CONVERGENZA DELLA SUCCESSIONE DELLE ITERATE: Per ogni $k\geq 0$$k \ge 0$, esiste un punto $\eta _{k}\in [\alpha ,x_{k}]$$\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$$

$$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 |$$

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

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

VERIFICA DEL LIMITE: Per la formula $\ast$$\ast$:

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

$$\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

Considero il metodo

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

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

Nel caso di convergenza, ci sono due situazioni possibili:

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

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

Condizione sufficiente di convergenza locale

Teorema 4.4 (teorema di Ostrosky)

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

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

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

 

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

Proposizione 4.1

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

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

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

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

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

Se $f'(\alpha )\neq 0$$f'(\alpha )\neq 0$ e quindi se $\alpha$$\alpha$ è una radice semplice, allora per la proposizione sopra $\gamma =1/2!\phi ''(\alpha )$$\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-{\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}}}$$

$$\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$$\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}}}$$

$$\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$$\alpha$, tenendo conto che $f(\alpha )=0$$f(\alpha )=0$:

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

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

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

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

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

$$\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)=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-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*\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)]]$$

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

$$\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 =s*\nu (x)+(x-\alpha )*\nu '(x)$$

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

$$\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 =[(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 )$$

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

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

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

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

e quindi $f'(\alpha )=0$$f'(\alpha )=0$ solo se $s=1$$s=1$, e quindi se $\alpha$$\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)}}$$\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}}}$$

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

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

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

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