Bisezione corde secanti Newton

(Pywikibot v.2)
 
m (Pywikibot v.2)
 
(Una versione intermedia di un altro utente non mostrate)
Riga 2: Riga 2:
  
 
==Metodo di bisezione==
 
==Metodo di bisezione==
{{InizioTeorema|titolo= teorema degli zeri per funzioni continue|number=4.1|anchor=Teorema4_1}}
+
{{InizioTeorema|title=teorema degli zeri per funzioni continue|number=4.1|anchor=Teorema4_1}}
 
Data una funzione <math>f \colon [a,b] \to \mathbb R</math> con <math>f \in C^0(a,b)</math> se <math>f(a)*f(b)<0</math>, allora esiste <math>\alpha \in (a,b)</math> tale che <math>f(\alpha)=0</math>.
 
Data una funzione <math>f \colon [a,b] \to \mathbb R</math> con <math>f \in C^0(a,b)</math> se <math>f(a)*f(b)<0</math>, allora esiste <math>\alpha \in (a,b)</math> tale che <math>f(\alpha)=0</math>.
 
{{FineTeorema}}
 
{{FineTeorema}}
Riga 8: Riga 8:
  
  
{{InizioDefinizione|titolo=|number=4.2|anchor=Definizione4_2}}
+
{{InizioDefinizione|title=|number=4.2|anchor=Definizione4_2}}
 
Diciamo che <math>a,b</math> costituiscono una ''bracket'', cioè un intervallo contenente la radice, se <math>f(a)*f(b) <0</math>.
 
Diciamo che <math>a,b</math> costituiscono una ''bracket'', cioè un intervallo contenente la radice, se <math>f(a)*f(b) <0</math>.
 
{{FineDefinizione}}
 
{{FineDefinizione}}
 
 
 
  
 
''Idea del metodo di bisezione'': ho una bracket di partenza <math>(a,b)</math>, tale che <math>f(a)*f(b)<0</math>, e cerco una bracket più piccola, e così via.
 
''Idea del metodo di bisezione'': ho una bracket di partenza <math>(a,b)</math>, tale che <math>f(a)*f(b)<0</math>, e cerco una bracket più piccola, e così via.
 
 
  
 
I passi del metodo sono i seguenti: calcolo <math>c=(a+b)/2</math> punto medio di <math>(a,b)</math> (sul calcolatore per questioni di stabilità il punto medio si calcola come <math>c=a+(b-a)/2)</math>). Trovato <math>c</math>, si possono verificare tre casi:
 
I passi del metodo sono i seguenti: calcolo <math>c=(a+b)/2</math> punto medio di <math>(a,b)</math> (sul calcolatore per questioni di stabilità il punto medio si calcola come <math>c=a+(b-a)/2)</math>). Trovato <math>c</math>, si possono verificare tre casi:
Riga 24: Riga 19:
 
#Se invece <math>f(c)*f(b)<0</math>, allora la bracket è <math>(b,c)</math>.
 
#Se invece <math>f(c)*f(b)<0</math>, allora la bracket è <math>(b,c)</math>.
 
#Nel caso <math>f(c)=0</math>, <math>c</math> è la radice cercata.
 
#Nel caso <math>f(c)=0</math>, <math>c</math> è la radice cercata.
 
  
 
A partire da una bracket <math>T_0</math>, genero una sottosuccessione di intervalli <math>I_k</math> di estremi <math>(a_k,b_k)</math> con <math>k \ge 0</math> con la proprietà che
 
A partire da una bracket <math>T_0</math>, genero una sottosuccessione di intervalli <math>I_k</math> di estremi <math>(a_k,b_k)</math> con <math>k \ge 0</math> con la proprietà che
Riga 30: Riga 24:
 
Viene contemporaneamente generata una successione di valori <math>C_k</math> punti medi degli intervallini <math>I_k</math>, che converge alla radice.
 
