Iterazioni di punto fisso
Ciao!
Mi sono imbattuto nel seguente esercizi sull'iterazione di punto fisso, con soluzione annessa. Ma non ne vengo fuori a capirne il procedimento!
Si analizzi la convergenza delle iterazioni di punto fisso definite da:
$ x_{k+1} = sqrt(2x_x + 3) $
$ x_{k+1} = 3 / (x_k - 2) $
$ x_{k+1} = (x_k^2 - 3)/2 $
per la risoluzione dell'equazione lineare $x^2-2x-3=0$.
Io so (ma forse so male) che, condizione necessaria e sufficiente affinché si abbia convergenza, è che mi basti prendere un $x_0$ tale che la funzione $g(x)$ associata all'iterazione $x_{k+1}=g(x_k)$ abbia derivata, in modulo, strettamente minore di $1$.
Prendiamo il secondo ad esempio.. avrei $g(x)=3/(x-2)$ e dunque $g'(x)=-3/(x-2)^2$ e con qualche calcolo si ha
$|g'(x)|<1 \leftrightarrow x<2-sqrt(3) vee x>2-sqrt(3)$.
La soluzione mi dice che converge per ogni $x_0<2$
Provando con la calcolatrice, in effetti, converge per ogni $x in RR wedge x ne 2$
Una mano? Grazie!
Mi sono imbattuto nel seguente esercizi sull'iterazione di punto fisso, con soluzione annessa. Ma non ne vengo fuori a capirne il procedimento!
Si analizzi la convergenza delle iterazioni di punto fisso definite da:
$ x_{k+1} = sqrt(2x_x + 3) $
$ x_{k+1} = 3 / (x_k - 2) $
$ x_{k+1} = (x_k^2 - 3)/2 $
per la risoluzione dell'equazione lineare $x^2-2x-3=0$.
Io so (ma forse so male) che, condizione necessaria e sufficiente affinché si abbia convergenza, è che mi basti prendere un $x_0$ tale che la funzione $g(x)$ associata all'iterazione $x_{k+1}=g(x_k)$ abbia derivata, in modulo, strettamente minore di $1$.
Prendiamo il secondo ad esempio.. avrei $g(x)=3/(x-2)$ e dunque $g'(x)=-3/(x-2)^2$ e con qualche calcolo si ha
$|g'(x)|<1 \leftrightarrow x<2-sqrt(3) vee x>2-sqrt(3)$.
La soluzione mi dice che converge per ogni $x_0<2$
Provando con la calcolatrice, in effetti, converge per ogni $x in RR wedge x ne 2$
Una mano? Grazie!
Risposte
Quella condizione è sufficiente, ma non necessaria!
Fai qualche prova grafica col grafico della funzione e di x, ripercorrendo le iterazioni ad occhio e vedrai cosa succede.
Fai qualche prova grafica col grafico della funzione e di x, ripercorrendo le iterazioni ad occhio e vedrai cosa succede.
Grazie della risposta e del chiarimento!
Cioè, guardando il grafico, facendo qualche prova, mi ero convinto anch'io della bontà di quella soluzione..
..Ma come arrivo a trovarla? Credo che, in qualche modo, debba arrivare a dire che la funzione converge globalmente, su tutto $RR$, con $x ne 2$. Poi, la restrizione a $x<2$ vien da sé perché vado a cercarmi un intervallo, ma non so spiegare formalmente come dedurre questa convergenza globale..
Cioè, guardando il grafico, facendo qualche prova, mi ero convinto anch'io della bontà di quella soluzione..
..Ma come arrivo a trovarla? Credo che, in qualche modo, debba arrivare a dire che la funzione converge globalmente, su tutto $RR$, con $x ne 2$. Poi, la restrizione a $x<2$ vien da sé perché vado a cercarmi un intervallo, ma non so spiegare formalmente come dedurre questa convergenza globale..
Di fatto la condizione vera e propria è che sia una contrazione o che una sua ‘potenza’ (\(g\circ g\circ \dotsb \circ g\)) lo sia.
"vict85":
Di fatto la condizione vera e propria è che sia una contrazione o che una sua ‘potenza’ (\(g\circ g\circ \dotsb \circ g\)) lo sia.
Questa parrebbe fare al caso mio!
Dunque si può dire che, condizione necessaria e sufficiente affinché un'iterazione del tipo $x_{k+1}=g(x_k)$ sia convergente in un insieme $D subset RR$ è che esista un intero $k$ tale che $| g'(x)^k | < 1$ per ogni $x in D$?
Conferme?
Smentite?
Bla?
Scusa ma sono stato un po' preso. Se con \(g'(x)^k\) intendiamo la stessa cosa allora si e no. Insomma la funzione potrebbe non avere derivata e quindi la condizione è solo sufficiente. Dovresti comunque tener conto che la funzione dovrebbe essere una contrazione da uno spazio in se stesso.
La teoria in questione si basa sulla teoria delle contrazioni e quindi lo spazio che tu consideri deve essere una contrazione da sé stesso in sé stesso. Il problema del mandare lo spazio in sé non è un problema da poco perché se la funzione manda \(\displaystyle (-\infty, 0) \) in se stessa, le cose sono più complicate per i numeri positivi. Siccome hai mostrato che la derivata ha valore assoluto minore di 1 in \(\displaystyle (-\infty, 0) \) allora la funzione è una contrazione di quell'insieme e possiede un punto fisso (insomma la successione converge).
Per il commento che ho fatto prima per ogni \(\displaystyle x_0 \in [0,2) \) si ha che \(\displaystyle x_1\in (-\infty, 0) \) e quindi la successione converge anche per questi valori. Se prendi \(\displaystyle x_0 > \frac{7}{2} \) allora \(\displaystyle x_1 = \frac{3}{x_0 - 2} < \frac{3}{7/2 - 2} = \frac{6}{7 - 4} = 2 \). Ma allora \(\displaystyle x_1 \in (-\infty, 2) \) e quindi la successione converge.
A questo punto usando la trasformazione inversa: \(\displaystyle x = \frac{3}{y} + 2 \) vedo che \(\displaystyle 3\cdot \frac{2}{7} + 2 = \frac{6 + 14}{7} = \frac{20}{7} = \vartheta_1 \approx 2,86 \). Quindi per \(\displaystyle (2,\vartheta_1) \) si ha convergenza perché l'immagine \(\displaystyle x_1 \) di ogni \(\displaystyle x_0 \) in questo intervallo è maggiore di \(\displaystyle\frac{7}{2} \).
Ora \(\displaystyle 3\cdot \frac{7}{20} + 2 = \frac{21 + 40}{20} = \frac{61}{20} = \vartheta_2 = 3.05 \) e \(\displaystyle x_0\in (\vartheta_2,\infty) \) converge. Si ha successivamente \(\displaystyle 3\cdot \frac{20}{61} + 2 = \frac{60 + 122}{61} = \frac{182}{61} = \vartheta_3 \approx 2.98 \), \(\displaystyle 3\cdot \frac{61}{182} + 2 = \frac{183 + 364}{182} = \frac{547}{182} = \vartheta_4 \) e così via.
È evidente che tutti questi passaggi sono un po' eccessivi, il punto è che \(\displaystyle \vartheta_i \to \vartheta \) e che la convergenza c'è per ogni \(\displaystyle x \) diverso da \(\displaystyle 2 \) e \(\displaystyle \vartheta \). A quel punto basterà dimostrare che \(\displaystyle \vartheta \) è un punto fisso per la funzione.
È evidente che \(\displaystyle \vartheta \) è uguale a \(\displaystyle 3 \) perché \(\displaystyle 3 \) è un punto fisso della funzione considerata. Inoltre essendo questa funzione l'inversa di quella di partenza un punto fisso della prima è anche punto fisso della seconda e quindi c'è solo da dimostrare la convergenza.
A occhio però non è facile perché le derivate nell'intorno di \(\displaystyle 3 \) non aiutano e non posso dire di essere praticissimo con questi calcoli. Ci devo pensare insomma. Se ti viene qualche idea dillo.
In sostanza comunque se \(\displaystyle x_0 \) è minore di \(\displaystyle 2 \) allora la successione tende a \(\displaystyle -1 \) rimanendo nella semiretta negativa per ogni elemento successivo a \(\displaystyle x_1 \) (compreso). Se è maggiore di \(\displaystyle 2 \) e diverso da \(\displaystyle 3 \) allora si allontana da \(\displaystyle 3 \) in modo alternato finché non finisce sotto \(\displaystyle 2 \) e a quel punto segue il suo percorso verso \(\displaystyle -1 \). Se \(\displaystyle x_0 = 3 \) allora ci rimane indefinitivamente. È da notare che questa successione non è adatta a trovare lo zero in \(\displaystyle 3 \).
La teoria in questione si basa sulla teoria delle contrazioni e quindi lo spazio che tu consideri deve essere una contrazione da sé stesso in sé stesso. Il problema del mandare lo spazio in sé non è un problema da poco perché se la funzione manda \(\displaystyle (-\infty, 0) \) in se stessa, le cose sono più complicate per i numeri positivi. Siccome hai mostrato che la derivata ha valore assoluto minore di 1 in \(\displaystyle (-\infty, 0) \) allora la funzione è una contrazione di quell'insieme e possiede un punto fisso (insomma la successione converge).
Per il commento che ho fatto prima per ogni \(\displaystyle x_0 \in [0,2) \) si ha che \(\displaystyle x_1\in (-\infty, 0) \) e quindi la successione converge anche per questi valori. Se prendi \(\displaystyle x_0 > \frac{7}{2} \) allora \(\displaystyle x_1 = \frac{3}{x_0 - 2} < \frac{3}{7/2 - 2} = \frac{6}{7 - 4} = 2 \). Ma allora \(\displaystyle x_1 \in (-\infty, 2) \) e quindi la successione converge.
A questo punto usando la trasformazione inversa: \(\displaystyle x = \frac{3}{y} + 2 \) vedo che \(\displaystyle 3\cdot \frac{2}{7} + 2 = \frac{6 + 14}{7} = \frac{20}{7} = \vartheta_1 \approx 2,86 \). Quindi per \(\displaystyle (2,\vartheta_1) \) si ha convergenza perché l'immagine \(\displaystyle x_1 \) di ogni \(\displaystyle x_0 \) in questo intervallo è maggiore di \(\displaystyle\frac{7}{2} \).
Ora \(\displaystyle 3\cdot \frac{7}{20} + 2 = \frac{21 + 40}{20} = \frac{61}{20} = \vartheta_2 = 3.05 \) e \(\displaystyle x_0\in (\vartheta_2,\infty) \) converge. Si ha successivamente \(\displaystyle 3\cdot \frac{20}{61} + 2 = \frac{60 + 122}{61} = \frac{182}{61} = \vartheta_3 \approx 2.98 \), \(\displaystyle 3\cdot \frac{61}{182} + 2 = \frac{183 + 364}{182} = \frac{547}{182} = \vartheta_4 \) e così via.
È evidente che tutti questi passaggi sono un po' eccessivi, il punto è che \(\displaystyle \vartheta_i \to \vartheta \) e che la convergenza c'è per ogni \(\displaystyle x \) diverso da \(\displaystyle 2 \) e \(\displaystyle \vartheta \). A quel punto basterà dimostrare che \(\displaystyle \vartheta \) è un punto fisso per la funzione.
È evidente che \(\displaystyle \vartheta \) è uguale a \(\displaystyle 3 \) perché \(\displaystyle 3 \) è un punto fisso della funzione considerata. Inoltre essendo questa funzione l'inversa di quella di partenza un punto fisso della prima è anche punto fisso della seconda e quindi c'è solo da dimostrare la convergenza.
A occhio però non è facile perché le derivate nell'intorno di \(\displaystyle 3 \) non aiutano e non posso dire di essere praticissimo con questi calcoli. Ci devo pensare insomma. Se ti viene qualche idea dillo.
In sostanza comunque se \(\displaystyle x_0 \) è minore di \(\displaystyle 2 \) allora la successione tende a \(\displaystyle -1 \) rimanendo nella semiretta negativa per ogni elemento successivo a \(\displaystyle x_1 \) (compreso). Se è maggiore di \(\displaystyle 2 \) e diverso da \(\displaystyle 3 \) allora si allontana da \(\displaystyle 3 \) in modo alternato finché non finisce sotto \(\displaystyle 2 \) e a quel punto segue il suo percorso verso \(\displaystyle -1 \). Se \(\displaystyle x_0 = 3 \) allora ci rimane indefinitivamente. È da notare che questa successione non è adatta a trovare lo zero in \(\displaystyle 3 \).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo