Învățământ < < <

Metode Numerice

Anul II, semestrul II

Prezentarea cursului

Structura cursului

Observații

Programa analitică

Suport pentru curs

Seminarii

Laborator

Subiecte date la examen

Prezentarea cursului
   Cursul universitar de Metode Numerice este o componentă importantă a a planului de învățământ al Facultății de Automatică și Calculatoare a Universitații Politehnica din București. Această prezentare se referă la cursul destinat studenților anului II de la secția de Automatică și Informatică Industrială, care are unele aspecte specifice în raport cu cursul omonim predat studenților secției de Calculatoare. Principalele obiective ale cursului de Metode Numerice sunt urmatoarele:
1. cunoașterea problematicii calculului științific modern;
2. expunerea, în manieră eminamente algoritmică, a metodelor de rezolvare a problemelor fundamentale de calcul din algebra matriceala;
3. dezvoltarea unei gândiri algoritmice la studenți, abordarea ordonată, structurală a problemelor de calcul, alegerea celor mai bune metode de calcul disponibile și expunerea într-o manieră clară, concisă și exactă a procesului de calcul;
4. conștientizarea faptului că întotdeauna datele inițiale sunt afectate de erori, că fiecare operație aritmetică este realizată cu un anumit nivel de precizie și că, în aceste condiții, obținerea unui rezultat numeric de o anumită acuratețe în urma unui proces de calcul de o lungime semnificativă nu este o problema simplă; în particular semnalarea faptului că multe metode tradiționale de calcul din matematica "clasica" eșuează în astfel de condiții;
5. cunoașterea celor mai performante produse software disponibile la momentul;
   Precizăm că restrângerea la prezentarea metodelor de rezolvare a problemelor fundamentale de calcul din algebra liniară este motivată, în primul rând, de faptul că acestea constituie primele și, de cele mai multe ori, principalele componente ale metodelor numerice de analiză și sinteză a sistemelor automate (un obiectiv de bază al pregătirii studenților de la secția de Automatică și Informatică Industrială) dar și a celor mai diverse aplicații din alte domenii inginerești, precum și din economie și numeroase alte ramuri ale științei.
   Pentru înțelegerea noțiunilor prezentate, cursantul trebuie să posede cunoștințe minime de matematică, în special de algebră liniară, la nivelul celor dobândite în liceu sau în primul an de facultate. De asemenea, pornim de la premiză că studentul este capabil să se exprime "fluent" într-un limbaj de programare de nivel înalt.
   Cursul este structurat în cinci parți, descrise succint mai jos.
   Prima parte prezintă specificul calculului numeric: reprezentarea numerelor reale în virgula mobilă, proprietățile (uneori neașteptate ale) operațiilor cu astfel de numere precum și mecanismele de apariție inevitabilă a erorilor numerice. Este apoi considerată perechea formată din problema de calcul și algoritmul de rezolvare, relativ la care sunt definite noțiunile fundamentale de condiționare și, respectiv, stabilitate numerică.
   Partea a doua tratează metodele directe de rezolvare a sistemelor liniare Ax = b, cu matricea A nesingulară. Sunt expuse metodele de rezolvare prin substituție numerică a sistemelor triunghiulare. Pentru cazul general se prezintă procedura de eliminare gaussiană, inclusiv strategiile de pivotare adecvate, precum și versiunile compacte ale acestei metode bazate pe factorizarea LU a matricei A. în afara matricelor de formă generală, sunt studiate și cazurile, des întâlnite în practică, ale sistemelor simetrice și simetrice pozitiv definite. De asemenea, sunt abordate probleme conexe, cum ar fi calculul inversei și al determinantului.
   Partea a treia descrie metodele de rezolvare în sensul celor mai mici patrate (CMMP) a sistemelor liniare Ax = b, în care numarul ecuațiilor diferă de cel al necunoscutelor, deci A este o matrice dreptunghiulară de formă generală. Sistemele liniare de acest tip apar frecvent în prelucrarea datelor experimentale, statistică, identificarea sistemelor etc. în acest caz se utilizează metode de "eliminare" specifice, bazate pe aplicarea transformărilor ortogonale (reflectori Householder, rotații Givens etc.) iar conceptul central este cel de factorizare QR. Daca matricea A nu este de rang maxim, se recomandă utilizarea factorizarii ortogonale complete, care are la baza un algoritm de triangularizare cu pivotarea coloanelor.
   Partea a patra expune principalele metode de calcul al valorilor și vectorilor proprii ai unei matrice pătrate A. Cunoașterea valorilor proprii este utilă în analiza stabilității sistemelor dinamice și în multe alte probleme aplicative majore. Se prezintă pe larg algoritmul QR, care aduce, prin transformări ortogonale de asemanare, matricea A la forma Schur, reală sau complexă, pornind de la forma de principiu a algoritmului și ajungând la variantele relativ sofisticate sub care acesta este implementat în programele profesionale. Alături de cazul general este tratat și cel al matricelor simetrice.
   Partea a cincea prezintă metodele de calcul al descompunerii valorilor singulare (DVS). Algoritmul DVS este o adaptare ingenioasă a algoritmului QR simetric, prezentat în partea a patra, și constituie instrumentul numeric cel mai sigur de rezolvare a numeroase probleme din algebra matriceală, cum ar fi determinarea rangului, calculul unor norme matriceale, construcția bazelor pentru diverse subspații, rezolvarea în sensul celor mai mici patrate a sistemelor cu matrice de rang nemaxim.
   Expunerile constau, în general, într-o formulare exactă a problemei de calcul în discuție, informații despre condiționarea acesteia, amintirea unor rezultate matematice fundamentale care stau la baza metodelor de rezolvare. Rezultatele expunerilor sunt concretizate sub forma de algoritmi de calcul descriși într-un pseudocod extrem de apropiat de implementarea directa într-un limbaj de programare de nivel înalt. Pentru majoritatea algoritmilor sunt precizate proprietațile de stabilitate numerică.
   De asemenea, sunt prezentate rutine (funcții) din biblioteca LAPACK (Linear Algebra PACKage) și din limbajul MATLAB (MATrix LABoratory), reprezentative pentru problemele de calcul studiate.
   Seminarul urmarește aprofundarea problemelor prezentate la curs prin stabilirea unor versiuni și alternative algoritmice la soluțiile problemelor din curs, elaborarea algoritmilor pentru diverse cazuri particulare și rezolvarea unei multitudini de probleme, unele cu un pronunțat caracter aplicativ. Se are în vedere în mod deosebit asigurarea unei ridicate eficiențe algoritmilor elaborați și gestionarea judicioasă a spațiului de memorie disponibil.
   Laboratorul are ca principal obiectiv efectuarea unor experimente numerice care să confirme corectitudinea și performanțele numerice ale algoritmilor fundamentali prezentați la curs. Ca obiective secundare menționăm cunoașterea aprofundată a mediului de programare MATLAB, a funcțiilor MATLAB care rezolvă problemele abordate la curs, compararea performanțelor propriilor programe MATLAB cu cele ale funcțiilor MATLAB corespondente. Precizăm că efectuarea tuturor lucrărilor de laborator este o condiție obligatorie pentru acceptarea prezentării la examen.
   Examinarea constă dintr-o apreciere a activitații pe parcursul semestrului (prezența la curs, prezența și gradul de participare la activitățile de la seminar, activitatea la laborator și rezultatul colocviului de laborator) ­ cu o pondere de 30% din total ­ și un examen scris ­ cu o pondere de 70%.
   Examenul scris constă în rezolvarea unui număr de probleme (vezi exemple de subiecte de examen) cu acces la orice sursa de informație proprie (cărți, notițe etc.) adusă de student în sala de examen.
   La cererea explicită a studenților se poate organiza un examen parțial. In cazul organizării unui examen parțial rezolvarea unor probleme de la examenul final poate necesita cunoștințe care au facut obiectul examenului parțial.
   Orice schimb de informații între studenți în timpul examenului, indiferent de momentul constatării (în timpul desfășurării examenului sau în timpul corecturii) se sancționează cu pierderea examenului. Se sancționează atât sursa cât și destinatarul schimbului de informații.