Viene contemporaneamente generata una successione di valori <math>C_k</math> punti medi degli intervallini <math>I_k</math>, che converge alla radice.
  
 
+
Ad ogni iterazione, la distanza tra il punto medio <math>C_k</math> e <math>\alpha</math> è minore di metà dell'ampiezza della bracket. Sia <math>L_0=|b-a|</math>  l'ampiezza della bracket iniziale. Allora<math display="block">L_k = d(a_k,b_k) = \frac{L_0}{2^k}.</math>Di conseguenza possiamo affermare<math display="block">|C_k-\alpha| \le 1/2 L_k = \frac{L_0}{2^{k+1}}</math>Per ottenere un'approssimazione sufficientemente buona della radice si richiede che <math>\frac{L_0}{2^{k+1}} \le \varepsilon</math>.<br>
 
+
In termini di iterazioni segue che:<math display="block">2^{k+1} \ge \frac{L_0}{\varepsilon} \,  \longrightarrow \, \bar k \ge \log_2 (\frac{L_0}{\varepsilon})-1</math>dove <math>\bar k</math> è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di <math>\varepsilon</math>. Il numero di iterazioni richieste dal metodo dipende solo dall'ampiezza della bracket iniziale.
Ad ogni iterazione, la distanza tra il punto medio <math>C_k</math> e <math>\alpha</math> è minore di metà dell'ampiezza della bracket. Sia <math>L_0=|b-a|</math>  l'ampiezza della bracket iniziale. Allora
 
<math display="block">L_k = d(a_k,b_k) = \frac{L_0}{2^k}.</math>
 
Di conseguenza possiamo affermare
 
<math display="block">|C_k-\alpha| \le 1/2 L_k = \frac{L_0}{2^{k+1}}</math>
 
Per ottenere un'approssimazione sufficientemente buona della radice si richiede che <math>\frac{L_0}{2^{k+1}} \le \varepsilon</math>.
 
 
 
 
 
In termini di iterazioni segue che:
 
<math display="block">2^{k+1} \ge \frac{L_0}{\varepsilon} \,  \longrightarrow \, \bar k \ge \log_2 (\frac{L_0}{\varepsilon})-1</math>
 
dove <math>\bar k</math> è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di <math>\varepsilon</math>. Il numero di iterazioni richieste dal metodo dipende solo dall'ampiezza della bracket iniziale.
 
 
 
 
 
  
 
La convergenza del metodo di bisezione è lenta, "lineare", e il metodo converge sempre. Questo metodo viene usato in mancanza di informazioni preliminari su dove si trova la radice, però non è applicabile a sistemi di equazioni non lineari.
 
La convergenza del metodo di bisezione è lenta, "lineare", e il metodo converge sempre. Questo metodo viene usato in mancanza di informazioni preliminari su dove si trova la radice, però non è applicabile a sistemi di equazioni non lineari.
Riga 49: Riga 31:
  
 
==Struttura generale degli altri metodi==
 
==Struttura generale degli altri metodi==
Considero la funzione <math>f</math> e lo sviluppo di Taylor centrato in <math>\alpha</math>.
+
Considero la funzione <math>f</math> e lo sviluppo di Taylor centrato in <math>\alpha</math>.<math display="block">f(x) = f(\alpha)+(x-\alpha)*f'(\xi), \, \xi \in (\alpha,x)</math>che si riscrive come:<math display="block">0 = f(\alpha) =f(x)-(\alpha-x)*f'(\xi)</math>Definisco il metodo iterativo nel seguente modo: assegnato <math>x_0</math>, per ogni <math>k \ge 0</math> determino la nuova iterata <math>x_{k+1}</math> risolvendo l'equazione <math>\circ</math>:<math display="block">\, f(x_k)+(x_{k+1}-x_k)*m_k =0</math>dove <math>m_k</math> è un'opportuna approssimazione di <math>f'(x_k)</math>.<br>
<math display="block">f(x) = f(\alpha)+(x-\alpha)*f'(\xi), \, \xi \in (\alpha,x)</math>
 
che si riscrive come:
 
<math display="block">0 = f(\alpha) =f(x)-(\alpha-x)*f'(\xi)</math>
 
Definisco il metodo iterativo nel seguente modo: assegnato <math>x_0</math>, per ogni <math>k \ge 0</math> determino la nuova iterata <math>x_{k+1}</math> risolvendo l'equazione <math>\circ</math>:
 
