ordine di convergenza metodo di Eulero in avanti

[dRic]

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

Testo nascosto, fai click qui per vederlo

Il problema da approssimare è:

$$\dot y(t) = f(t, y)$$

Allora, la condizione di convergenza è:

$$\lim_{\Delta t \rightarrow 0} |y(t_n) - u_n| = 0$$

Dove $y(t^n)$ è la soluzione esatta valutata all'istante $t_n$ appartenente al dominio discreto della soluzione numerica $u_n$. Visto che la suddetta condizione deve valere per tutti gli $n$ posso anche studiarla per $n+1$.
In questo caso so che:

$$u_{n+1} = u_{n} + \Delta t \cdot f(t_n, u_n)$$

Ma siccome il metodo è consistente (facile da verificare) posso scrivere $u_n = y(t_n)$ e dunque:

$$u_{n+1} = y(t_n) + \Delta t \cdot f(t_n, y(t_n))$$

Sostituendo nella seconda equazione (scritta per $n+1$):

$$|y(t_{n+1}) - y(t_n) + \Delta t \cdot f(t_n, y(t_n))| = |\Delta t \cdot ( \dot y(t_n) + O(\Delta t ) + \Delta t \cdot f(t_n, y(t_n))|$$
$$|\Delta t \cdot ( \dot y(t_n) - f(t_n, y(t_n))) + \Delta t O(\Delta t)| = |\Delta t \cdot O(\Delta t)|$$

Ora, se non dico una cappellata, $\Delta t \cdot O(\Delta t) = O( \Delta t^2)$ quindi per $\Delta t \rightarrow 0$ ottengo che il metodo di Eulero in avanti avrebbe ordine di convergenza 2... cosa che non è possibile perché è risaputo che ha ordine di convergenza uno.

Dove sto sbagliando ?

[feddy]

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.

[dRic]

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 ?

[feddy]

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.

[dRic]

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

[feddy]

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 .

[dRic]

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.

[dRic]

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ò

[...] (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 ?

[feddy]

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

[dRic]

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