Structura cursului
  • Facultatea: Automatică și Calculatoare
  • Secția: Automatică și Informatică Industrială
  • Anul II, semestrul II
  • Puncte de credit: 5
  • Numar de ore :
curs: 42 ore (3 ore pe săptămână)
seminar: 14 ore (1 ore pe săptămână)
laborator: 14 ore (1 ore pe săptămână)
total: 70 ore
  • Titulari:
prof.dr.ing. Corneliu Popeea
prof.dr.ing. Boris Jora
prof.dr.ing. Bogdan Dumitrescu
  • Condiționări: cursul de Algebră liniară (anul I)
  • Modalitatea de apreciere și notare:
participarea la cursuri: 10 puncte
activitatea la seminar: 10 puncte
activitatea la laborator: 10 puncte
examen parțial: 30 puncte
examen final: 40 puncte
total: 100 puncte
Observații
1. Efectuarea tuturor lucrărilor de laborator este o condiție obligatorie pentru accesul la examenul final.
2. Examenul parțial se organizează numai la solicitarea explicită a majorității simple a studenților.
3. Examenul parțial este un examen scris din materia predată până la data desfașurării parțialului.
4. Examenul final este un examen scris din materia predată care nu a fost examinată la examenul parțial. Daca nu se organizează examenul parțial, atunci examenul final se dă din toata materia predată, iar punctajul este de 70 puncte. Daca se organizează examenul parțial, atunci este posibil ca rezolvarea unor probleme de la examenul final să necesite cunoștințe din materia examinată la parțial.
5. In timpul desfașurării examenelor scrise studenții au acces la orice sursă documentară personală scrisă - carți, notițe, fițuici etc.
6. Orice schimb de informații între studenți în timpul examenelor scrise, indiferent de momentul constatării (în timpul desfășurării examenului sau în timpul corecturii) se sancționează cu pierderea examenului. Se sancționează atât sursa cât și destinatarul schimbului de informații.
Programa analitică
1. Problematica metodelor moderne de calcul științific. Reprezentarea informației numerice în calculator. Formatul virgulă mobilă. Aritmetica în format virgulă mobilă. Condiționarea problemelor de calcul numeric și stabilitatea numerică a algoritmilor. 6 ore
2. Metode directe de rezolvare a sistemelor liniare. Condiționarea sistemelor liniare. Sisteme triunghiulare. Eliminarea gaussiană. Tehnici de pivotare. Factorizari LU (Crout, Cholesky). Versiuni bloc. Calculul determinantului și a inversei unei matrice. 9 ore
3. Problema celor mai mici patrate. Transformări ortogonale. Reflectori și rotații. Triangularizare ortogonală. Factorizare QR. Rezolvarea în sens CMMP a sistemelor liniare supradeterminate și subdeterminate. Calcul de baze ortogonale pentru subspații liniare. Calculul pseudoinversei. 9 ore
4. Calculul valorilor și vectorilor proprii. Forma Schur reală. Tehnici de deflație. Metoda puterii și metoda puterii inverse. Algoritmul QR. Algoritmul QR simetric. 9 ore
5. Descompunerea valorilor singulare. Algoritmul DVS. Calculul rangului unei matrice. Rezolvarea problemei generale a celor mai mici patrate. Alte aplicații ale DVS. 9 ore
Seminarii
 
   Număr de ore: 14 (7 ședințe a 2 ore)
 
   Lista seminariilor:
 