<math display="block">\, f(x_k)+(x_{k+1}-x_k)*m_k =0</math>
 
dove <math>m_k</math> è un'opportuna approssimazione di <math>f'(x_k)</math>.
 
 
 
 
 
 
Trovare la soluzione di <math>\circ</math> equivale a trovare l'intersezione tra l'asse x e la retta <math>y=m_k*(x-x_k)+f(x_k)</math>.
 
Trovare la soluzione di <math>\circ</math> equivale a trovare l'intersezione tra l'asse x e la retta <math>y=m_k*(x-x_k)+f(x_k)</math>.
 
  
 
Esplicitando <math>x_{k+1}</math>, la relazione <math>\circ</math> diventa
 
Esplicitando <math>x_{k+1}</math>, la relazione <math>\circ</math> diventa
<math display="block">x_{k+1} = x_k-m_k^{-1} f(x_k), \quad k \ge 0</math>
+
<math display="block">x_{k+1} = x_k-m_k^{-1} f(x_k), \quad k \ge 0</math>A seconda dell'approssimazione di <math>f'(x_k)</math> e quindi della scelta di <math>m_k</math> si ottengono i metodi delle corde, secanti e di Newton.
  
A seconda dell'approssimazione di <math>f'(x_k)</math> e quindi della scelta di <math>m_k</math> si ottengono i metodi delle corde, secanti e di Newton.
+
==Metodo delle corde==
 +
;Scelta del coefficiente:Per ogni <math>k \ge 0</math>, scelgo il coefficiente <math>m_k=m</math> ponendo<math display="block">m=\frac{f(b)-f(a)}{b-a},</math>quindi la relazione <math>\circ</math> diventa:<math display="block">x_{k+1} = x_k-\frac{b-a}{f(b)-f(a)}*f(x_k), \quad k \ge 0</math>
  
==Metodo delle corde==
 
;Scelta del coefficiente:Per ogni <math>k \ge 0</math>, scelgo il coefficiente <math>m_k=m</math> ponendo
 
<math display="block">m=\frac{f(b)-f(a)}{b-a},</math>
 
quindi la relazione <math>\circ</math> diventa:
 
<math display="block">x_{k+1} = x_k-\frac{b-a}{f(b)-f(a)}*f(x_k), \quad k \ge 0</math>
 
 
;Caratteristiche:a differenza del metodo di bisezione, qui ad ogni iterata si usa il vettore ottenuto all'iterata precedente.
 
;Caratteristiche:a differenza del metodo di bisezione, qui ad ogni iterata si usa il vettore ottenuto all'iterata precedente.
  
Riga 78: Riga 47:
 
L'iterata <math>x_1</math> è l'intersezione di questa retta con l'asse delle ascisse.
 
L'iterata <math>x_1</math> è l'intersezione di questa retta con l'asse delle ascisse.
 
Considero poi la retta per <math>(x_1,f(x_1))</math> parallela a quelle disegnate sopra, e l'intersezione con l'asse x è l'iterata <math>x_2</math>.
 
Considero poi la retta per <math>(x_1,f(x_1))</math> parallela a quelle disegnate sopra, e l'intersezione con l'asse x è l'iterata <math>x_2</math>.
 
  
 
Si considerano quindi rette tra loro parallele e ognuna passante per il punto <math>(x_k,f(x_k))</math>.
 
Si considerano quindi rette tra loro parallele e ognuna passante per il punto <math>(x_k,f(x_k))</math>.
  
 
==Metodo delle secanti==
 
==Metodo delle secanti==
;Scelta del coefficiente:Per ogni <math>k \ge 0</math>, fisso il coefficiente <math>m_k</math> ponendo
+
;Scelta del coefficiente:Per ogni <math>k \ge 0</math>, fisso il coefficiente <math>m_k</math> ponendo<math display="block">m_k = \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}</math>quindi la relazione <math>\circ</math> diventa:<math display="block">x_{k+1} = x_k- \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}*f(x_k), \quad \forall k \ge 0</math>
<math display="block">m_k = \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}</math>
+
 
quindi la relazione <math>\circ</math> diventa:
 
