1 CALCOLO NUMERICO Corso di Laurea in Chimica Francesca Mazzia Dipartimento Interuniversitario di Matematica Universit`a di Bari

CALCOLO NUMERICO Corso di Laurea in Chimica

Francesca Mazzia

Dipartimento Interuniversitario di Matematica Universit`a di Bari

1. Formule di ricorrenza del primo ordine Le formule di ricorrenza del tipo:

y n+1 = φ(y n ) (1)

con y ₀ assegnato ed n ≥ 0, vengono chiamate formule di ricorrenza del primo ordine. La funzione φ ` e una qualunque funzione continua definita per tutti i valori che la y n pu` o assumere.

Una interpretazione di questa equazione pu` o essere la seguente: sull’as- se si individuano un numero discreto di punti (si puo pensare ad intervalli successivi di tempo, per esempio):

y ₀ t 0

y ₁ t 1

y ₂ t 2

y ₃ t 3

. . . . . .

y _n t n

In corrispondenza di tali punti risultano definiti i valori di un’altra grandezza y. La (1) definisce i valori che quest’ultima grandezza assume in un punto mediante il valore assunto nel punto precedente.

Le relazioni di ricorrenza del tipo precedente sono anche chiamate equa- zioni alle differenze del primo ordine.

Particolare importanza hanno le equazioni alle differenze del primo ordine

lineari, quelle cio` e per cui la funzione φ(y) ` e una retta, cio` e del tipo φ(y) ≡

ay + b, con a e b parametri reali.

Quando i successivi valori t ₀ , t ₁ , . . . rappresentano istanti discreti di tem- po, le equazioni alle differenze del primo ordine possono essere considerate come lo strumento pi` u semplice per descrivere l’evoluzione della grandezza y al variare del tempo.

Lo studio della evoluzione di un sistema, sia esso fisico, chimico, economi- co o di qualunque altra natura, ` e uno degli obiettivi principali della scienza.

Ogni sistema ` e formato da componenti interagenti fra loro. Tali componenti possono essere pi` u o meno numerose e le interazioni possono essere pi` u o meno note e pi` u o meno forti. La descrizione matematica di un sistema ri- chiederebbe la conoscenza di tutte le varie componenti e delle loro interazioni in maniera molto precisa. Spesso, come abbiamo detto, non si ha una cono- scenza completa di tutto ci` o. Si ` e obbligati a trascurare alcune componenti o a descrivere in maniera approssimata alcune interazioni. Si parla in tal caso di modelli descriventi il sistema oggetto di studio.

E importante tenere sempre presente che un modello descrive il sistema ` nei limiti delle approssimazioni fatte. I calcolatori, a loro volta, introduco- no degli errori nelle elaborazioni dei calcoli i quali, quando la simulazione non viene fatta in maniera corretta, potrebbero alterare completamente il comportamento del modello.

Diamo alcuni esempi di modelli che possono essere descritti da relazioni di ricorrenza del tipo (1).

Modello 1 Catena di lettere

Supponiamo di ricevere una lettera che elenca sei nomi e indirizzi. La lettera chiede di inviare 1000 lire alla prima persona della lista. Bisogna quindi scrivere una nuova lettera con il primo nome cancellato e il nostro nome inserito alla fine della lista. Dobbiamo inviare la lettera a cinque amici.

La promessa ` e che in poche settimane si ricevono pi` u di 15 milioni.

Verifichiamo le promesse della lettera sotto le ipotesi che ognuno segua le istruzioni, e quindi la catena non si spezza. Il problema pu` o essere formu- lato in termini di un’equazione alle differenze. Seguiamo solo le lettere che derivano dalla nostra. Sia y <sub>n</sub> la lettera della n-sima generazione, la lettera che noi riceviamo sar` a la y ₀ = 1, le lettere scritte da noi corrispondono a y ₁ e cos`ı via. La relazione appropriata fra una lettera e la successiva ` e

y _n+1 = 5y _n

proviamo a calcolare quante lettere conterranno il nostro nome come primo dopo 6 generazioni.

Scriviamo una function Scilab che calcola la soluzione di una generica equazione di ricorrenza del tipo:

y _n+1 = ay _n

I dati di input sono a, y ₀ e N il numero massimo di iterate che vogliamo calcolare. Il dato di output il vettore y che contiene la soluzione ad ogni passo.

function [y]=ric(a, y0,N)

% Equazione alle differenze del primo ordine

%

% y(n+1) = a y(n)

%

% y vettore solouzione di N+1 elementi

%

y(1) = y0;

for i = 1:N

y(i+1) = a*y(i);

end

eseguiamo adesso la funzione

>> y=ric(5,1,6) y =

1 5 25 125 625 3125 15625

>>

Queste equazioni alle differenze descrivono anche modelli pi` u complicati, come il Modello di Malthus, che viene utilizzato per studiare la crescita di una popolazione.

