+ All Categories
Home > Documents > Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii

Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii

Date post: 21-Jan-2016
Category:
Upload: milly
View: 73 times
Download: 0 times
Share this document with a friend
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 Presentation
21
Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii Supervizor: Prof. Dr. Ing. Octavian CRET Autor: Filip Silviu-Ioan
Transcript
Page 1: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Aproximari de functii utilizand polinoame de grade foarte mari si

aplicatii

Supervizor: Prof. Dr. Ing. Octavian CRET

Autor: Filip Silviu-Ioan

Page 2: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Cuprins

• Justificare si obiectivele proiectului• Solutii existente• Solutia propusa• Implementare si testare• Rezultate si concluzii

Page 3: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Justificare si obictivele proiectului

Teoria 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 actuala

Page 4: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Justificare si obictivele proiectului

• Dorinta de a studia comportamentul metodelor existente de aproximare a functiilor numerice in vederea extinderii acestora in alte domenii, cum ar fi procesarea semnalelor digitale

• Oferirea unor metode de calcul numeric cat mai precise

Motivatia

Page 5: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Cuprins

• Justificare si obiectivele proiectului• Solutii existente• Solutia propusa• Implementare si testare• Rezultate si concluzii

Page 6: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutii existente

• Numeroase rezultate teoretice si practice (dezvoltare Taylor, alg. Remez, etc.)

• Sunt usor de stocat in memorie• Permit o evaluare eficienta prin utilizarea:

• Schemei lui Horner• Operatiei de adunare inmultire fuzionate FMA

Q: Este chiar asa de usor?A: De fapt, NU.

De ce polinoame?

Page 7: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutii existente

Amintim:• 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 diferite• Sa aiba precizii diferite• Sa aiba valori fixate

→ trebuie luate in calcul → spatiu finit de cautare al polinoamelor

Constrangeri(1)

Page 8: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutii existente

Exemplu: Aproximati in eroare absoluta cu un polinom cu coeficienti in virgula mobila cu simpla precizie (24 biti)

Legenda: cel mai bun polinom de aproximare cu coeficienti reali (alg. Remez)obtinut din prin rotunjirea coeficientilor la simpla precizie obtinut printr-o metoda specializata la constrangeri (alg. Fpminimax)

→ pierdere calitate aproximare (rotunjire). Se poate mult mai bine: aici acuratete crescuta cu 3.65 biti prin folosirea lui

polinom

Constrangeri(2)

Page 9: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Cuprins

• Justificare si obiectivele proiectului• Solutii existente• Solutia propusa• Implementare si testare• Rezultate si concluzii

Page 10: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusa

Tine 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 generala

Page 11: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusaExemplu: Reteaua generata de vectorii (2, 1) si (0, 2)

Page 12: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusaExemplu: CVP

Page 13: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusaExemplu: CVP

Page 14: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusa

Problema 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 CVP

Page 15: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Solutia propusaArhitectura (fluxul de executie al aplicatiei)

Generator puncte de interpolare

Modelator constrangeri coeficienti

Generator baza retea laticiala

Rezolvitor CVP (alg. Babai)

Generator coeficienti polinom de aproximare

Functia de aproximat Mapare interval de aproximare pe cercul

trigonometric + determianare puncte

egal distantate pe cercTransformare fiecare coeficient in forma mantisa exponent

Reducere problema la lucru cu intregi (se elimina erorile de

rotunjire)Aplicare

algoritm Babai (LLL)

Rezolvare sistem de ecuatii liniare ce determina valorile coeficentilor

Page 16: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Cuprins

• Justificare si obiectivele proiectului• Solutii existente• Solutia propusa• Implementare si testare• Rezultate si concluzii

Page 17: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Implementare si testare

Generator puncte de interpolare

Modelator constrangeri coeficienti

Generator baza retea laticiala

Tehnologii folosite (C/C++)

Librariile GMP si MPFR pentru calcule cu numere intregi si in virgula mobila de

precizie arbitrare

Rezolvitor CVP (alg. Babai)

Libraria fplll ce contine implementari foarte rapide

pentru algoritmii LLL si Babai

Generator coeficienti polinom de aproximare

Librariile ATLAS si IML pentru rezolvare de

sisteme liniare intregi de grad foarte mare

Page 18: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Implementare si testare

Functii de aproximat:• , pe intervalul coeficienti intregi, grade • pe intervalul , coeficienti intregi, grade , ,

Evaluare:• Eroarea absoluta

Evaluare si testare

Page 19: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Cuprins

• Justificare si obiectivele proiectului• Solutii existente• Solutia propusa• Implementare si testare• Rezultate si concluzii

Page 20: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Rezultate si concluzii

Calcularea certificata: utilitarul Sollya

Evolutia erorii

Functia

Page 21: Aproximari  de  functii utilizand polinoame  de grade  foarte mari si aplicatii

Va multumesc pentru atentie!

Intrebari? Sugestii?


Recommended