Ordine di convergenza metodo di Eulero in avanti
Ciao, devo andare a stabilire se il metodo di Eulero in avanti è convergente e con quale ordine.
E' tutto sbagliato... però non mi sembra corretto cancellarlo. Vedere commenti successivi
E' tutto sbagliato... però non mi sembra corretto cancellarlo. Vedere commenti successivi
Risposte
E' una dimostrazione che si trova in un qualsiasi libro di analisi numerica di ODE.
Consideriamo quello che viene chiamato errore locale di troncamento , ossia la distanza tra la soluzione analitica al tempo $t_{n+1}$ e la soluzione che si otterrebbe applicando il metodo numerico alla soluzione analitica andando da $t_n$ a $t_{n+1}$.
Nel caso di Eulero "in avanti", vale $|y(t_{n+1}) - y(t_n) - k f(t_n,y(t_n))|=|y(t_n) + k*y'(t_n)+ ck^2 - y(t_n)-k y'(t_n)|= \mathcal{O}(k^2)$, dove ho sviluppato con Taylor e usato il fatto che $f(t_n,y(t_n)=y'(t_n)$. Quindi, vale che ad ogni passo si commette un errore proporzionale a $k^2$, e, poichè i passi sono $N=\frac{t_f-t_0}{k}$, allora si commette un errore massimo di ordine $\frac{t_f-t_0}{k} \mathcal{O}(k^2)=\mathcal{O}(k)$.
A dire il vero, però, la dimostrazione che Eulero è convergente, NON è questa. Per dimostrarlo bisogna considerare l'errore globale, ma a quanto vedo non è questo quello che vi è richiesto.
Consideriamo quello che viene chiamato errore locale di troncamento , ossia la distanza tra la soluzione analitica al tempo $t_{n+1}$ e la soluzione che si otterrebbe applicando il metodo numerico alla soluzione analitica andando da $t_n$ a $t_{n+1}$.
Nel caso di Eulero "in avanti", vale $|y(t_{n+1}) - y(t_n) - k f(t_n,y(t_n))|=|y(t_n) + k*y'(t_n)+ ck^2 - y(t_n)-k y'(t_n)|= \mathcal{O}(k^2)$, dove ho sviluppato con Taylor e usato il fatto che $f(t_n,y(t_n)=y'(t_n)$. Quindi, vale che ad ogni passo si commette un errore proporzionale a $k^2$, e, poichè i passi sono $N=\frac{t_f-t_0}{k}$, allora si commette un errore massimo di ordine $\frac{t_f-t_0}{k} \mathcal{O}(k^2)=\mathcal{O}(k)$.
A dire il vero, però, la dimostrazione che Eulero è convergente, NON è questa. Per dimostrarlo bisogna considerare l'errore globale, ma a quanto vedo non è questo quello che vi è richiesto.
Sono un mongoloide... Eì che sto leggendo da degli appunti presi da non so chi perché non ho seguito il corso e ci stanno degli orrori che mi fanno confondere...
La dimostrazione che ho fatto dovrebbe essere giusta, ma stavo dimostrando la consistenza (ovvero la stessa cosa che hai fatto tu). Soltanto che mi ero dimenticato di dividere per $\Delta t$...
La convergenza la dimostro poi dimostrando la zero-stabilità e aggiungendola alla consistenza... giusto ?
Un ultima domanda: ma l'ordine di convergenza quindi lo stimo dalla consistenza, giusto ?
La dimostrazione che ho fatto dovrebbe essere giusta, ma stavo dimostrando la consistenza (ovvero la stessa cosa che hai fatto tu). Soltanto che mi ero dimenticato di dividere per $\Delta t$...
La convergenza la dimostro poi dimostrando la zero-stabilità e aggiungendola alla consistenza... giusto ?
Un ultima domanda: ma l'ordine di convergenza quindi lo stimo dalla consistenza, giusto ?
Non ti preoccupare.
Comunque, l'ordine di convergenza si dimostra essere 1. Non mi pare ci siano tanti giri diversi.
Vedi sezione 2.1. Poi dipende da cosa abbia voluto fare il tuo prof, da che corso di laurea fai, ecc.
Comunque, l'ordine di convergenza si dimostra essere 1. Non mi pare ci siano tanti giri diversi.
Vedi sezione 2.1. Poi dipende da cosa abbia voluto fare il tuo prof, da che corso di laurea fai, ecc.
Grazie mille, scusa per la tarda risposta. Credo di aver fatto parecchia confusione oggi, ma penso di aver risolto...
Già che ci sono posso farti una domanda: un algoritmo "a un passo" lo posso sempre scrivere come $u^{n+1} = \Phi(u^n)$ dove $\Phi$ è un qualche operatore lineare (matrice di iterazione, tanto sono in dimensione finita quindi un operatore lineare lo posso sempre scrivere come una matrice). Allora si dice che l'algoritmo è stabile se
$$||\Phi|| < K \text{ con} \space K > 0 $$
e in più dico che è zero-stabile se vale:
$$||\Phi|| < 1 $$
?
Già che ci sono posso farti una domanda: un algoritmo "a un passo" lo posso sempre scrivere come $u^{n+1} = \Phi(u^n)$ dove $\Phi$ è un qualche operatore lineare (matrice di iterazione, tanto sono in dimensione finita quindi un operatore lineare lo posso sempre scrivere come una matrice). Allora si dice che l'algoritmo è stabile se
$$||\Phi|| < K \text{ con} \space K > 0 $$
e in più dico che è zero-stabile se vale:
$$||\Phi|| < 1 $$
?
Scusa ma quelle sono definizioni, non hai nessun testo di riferimento? Ad ogni modo, quello che dicevi oggi è vero: consistenza + zero stabilità implica convergenza.
Per quanto riguarda l'ultima cosa, sappi che normalmente la zero stabilità è caratterizzata come segue: si può controllare per metodi multistep (e quindi ad un passo), tramite la condizione delle radici, che avrai sicuramente visto a lezione ( o chi ha preso gli appuntI). Se il polinomio associato $P(\theta)$ ha radice in modulo minori o uguali a $1$, e quelle uguali a 1 sono semplici, allora è zero stabile.
Per i dettagi su quali siano i coefficienti del polinomio prendi un qualsiasi testo, oppure ho trovato questo googlando .
Per quanto riguarda l'ultima cosa, sappi che normalmente la zero stabilità è caratterizzata come segue: si può controllare per metodi multistep (e quindi ad un passo), tramite la condizione delle radici, che avrai sicuramente visto a lezione ( o chi ha preso gli appuntI). Se il polinomio associato $P(\theta)$ ha radice in modulo minori o uguali a $1$, e quelle uguali a 1 sono semplici, allora è zero stabile.
Per i dettagi su quali siano i coefficienti del polinomio prendi un qualsiasi testo, oppure ho trovato questo googlando .
No, non ho un testo di riferimento perché il corso è un po' un calderone di roba buttata un po' a caso secondo me... comunque questo criterio delle radici non l'ho mai sentito né trovato negli appunti.
Ma vorrei chiedere una cosa: se hai detto che sono definizioni quelle che ho riportato prima (in effetti le ho preso de un libro, era per essere sicuro), allora per vedere se un metodo è stabile o zero-stabile non mi "basta" calcolare la norma della matrice di iterazione ? Nel corso sono stati affrontati esempi relativamente semplici in cui era facile calcolare la norma della suddetta matrice, quindi in questo caso non ho finito ?
Metodi generici per il calcolo della zero-stabilità non ne abbiamo visti.
Ma vorrei chiedere una cosa: se hai detto che sono definizioni quelle che ho riportato prima (in effetti le ho preso de un libro, era per essere sicuro), allora per vedere se un metodo è stabile o zero-stabile non mi "basta" calcolare la norma della matrice di iterazione ? Nel corso sono stati affrontati esempi relativamente semplici in cui era facile calcolare la norma della suddetta matrice, quindi in questo caso non ho finito ?
Metodi generici per il calcolo della zero-stabilità non ne abbiamo visti.
Scusa se ti disturbo ancora. Ho risolto andando a studiare su un libro (finalmente) che ha fatto molta chiarezza (Modellistica Numerica per Problemi Differenziali, A. Quarteroni). Mi è rimasta una sola domanda a proposito della stabilità:
in questo libro (negli esempi che ho studiato) controlla la stabilità di una PDE (o ODE, è uguale) usando il metodo che dicevo prima, ovvero "giocando" con le norme. A un certo punto dice però
dove con $||\cdot||_{\Delta , 1}$ intende:
$$||u|| = h \sum_{j=-\infty}^\infty |u_j|$$
dove $h$ è il passo di discretizzazione, ovvero una costante e quindi potrei anche ometterla (nel senso che non fa alcuna differenza).
Ora la mia domanda è: ma, data l'equivalenza delle norme in $RR^N$ l'algoritmo non dovrebbe essere stabile per TUTTE le norme? Perché ne ha specificata una ? Infatti poi dice che un algoritmo può essere stabile (e convergente) rispetto a una norma e non ad un'altra... Ma come è possibile ?
in questo libro (negli esempi che ho studiato) controlla la stabilità di una PDE (o ODE, è uguale) usando il metodo che dicevo prima, ovvero "giocando" con le norme. A un certo punto dice però
[...] (il metodo di cui stava parlando) è fortemente stabile in norma $||\cdot||_{\Delta , 1}$
dove con $||\cdot||_{\Delta , 1}$ intende:
$$||u|| = h \sum_{j=-\infty}^\infty |u_j|$$
dove $h$ è il passo di discretizzazione, ovvero una costante e quindi potrei anche ometterla (nel senso che non fa alcuna differenza).
Ora la mia domanda è: ma, data l'equivalenza delle norme in $RR^N$ l'algoritmo non dovrebbe essere stabile per TUTTE le norme? Perché ne ha specificata una ? Infatti poi dice che un algoritmo può essere stabile (e convergente) rispetto a una norma e non ad un'altra... Ma come è possibile ?
Secondo me il problema non è ambientato in $RR^n$... magari in qualche spazio diverso. Però dovrei sapere la pagina per poterti dire con più certezza...
Il problema è quello di trasporto (almeno il capitolo parla della classica equazione $\frac {\partial y}{\partial t} + \alpha \frac {\partial y}{\partial x}$ con $\alpha$ costante). Però penso che questa affermazione abbia un ché di più generale, perché considerazioni simili le posso applicare anche all'equazione di diffusione/poisson (per esempio).
Se vuoi (hai voglia/ti interessa) ti mando due screen delle pagine.
(Tra l'altro la cosa che mi lascia ancora più perplesso è nel libro "A Primer on PDE", Salsa, Vegni, Zaretti, Zunino, gli autori danno la stessa definizione, ma omettono il tipo di norma dicendo semplicemente che la norma è una norma discreta di $\RR^N$).
PS: penso che nel caso aprirò un nuovo post... mi sa che sto andando off topic
Se vuoi (hai voglia/ti interessa) ti mando due screen delle pagine.
(Tra l'altro la cosa che mi lascia ancora più perplesso è nel libro "A Primer on PDE", Salsa, Vegni, Zaretti, Zunino, gli autori danno la stessa definizione, ma omettono il tipo di norma dicendo semplicemente che la norma è una norma discreta di $\RR^N$).
PS: penso che nel caso aprirò un nuovo post... mi sa che sto andando off topic
Scrivi il numero delle pagine interessate.
A. Quartenoni, "Modellistica numerica per problemi Differenziali" pag 362. Qui di dice che uno schema è "fortemente stabile rispetto alla norma $||\cdot||_{\Delta}$". Da cui deduco che ne vada scelta una di volta in volta conveniente al problema in questione.
Mentre per "Prime on PDEs" Salsa, Vegni, Zaretti, Zunino a pag 470-471 si asserisce che $||\cdot||$ è una norma discreta (quindi lasciandomi intuire che tutte le norme vadano bene).
PS: Tra l'altro già che ci sono mi piacerebbe sapere perché nel primo libro citato, la norma $\Delta$ è definita da $j=-\infty$ a $j = +\infty$... che senso ha estendere la somma a infinito (peraltro negativo) se tanto lavoro in uno spazio discreto ?
Pss: Grazie mille della disponibilità e scusa se ti sto stressando
Mentre per "Prime on PDEs" Salsa, Vegni, Zaretti, Zunino a pag 470-471 si asserisce che $||\cdot||$ è una norma discreta (quindi lasciandomi intuire che tutte le norme vadano bene).
PS: Tra l'altro già che ci sono mi piacerebbe sapere perché nel primo libro citato, la norma $\Delta$ è definita da $j=-\infty$ a $j = +\infty$... che senso ha estendere la somma a infinito (peraltro negativo) se tanto lavoro in uno spazio discreto ?
Pss: Grazie mille della disponibilità e scusa se ti sto stressando
Il Quarteroni che citi ce l'ho in inglese, ma quella frase non la riporta. Anzi, la norma scritta da te prprio non compare nel mio, perché si parla solo di norma $L^2$. Forse è qui il problema: due norme si dicono equivalenti se definiscono la stessa struttura topologica sull'insieme dove le definisco. Su $RR^n$, come leggevo che avevi scritto da qualche parte, tutte le norme sono equivalenti, ma in dimensione infinita, che è il nostro caso, esistono esempi di norme NON equivalenti: l'esempio classico è $(C(\Omega),RR)$ con le norme su $L^p(\Omega)$. Ad esempio si mostra di solito che per $p=\+infty,1,2$ le norme non sono equivalenti.
Sull'altra domanda non saprei, non ho quel testo
Sull'altra domanda non saprei, non ho quel testo
"feddy":
Il Quarteroni che citi ce l'ho in inglese, ma quella frase non la riporta. Anzi, la norma scritta da te prprio non compare nel mio, perché si parla solo di norma L2.
Io ce l'ho sia cartaceo che pdf... Ecco la scan del pdf
(Credo che alla fine la norma $\Delta$ non è altro che la classica norma $L^p$ con la misura del conteggio)
"feddy":
Forse è qui il problema: due norme si dicono equivalenti se definiscono la stessa struttura topologica sull'insieme dove le definisco. Su Rn, come leggevo che avevi scritto da qualche parte, tutte le norme sono equivalenti, ma in dimensione infinita, che è il nostro caso, esistono esempi di norme NON equivalenti
Quindi un metodo può essere stabile o meno a seconda della norma che scelgo ? Mi pare un po' strano...
E, scusa ancora, ma perché siamo in dimensione infinita? La soluzione numerica non è un vettore finito ?
_____________________________________________
PS: ho cercato in biblioteca altre edizioni del libro e in altre edizioni si trova a pagine differenti (in una a pag 271 e in un altra a pag 465)
Si, la norma che scrivi tu nel tuo ultimo messaggio corrisponde ad prendere la misura del conteggio, oppure puoi considerare $l^p$ come lo spazio delle sequenze tali per cui $\sum_{k \in \mathbb{Z}} |x_k|^p < +\infty$ e definirci sopra la rispettiva norma. Solo che, se noti, lì hai un coefficiente $h$ (passo) che moltiplica il tutto. Ma non dovrebbe essere un problema.
Comunque è giusto specificare che è stabile rispetto ad una norma data. Voglio dire, specie in ambito numerico, ho interesse a sapere in quale "senso" questo schema è stabile (magari appunto in una situazione sono più interessato alla stabilità nel senso di $L^2$, piuttosto che $L^{+\infty}$, cioè concorderai che è ben diverso sapere se una cosa è limitata in $L^2$ oppure in $L^{\infty}$)
Purtroppo però ora non ho proprio il tempo per pensarci di più
Comunque è giusto specificare che è stabile rispetto ad una norma data. Voglio dire, specie in ambito numerico, ho interesse a sapere in quale "senso" questo schema è stabile (magari appunto in una situazione sono più interessato alla stabilità nel senso di $L^2$, piuttosto che $L^{+\infty}$, cioè concorderai che è ben diverso sapere se una cosa è limitata in $L^2$ oppure in $L^{\infty}$)
Purtroppo però ora non ho proprio il tempo per pensarci di più
Va bene. Grazie mille della disponibilità, sei stato gentilissimo 
Con ritardo, prego! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo