Che materia stai cercando?

Calcolo Numerico II – Elaborato Appunti scolastici Premium

Elaborato di Calcolo Numerico II. Nello specifico gli argomenti trattati sono i seguenti: Indicatori d'errore, La routine genera errore, Algoritmo, gseidel, Esempi di accuratezza, funzioni JACVET e GSEIDEL, Esempio 2: Con matrice 100x100 mal-condizionata, ecc.

Esame di Calcolo Numerico II docente Prof. L. D'Amore

Anteprima

ESTRATTO DOCUMENTO

Diagrammi efficienza temporale, funzioni JACVET e GSEIDEL

-14

NITER ERROR REL

x 10

5000 JACVET JACVET

4000 GSEIDEL GSEIDEL

1

3000

2000 0.5

1000

0 0

0 200 400 600 0 200 400 600

TIME(sec) COND

50 500

JACVET

40 400

GSEIDEL

30 300

20 200

10 100

0 0

0 200 400 600 0 200 400 600

I diagrammi riportati sono generati utilizzando come matrice dei coefficienti la matrice di

riportate sull’asse dell’ascisse.

POISSON, a vari ordini di grandezza Processore Intel® Core™ 2 Duo T7300 2GHz,

Il calcolatore utilizzato per i test è un laptop HP con

Memoria centrale 2048 MB, Sistema Operativo Windows 7 Professional, Matlab 7.9.0(R2009b)

Di seguito è riportato lo script per generare i grafici:

data = zeros(2,7); dataj = zeros(3,7); datag = zeros(3,7);

ord = round(logspace(0.5,1.4,7));

for index = 1:7,

A = gallery('poisson',ord(index));

dim = ord(index).^2;

xsol = rand(dim,1); b = A*xsol;

data(:,index) = [dim; condest(A)];

start = cputime; [jx jNITER] = jacvet(A,b,eps,5000); jtime = cputime - start;

dataj(:,index) = [jNITER; norm(jx-xsol)/norm(jx); jtime];

start = cputime; [gx gNITER] = gseidel(A,b,eps,5000); gtime = cputime - start;

datag(:,index) = [gNITER; norm(gx-xsol)/norm(gx); gtime];

disp(['passo: ', num2str(index),' di 7']);

end;

figure;

subplot(2,2,1); plot(data(1,:), dataj(1,:), 'b-', data(1,:), datag(1,:), 'r-');

axis([0,650,0,5000]); legend('JACVET','GSEIDEL','Location','NorthWest');

title('NITER');

subplot(2,2,2);

plot(data(1,:), dataj(2,:), 'b-', data(1,:), datag(2,:), 'r-');

axis([0,650,0,1.5*10^(-14)]); legend('JACVET','GSEIDEL','Location','NorthWest');

title('ERROR REL');

subplot(2,2,3); plot(data(1,:), dataj(3,:), 'b-', data(1,:), datag(3,:), 'r-');

axis([0,650,0,50]); legend('JACVET','GSEIDEL','Location','NorthWest');

title('TIME(sec)');

subplot(2,2,4); plot(data(1,:), data(2,:), 'g-');

axis([0,650,0,500]); title('COND'); 5

Test di Robustezza, funzione JACVET

Verifica della funzione jacvet nei confronti dei parametri di ingresso:

Script del test Output ottenuto Esito

Omissione parametri di input

>> x = jacvet; ??? Error using

I parametri A e b sono obbligatori.

TJ1 Positivo

>> x = jacvet(sprand(2,2,0.2)); ??? Error using

I parametri A e b sono obbligatori.

TJ2 Positivo

Con matrice A non numerica, sparsa, quadrata

>> x = jacvet(‘ciao’,[1;2]); ??? Error using

Parametro A invalido: deve contenere solo

TJ3 Positivo

numeri.

>> x = jacvet(rand(3,3),[ 1 2 ??? Error using

3]); Parametro A invalido: deve essere una

TJ4 Positivo

matrice sparsa.

>> x=jacvet(sprand(5,3,0.08),[ 1 ??? Error using

2 3]); Parametro A invalido: deve essere una

TJ5 Positivo

matrice quadrata.

Con matrice A avente elementi NaN o Inf

>> A = sprand(30,30,0.08); ??? Error using

>> A(3) = nan; A(6) = nan; Parametro A invalido: non deve contenere

TJ6 Positivo

>> x = jacvet(A,1:30); valori NaN.

>> A = sprand(30,30,0.08); ??? Error using

>> A(6) = inf; Parametro A invalido: non deve contenere

TJ7 Positivo

>> x = jacvet(A,1:30); valori Inf.

con matrice A che ha elementi nulli sulla diagonale

>> A = bucky; ??? Error using

>> x = jacvet(A, ones(60,1)); Parametro A invalido: la diagonale

TJ8 Positivo

principale di A non deve avere valori

nulli.

Con vettore b non numerico

>> A = sparse([3,3; 0, 1]); ??? Error using

>> b = ‘fg’; Parametro b invalido: deve contenere solo

TJ9 Positivo

>> x = jacvet(A,b); numeri.

Con vettore b avente elementi NaN o Inf

>> A = sparse([3,3; 0, 1]); ??? Error using

>> b = [2 NaN]; Parametro b invalido: non deve contenere

TJ10 Positivo

>> x = jacvet(A,b); valori NaN.

>> A = sparse([3,3; 0, 1]); ??? Error using

>> b = [inf; 4]; Parametro b invalido: non deve contenere

TJ11 Positivo

>> x = jacvet(A,b); valori Inf.

Con matrice A e vettore b non compatibili

>> A = sparse([3,3, 0; 0, 1, 9; ??? Error using

0, 0, 2]); Le dimensioni dei parametri

>> b = [1; 4]; incompatibili; il numero di colonne di A

TJ12 Positivo

>> x = jacvet(A,b); deve essere pari al numero di elementi di

b.

Con TOL non numerico, scalare, reale

>> A = sparse([3,3, 0; 0, 1, 9; ??? Error using

0, 0, 2]); Parametro TOL invalido: deve essere un

TJ13 Positivo

>> b = [1; 4; 9]; numero.

>> x = jacvet(A,b,’h’);

>> x = jacvet(A,b,[7 8]); ??? Error using

Parametro TOL invalido: deve essere uno

TJ14 Positivo

scalare.

>> x = jacvet(A,b, 6+i*9); ??? Error using

Parametro TOL invalido: deve essere un

TJ15 Positivo

numero reale positivo. 6

Con TOL pari a NaN e inf

>> x = jacvet(A,b, nan); ??? Error using

Parametro TOL invalido: non deve essere

TJ16 Positivo

NaN.

>> x = jacvet(A,b, inf); ??? Error using

Parametro TOL invalido: non deve essere

TJ17 Positivo

Inf.

Con TOL non positivo

>> x = jacvet(A,b, -4); ??? Error using

Parametro TOL invalido: deve essere un

TJ18 Positivo

numero positivo.

>> x = jacvet(A,b, 0); ??? Error using

Parametro TOL invalido: deve essere un

TJ19 Positivo

numero positivo.

Con MAXITER non numerico, scalare, reale

>> x = jacvet(A,b,eps,’h’); ??? Error using

Parametro MAXITER invalido: deve essere

TJ20 Positivo

un numero.

>> x = jacvet(A,b,eps,[7 8]); ??? Error using

Parametro MAXITER invalido: deve essere

TJ21 Positivo

uno scalare.

>> x = jacvet(A,b,eps, i*3); ??? Error using

Parametro MAXITER invalido: deve essere

TJ22 Positivo

un numero intero maggiore o uguale a 1.

Con MAXITER pari a NaN e inf

>> [x N] = jacvet(A,b,eps,NaN); ??? Error using

Parametro MAXITER invalido: non deve

TJ23 Positivo

essere NaN.

>> [x N] = jacvet(A,b,eps,-inf); ??? Error using

Parametro MAXITER invalido: non deve

TJ24 Positivo

essere Inf.

Con MAXITER minore di uno

>> x = jacvet(A,b,eps,-1); ??? Error using

Parametro MAXITER invalido: deve essere

TJ25 Positivo

un numero intero maggiore o uguale a 1.

>> x = jacvet(A,b,eps,0.5); ??? Error using

Parametro MAXITER invalido: deve essere

TJ26 Positivo

un numero intero maggiore o uguale a 1.

>> x = jacvet(A,b,eps,1-eps); ??? Error using

Parametro MAXITER invalido: deve essere

TJ27 Positivo

un numero intero maggiore o uguale a 1.

Con parametri coretti

>> A = gallery('poisson',4); N = 164

>> xvero = ones(size(A,1),1);

>> b= A*xvero; ans = 7.6113e-016

TJ28 Positivo

>> [x N] = jacvet(A,b);

>> N

>> norm(x-xvero)./norm(x)

>> [x N] = jacvet(A,b,10^(-2)); N = 15

>> N

TJ29 Positivo

>> norm(x-xvero)./norm(x) ans = 0.0410

>> [x N] = jacvet(A,b,eps,1); Warning: JACVET non converge per 1

>> N iterazioni con tolleranza 2.22045e-016

TJ30 Positivo

N = 1

>> [x N] = jacvet(A,b,eps/2 Warning: Parametro TOL inaccettabile:

,1000); deve essere maggiore o uguale all'epsilon

>> N macchina.

TJ31 Positivo

N = 164 7

Test di Robustezza, funzione GSEIDEL

Verifica della funzione gseidel nei confronti dei parametri di ingresso:

Script del test Output ottenuto Esito

Omissione parametri di input

>> x = gseidel; ??? Error using

I parametri A e b sono obbligatori.

TG1 Positivo

>> x = gseidel(sprand(2,2,0.2)); ??? Error using

I parametri A e b sono obbligatori.

TG2 Positivo

Con matrice A non numerica, sparsa, quadrata

>> x = gseidel(‘ciao’,[1;2]); ??? Error using

Parametro A invalido: deve contenere solo

TG3 Positivo

numeri.

>> x = gseidel(rand(3,3),[ 1 2 ??? Error using

3]); Parametro A invalido: deve essere una

TG4 Positivo

matrice sparsa.

>> x= gseidel(sprand(5,3,0.08),[ ??? Error using

1 2 3]); Parametro A invalido: deve essere una

TG5 Positivo

matrice quadrata.

Con matrice A avente elementi NaN o Inf

>> A = sprand(30,30,0.08); ??? Error using

>> A(3) = nan; A(6) = nan; Parametro A invalido: non deve contenere

TG6 Positivo

>> x = gseidel(A,1:30); valori NaN.

>> A = sprand(30,30,0.08); ??? Error using

>> A(6) = inf; Parametro A invalido: non deve contenere

TG7 Positivo

>> x = gseidel(A,1:30); valori Inf.

con matrice A che ha elementi nulli sulla diagonale

>> A = bucky; ??? Error using

>> x = gseidel(A, ones(60,1)); Parametro A invalido: la diagonale

TG8 Positivo

principale di A non deve avere valori

nulli.

Con vettore b non numerico

>> A = sparse([3,3; 0, 1]); ??? Error using

>> x = gseidel(A,‘fg’); Parametro b invalido: deve contenere solo

TG9 Positivo

numeri.

Con vettore b avente elementi NaN o Inf

>> A = sparse([3,3; 0, 1]); ??? Error using

TG >> b = [2 NaN]; Parametro b invalido: non deve contenere Positivo

10 >> x = gseidel(A,b); valori NaN.

>> A = sparse([3,3; 0, 1]); ??? Error using

TG >> b = [inf; 4]; Parametro b invalido: non deve contenere Positivo

11 >> x = gseidel(A,b); valori Inf.

Con matrice A e vettore b non compatibili

>> A = sparse([3,3, 0; 0, 1, 9; ??? Error using

0, 0, 2]); Le dimensioni dei parametri

TG >> b = [1; 4]; incompatibili; il numero di colonne di A Positivo

>> x = gseidel(A,b); deve essere pari al numero di elementi di

12 b.

Con TOL non numerico, scalare, reale

>> A = sparse([3,3, 0; 0, 1, 9; ??? Error using

0, 0, 2]); Parametro TOL invalido: deve essere un

TG >> b = [1; 4; 9]; numero. Positivo

13 >> x = gseidel(A,b,’h’);

>> x = gseidel(A,b,[7 8]); ??? Error using

TG Parametro TOL invalido: deve essere uno Positivo

14 scalare.

>> x = gseidel(A,b, 6+i*9); ??? Error using

TG Parametro TOL invalido: deve essere un Positivo

15 numero reale positivo. 8

Con TOL pari a NaN e inf

>> x = gseidel(A,b, nan); ??? Error using

TG Parametro TOL invalido: non deve essere Positivo

NaN.

16 >> x = gseidel(A,b, inf); ??? Error using

TG Parametro TOL invalido: non deve essere Positivo

Inf.

17

Con TOL non positivo

>> x = gseidel(A,b, -4); ??? Error using

TG Parametro TOL invalido: deve essere un Positivo

18 numero positivo.

>> x = gseidel(A,b, 0); ??? Error using

TG Parametro TOL invalido: deve essere un Positivo

19 numero positivo.

Con MAXITER non numerico, scalare, reale

>> x = gseidel(A,b,eps,’h’); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

20 un numero.

>> x = gseidel(A,b,eps,[7 8]); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

21 uno scalare.

>> x = gseidel(A,b,eps, i*3); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

22 un numero intero maggiore o uguale a 1.

Con MAXITER pari a NaN e inf

>> [x N] = gseidel(A,b,eps,NaN); ??? Error using

TG Parametro MAXITER invalido: non deve Positivo

23 essere NaN.

>> [x N] = gseidel(A,b,eps,- ??? Error using

TG inf); Parametro MAXITER invalido: non deve Positivo

24 essere Inf.

Con MAXITER minore di uno

>> x = gseidel(A,b,eps,-1); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

25 un numero intero maggiore o uguale a 1.

>> x = gseidel(A,b,eps,0.5); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

26 un numero intero maggiore o uguale a 1.

>> x = gseidel(A,b,eps,1-eps); ??? Error using

TG Parametro MAXITER invalido: deve essere Positivo

27 un numero intero maggiore o uguale a 1.

Con parametri coretti

>> A = gallery('poisson',4); N = 84

>> xvero = ones(size(A,1),1);

TG >> b= A*xvero; ans = 4.432209994207159e-016 Positivo

>> [x N] = gseidel(A,b);

28 >> N

>> norm(x-xvero)./norm(x)

>> [x N] = gseidel(A,b,10^(-2)); N = 10

TG >> N Positivo

>> norm(x-xvero)./norm(x) ans = 0.017715506197618

29 >> [x N] = gseidel(A,b,eps,1); Warning: GSEIDEL non converge per 1

>> N iterazioni con tolleranza 2.22045e-016

TG Positivo

30 N = 1

>> [x N] = gseidel(A,b,eps/2, Warning: Parametro TOL inaccettabile:

1000); deve essere maggiore o uguale all'epsilon

TG >> N macchina. Positivo

31 N = 84 9

pagerank :: Functions file:///D:/Universita/workspaceCN/Elaborati1/pagerank.html

pagerank

Calcola il rank dei nodi(pagine web) di una rete usando l’algoritmo del PageRank di Google.

Sintassi

R = pagerank(G, U)

[R, OUT, IN] = pagerank(G, U)

[R, OUT, IN, NITER] = pagerank(G, U)

Descrizione , calcola il rank di una rete(WEB), dove rappresenta la matrice logica sparsa delle adiacenze

R = pagerank(G, U) G

