FESB Split
Poslijediplomski doktorski studij elektrotehnike i informacijske tehnologije
Poslijediplomski doktorski studij strojarstva

MATRIČNI RAČUN I PRIMJENE

2011./2012.

Ivan Slapničar

UVOD
Numeričko rješavanje velikog broja problema koji se javljaju u znanstvenim i tehničkim primjenama svodi se na numeričko rješavanje sustava linearnih jednadžbi ili na računanje svojstvenih i singularnih vrijednosti i pripadnih vektora. Studenti će upoznati numeričke metoda linearne algebre koje se najčešće koriste u primjenama te steći sposobnost procjene točnosti metode, izrade vlastitih algoritama i korištenje gotovih programskih biblioteka. Posebno će se obraditi primjene na klasteriranje podataka i ekstrakciju znanja (data mining) i pretraživanje tekstualnih podataka.

SADRŽAJ I LITERATURA
Temeljne ideje linearne algebre: osnovni algoritmi na matricama, vektorske i matricne norme. Aritmetika računala. Sustavi linearnih jednadžbi: LU rastav (Gaussova eliminacija), rastav Choleskog, procjena i poboljšanje točnosti, iterativne metode. Problem najmanjih kvadrata (LS) i QR rastav. Problem vlastitih vrijednosti za simetrične matrice: tridijagonalizacija, QR metoda, Jacobijeva metoda. Rastav singularnih vrijednosti (SVD): bidijagonalizacija, SVD za bidijagonalne matrice. Brzo ažuriranje SVD rastava (updating i downdating). Klasteriranje podataka i ekstrakcija znanja pomoću Fiedlerovog vektora. Latentno semantičko indeksiranje (LSI). Primjena SVD rastava kod web pretraživača. Rangiranje rezultata (page rank).
Vježbe: Upoznavanje svih metoda ``na djelu'' izrađujući programe u paketima Octave ili Matlab i korištenje javno dostupnih visoko kvalitetnih programskih paketa BLAS (Basic Linear Algebra Subroutines) i LAPACK (Linear Algebra Package).
Literatura:
  1. G. H. Golub i C. F. Van Loan: Matrix Computations, 3rd Edition, John Hopkins University Press, Baltimore, Maryland, 1996.
  2. E. Anderson i drugi: LAPACK Users' Guide, 2nd Edition, SIAM, Philadelphia 1995.
  3. M. W. Berry, Z. Drmač, E. R. Jessup: Matrices, Vector Spaces and Information Retrieval, SIAM Review, 41 (1999) 335-362.
  4. A. N. Langville and C. D. Meyer. Deeper Inside PageRank. Internet Mathematics, Vol. 1(3):335-380, 2005. (pdf)
Detaljan sadržaj iz [1]:
1. DOMAĆI RAD
  1. Upoznavanje s Matlab-om i Octave-om
  2. Upoznavanje s numerikom računala
  3. Upoznavanje s metodom najmanjih kvadrata i QR rastavom
2. DOMAĆI RAD
  1. Pročitajte poglavlje 1.
  2. Pročitajte poglavlja 2.1, 2.2, 2.3, 2.4 i riješite zadatke: P2.1.1 - P2.1.5 (dva zadatka po volji), P2.3.1 - P2.3.10 (dva zadatka po volji).
  3. Pročitajte poglavlja 5.1, 5.2 i 5.3.
  4. Proučite sadržaj paketa BLAS - posebno proučite BLAS 1 rutine daxpy.f, zaxpy.f, dnrm2.f, dznrm2.f, scnrm2.f, te BLAS 3 rutinu dgemm.f.
  5. Proučite sadržaj paketa LAPACK.
    Proučite rutinu dgeqrf.f za računanje QR rastava i njenu strukturu (link na "dgeqrf.f. plus dependencies").
    Proučite rutine dgels.f i dgelsx.f za rješavanje problema najmanjih kvadrata i njihove pripadne strukture. Koja je razlika izmedju tih rutina?
3. DOMAĆI RAD
  1. Pročitajte poglavlja 2.7.2, 3.1, 3.2, 3.3 i 3.4.
  2. Usporedite rutinu dgecp.m s Matlab naredbama [l,u]=lu(a) i [l,u,p]=lu(a).
  3. Napišite glavni program za jednu od driver rutina za rješavanje sustava linearnih jednadžbi. Izvedite program i napišite kratki izvještaj. Usporedite rješenja s onima koja daje Matlab.

    Rutine se nalaze na stranici LAPACK Search Engine.
    Odaberite "Driver Routines", "Linear Equations".
    Odaberite opcije "Precision Real, Double", "With Dependencies", "Driver Type Simple".
    Odaberite jedan "Matrix & Storage Type" kako slijedi: General, Band, Tridiagonal, Symmetric Positive Definite, Sym. Pos. Def. Band, Sim. Pod. Def. Tridiagonal, Symmetric Indefinite.

    Primjeri glavnog programa su glavni.f i glavni1.f.

SOFTWARE I UPUTE
MFILES