<math display="block">x_{k+1} = x_k- \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}*f(x_k), \quad \forall k \ge 0</math>
 
 
;Caratteristiche:Questo non è un metodo del punto fisso, perché ad ogni passo si considerano informazioni ottenute nelle due iterate precedenti. Tranne nel primo passo, in cui <math>f</math> viene valutata nei due valori di innesco, ad ogni iterazione viene fatta una sola valutazione della funzione, e quindi, rispetto al metodo delle corde, il costo computazionale non aumenta di molto, aumenta solo nella prima iterazione.
 
;Caratteristiche:Questo non è un metodo del punto fisso, perché ad ogni passo si considerano informazioni ottenute nelle due iterate precedenti. Tranne nel primo passo, in cui <math>f</math> viene valutata nei due valori di innesco, ad ogni iterazione viene fatta una sola valutazione della funzione, e quindi, rispetto al metodo delle corde, il costo computazionale non aumenta di molto, aumenta solo nella prima iterazione.
  
Riga 92: Riga 58:
 
In particolare vale il seguente teorema:
 
In particolare vale il seguente teorema:
  
{{InizioTeorema|titolo=|number=4.2|anchor=Teorema4_2}}
+
{{InizioTeorema|title=|number=4.2|anchor=Teorema4_2}}
 
Se <math>f</math> è <math>C^2</math> in un opportuno intorno della radice, se <math>f'(\alpha) \neq 0</math> cioè se <math>\alpha</math> è una radice semplice, e se <math>x_0,x_1 \in U(\alpha)</math>, allora il metodo delle secanti converge con ordine <math>P=(1+\sqrt{5})/2=1.6</math>, cioè con una convergenza superlineare.
 
Se <math>f</math> è <math>C^2</math> in un opportuno intorno della radice, se <math>f'(\alpha) \neq 0</math> cioè se <math>\alpha</math> è una radice semplice, e se <math>x_0,x_1 \in U(\alpha)</math>, allora il metodo delle secanti converge con ordine <math>P=(1+\sqrt{5})/2=1.6</math>, cioè con una convergenza superlineare.
 
{{FineTeorema}}
 
{{FineTeorema}}
Riga 99: Riga 65:
  
 
==Metodo di Newton==
 
==Metodo di Newton==
;Scelta del coefficiente:Si richiede che <math>f</math> sia di classe <math>C^1</math> in un opportuno intorno della radice, che <math>f'(\alpha) \neq 0</math>, e per ogni <math>k</math>, fissiamo il coefficiente <math>m_k = f'(x_k)</math>. Allora
+
;Scelta del coefficiente:Si richiede che <math>f</math> sia di classe <math>C^1</math> in un opportuno intorno della radice, che <math>f'(\alpha) \neq 0</math>, e per ogni <math>k</math>, fissiamo il coefficiente <math>m_k = f'(x_k)</math>. Allora<math display="block">x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)}, \quad k \ge 0</math>
<math display="block">x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)}, \quad k \ge 0</math>
+
 
 
;Caratteristiche:Il costo computazionale viene aumentato in modo considerevole perché viene richiesta anche la valutazione della funzione e della sua derivata prima in <math>x_k</math>.
 
;Caratteristiche:Il costo computazionale viene aumentato in modo considerevole perché viene richiesta anche la valutazione della funzione e della sua derivata prima in <math>x_k</math>.
  

Versione attuale delle 15:14, 21 mag 2018

Data una funzione , trovare tale che .

Metodo di bisezione[modifica | modifica wikitesto]

Teorema 4.1 (teorema degli zeri per funzioni continue)

Data una funzione con se , allora esiste tale che .

 


Definizione 4.2

Diciamo che costituiscono una bracket, cioè un intervallo contenente la radice, se .

 

Idea del metodo di bisezione: ho una bracket di partenza , tale che , e cerco una bracket più piccola, e così via.

I passi del metodo sono i seguenti: calcolo punto medio di (sul calcolatore per questioni di stabilità il punto medio si calcola come ). Trovato , si possono verificare tre casi:

  1. se allora la nuova bracket è l'intervallo .
  2. Se invece , allora la bracket è .
  3. Nel caso , è la radice cercata.