Modello 2 (di Malthus).

L’obiettivo dello studio ` e l’evoluzione nel tempo di un gruppo di indi- vidui che segue gli eventi della vita essenziali: essi nascono, maturano, si riproducono e muoiono. Il gruppo pu` o essere un gruppo di batteri, di ani- mali o di uomini. Per semplicit` a consideriamo solo la parte femminile della popolazione.

Il modello pi` u semplice ` e quello di Malthus. Supponiamo che si voglia studiare una popolazione di batteri immersa in un liquido contenente sostanze di cui essi si nutrono. Ad intervalli regolari di tempo si procede a contarli.

Siano t ₀ , t ₁ , . . ., t _{n −1} , t _n , . . . i valori discreti del tempo. Nella costruzione del modello dobbiamo considerare le possibili cause che possono influenzare la crescita della popolazione dei batteri. Vediamo di individuarne qualcuna:

1) la nascita di nuovi batteri;

2) la morte di alcuni batteri;

3) la struttura di et` a: un batterio anziano potrebbe comportarsi in maniera diversa rispetto ad un batterio giovane;

4) la scarsit` a di nutrimento.

Gli eventi 1) e 2) sono ineluttabili e devono necessariamente essere con- siderati. La 3), considerato che la vita media di un batterio ` e pi` u piccola o almeno comparabile con il tempo di osservazione, potrebbe non essere impor- tante. Decidiamo, quindi, di trascurarla per il momento. Questa decisione potrebbe per` o non essere opportuna se, invece che i batteri, si volesse stu- diare, ad esempio, una popolazione di insetti o addirittura una popolazione umana. La 4) infine potrebbe non verificarsi se decidiamo di stare attenti a non far mancare il nutrimento necessario alla popolazione oggetto di studio (come vedremo questa decisione potrebbe costare molto). Facendo le ipotesi semplificative di trascurare la 3) e la 4) si ottiene un modello semplificato.

Considerando che il numero di nuovi nati tra t _n e t _n+1 ` e proporzionale al numero di batteri al tempo t <sub>n</sub> , che indicheremo con y <sub>n</sub> , e che lo stesso si pu` o dire per i batteri morti nello stesso intervallo di tempo, potremo scrivere:

y _n+1 = y _n +α(coefficiente di natalit` a)y _n −

−β(coefficiente di mortalit`a)y n .

` e ovvio che i due coefficienti α e β sono entrambi minori di 1. Quindi il

modello diventa:

y _n+1 = (1 + α − β)y n = ay _n ,

in cui abbiamo posto a = (1 + α − β). Se a > 1, si avr`a che la popolazione al tempo t n+1 sar` a maggiore della popolazione al tempo t n . Se supponiamo che all’inizio dell’esperimento vi siano y ₀ batteri, il nostro modello sar` a:

( y _n+1 = ay _n

y ₀ fissato (2)

La soluzione di (2) si ottiene facilmente iterando. Infatti si ha:

y _n+1 = ay _n = a(ay _{n −1} ) = . . . = a ⁿ⁺¹ y ₀

Si deduce che se a > 1 la popolazione cresce esponenzialmente e tende ad infinito. Se a < 1 la popolazione tende a zero.

Si noti che nel primo caso avremo problemi di spazio e, soprattutto, problemi di nutrimento e quindi l’ipotesi semplificativa che abbiamo fatto trascurando la 4) non sar` a pi` u giustificata. Ma non ` e questo il punto che vogliamo discutere ora. Ora vogliamo discutere il problema di approssimare numericamente il modello.

Eseguiamo il modello nell’ambiente di lavoro Scilab. Se il nostro problema

`

