Matlab: complessit`a e stabilit`a degli algoritmi. Alcuni esempi.

(1)

Matlab: complessit`

a e stabilit`

a degli algoritmi.

Alcuni esempi.

´

Angeles Mart´ınez Calomardo e Alvise Sommariva

Universit`a degli Studi di Padova

(2)

Stabilit`

a : radici secondo grado

Dato x2_{+ 2 px − q, con}p

p2_{+ q ≥ 0 eseguiamo un primo}

algoritmo Matlab che valuta la radice via:

y = −p +pp2_{+ q.} ₍₁₎

I pp2_{+ q ≥ 0 implica radici reali.}

I Potenzialmente instabile per p q a causa della sottrazione

tra p epp2_{+ q (cancellazione).}

(3)

Codice stabilit`

a : algoritmo 1

Salviamo il seguente codice in radicesecgrado.m.

(4)

(5)

Codice stabilit`

a : stampa risultati

f p r i n t f(’ \ n \ t [ ALG . 1 ] : %10.19 f ’, s1 ) ; f p r i n t f(’ \ n \ t [ ALG . 2 ] : %10.19 f ’, t1 ) ; i f l e n g t h( sol ) > 0 & ( sol ˜= 0 )

rerr1 =a b s( s1−sol ) /a b s( sol ) ; rerr2=a b s( t1−sol ) /a b s( sol ) ;

(6)

Test.

Come previsto, il secondo algoritmo si comporta notevolmente meglio del primo, che compie un errore relativo dell’ordine di circa 10−9. Infatti:

>> radicesecgrado

(7)

Calcolo π

Eseguiamo un codice Matlab che valuti le successioni {un}, {zn},

(8)

Calcolo π

Implementiamo poi la successione, diciamo {yn}, che si ottiene

razionalizzando (3), cio`e moltiplicando numeratore e denominatore

di zn+1= 2n− 1 2 r 1 − q 1 − 41−n_{· z}2 n per r 1 + q 1 − 41−n_{· z}2 n

e calcoliamo um, zm e ym per m = 2, 3, . . . , 40 (che teoricamente

dovrebbero approssimare π).

Infine disegniamo in un unico grafico l’andamento dell’errore relativo di un, zn e yn rispetto a π aiutandoci con l’help di Matlab

(9)

Calcolo π: metodo 1

In seguito scriviamo un’implementazione di quanto richiesto commentando i risultati. Si salvi in un file pigreco.m il codice

(10)

(11)

(12)

Calcolo π: plots

% SEMILOGY PLOT .

s e m i l o g y( 1 :l e n g t h( u ) , rel_err_u , ’ k . ’ , . . . 1 :l e n g t h( z ) , rel_err_z ,’m+ ’ , . . . 1 :l e n g t h( y ) , rel_err_y ,’ r o ’) ;

Di seguito digitiamo sulla shell di Matlab/Octave

(13)

Plot risultati

0 5 10 15 20 25 30 35 40 45 10−15 10−10 10−5 100

(14)

Discussione risultati.

I La prima successione converge molto lentamente a π, la

seconda diverge mentre la terza converge velocemente a π.

I Per alcuni valori {zn} e {yn} coincidono per alcune iterazioni

per poi rispettivamente divergere e convergere a π. Tutto ci`o

`

e naturale poich`e le due sequenze sono analiticamente (ma

non numericamente) equivalenti.

I Dal grafico dell’errore relativo, la terza successione, dopo aver

raggiunto errori relativi prossimi alla precisione di macchina, si

assesta ad un errore relativo di circa 10−15 (probabilmente per

(15)

Una successione ricorrente.

Consideriamo la successione {In} definita da

In= e−1 Z 1 0 xnexdx (4) I n = 0: I0 = e−1 R1 0 e x_{dx = e}−1_(e1_{− 1).}

I integrando per parti

In+1 = e−1 xn+1ex |1₀−(n + 1) Z 1 0 xnexdx = 1 − (n + 1) In.

(16)

Problema.

Calcoliamo In per n = 1, . . . , 99:

I mediante la successione in avanti

I0 = e−1(e1− 1)

In+1= 1 − (n + 1) In. (5)

I mediante la successione all’indietro

t1000 = 0

tn−1= (1 − tn)/n.

Si noti che se In+1 = 1 − (n + 1) In allora In= (1 − In+1)/(n + 1) e

(17)

Successioni ricorrente in Matlab

Scriviamo il codice in un file succricorrente.m.

(18)

Successioni ricorrente in Matlab

% PLOT SEMI−LOGARITMICO . c l f ;

s e m i l o g y( 1 :l e n g t h( s ) ,a b s( s ) ,’ k− ’ , . . . 1 :l e n g t h( s ) ,a b s( t ( 1 :l e n g t h( s ) ) ) ) ;

Di seguito digitiamo sulla shell di Matlab/Octave

(19)

Plot risultati

0 20 40 60 80 100 10−50 100 1050 10100 10150

Figura : Grafico che illustra i valori assoluti assunti dalla successione in

(20)

Commento successione ricorrente.

(21)

Commento successione ricorrente.

(22)

Facoltativo. Complessit`

a : algoritmo di Horner.

Ci poniamo il problema di valutare il polinomio

p(x ) = a0+ a1· x + . . . + an· xn (6)

in un punto x . Osserviamo che

p(x ) = a0+ x · (a1+ x · (a2+ . . . + x · (an−1+ x · an))) (7)

Supponiamo sia a = (a0, . . . , an) il vettore di dimensione n + 1

(23)

Complessit`

a : algoritmo di Horner.

In Matlab avremo allora

f u n c t i o n s=al gor itm o1 ( a , x ) xk =1; s=a ( 1 ) ; f o r i =2:l e n g t h( a ) xk=xk∗x ; s=s+a ( i )∗xk ; end e

f u n c t i o n s=al gor itm o2 ( a , x ) L=l e n g t h( a ) ;

s=a ( L ) ; % COMPONENTE a n IMMAGAZZINATA IN a ( n+1) . f o r i=L −1: −1:1

(24)

Complessit`

a : algoritmo di Horner.

Se lanciamo il codice demo horner per la valutazione di p(x ) = 1 + 2 · x + 3 · x2+ 4 · x3 in x = π

c l e a r a l l; a =[1 2 3 4 ] ; x=p i;

(25)

Complessit`

a : algoritmo di Horner.

La differenza sta nella complessit`a computazionale e non nel