1. Calcule matriceale elementare.
2. Rezolvarea directă a sistemelor liniare determinate. Eliminarea gaussiană. Factorizari LU. Calculul inversei și al determinantului.
3. Transformări ortogonale: reflectori și rotații. Triangularizare ortogonală. Factorizarea QR.
4. Problema celor mai mici patrate (CMMP). Rezolvarea în sens CMMP a sistemelor liniare supradeterminate și subdeterminate.
5. Calculul valorilor și vectorilor proprii.
6. Calculul descompunerii valorilor singulare și aplicații.
7. Rezolvarea unor probleme tip pentru examen.
 
   Modul de desfășurare a seminariilor:
 
   Prezența studenților la seminarii nu este obligatorie, dar este cuantificată în punctajul acordat activității de la seminar. Seminariile se doresc a fi dezbateri deschise ale problemelor tratate la curs în următoarele scopuri:
 
  • lămurirea tuturor aspectelor legate de înțelegerea de către studenți a materiei predate la curs;
  • rezolvarea unor probleme reprezentative pentru materia predată la curs;
  • rezolvarea unor probleme de calcul numeric cu caracter aplicativ în diverse domenii;
  • rezolvarea unor probleme de tipul celor care sunt date la examen.
 
   Orice student are dreptul să solicite cadrului didactic lămurirea oricăror aspecte tehnice și științifice legate de subiectele programate pentru seminarul respectiv. Utilitatea seminariilor pentru studenți este în proporție covârșitoare condiționată de pregătirea lor pentru seminar.
 
   Rezolvarea problemelor propuse la fiecare seminar va fi făcută exclusiv de studenți, sub îndrumarea cadrului didactic. În nici un caz seminarul nu se va transforma într-o ședința de rezolvare a unor probleme de către cadrul didactic.
 
   Modalitatea de apreciere și notare:
 
   Punctajul acordat pentru activitatea de la seminar va reflecta, în proporții egale, urmatoarele:
 
  • participarea activa la dezbaterile din cadrul seminariilor;
  • prezența la seminarii.
 
   La cererea explicită a studenților se pot organiza seminarii suplimentare pe teme propuse de studenți numai dacă participarea medie la seminariile ordinare depașește 50% din efectiv.
 
