CN - curs 01 - 2012immobilier-montreal.net/upload/documents/292859.pdf · Săptămânânile 1-7 şi...

35
Calcul Numeric Cursul 1 2011-2012 Anca Ignat

Transcript of CN - curs 01 - 2012immobilier-montreal.net/upload/documents/292859.pdf · Săptămânânile 1-7 şi...

Calcul Numeric

Cursul 1

2011-2012

Anca Ignat

1

[email protected] , [email protected]

[email protected] – pentru temele de laborator

http://www.infoiasi.ro/~ancai/CN/

Consultaţii:

prin e-mail la adresa de mai sus sau

la cabinet (C-307), joi, 16-18

2

Regulament - 2011-2012

Laborator

8 teme

cei care prezintă temele până la termenul limită precizat la

fiecare temă, punctajul maxim ce poate fi obţinut este

punctajul afişat pentru fiecare temă

cei care prezintă temele după termenul limită precizat

punctarea se va face din 50% din punctajul temei prezentate

3

Examen

teză scrisă de 1 oră, cu 3 sau 4 exerciţii din materia predată,

˝cu cursurile pe masa˝ - exclusă documentaţia pe suport

electronic

teza scrisă este notată între 1 şi 10

prezenţa la examen este obligatorie chiar dacă s-a obţinut

punctaj de promovare doar din punctajul de la laborator

4

Calculul punctajului / notei final(e)

Punctaj final = punctaj laborator + 29*nota examen

Promovează disciplina acei studenţi care au:

nota la examen ≥ 3

şi

punctaj final ≥ 260 pt

Nota finală se calculează din punctajul final aplicând ”curba lui Gauss”.

5

Desfăşurarea semestrului

Săptămânânile 1-7 şi 9-15 – şcoală conform orarului

Prima săptămâna de evaluare – liber

Săptămâna 15

- prezentare teme de laborator restante

Săptămâna 15 sau 16 - examen

6

Bibliografie 1. Elemente de informatică şi calcul numeric, vol. 1 - C.Ignat,

C.Ilioi, T.Jucan - Ed. Univ. ‘Al. I. Cuza’ Iaşi, 1987 2. Calcul numeric în C - T. A. Beu - Ed. Albastră, Cluj, 2004 3. Metode numerice - V.Iorga, B.Jora - Ed. Albastră, Cluj, 2004 4. Numerical Recipes in C/C++ (www.nr.com) 5. Matrix Computations - G.H. Golub, C.F. van Loan - John

Hopkins Univ. Press, 1996 6. Numerical Analysis – R.L. Burden, J.D. Faires – Brooks/Cole,

Thomson Learning, 2001 7. Computing for numerical methods using Visual C++ - S. Salleh,

A.Y. Zomaya, S. Abu Baka – John Wiley & Sons, 2008 8. Numerical Optimization – J. Nocedal, S.J. Wright – Springer,

1999

7

Capitolele cursului

1. Rezolvarea sistemelor liniare (Ax=b)

2. Optimizare numerică ( min { F(x) ; x Œ Rn } )

3. Valori şi vectori proprii (Au = λu)

4. Ecuaţii neliniare (f(x)=0)

5. Interpolare numerică

8

Exemple

Web search – Google’s PageRank

- informaţii nestructurate, ‘self-organized’

- fără standarde, recenzenţi, ‘paznici’ ai conţinutului

- informaţie volatilă, eterogenă şi foarte diversă (conţinut,

structură, format, limbi, alfabete, scop)

- 1013 – pagini web (probabil mai multe) ???

9

Căutarea

roboţi web – parcurg permanent graful Web pentru informaţii

depozitul de pagini - memorează temporar paginile web

(paginile foarte populare sunt stocate perioade mai lungi)

modulul de indexare – se extrage din paginile depozitate

informaţia esenţială (cuvinte-cheie, fraze-cheie, descriptori) →

se obţine o versiune comprimată a paginii; în funcţie de

popularitatea paginii aceasta este fie ştearsă, fie păstrată în

depozitul de pagini

10

informaţiile esenţiale memorate despre orice pagină Web

index de conţinut - cuvinte sau fraze cheie, titlu (se

construieşte inverted file - similar indexului unei cărţi) index de structură hyperlink index de informaţii speciale – imagini, pdf

11

modul de interogare – transformă cererea din limbaj natural

într-un limbaj pentru motorul de căutare (de obicei numere); se

