Osservazioni introduttive

(Pywikibot v.2)
 
Riga 1: Riga 1:
 
==Problema da risolvere==
 
==Problema da risolvere==
 
Data una funzione <math>f \colon [a,b] \to \mathbb R</math>, si cerca <math>\alpha</math> tale che <math>f(\alpha)=0</math>.
 
Data una funzione <math>f \colon [a,b] \to \mathbb R</math>, si cerca <math>\alpha</math> tale che <math>f(\alpha)=0</math>.
Si utilizzano metodi iterativi, cioè si cercano <math>x_k</math> tali che
+
Si utilizzano metodi iterativi, cioè si cercano <math>x_k</math> tali che<math display="block">\lim_{k \to \infty} x_k = \alpha</math>La convergenza del metodo non dipende solo dal metodo usato, ma anche dalla scelta del vettore d'innesco: infatti se il vettore d'innesco appartiene a un determinato intorno della radice, il metodo converge, altrimenti questa condizione non è verificata.
<math display="block">\lim_{k \to \infty} x_k = \alpha</math>
 
La convergenza del metodo non dipende solo dal metodo usato, ma anche dalla scelta del vettore d'innesco: infatti se il vettore d'innesco appartiene a un determinato intorno della radice, il metodo converge, altrimenti questa condizione non è verificata.
 
 
 
 
 
  
 
I metodi usati possono avere una convergenza lineare, del tipo <math>E_k \le c*E_{k-1}</math> in cui sono necessarie varie iterazioni prima che l'ordine di grandezza dell'errore diminuisca.
 
I metodi usati possono avere una convergenza lineare, del tipo <math>E_k \le c*E_{k-1}</math> in cui sono necessarie varie iterazioni prima che l'ordine di grandezza dell'errore diminuisca.
 
 
 
Altrimenti può verificarsi una convergenza superlineare: consideriamo un esempio di convergenza quadratica, in cui a un certo passo <math>E_k= 10^{-2}</math>, al successivo <math>E_{k+1}=10^{-4}</math> e al successivo <math>E_{k+2}=10^{-8}</math>, cioè l'errore crolla velocemente.
 
Altrimenti può verificarsi una convergenza superlineare: consideriamo un esempio di convergenza quadratica, in cui a un certo passo <math>E_k= 10^{-2}</math>, al successivo <math>E_{k+1}=10^{-4}</math> e al successivo <math>E_{k+2}=10^{-8}</math>, cioè l'errore crolla velocemente.
  
 
==Ordine di convergenza==
 
==Ordine di convergenza==
 
{{InizioDefinizione|titolo=|number=4.1|anchor=Definizione4_1}}
 
{{InizioDefinizione|titolo=|number=4.1|anchor=Definizione4_1}}
Considero una successione <math>x_k \to \alpha</math>, con <math>x_k \neq \alpha \forall k</math>. Dico che la successione ha ''ordine di convergenza''<math>P</math> se esiste un <math>P \ge 1</math>  tale che
+
Considero una successione <math>x_k \to \alpha</math>, con <math>x_k \neq \alpha \forall k</math>. Dico che la successione ha ''ordine di convergenza''<math>P</math> se esiste un <math>P \ge 1</math>  tale che<math display="block">\lim_{k \to \infty} \frac{|x_{k+1}-\alpha|}{(|x_k-\alpha|)^P} = \gamma</math>dove <math>0<\gamma <1</math> se <math>P=1</math>, mentre <math>\gamma >1</math> se <math>P>1</math>.
<math display="block">\lim_{k \to \infty} \frac{|x_{k+1}-\alpha|}{(|x_k-\alpha|)^P} = \gamma</math>
 
dove <math>0<\gamma <1</math> se <math>P=1</math>, mentre <math>\gamma >1</math> se <math>P>1</math>.
 
 
<math>\gamma</math> si dice ''fattore di convergenza''.
 
<math>\gamma</math> si dice ''fattore di convergenza''.
 
