aproximari de functii utilizand polinoame de grade foarte mari si aplicatii
Click here to load reader
Post on 21-Jan-2016
68 views
Embed Size (px)
DESCRIPTION
Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii. Supervizor : Prof. Dr. Ing . Octavian CRET Autor : Filip Silviu-Ioan. Cuprins. Justificare si obiectivele proiectului Solutii existente Solutia propusa Implementare si testare Rezultate si concluzii. - PowerPoint PPT PresentationTRANSCRIPT
Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii
Aproximari de functii utilizand polinoame de grade foarte mari si aplicatiiSupervizor: Prof. Dr. Ing. Octavian CRET
Autor: Filip Silviu-IoanCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii
Justificare si obictivele proiectuluiTeoria aproximarilor numerice sta la baza calculelor din multe din domeniile de activitate curente (cercetari stiintifice, inginerie, finante, etc.)
Numerele utilizate sunt reprezentate in formate cu precizie limitata (virgula fixa, virgula mobila, etc.) aritmetici specializate pe aceste formate
Starea actualaJustificare si obictivele proiectuluiDorinta de a studia comportamentul metodelor existente de aproximare a functiilor numerice in vederea extinderii acestora in alte domenii, cum ar fi procesarea semnalelor digitaleOferirea unor metode de calcul numeric cat mai preciseMotivatiaCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii
Solutii existenteNumeroase rezultate teoretice si practice (dezvoltare Taylor, alg. Remez, etc.)Sunt usor de stocat in memoriePermit o evaluare eficienta prin utilizarea:Schemei lui HornerOperatiei de adunare inmultire fuzionate FMA
Q: Este chiar asa de usor?A: De fapt, NU.De ce polinoame?Solutii existenteAmintim:sistemele de calcul pot reprezenta doar un subset finit de numere reale, stocate de obicei in virgula mobila;Constrangerile hardware si de eficienta pot forta coeficientii aceluiasi polinom sa:Utilizeze formate diferiteSa aiba precizii diferiteSa aiba valori fixate trebuie luate in calcul spatiu finit de cautare al polinoamelorConstrangeri(1)Solutii existenteConstrangeri(2)CuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii
Solutia propusaTine cont de toate constrangerile foloseste rezultate din teoria retelelor laticiale euclidiene
Se reduce la a rezolva o problema de tip CVP (Closest Vector Problem)Prezentare generalaSolutia propusa
Exemplu: Reteaua generata de vectorii (2, 1) si (0, 2)Solutia propusa
Exemplu: CVPSolutia propusa
Exemplu: CVPSolutia propusaProblema NP-dura algoritmi de rezolvare exponentiali, intractabili pentru dimensiuni mari utilizam algoritmi rapizi, mai imprecisiAlgoritmul lui Babai: porneste de la o retea generata de vectori foarte scurti problema SVP (Shortest Vector Problem) rezolvabila cu algoritmul LLL.Rezolvarea problemei CVPSolutia propusaArhitectura (fluxul de executie al aplicatiei)Generator puncte de interpolareModelator constrangeri coeficientiGenerator baza retea laticialaRezolvitor CVP (alg. Babai)Generator coeficienti polinom de aproximareFunctia de aproximatMapare interval de aproximare pe cercul trigonometric + determianare puncte egal distantate pe cercReducere problema la lucru cu intregi (se elimina erorile de rotunjire)Aplicare algoritm Babai (LLL)Rezolvare sistem de ecuatii liniare ce determina valorile coeficentilorCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii
Implementare si testareGenerator puncte de interpolareModelator constrangeri coeficientiGenerator baza retea laticialaTehnologii folosite (C/C++)Librariile GMP si MPFR pentru calcule cu numere intregi si in virgula mobila de precizie arbitrareRezolvitor CVP (alg. Babai)Libraria fplll ce contine implementari foarte rapide pentru algoritmii LLL si BabaiGenerator coeficienti polinom de aproximareLibrariile ATLAS si IML pentru rezolvare de sisteme liniare intregi de grad foarte mareImplementare si testareEvaluare si testareCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii
Rezultate si concluziiCalcularea certificata: utilitarul Sollya
Evolutia eroriiVa multumesc pentru atentie!Intrebari? Sugestii?