consultă informaţiile esenţiale memorate; se obţin paginile

relevante cererii (care conţin termeni din interogare). modulul de ‘ranking’(evaluare a relevanţei) – prelucrează

paginile relevante furnizate de modulul de interogare şi le

ordonează după anumite criterii (funcţie de motorul de

căutare); acest modul trebuie să discearnă care pagină Web

răspunde cel mai bine interogaţiei şi le ordonează;

12

PageRank este sistemul de evaluare a paginilor web din punctul

de vedere al importanţei, folosit de motorul de căutare Google.

Nota furnizată de PageRank este unul din factorii folosiţi

pentru a ordona paginile web atunci cand se face o căutare.

“PageRank is an important factor. It is one out of 200 signals

but still it is an important one for a large number of queries.”

(Matt Cutts – head of Google’s Webspam team)

13

Google dă cel puţin 2 ‘note’/’scoruri’ fiecărei pagini Web:

a. popularitate

b. conţinut – modul de calcul este secret – termenii din

interogare sunt în titlu sau în interiorul paginii, de câte

ori termenii apar în pagină, cât de aproape unii de alţii

sunt termenii din interogaţiile cu cuvinte multiple, cum

apar termenii de interogare (bold, subtitluri…),

conţinutul paginilor vecine

Nota/scorul finală cu care se face ordonarea este o medie ponderată

între notele de mai sus, componenta principală fiind popularitatea.

14

PageRank (Google) – S. Brin, L. Page (popularitate) Sergey Brin, Lawrence Page, R. Motwami, Terry Winograd – ‘The

PageRank citation ranking: bringing order to the Web’ –

Technical Report 1999-0120, Computer Science Department,

Stanford University, 1999

Ideea: O pagină este importantă dacă este referită (citată) de alte

pagini importante.

15

Importanţa unei pagini (PageRank-ul ei) este calculată sumând

PageRank-urile tuturor paginilor care citează pagina respectivă.

Dacă o pagină importantă citează mai multe pagini, atunci

importanţa ei se împarte egal paginilor pe care le citează.

Graful Web – cu n noduri.

daca pagina citeaza pagina altfel

10ij

j iI

cj = numarul de citari ale paginii j (outlink-urile paginii j)

ri = PageRank-ul paginii i

16

?1

(1 ) , 0 , 0.85n

iji j

j j

Ir d d r d d

c

(1)

Constanta d asigură faptul că fiecare pagina Web are un Pagerank

de cel puţin (1-d).

Relaţia (1) poate fi scrisă matricial astfel:

1(1 ) Tr d e d e I C r (2)

17

diag 1 2

11

, , , , ,

1

n n n n nij ne I I C c c c

Deoarece suma tututror Pagerank-urilor este 1 putem scrie:

11

nT

ii

r e r

.

11 T n ndA ee d I Cn

18

Relaţia (2) se poate scrie:

r Ar

Această relaţie ne spune că matricea A (matrice de dimensiuni

foarte mari şi rară) are valoarea proprie 1 iar vectorul de Pagerank-

uri este vectorul propriu asociat. Se poate folosi metoda puterii

pentru determinarea lui r.

19

Alte tehnici de CN folosite pentru PageRank: rezolvarea sistemelor

liniare, SVD (Singular Value Decomposition)

An Arnoldi-type Algortihm for Computing Page Rank, G.H. Golub, C.

Greif, BIT Numerical Mathematics, Springer, 2006

Fast Parallel PageRank: A Linear System Approach, D. Gleich, L.

Zhukov, P. Berkhin, WWW2005, May 10–14, 2005, Chiba, Japan

The Use of the Linear Algebra by Web Search Engines, A.N.Langville,

C.D. Meyer, 2004