{{FineDefinizione}}
 
{{FineDefinizione}}
 
 
  
 
#Se <math>P=1</math> e <math>\gamma <1</math> ho una convergenza ''lineare'';
 
#Se <math>P=1</math> e <math>\gamma <1</math> ho una convergenza ''lineare'';
Riga 26: Riga 16:
 
#se <math>P>1</math> e <math>\gamma>0</math> ho una convergenza ''superlineare''.
 
#se <math>P>1</math> e <math>\gamma>0</math> ho una convergenza ''superlineare''.
  
 
+
In ogni caso, esiste una costante <math>c>0</math> tale che<math display="block">|x_{k+1}-\alpha| \le c|x_k-\alpha|^P</math>Per <math>k</math> abbastanza grande, cioè, in termini dell'errore assoluto:<math display="block">E_{k+1} \le c E_k^P</math>e in termini di errore relativo:<math display="block">E_{r,k+1} = \frac{|x_{k+1}-\alpha|}{\alpha} \le c \frac{|x_k-\alpha|^P}{\alpha}</math><math display="block">\le c |\alpha^{P-1}| (\frac{|x_k-\alpha|}{\alpha})^P  \le c \alpha^{P-1} E_{r,k}^P</math>Se <math>P=1</math>, più è piccola la costante <math>\gamma</math> più il metodo converge rapidamente.
 
 
 
 
In ogni caso, esiste una costante <math>c>0</math> tale che
 
<math display="block">|x_{k+1}-\alpha| \le c|x_k-\alpha|^P</math>
 
Per <math>k</math> abbastanza grande, cioè, in termini dell'errore assoluto:
 
<math display="block">E_{k+1} \le c E_k^P</math>
 
e in termini di errore relativo:
 
<math display="block">E_{r,k+1} = \frac{|x_{k+1}-\alpha|}{\alpha} \le c \frac{|x_k-\alpha|^P}{\alpha}</math><math display="block">\le c |\alpha^{P-1}| (\frac{|x_k-\alpha|}{\alpha})^P  \le c \alpha^{P-1} E_{r,k}^P</math>
 
Se <math>P=1</math>, più è piccola la costante <math>\gamma</math> più il metodo converge rapidamente.
 
 
 
 
 
  
 
Supponiamo di avere <math>P=2</math>. Allora se <math>E_k = 10^{-2}</math>, al passo successivo si ha <math>E_{k+1} = (10^{-2})^2 = 10^{-4}</math>, e <math>E_{k+2} = (10^{-4})^2 = 10^{-8}</math>. Se invece <math>P=1</math>,  <math>E_{k+1} = c*10^{-2}</math>, dove <math>0<c<1</math> e ci vogliono più iterazioni prima che cambi l'ordine dell'errore.
 
Supponiamo di avere <math>P=2</math>. Allora se <math>E_k = 10^{-2}</math>, al passo successivo si ha <math>E_{k+1} = (10^{-2})^2 = 10^{-4}</math>, e <math>E_{k+2} = (10^{-4})^2 = 10^{-8}</math>. Se invece <math>P=1</math>,  <math>E_{k+1} = c*10^{-2}</math>, dove <math>0<c<1</math> e ci vogliono più iterazioni prima che cambi l'ordine dell'errore.
Riga 43: Riga 22:
 
==Esempi sui tipi di convergenza==
 
==Esempi sui tipi di convergenza==
 
{{InizioEsempio|titolo= convergenza lineare|number=4.1|anchor=Esempio4_1}}
 
{{InizioEsempio|titolo= convergenza lineare|number=4.1|anchor=Esempio4_1}}
Consideriamo la successione
+
Consideriamo la successione<math display="block">x_{k+1} = \cos x_k</math>con <math>P=1</math>. Allora <math>\gamma = \sin \alpha</math>.
<math display="block">x_{k+1} = \cos x_k</math>
 
con <math>P=1</math>. Allora <math>\gamma = \sin \alpha</math>.
 
 
{{FineEsempio}}
 