della rete (se allora c’è un link dal nodo al nodo , altrimenti) ed cell-array che contiene i nomi(URL)

G(i,j)=1 j i 0 U

dei nodi della rete. Restituisce il vettore ; se il metodo converge contiene i rank dei nodi(pagine).

R R

, restituisce anche e . vettore che contiene i corrispondenti outdegree

[R, OUT, IN] = pagerank(G, U) OUT IN OUT

dei nodi(pagine), ovvero il numero di link uscenti dal nodo. vettore che contiene i corrispondenti indegree dei

IN

nodi(pagine), ovvero il numero di link entranti al nodo.

, restituisce anche , il numero di iterazioni effettuate per il calcolo

[R, OUT, IN, NITER] = pagerank(G, U) NITER

del rank.

Esempio

U = {'node1' ,'node2', 'node3'};

G = logical(sparse([1 0 1; 1 0 1; 1 0 0]));

R = pagerank(G,U);

Indicatori d'errore

La routine genera warning:

Se il metodo non converge dopo 1000 iterazioni.

La routine genera errore:

Se il numero di parametri di input è insufficiente.

Se il numero di parametri di output è insufficiente.

Se il parametro non è una matrice logica quadratra sparsa.

G

Se il parametro non è un cell-array di stringhe.

U

Se le dimensioni dei parametri e non sono campatibili. La lunghezza di deve essere pari al numero di

G U U

colonne di .

G

Algoritmo

usa il metodo iterativo di Google per calcolare il rank di pagine web con matrice di adiacenza sparsa di

pagerank

grandi dimensioni, vedi http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf.

Esempi di funzionamento, funzione PAGERANK

Per gli esempi di funzionamento del pagerank sono stati utilizzate le matrici di adiacenza

princeton500 e princeton1000 che rappresentano i grafi delle prime 500 e 1000 pagine web

collegate al sito www.princeton.edu . Processore Intel® Core™ 2 Duo T7300 2GHz,

Il calcolatore utilizzato per i test è un laptop HP con

Memoria centrale 2048 MB, Sistema Operativo Windows 7 Professional, Matlab 7.9.0(R2009b)

Di seguito è riportato lo script per generare i grafici per princeton500:

% test di funzionamento PAGERANK con princeton500.mat

load princeton500;

figure(1);

spy(G);

title('Matrice di Adiacenza di princeton500');

R = pagerank(G,U);

% grafico a barra dei PageRank dei primi 15 siti web

[R, order] = sort(R, 'descend');

figure(2);

barh(1:15,R(15:-1:1));

title('Page Rank dei primi 15 Pagine Web di princeton500');

xlabel('Rank');

set(gca, 'YTickLabel', U(order(15:-1:1)));

% verifichiamo che la somma dei page rank sia 1

disp(['La somma dei page rank è ' num2str(sum(R))]);

Di seguito è riportato lo script per generare i grafici per princeton1000:

% test di funzionamento PAGERANK con princeton1000.mat

load princeton1000;

figure(3);

spy(G);

title('Matrice di Adiacenza di princeton1000');

R = pagerank(G,U);

% grafico a barra dei PageRank dei primi 15 siti web

[R, order] = sort(R, 'descend');

figure(4);

barh(1:15,R(15:-1:1));

title('Page Rank dei primi 15 Pagine Web di princeton1000');

xlabel('Rank');

set(gca, 'YTickLabel', U(order(15:-1:1)));

% verifichiamo che la somma dei page rank sia 1

disp(['La somma dei page rank è ' num2str(sum(R))]); 1


PAGINE

17

PESO

683.74 KB

AUTORE

Sara F

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2010-2011

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Sara F di informazioni apprese con la frequenza delle lezioni di Calcolo Numerico II e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof D'Amore Luisa.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Calcolo numerico ii

Calcolo Numerico II – Elaborato
Esercitazione
Calcolo Numerico II – Elaborato
Esercitazione
Teoria completa, Metodi Matematici per l'Ingegneria
Appunto
Geometria e Algebra - Determinanti
Dispensa