(http://www.infoiasi.ro/~ancai/CN/bibliografie/)

20

Compresia imaginilor digitale si descompunerea după valori singulare

o imagine digitală ↔ matrice de pixeli A cu m linii şi n coloane

sau 31,...,1,...,

,ij iji mj n

A a a

( sau 30,1, ...,255 0,1, ...,255ij ija a )

Pentru memorarea lui A e nevoie de m·n·mem(int) = 2 m n bytes

Descompunerea dupa valori singulare (SVD) a unei matrici

, , ,T m m m n n nA U SV U S V

matrici ortogonale1 2 1 2, , ..., , , , ...,m nU u u u V v v v

21

daca daca

1, , , ,

0m ni j ij i j ij

i ju u v v i j

i j

1

2

0 0 00 0 0

0 0 0

0 0 0 0

m n

r

S

- valorile singulare ale matricii 1 2 0 , min{ , }r r m n A

22

1 1 1 2 2 2T T T

r r rA u v u v u v

1 1 1 2 2 2T T T

k k k kA A u v u v u v

memorarea lui Ak necesită k(m+n+1)·mem(double)

m=2448 , n=3264 , ( 1)c

mnrk m n

, r=2448

k=50 rc= 27.9722 ; k=100 rc= 13.9861 ; k=150 rc= 9.3241

k=200 rc= 6.9931 ; k=250 rc=5.5944 ; k=300 rc= 4.662

23

Vectori şi matrici

Fie xi , yi , . Se definesc vectorii , nx y şi operaţiile

de adunare şi înmulţire cu scalari astfel:

1 1 1 1 1

2 2 2 2 2, , ,

n n n n n

x y x y xx y x y x

x y x y x

x y x y x

.

24

Fie vectorul nz :

cu

1

21 2, , ..., .n

n

zz

z z z z

z

Pentru z utilizăm notaţiile:

z = a + ib , Re z = a, Im z = b , 2 2,z a ib z a b

25

Notăm cu m n / m n spaţiul matricilor cu elemente reale / complexe cu m linii şi n coloane

,11 1

1

, / 1,2, ..., , 1,2, ...,n

ij

m mn

a aA a i m j n

a a

26

Definiţie

X se numeşte spaţiu vectorial (spaţiu liniar)

+ : X X Æ X şi : K X Æ X,

astfel încât ( X , + ) este un grup comutativ :

a + b = b + a , a,b X – comutativitate,

(a + b) + c = a + (b + c) , a,b,c X – asociativitate ,

0 X a. î. a + 0 = 0 + a = a , a X - element neutru ,

a X, -a X a.î. a + (-a) = (-a) + a = 0 – element opus.

27

iar pentru operaţia de înmulţire cu scalari au loc relaţiile:

(a+b) = a + b , K , a,b X ,

( + ) a = a + a , , K , a X,

( a ) = ( )a , , K , a X,

1 K astfel încât 1 a = a , a X.

28

Definiţie Fie X un spaţiu liniar. Spunem că vectorii x1 , x2 , …, xp X

sunt liniar independenţi dacă:

1 1 2 2 1 2.. 0 ... 0p p p ix x x K

Spaţiul vectorial X este finit dimensional dacă există p

vectori liniar independenţi în X, x1 , x2 , …,xp X, şi orice

mulţime de q elemente din X cu q > p este liniar dependentă.

În acest caz dimensiunea spaţiului X este p (dim X = p).

29

Fie spaţiul vectorial X finit dimensional cu dim X = p. Orice

sistem de p vectori liniar independenţi din X se numeşte bază

a spaţiului X.

Fie x1 , x2 , …,xp X o bază pentru spaţiul X . Atunci pentru

x X , unice constantele 1, 2,…, p K astfel încât

1 1 2 21

..p

p p i ii

x x x x x

n este un spaţiu vectorial finit dimensional, dim n = n cu

baza canonică:

30

poziţia-1 2

01 0 0 00 1 0

, , , , ,1

0 0 10

k nke e e e

31

Calcul matricial Fie matricea m nA :

11 1

1 , 1

1

,n

ij i m j n

m mn

a aA A a

a a

Se defineşte matricea transpusă:

11 1

1 , 1

1

,m

T T n mji i m j n

n mn

a aA A a

a a

32

Pentru matricea: 1

1,m n

i mijj n

A A a

se defineşte matricea adjunctă AH:

11

11 1 11 1

1 1

,

H Tj njii m

n mH

m mn n mn

A A a

a a a aA A

a a a a

33

Pentru m nA matricea adjunctă coincide cu transpusa,

AH = AT.

Fie vectorul nx , acesta este considerat vector coloană, 1nx :

1

21 2

Tn

n

xx

x x x x x

x

34

Dacă facem înmulţirea matricială Aej obţinem coloana j a

matricii A:

poziţia

1

11 12

1

0

1

0

j

nj

j j

m mnmj

aa a

aAe

a aa

Aej este coloana j a matricii A, j=1,...,n ;

eiTA este linia i a matricii A, i=1,...,m.