e quello di trovare il valore y 10 , partendo dai dati iniziali a = 0.9 e y 0 = 2, potremo usare il programma

ric.sci

con i nuovi dati di input:

>> y = ric(0.9,2,11)

Si ` e cos`ı creato un vettore y di lunghezza 11 contenente tutti i risultati intermedi da y ₀ a y ₁₀ (notare che sono 11 valori). Il risultato si pu` o disegnare mediante il comando:

>> plot(y)

oppure:

>> t = [0 1 2 3 4 5 6 7 8 9 10];

>> plot(t, y)

ove t ` e il vettore definito dalla seguente istruzione:

oppure:

>> t = 0:10;

>> plot(t, y)

Eseguire le due opzioni e notare la differenza.

Supponiamo che nel fare i calcoli si commetta ad ogni passo un errore costante δ anche molto piccolo. Il modello diventa

( y _n+1 = ay _n + δ

y 0 fissato (3)

I due modelli sono molto vicini quando δ ` e molto piccolo. Tuttavia le due soluzioni possono essere molto diverse. Infatti la soluzione del modello (3) ` e data da

y _n+1 = a ⁿ⁺¹ y ₀ +

n

X

j=0

a ^{n −j} δ (4)

Il simbolo ^{P n} _j=0 a _j ` e una forma abbreviata per scrivere la somma di tutti i successivi valori degli a j da a 0 ad a n . Cio` e si ha, per definizione:

n

X

j=0

a _j = a _n + a _n−1 + . . . + a ₀

con la convenzione che, qualora l’indice superiore fosse pi` u piccolo dell’indice inferiore, il valore sia 0. Ad esempio si ha

−1

X

j=0

a _j = 0 Pertanto la (1.4), quando a 6= 1, diventa ¹

1 Si ricorda che, se a 6= 1, P n

j=0 a ^j = ^a

_{a −1} ⁻¹ . Infatti, se poniamo s n = 1 + a + . . . + a ⁿ ,

allora as n − s n = a ⁿ⁺¹ − 1, cio`e s n (a − 1) = a ⁿ⁺¹ − 1.

y _n+1 = a ⁿ⁺¹ y ₀ + a ⁿ⁺¹ − 1 a − 1 δ.

Il primo termine al secondo membro rappresenta la soluzione del modello (2 mentre l’altro termine, che rappresenta quindi la differenza tra le due soluzioni pu` o diventare, quando a > 1, molto grande al crescere di n, anche se δ ` e piccolo. Al contrario se a < 1, questo termine non cresce. Quindi una piccola perturbazione nel modello, in questo caso dovuta ad errori numerici, pu` o portare a grossi errori nella soluzione. Questo fenomeno viene chiamato instabilit` a ed in questo caso ` e stato facile da valutare, in casi pi` u complessi la instabilit` a pu` o presentarsi in maniera pi` u subdola.

Modello 3 Deposito in banca.

Supponiamo di depositare ogni anno una quantit` a costante b di denaro in banca. Sia r l’interesse che la banca paga ogni anno sulla somma accumulata.

Indicando con y _n la somma accumulata al tempo t _n , si ha:

y _n+1 = y _n + ry _n + b = (1 + r)y _n + b = ay _n + b

la cui soluzione ` e la stessa ottenuta nel modello 1 perturbato ponendo 1 + r al posto di a e b al posto di δ.

Esercizio

Costruire una function MATLAB per calcolare i valori di y _n partendo da y ₀ dato di input fino a y _N con N dato di input. Inserire come dati di input anche a e b. Eseguire la function supponenendo che l’interesse sia il 5 per cento e che b sia uguale ad un milione.

In tutti i modelli considerati ` e comparsa la formula di ricorrenza:

y _n+1 = ay _n + b (5)

la quale descrive il comportamento di una quantit` a che ad ogni passo si ottiene dalla precedente moltiplicandola per un parametro a e addizionando un’altra quantit` a fissa b. Si verifica subito che se la quantit` a iniziale y <sub>0</sub> fosse b/(1 − a), tutti i valori successivi di y n rimarrebbero costanti ed uguali al valore iniziale. Cio` e la soluzione sarebbe una soluzione costante:

y _n = b

1 − a ≡ y. (6)

Esercizio

Eseguire la function precedente per verificare questo risultato (porre y ₀ = b/(1 − a)).

Per ottenere la soluzione costante basta cercare nella (5) la soluzione y indipendente da n. Si ha y = ay + b. Risolvendo rispetto ad y si ottiene la (6).

La (5) ` e un caso particolare della relazione di ricorrenza:

y _n+1 = a _n y _n + b _n (7)

che ` e la pi` u generale formula di ricorrenza lineare.

La soluzione della (7), indicando con y ₀ il valore iniziale, ` e data da:

y _n =

n−1

Y

j=0

a _j y ₀ +

n−1

X

j=0

b _j

n−1

Y

s=j+1

a _s (8)

Abbiamo gi` a visto il significato del simbolo <sup>P</sup> . Il simbolo <sup>Q n</sup> <sub>j=k</sub> <sup>−1</sup> a <sub>j</sub> ` e una forma abbreviata per scrivere il prodotto di tutti i successivi valori degli a _j da a _k ad a _n−1 . Cio` e si ha, per definizione:

n −1

Y

j=0

a j = a n −1 a n −2 . . . a 0

con la convenzione che, qualora l’indice superiore fosse pi` u piccolo dell’indice inferiore, il valore sia 1. Ad esempio si ha:

−1

Y

j=0

a _j = 1

Verifichiamo ora che l’espressione (8) soddisfa la relazione di ricorrenza

(7). Riscriviamo la (8) ponendo n + 1 al posto di n. Si ha:

y n+1 =

n

Y

j=0

a j y 0 +

n

X

j=0

b j n

Y

s=j+1

a s =

= a n n −1

Y

j=0

a j y 0 +

n −1

X

j=0

b j a n n −1

Y

s=j+1

a s + b n =

= a _n





n−1

Y

j=0

a _j y ₀ +

n−1

X

j=0

b _j

n−1

Y

s=j+1

a _s



 + b _n = a _n y _n + b _n

Quindi la successione di valori fornita dalla (8) soddisfa la relazione di ricorrenza (7). Nel caso particolare in cui tutte le a _i siano costanti ed uguali ad a, mentre le b _i siano costanti ed uguali a b, essendo

n −1

Y

j=0

a = a ⁿ ed, ovviamente,

n −1

Y

j=k

a j = a ^{n −k} si ha:

y _n = a ⁿ y ₀ + b

n−1

X

j=0

a ^n−j−1 = a ⁿ y ₀ + b a ⁿ − 1

a − 1 , (9)

Stabilit` a della soluzione costante

Nelle applicazioni assume molta importanza il concetto di stabilit` a di una soluzione. Per semplicit` a ci riferiremo alla soluzione costante y dell’equazio- ne:

y _n+1 = ay _n + b (10)

la quale si ottiene, come abbiamo gi` a visto, ponendo

y = ay + b (11)

Diremo che la soluzione costante y ` e stabile se per qualunque soluzione y _n la differenza y _n − y rimane limitata al crescere di n.

Diremo che la soluzione costante y ` e asintoticamente stabile se per qualunque

soluzione y _n , la differenza y _n − y tende a zero al crescere di n.

Diremo che la soluzione costante y ` e instabile se la differenza y _n − y cresce al crescere di n.

Quanto detto precedentemente rimane invariato se, al posto della solu- zione costante y, si prendesse come soluzione di riferimento una qualunque altra soluzione y _n .

Nelle applicazioni di solito la y viene chiamata soluzione di equilibrio.

Le definizioni precedenti servono a caratterizzare i possibili comportamenti in vicinanza della soluzione di equilibrio (o nell’intorno di una qualunque altra soluzione). Infatti tutte le soluzioni della (10) sono date dalla formula (9), variando il valore iniziale y ₀ . Ripetiamo che se la condizione iniziale ` e proprio y, allora la soluzione rimane sempre uguale a questo valore. Quindi le definizioni precedenti tendono a caratterizzare il comportamento qualitativo delle soluzioni quando si varia anche leggermente il valore iniziale nell’intorno di y (perturbazione del dato iniziale).

Sottraiamo la (11) dalla (10) ed indichiamo con e _n la quantit` a y _n − y. Si ha:

e n+1 = ae n

cio` e e _n = a ⁿ e ₀ . Si possono avere tre casi:

1) |a| ≤ 1. In questo caso |e ⁿ | non cresce al crescere di n e si ha stabilit`a.

2) |a| < 1. In questo caso |e n | tende a zero al crescere di n e si ha quindi asintotica stabilit` a.

3) |a| > 1. Si ha instabilit`a.

Esercizio

Trovare la soluzione costante del Modello 3 (Deposito in banca) e studiare il tipo di stabilit` a.