Laborator
 
   Sediu: Sala ED 205
 
   Dotare: Rețea de 16 calculatoare PC (800MHz,HDD 10G,....)
 
   Numar de ore: 14 (7 ședințe a 2 ore)
 
   Lista lucrarilor de laborator:
 
1. Prezentarea mediului de lucru MATLAB
2. Rezolvarea sistemelor liniare determinate. Sisteme triunghiulare. Eliminare gaussiană
3. Calculul factorizării LU. Calculul inversei și al determinantului
4. Triangularizare ortogonală cu reflectori. Factorizare QR. Problema celor mai mici patrate
5. Calculul valorilor proprii
6. Descompunerea valorilor singulare
7. Colocviu de laborator
 
   Modul de desfășurare a laboratoarelor:
 
   Studenții au obligația de a se pregăti acasă pentru lucrarea de laborator curentă. Cadrul didactic care conduce ședința de laborator are libertatea de a testa acest lucru prin sondaj, scurte lucrări de control etc. și de a refuza participarea la ședință a studenților nepregătiți.
 
   În timpul ședințelor de laborator, fiecare student, în mod individual, va edita, corecta și testa programele MATLAB de implementare a algoritmilor de calcul numeric din lucrarea respectivă. Sarcinile studentului la ședința curentă de laborator vor fi considerate realizate numai dacă funcționalitatea programelor elaborate a fost prezentată cadrului didactic.
 
   Fiecare program elaborat de studenți va purta obligatoriu un antet-comentariu care va cuprinde:
 
  • identitatea studentului
  • data elaborării programului
  • informații minimale despre problema rezolvată:
    • ce problemă se rezolva
    • cum se rezolva (metoda folosită)
    • datele de intrare
    • datele de ieșire
 
   Studentul are dreptul să solicite cadrului didactic lămurirea oricaror aspecte tehnice și științifice legate de lucrarea respectivă.
 
   Fiecare lucrare de laborator este prevăzută cu sarcini pentru acasă care fac parte integrantă din lucrarea respectivă. Studenții care nu dispun acasă sau la camin de echipamentele de calcul necesare pentru realizarea acestor sarcini pot utiliza calculatoarele puse la dispoziția studenților de către decanatul facultații (sala EF013) și, în caz de suprasolicitare a acestora, tehnica de calcul din laboratorul de Metode Numerice (în afara orelor ocupate cu activități didactice).
 
   Modalitatea de apreciere și notare:
 
   Pentru a putea participa la examen studentul trebuie să efectueze toate lucrările de laborator și să aibe o notă finală la laborator de minimum cinci.
 
   Nota de la laborator va reflecta, în proporții egale, următoarele:
 
  • activitatea pe parcurs (pregătirea de acasă pentru fiecare ședință, activitatea din timpul ședințelor de laborator, realizarea sarcinilor pentru acasă); în acest scop fiecare student va prezenta la colocviul de laborator un dosar (o dischetă) cu toate programele realizate de el pe parcursul semestrului.
  • rezultatul colocviului de laborator; colocviul va consta din rezolvarea individuală, pe calculator, a unei probleme (simple - vezi exemplele prezentate) de calcul numeric.
 
   Studenții sunt obligați să participe la ședințele de laborator conform programării din orar. NU se organizează ședințe de refaceri de lucrări de laborator. În modul cu totul excepțional, având motive întemeiate, un student poate efectua o lucrare de laborator cu o altă subgrupă, în spațiul de timp de două săptămâni afectat lucrării respective.
Subiecte date la examen
 
   Exemple de subiecte date la examen se găsesc în secțiunea de download a acestui site.