Teorija aproksimacije

U matematici, teorija aproksimacije se bavi načinom na koji se funkcije najbolje mogu aproksimirati jednostavnijim funkcijama, i kvantitativnim karakterisanjem grešaka koje su time uvedene. Treba imati na umu da ono što se podrazumeva najboljim i jednostavnijim zavisi od aplikacije. Blisko srodna tema je aproksimacija funkcija generalizovanim Furijeovim redom, tj. aproksimacija zasnovana na sumaciji niza termina baziranih na ortogonalnim polinomima.

Jedan od problema od posebnog interesa je aproksimacija funkcije u računarskoj matematičkoj biblioteci, korišćenjem operacija koje se mogu izvršiti na računaru ili kalkulatoru (npr. sabiranje i množenje), tako da je rezultat što je moguće bliži stvarnoj funkciji. Ovo se obično radi sa polinomskim ili racionalnim (odnos polinoma) aproksimacijama.

Cilj je da aproksimacija bude što je moguće bliže stvarnoj funkciji, tipično sa tačnošću koja je bliska onoj koja postoji u osnovnoj računarskoj aritmetici sa pokretnim zarezom. Ovo se postiže korišćenjem polinoma visokog stepena i/ili sužavanjem domena nad kojim polinom treba da aproksimira funkciju. Sužavanje domena često se može obaviti upotrebom različitih formula za dodavanje ili skaliranje funkcija koje se aproksimiraju. Moderne matematičke biblioteke često redukuju domen na mnoge male segmente i koriste polinom niskog stepena za svaki segment.

Greška između optimalnog polinoma i -{log(x)}- (crveno) i Čebiševljeve aproksimacije i -{log(x)}- (plavo) preko intervala [2, 4]. Vertikalne podele su 10−5. Maksimalna greška za optimalni polinom je 6,07 x 10−5.

Greška između optimalnog polinoma i -{exp(x)}- (crveno) i Čebiševljeve aproksimacije i -{exp(x)}- (plavo) preko intervala [−1, 1]. Vertikalne podele su 10−4. Maksimalna greška za optimalni polinom je 5,47 x 10−4.

Optimalni polinomi

Kada se izabere domen (tipično interval) i stepen polinoma, sam polinom se bira na takav način da se minimizuje greška u najgorem slučaju. To jest, cilj je da se minimizuje maksimalna vrednost od $\mid P(x)-f(x)\mid$, gde je -{P(x)}- aproksimacioni polinom, -{f(x)}- je stvarna funkcija, i x varira u izabranom intervalu. Za funkcije koje se dobro ponašaju, postoji polinom -{N}--tog stepena koji će dovesti do krive greške koja osciluje između $+\epsilon$ i $-\epsilon$ ukupno -{N + 2}- puta, dajući najgoru grešku od $\epsilon$. Može se videti je da postoji polinom -{N}--tog stepena koji može da interpolira -{N}- + 1 tačaka krive. Takav polinom je uvek optimalan. Mogu se osmisliti funkcije -{f(x)}- za koje ne postoji takav polinom, ali se one u praksi retko javljaju.

Na primer, grafovi prikazani na desnoj strani pokazuju grešku u aproksimaciji -{log(x)}- i -{exp(x)}- za -{N}- = 4. Crvene krive, za optimalni polinom, su nivo, tj. one osciliraju između $+\epsilon$ i $-\epsilon$. Traba imati na umu da je u svakom slučaju broj ekstrema -{N}- + 2, tj. 6. Dva ekstrema su na krajnjim tačkama intervala, na levim i desnim ivicama grafova.

Greška -{P(x) − f(x)}- za nivo polinoma (crvena linija) i za poboljšani polinom (plava linija)

Da bi se dokazalo da je ovo tačno, pretpostavimo da je -{P}- polinom stepena -{N}- koji ima opisano svojstvo, to jest, daje funkciju greške koja ima -{N}- + 2 ekstrema, naizmeničnih znakova i jednakih veličina. Crveni graf na desnoj strani pokazuje kako ova funkcija greške može izgledati za -{N}- = 4. Pretpostavimo da je -{Q(x)}- (čija je funkcija greške prikazana plavom bojom na desnom grafikonu) još jedan -{N}--stepeni polinom koji je bolja aproksimacija za -{f}- nego -{P}-. Konkretno, Q je bliže -{f}- od -{P}- za svaku vrednost x_i gde se ekstrem -{P−f}- javlja, tako da je

$|Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|.$

Kad se javi maksimum od -{P−f}- u -{x_i}-, onda je

$Q(x_i)-f(x_i)\le |Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|=P(x_i)-f(x_i),$

Kad se javi minimum od -{P−f}- u -{x_i}-, onda je

$f(x_i)-Q(x_i)\le |Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|=f(x_i)-P(x_i).$