A partire da una bracket , genero una sottosuccessione di intervalli di estremi con con la proprietà che , e tali che per ogni k, . Viene contemporaneamente generata una successione di valori punti medi degli intervallini , che converge alla radice.

Ad ogni iterazione, la distanza tra il punto medio e è minore di metà dell'ampiezza della bracket. Sia l'ampiezza della bracket iniziale. Allora

Di conseguenza possiamo affermare
Per ottenere un'approssimazione sufficientemente buona della radice si richiede che .
In termini di iterazioni segue che:
dove è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di . Il numero di iterazioni richieste dal metodo dipende solo dall'ampiezza della bracket iniziale.

La convergenza del metodo di bisezione è lenta, "lineare", e il metodo converge sempre. Questo metodo viene usato in mancanza di informazioni preliminari su dove si trova la radice, però non è applicabile a sistemi di equazioni non lineari. Per guadagnare una cifra decimale occorrono iterazioni.

Struttura generale degli altri metodi[modifica | modifica wikitesto]

Considero la funzione e lo sviluppo di Taylor centrato in .

che si riscrive come:
Definisco il metodo iterativo nel seguente modo: assegnato , per ogni determino la nuova iterata risolvendo l'equazione :
dove è un'opportuna approssimazione di .
Trovare la soluzione di equivale a trovare l'intersezione tra l'asse x e la retta .

Esplicitando , la relazione diventa

A seconda dell'approssimazione di e quindi della scelta di si ottengono i metodi delle corde, secanti e di Newton.

Metodo delle corde[modifica | modifica wikitesto]

Scelta del coefficiente
Per ogni , scelgo il coefficiente ponendo
quindi la relazione diventa:
Caratteristiche
a differenza del metodo di bisezione, qui ad ogni iterata si usa il vettore ottenuto all'iterata precedente.
Ordine di convergenza
Questo metodo ha un ordine di convergenza di , quindi la convergenza è lineare.
Interpretazione gemetrica
Supponiamo di avere una funzione su un intervallo , considero un punto , considero la retta per con coefficiente angolare definito come sopra.

L'iterata è l'intersezione di questa retta con l'asse delle ascisse. Considero poi la retta per parallela a quelle disegnate sopra, e l'intersezione con l'asse x è l'iterata .

Si considerano quindi rette tra loro parallele e ognuna passante per il punto .

Metodo delle secanti[modifica | modifica wikitesto]

Scelta del coefficiente
Per ogni , fisso il coefficiente ponendo
quindi la relazione diventa:
Caratteristiche
Questo non è un metodo del punto fisso, perché ad ogni passo si considerano informazioni ottenute nelle due iterate precedenti. Tranne nel primo passo, in cui viene valutata nei due valori di innesco, ad ogni iterazione viene fatta una sola valutazione della funzione, e quindi, rispetto al metodo delle corde, il costo computazionale non aumenta di molto, aumenta solo nella prima iterazione.
Ordine di convergenza
Questo metodo è superlineare, perché .

In particolare vale il seguente teorema:

Teorema 4.2

Se è in un opportuno intorno della radice, se cioè se è una radice semplice, e se , allora il metodo delle secanti converge con ordine , cioè con una convergenza superlineare.

 
Interpretazione geometrica
A differenza del grafico precedente qui le rette non sono parallele. Dopo aver tracciato la retta per e , l'iterata successiva è l'intersezione di questa retta con l'asse x.

Metodo di Newton[modifica | modifica wikitesto]

Scelta del coefficiente
Si richiede che sia di classe in un opportuno intorno della radice, che , e per ogni , fissiamo il coefficiente . Allora
Caratteristiche
Il costo computazionale viene aumentato in modo considerevole perché viene richiesta anche la valutazione della funzione e della sua derivata prima in .
Ordine di convergenza
Sotto opportune ipotesi di regolarità, il metodo permette di avere ordine di convergenza 2.
Interpretazione geometrica
Graficamente viene considerata la retta tangente alla funzione nel punto , e si considera la sua intersezione con l'asse x che è l'iterata successiva.
 PrecedenteSuccessivo