Cerchiamo di seguire in Scilab una soluzione della (10) partendo da un

valore y ₀ = 1, fino a quando essa non dista dalla soluzione costante di una

quantit` a prefissata, per esempio 10 ⁻⁴ . Sia a = 0.5 e b = 2. Dalla (10)

si ottiene y = 4. Indichiamo questo valore con yb. Ci` o si ottiene con le

istruzioni:

>> yb = 4;

>> y(1) = 1;

>> i = 1;

>> while abs(y(i)-yb)> 1e-4, i=i+1; y(i) = 0.5*y(i-1) + 2; end L’istruzione while ripete le operazioni successive che si trovano prima della parola end fino a quando la condizione logica, in questo caso abs(y- yb)¿ 1e-4, sia verificata. La funzione abs(y-yb) d` a come risultato il valore assoluto della espressione in parentesi.

Il risultato finale ` e un vettore y contenente tutti i valori intermedi della soluzione. Ci` o ` e stato ottenuto mediante l’attivazione di un contatore, l’indice i, che viene incrementato di una unit` a ad ogni passaggio. Il contenuto di y si pu` o disegnare con plot(y).

Per rendere il nostro algoritmo il pi` u generale possibile, possiamo scrivere una function che richieda in input il valore di a, b, y <sub>0</sub> , e calcoli il valore della (10) fino a quando essa non disti dalla soluzione costante di una quantit` a prefissata. Il nostro file, che chiameremo modello.sci, sar` a:

function [y] = modello(a,b,y0,tol) y(1)=y0;yb=b/(1-a);

i=1;

while abs(y(i)-yb) > tol, i=i+1;

y(i) = a*y(i-1) + b;

end

Prima di richiamare il file modello dobbiamo fissare il valore dei dati di input. Il modello descritto precedentemente ` e equivalente ad eseguire:

>> y = modello(.5,2,1,1e-4)

Per verificare il comportamento della nostra function possiamo usare il comando keyboard, con questo comando compare un nuovo prompt da cui

`

e possibile controllare i dati utilizzati all’interno della function. Se quindi scriviamo la function:

function [y] = modello(a,b,y0,tol)

y(1)=y0;yb=b/(1-a);

i=1;

while abs(y(i)-yb) > tol, i=i+1;

y(i) = a*y(i-1) + b;

keyboard end

e la eseguiamo con l’istruzione

>> y = modello(.5,2,1,1e-4) comapare il nuovo prompt K>>

da cui possiamo visualizzare le variabili utilizzate all’interno della func- tion.

K>>

y = 1.

2.5 K>i

i = 2.

K>

per proseguire nell’esecuzione dobbiamo scrivere K>return

compare di nuovo il prompt. Questa istruzione pu` o essere utilizzata per- controllare il comportamento delle function. Per uscire definitivamente dal prompt dell’istruzione keyboard si usa il comando dbquit.

Verifichiamo se la function funziona sempre correttamente, ponendo a =

5:

>> y = modello(5,2,1,1e-4) K>> y

y =

1 7

K>> return K>> y y =

1 7 37

K>> return K>> y y =

1 7 37 187

K>> return K>> y y =