Dakle, kao što se može videti na grafiku, -{[P(x) − f(x)] − [Q(x) − f(x)]}- mora ima naizmeničan znaku za -{N}- + 2 vrednosti od x_i. Ali -{[P(x) − f(x)] − [Q(x) − f(x)]}- se svodi na -{P(x) − Q(x)}- koji je polinom stepena -{N}-. Ova funkcija menja znak najmanje -{N}-+1 puta, dakle, po teoremi o srednjoj vrednosti, ona ima -{N}-+1 nula, što je nemoguće za polinom stepena -{N}-.

Glavni časopisi

• -{Journal of Approximation Theory}-
• -{Constructive Approximation}-
• -{East Journal on Approximations}-

Vidi još

• Čebiševljevi polinomi
• Teorija procene
• Generalizovane Furijeovi redovi
• Ortogonalni polinomi
• Ortonormirana baza
• Furijeov red
• Šauderova baza
• Padeova aproksimacija
• Aproksimacija funkcija

Literatura

• A. F. Timan, Theory of approximation of functions of a real variable, 1963 Шаблон:ISBN
• C. Hastings, Jr. Approximations for Digital Computers. Princeton University Press, 1955.
• J. F. Hart, E. W. Cheney, C. L. Lawson, H. J. Maehly, C. K. Mesztenyi, J. R. Rice, H. C. Thacher Jr., C. Witzgall, Computer Approximations. Wiley, 1968, Lib. Cong. 67-23326.
• L. Fox and I. B. Parker. "Chebyshev Polynomials in Numerical Analysis." Oxford University Press London, 1968.
• Шаблон:Citation
• W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions. Prentice-Hall, 1980, Шаблон:ISBN.
• E. Remes [Remez], "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 C. R. Acad. Sci., Paris, 199, 337-340.
• K.-G. Steffens, "The History of Approximation Theory: From Euler to Bernstein," Birkhauser, Boston 2006 Шаблон:ISBN.
• T. Erdélyi, Шаблон:Cite journal.
• T. Erdélyi. Шаблон:Cite journal.
• L. N. Trefethen, "Approximation theory and approximation practice", SIAM 2013. [1]
• Theory of Point Estimation by E.L. Lehmann and G. Casella. (Шаблон:ISBN)
• Systems Cost Engineering by Dale Shermon. (Шаблон:ISBN)
• Mathematical Statistics and Data Analysis by John Rice. (Шаблон:ISBN)
• Fundamentals of Statistical Signal Processing: Estimation Theory by Steven M. Kay (Шаблон:ISBN)
• An Introduction to Signal Detection and Estimation by H. Vincent Poor (Шаблон:ISBN)
• Detection, Estimation, and Modulation Theory, Part 1 by Harry L. Van Trees (Шаблон:ISBN; website)
• Optimal State Estimation: Kalman, H-infinity, and Nonlinear Approaches by Dan Simon website Шаблон:Wayback
• Ali H. Sayed, Adaptive Filters, Wiley, NJ, 2008, Шаблон:ISBN.
• Ali H. Sayed, Fundamentals of Adaptive Filtering, Wiley, NJ, 2003, Шаблон:ISBN.
• Thomas Kailath, Ali H. Sayed, and Babak Hassibi, Linear Estimation, Prentice-Hall, NJ, 2000, Шаблон:ISBN.
• Babak Hassibi, Ali H. Sayed, and Thomas Kailath, Indefinite Quadratic Estimation and Control: A Unified Approach to H² and H^{$\mathrm{\infty }$} Theories, Society for Industrial & Applied Mathematics (SIAM), PA, 1999, Шаблон:ISBN.
• V.G.Voinov, M.S.Nikulin, "Unbiased estimators and their applications. Vol.1: Univariate case", Kluwer Academic Publishers, 1993, Шаблон:ISBN.
• V.G.Voinov, M.S.Nikulin, "Unbiased estimators and their applications. Vol.2: Multivariate case", Kluwer Academic Publishers, 1996, Шаблон:ISBN.
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite web
• Шаблон:Cite book
• Шаблон:Cite book 2003 unabridged republication of the 1878 English translation by Alexander Freeman of Fourier's work Théorie Analytique de la Chaleur, originally published in 1822.
• Шаблон:Cite journal
• Шаблон:Cite book
• Felix Klein, Development of mathematics in the 19th century. Mathsci Press Brookline, Mass, 1979. Translated by M. Ackerman from Vorlesungen über die Entwicklung der Mathematik im 19 Jahrhundert, Springer, Berlin, 1928.
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Springer
• Шаблон:Cite book
• Шаблон:Cite journal
• C. Chan, A. Mironov, A. Morozov, A. Sleptsov, Шаблон:ArXiv.

Spoljašnje veze

• -{History of Approximation Theory (HAT) Шаблон:Wayback}-
• -{Surveys in Approximation Theory (SAT) Шаблон:Wayback}-