{{FineEsempio}}
  
Riga 51: Riga 28:
  
 
{{InizioEsempio|titolo= convergenza sublineare|number=4.2|anchor=Esempio4_2}}
 
{{InizioEsempio|titolo= convergenza sublineare|number=4.2|anchor=Esempio4_2}}
In questo tipo di convergenza la velocità di converenza diminuisce quando ci si avvicina ad <math>\alpha</math>. Considero la successione:
+
In questo tipo di convergenza la velocità di converenza diminuisce quando ci si avvicina ad <math>\alpha</math>. Considero la successione:<math display="block">x_{k+1} = \sin x_k</math><math display="block">\gamma = 1</math>
<math display="block">x_{k+1} = \sin x_k</math><math display="block">\gamma = 1</math>
 
 
{{FineEsempio}}
 
{{FineEsempio}}
  
Riga 58: Riga 34:
  
 
{{InizioEsempio|titolo= convergenza superlineare|number=4.3|anchor=Esempio4_3}}
 
{{InizioEsempio|titolo= convergenza superlineare|number=4.3|anchor=Esempio4_3}}
Considero la successione:
+
Considero la successione:<math display="block">5x_k^3+x_k^4, \, P=3, \, x \in (0,1/3)</math>allora<math display="block">\gamma = \lim_{k \to \infty} \frac{|x_{k+1}-\alpha|}{|x_k-\alpha|^P}=</math><math display="block">\gamma = \lim_{k \to \infty} \frac{|5x_k^3+x_k^4-\alpha|}{|x_k-\alpha|^3}=</math><math display="block">\gamma = 5</math>
<math display="block">5x_k^3+x_k^4, \, P=3, \, x \in (0,1/3)</math>
 
allora
 
<math display="block">\gamma = \lim_{k \to \infty} \frac{|x_{k+1}-\alpha|}{|x_k-\alpha|^P}=</math><math display="block">\gamma = \lim_{k \to \infty} \frac{|5x_k^3+x_k^4-\alpha|}{|x_k-\alpha|^3}=</math><math display="block">\gamma = 5</math>
 
 
{{FineEsempio}}
 
{{FineEsempio}}

Versione delle 14:28, 20 set 2017

Problema da risolvere

Data una funzione , si cerca tale che . Si utilizzano metodi iterativi, cioè si cercano tali che

La convergenza del metodo non dipende solo dal metodo usato, ma anche dalla scelta del vettore d'innesco: infatti se il vettore d'innesco appartiene a un determinato intorno della radice, il metodo converge, altrimenti questa condizione non è verificata.

I metodi usati possono avere una convergenza lineare, del tipo in cui sono necessarie varie iterazioni prima che l'ordine di grandezza dell'errore diminuisca. Altrimenti può verificarsi una convergenza superlineare: consideriamo un esempio di convergenza quadratica, in cui a un certo passo , al successivo e al successivo , cioè l'errore crolla velocemente.

Ordine di convergenza

Definizione 4.1

Considero una successione , con . Dico che la successione ha ordine di convergenza se esiste un tale che

dove se , mentre se . si dice fattore di convergenza.

 
  1. Se e ho una convergenza lineare;
  2. se e ho una convergenza sublineare;
  3. se e ho una convergenza superlineare.

In ogni caso, esiste una costante tale che

Per abbastanza grande, cioè, in termini dell'errore assoluto:
e in termini di errore relativo:
Se , più è piccola la costante più il metodo converge rapidamente.

Supponiamo di avere . Allora se , al passo successivo si ha , e . Se invece , , dove e ci vogliono più iterazioni prima che cambi l'ordine dell'errore.

Esempi sui tipi di convergenza

Esempio 4.1

Consideriamo la successione

con . Allora .

 


Esempio 4.2

In questo tipo di convergenza la velocità di converenza diminuisce quando ci si avvicina ad . Considero la successione:

 


Esempio 4.3

Considero la successione:

allora

 
Successivo