1 7 37 187 937

K>> dbquit

>>

vediamo che la soluzione diverge, quindi il ciclo while non termina mai, perc` e la condizione non ` e mai verificata. Dobbiamo modificare la function in modo da prendere in considerazione anche il caso in cui la soluzione costante

`

e instabile. La nuova function dal nome modelloc.sci avr` a come dato di input anche il numero massimo di iterate:

function [y] = modelloc(a,b,y0,tol,Nmax)

%Equazione alle differenze del primo ordine

%

%y(n+1) = a y(n)+b

%

%y vettore solouzione di N+1 elementi

%

y(1)=y0;yb=b/(1-a);

i=1;

while (abs(y(i)-yb) > tol) & (i < Nmax), i=i+1;

y(i) = a*y(i-1) + b;

end

if (i >= Nmax)

disp(‘‘Soluzione costante instabile o Nmax piccolo") else

disp("Soluzione costante stabile") end

endfunction

Con gli stessi dati di input e Nmax uguale a 20 abbiamo --> y = modelloc(5,2,1,1e-4,20);

Soluzione costante instabile o Nmax piccolo

Si possono dare anloghe definizioni sulla stabilit` a anche nel caso in cui le variazioni, invece che solo sul dato iniziale, siano date anche sui coefficienti a e b, nel caso in cui, cio` e, si considerino equazioni del tipo:

y _n+1 = (a +  ₁ )y _n + b +  ₂ (12) con  ₁ ed  ₂ piccole rispetto ad a e b.Come risultato, che applicheremo in seguito, si ha:

Se |a| < 1, e se le perturbazioni sono piccole, vi `e anche stabilit`a rispetto a

perturbazioni dei coefficienti, nel senso che la differenza tra la soluzione y _n

dell’equazione imperturbata (10) e la soluzione y _n dell’equazione perturbata 12) rimane limitata per tutti i valori di n.

Errore assoluto ed errore relativo

Anche se due modelli sono vicini nel senso che i parametri che definisco- no i modelli differiscono di poco, le rispettive soluzioni possono differire di molto. Ci` o non sempre ` e pericoloso nelle applicazioni. Cerchiamo di chia- rire questo concetto nel caso semplice in cui i due modelli siano descritti da ricorrenze lineari. Anzi, per rendere la discussione ancora pi` u sempli- ce, considereremo solo perturbazioni rispetto ai dati iniziali. I risultati a cui si perviene in questo semplice caso sono per` o generalizzabili a casi pi` u complicati. Consideriamo le soluzioni dei problemi:

( y _n+1 = ay _n + b y ₀ = q ₁

( x _n+1 = ax _n + b x ₀ = q ₂

Consideriamo la differenza tra le due soluzioni: e _n = y _n − x n . Essa soddisfa l’equazione (basta sottrarre le due precedenti):

( e n+1 = ae n

e ₀ = q ₁ − q 2

la cui soluzione ` e e _n = (q ₁ − q 2 )a ⁿ . Consideriamo il caso peggiore in cui

|a| > 1. In questo caso e n cresce in valore assoluto e quindi le due soluzioni, anche se differiscono solo per il valore iniziale tendono a divergere. Nelle applicazioni per` o, pi` u che l’errore e _n , assume molta pi` u importanza l’errore relativo definito da (se si prende come soluzione di riferimento la soluzione y _n ):

η n =

y _n − x n

y _n

.

Il termine a numeratore ` e proprio e <sub>n</sub> che sappiamo divergere. Se la soluzione a denominatore rimane limitata al crescere di n, l’errore relativo pu` o diventare molto grande. Ci` o accadrebbe certamente se, per esempio, y _n fosse proprio la soluzione costante y.

Esempio:

Prendiamo b = 0. In questo caso si ha:

η _n =

q ₁ − q 2

q ₁

.

e quindi η _n diventerebbe molto grande solo quando q ₁ si avvicina allo zero.