Post on 07-Nov-2015
description
Calcul Numeric
Cursul 1
2015
Anca Ignat
1
ancai@info.uaic.ro , olariu@info.uaic.ro
cn@fenrir.infoiasi.ro pentru temele de laborator
http://www.infoiasi.ro/~ancai/CN/
Consultaii:
prin e-mail la adresa de mai sus sau la cabinet (C-307)
2
Regulament - 2015
Laborator
8 teme cei care prezint temele pn la termenul limit precizat la
fiecare tem, punctajul maxim ce poate fi obinut este
punctajul afiat 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 exerciii din materia predat, cu cursurile pe masa - exclus documentaia pe suport
electronic
teza scris este notat ntre 1 i 10 prezena la examen este obligatorie chiar dac s-a obinut
punctaj de promovare doar din punctajul de la laborator
4
Calculul punctajului / notei final(e)
Punctaj final = punctaj laborator + 42*nota examen
Promoveaz disciplina acei studeni care au:
nota la examen 3 i
punctaj final 375 pt Nota final se calculeaz din punctajul final aplicnd curba lui Gauss.
5
Desfurarea semestrului
Sptmnnile 1-7 i 9-15 coal conform orarului
Sptmna 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 Iai, 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. Ecuaii neliniare (f(x)=0)
5. Interpolare numeric
8
9
Exemple
Centralitate n reelele sociale
- noiune introdus de A. Bavelas n 1948 studiind comunicarea ntre oameni
(V, E) graful care modeleaz reeaua, A matricea de adiacen asociat, , 1( )
Nij i jA a , N=|?|
- care sunt cele mai importante noduri din reea?
10
1. Centralitate de grad (degree centrality) se bazeaz pe noiunea de grad/grade asociate nodurilor n grafuri
Se numete drum geodesic ntre dou vrfuri orice drum de lungime minim (numr minim de muchii) dintre cele 2 vrfuri.
2. Centralitate de apropiere (closeness centrality)
Centralitatea de apropiere a unui nod este suma lungimilor drumurilor geodesice de la nodul respectiv la toate celelalte noduri.
11
3. Centralitate de interrelaie (betweennes centrality)
,,
( )( ) sts v t sts t V
n vb vn
unde nst este numrul total de drumuri geodesice ntre nodurile s i t, iar nst(v) este numrul de drumuri geodesice care trec prin nodul v.
- msoar controlul pe care l deine nodul v n circulaia informaiilor n reea
12
4. Centralitate de vector propriu (eigenvector centrality)
- se ine cont de faptul c nu toate muchiile (conexiunile) sunt la fel de importante (ca n cazul centralitii de grad)
- conexiunile ctre persoane influente vor mprumuta importan mai mare dect conexiunie ctre persoanele mai puin influente
x(i) = centralitatea de vector propriu a nodului vi
13
o constanta( ) 1
1 1( ) ( ) ( ) , 0i
N
ijj v j
x i x j a x j ( (1), (2), ... , ( ))Tx x x x N
1x Ax Ax x A>0 - valoarea proprie Perron (cea mai mare valoare proprie) , x vectorul propriu asociat
14
Compresia imaginilor digitale i 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 sau (3)0,1ija ) Memorarea lui A: mnmem(int/double)(3) 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
15
daca daca1, , , ,0m ni j ij i j iji ju u v v i ji j 1
2
0 0 00 0 0
0 0 0
0 0 0 0
m n
r
S
- valorile singulare ale matr. 1 2 0 , min{ , }r r m n A
16
1 1 1 2 2 2T T T
r r rA u v u v u v 1 1 1 2 2 2
T T Tk k k kA A u v u v u v
memorarea lui Ak necesit k(m+n+1)mem(double)
m=1200, n=1600 , ( 1)c
mnrk m n
, k=50 rc= 13.7094 ; k=100 rc= 6.8547; k=150 rc= 4.5698
k=200 rc= 3.4273; k=250 rc=2.7419; k=300 rc= 2.2849
17
Vectori i matrici
Fie xi , yi , . Se definesc vectorii , nx y i operaiile de adunare i nmulire 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
.
18
Fie vectorul nz :
cu
1
21 2, , ..., .n
n
zz
z z z z
z
Pentru z utilizm notaiile: z = a + ib , Re z = a, Im z = b ,
conjugatul numarului
- modulul numarului complex 2 2z a ib z
z a b z
19
Notm cu m n / m n spaiul 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
20
Definiie
X se numete spaiu vectorial (spaiu liniar)
+ : X X X i : K X X, ( )K astfel nct ( 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.
21
iar pentru operaia de nmulire cu scalari au loc relaiile:
(a+b) = a + b , K , a,b X , ( + ) a = a + a , , K , a X, ( a ) = ( )a , , K , a X, 1 K astfel nct 1 a = a , a X.
22
Definiie Fie X un spaiu liniar. Spunem c vectorii x1 , x2 , , xp X sunt liniar independeni dac:
1 1 2 2 1 2.. 0 ... 0p p p ix x x K Spaiul vectorial X este finit dimensional dac exist p
vectori liniar independeni n X, x1 , x2 , ,xp X, i orice mulime de q elemente din X cu q > p este liniar dependent.
n acest caz dimensiunea spaiului X este p (dim X = p).
23
Fie spaiul vectorial X finit dimensional cu dim X = p. Orice
sistem de p vectori liniar independeni din X se numete baz
a spaiului X.
Fie x1 , x2 , ,xp X o baz pentru spaiul X . Atunci pentru x X , unice constantele 1, 2,, p K astfel nct
1 1 2 21
..p
p p i ii
x x x x x
24
n este un spaiu vectorial finit dimensional, dim n = n cu
baza canonic:
poziia-1 2
01 0 0 00 1 0
, , , , ,1
0 0 10
k nke e e e
25
Calcul matricial Fie matricea m nA :
11 1 1 , 11
,n
ij i m j n
m mn
a aA A a
a a
Se definete matricea transpus:
11 1 1 , 11
,m
T T n mji i m j n
n mn
a aA A a
a a
26
Pentru matricea: 11
,m n i mijj n
A A a
se definete 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
Pentru m nA matricea adjunct coincide cu transpusa, AH = AT.
27
Fie vectorul nx , acesta este considerat vector coloan, 1nx :
1
21 2
Tn
n
xx
x x x x x
x
28
Dac facem nmulirea matricial Aej obinem coloana j a
matricii A:
poziia
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.
29
Fie vectorii x, y, cu ajutorul lor definim produsele scalare n
in n :
1 1
2 2
1
21 2
1
,
,
n n
n n
nH
i i ni
n
x yx y
x y
x yxx
x y x y y x y y y
x
30
1 1
2 2
1
21 2
1
,
,
n n
n n
nT
i i ni
n
x yx y
x y
x yxx
x y x y y x y y y
x
31
Proprietile matricii AH Proprieti ale matricii AT
1. (A + B)H = AH + BH (A + B)T = AT + BT 2. (AH)H = A (AT)T = A 3. (AB)H = BH AH (AB)T = BT AT 4. (A-1)H = (AH )-1 (A-1)T = (AT )-1