Approximáció

A matematikában approximációnak nevezzük azt az eljárást, mellyel függvények értékét próbáljuk közelíteni egyszerűbb függvényekkel, közben számosítva a lehetséges hibakorlátot.

Szorosan kapcsolódik a tematikához a függvények Fourier-sorok általi közelítése, azaz ortogonális polinomokon alapuló sorozatok szummázásával való közelítés.

Egy különlegesen érdekes probléma egy függvény közelítése számítógépes matematikai közegben, oly módon alkalmazva számítógépes operációkat (pl. összeadás, szorzás), hogy a megoldás az adott függvényt a lehető legjobban közelítse. Ez esetben tipikusan polinomiális vagy törtfüggvényekkel közelítünk.

A cél a függvény közelítése oly módon, hogy az megközelítse a számítógép által szabott lebegőpontos aritmetikát. Ezt egy magas fokú polinom használatával érhetjük el és/vagy leszűkítve az értéktartományt, melyen a polinomnak közelítenie kell a függvényt. Napjainkban az értékkészletet gyakran kicsiny részekre bontjuk, külön-külön közelítve minden részét alacsony fokú polinomokkal.

Hiba az optimális polinom és log(x) közt (piros) és a Csebisev approximáció és log(x) (kék) a [2,4] intervallumon. A függőleges vonalak $10^{-5}$ távolsággal vannak behúzva. Az optimális polinom maximum hibája $6,07 x 10^{-5}$

Hiba az optimális polinom és exp(x) közt (piros) és a Csebisev approximáció és exp(x) (kék) a [-1,1] intervallumon. A függőleges vonalak $10^{-5}$ távolsággal vannak behúzva. Az optimális polinom maximum hibája $5,47 x 10^{-4}$

Optimális polinomok

Miután megválasztottuk az értéktartományt és a polinom fokát, magát a polinomot úgy választjuk, hogy a minimalizáljuk a lehető legrosszabb eset hibáját. A cél tehát |P(x)-f(x)| értékének minimalizálása, ahol P(x) a közelítés, f(x) pedig a közelítendő függvény. Szép függvények esetén létezik egy N-edfokú polinom, melynek hibagörbéje +$\varepsilon$ és -$\varepsilon$ közt oszcillál összesen N+2-szer, $\varepsilon$-ra korlátozva a lehető legnagyobb hibát. Egy N-ed fokú polinom képes N+1 görbén lévő pontot interpolálni. Egy ilyen polinom mindig optimális. Lehetséges olyan mesterséges függvények előállítása, melyekre nem létezik ilyen polinom, viszont ezek a gyakorlatban ritkán fordulnak elő.

Nézzük például jobboldalt a log(x) és exp(x) közelítését N=4 esetén. A piros grafikon pontosan +$\varepsilon$ és -$\varepsilon$ között oszcillál. Vegyük észre, hogy a szélsőértékek száma N+2, azaz 6. Két szélsőértéket az intervallum végpontjain találunk, a grafikon két szélén.

P(x)-f(x) hibafüggvénye (piros) és jobb polinommal való közelítése (kék)

Ennek általános bizonyítása végett tegyük fel, hogy P egy N-ed fokú polinom az előzőleg tárgyalt tulajdonságokkal, azaz létrehoz egy N+2 szélsőértékkel rendelkező hibafüggvényt, melyeknek azonos a magnitúdója és váltakozó előjelűek. A piros grafikon mutatja, hogyan nézhetne ki egy ilyen függvény N=4 esetén. Tegyük fel, hogy Q(x) (melynek hibafüggvényét kékkel jelöljük) egy másik N-ed fokú polinom, mely f-nek jobb közelítése, mint P. Bővebben, Q közelebb van f-hez mint P minden x_i esetén, ahol egy P-f szélsőérték lép fel. Azaz

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

Ahol P-f-nek maximuma van x_i-ben, ott

$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),$

Ahol P-f-nek minimuma van x_i-ben, ott

$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).$

Amint tehát a grafikonon látszik, [P(x) − f(x)] − [Q(x) − f(x)]-nek alternálnia kell előjelben x_i N+2 értéke esetén. Viszont [P(x) − f(x)] − [Q(x) − f(x)] egyszerűsödik P(x) − Q(x)-vá, ami egy N-ed fokú polinom. Ez a függvény legalább N+1-szer vált előjelet, tehát a Bolzano–Darboux-tételnek megfelelően N+1 zérushelye van, amely lehetetlen N-ed fokú polinom esetén.

Csebisev approximáció

Az optimális polinomot nagyon jól közelíthetjük, ha kifejtjük az adott függvényt Csebisev polinomok szerint és ezt követően levágjuk a kifejtést a kívánt foknál. Ez az eljárás hasonlít a sor Fourier-sorok általi függvényközelítéshez, Csebisev polinomokat használva trigonometrikus függvények helyett.

Ha kiszámoljuk egy függvény Csebisev kifejtés által keletkező tagoknak együtthatóit:

$f(x) \sim \sum_{i=0}^\infty c_i T_i(x)$

és utána levágjuk a sorozatot a $T_n$-edik tag után, egy N-ed fokú f(x)-et közelítő polinomhoz jutunk.

Ez a polinom azért közel optimális, mert gyorsan konvergáló sorú függvények esetén, ha elvágjuk a sort valamelyik tagjánál, az elvágás által keletkező hiba nagyon közel van a levágást követő taghoz. Azaz a levágást követő tag dominálja az összes hátralévő tagot. Ugyanez igaz, ha a kifejtés a Csebisev polinomoknak megfelelően történik. Ha egy Csebisev kifejtést $T_n$-nél vágjuk le, a hiba $T_{n+1}$ többszöröseként fog előállni. A Csebisev polinomoknak megvan az a tulajdonságuk, hogy +1 és -1 között oszcillálnak a [-1, 1] intervallumon. $T_{n+1}$-nek N+2 szélsőértéke van, azaz közel van az optimális N-ed fokú polinomhoz.

A fenti grafikonokon a kék közelítés néha jobb, mint a piros függvény, néha pedig rosszabb, melyek szerint nem teljesen az optimális polinom. Vegyük észre, hogy a különbség enyhébb az exp függvény esetén, mely egy sokkal gyorsabban konvergáló hatványsor, mint a log függvény.

Remez algoritmusa

A Remez algoritmus segítségével előállíthatunk egy P(x) optimális polinomot egy adott f(x) függvény közelítésére egy adott intervallumon. Egy iteratív algoritmus, mely egy N+2 szélsőértékű függvény polinomjához konvergál. A fenti tétel alapján ez a polinom optimális.

Remez algoritmusa kihasználja azt a tényt, hogy előállítható egy N-ed fokú polinom, mely adott N+2 pont esetén alternáló szélsőértékekhez vezet.

Adott N+2 $x_1$, $x_2$ ... $x_{n+2}$ pont esetén (ahol $x_1$ és $x_{n+2}$ feltehetően a közelítendő intervallum végpontjai) a következő egyenlőségeket kell megoldani:

$P(x_1) - f(x_1) = + \varepsilon\,$

$P(x_2) - f(x_2) = - \varepsilon\,$

$P(x_3) - f(x_3) = + \varepsilon\,$

$\vdots$

$P(x_{n+2}) - f(x_{n+2}) = \pm \varepsilon.\,$

A jobboldali értékek előjele váltakozik, azaz

$P_0 + P_1 x_1 + P_2 x_1^2 + P_3 x_1^3 ... P_n x_1^n - f(x_1) = + \varepsilon\,$

$P_0 + P_1 x_2 + P_2 x_2^2 + P_3 x_2^3 ... P_n x_2^n - f(x_2) = - \varepsilon\,$

$\vdots$

Mivel $x_1$ ... $x_{n+2}$ adottak voltak, minden hatványuk ismert és $f(x_1)$ ... $f(x_{n+2})$ szintén ismert. Ez azt jelenti, hogy a fenti egyenletek csupán n+2 lineáris egyenlet n+2 változóval: $P_0$, $P_1$ ... $P_n$, and $\varepsilon$.

Az adott $x_1$ ... $x_{n+2}$ pontok segítségével megoldható ez az egyenletrendszer és előállítható a P polinom és $\varepsilon$.

Az alábbi grafikon szemlélteti ezt az eljárást, előállítva egy 4-ed fokú polinomot az $e^x$ [-1, 1] intervallumon való közelítésére. Az adott pontok a -1; -0,7; -0,1; +0,4; +0,9; és 1. Azok értéke zölddel van ábrázolva. $\varepsilon$ értéke 4,43 x 10⁻⁴

A polinom hibája Remez algoritmusának első lépése segítségével előállítva, $e^x$-et becsülve a [-1,1] intervallumon. A függőleges vonalak $10^{-4}$ távolsággal vannak behúzva.

Vegyük észre, hogy a hiba-görbe valóban nem veszi föl $\pm \varepsilon$ értéket az adott 6 pontban, beszámítva a végpontokat, melyek nem szélsőértékek. Ha a 4 belső pont szélsőérték lett volna (azaz a P(x)-f(x)-nek minimuma vagy maximuma lett volna e helyeken), a polinom optimális lenne.

Remez algoritmusának második lépése az adott pontokat a lehető legközelebb vinni oda, ahol a hibafüggvénynek a valóságos lokális minimuma vagy maximuma van. Például ha a grafikont tekintjük, látjuk, hogy a -0,1 pontnak valahol a -0,28 környezetében kellett volna lennie. Az algoritmusban ezt a Newton-módszer egyszeri alkalmazása segítségével érjük el. Mivel a P(x)-f(x) első és második deriváltjai ismertek, kiszámolható, hogy közelítően milyen messze kell egy adott pontot mozgatni, hogy a derivált nulla legyen.

Egy polinom deriváltjainak kiszámítása egyszerű. Szükséges kiszámolni f(x) első és második deriváltjait. Remez algoritmusának feltétele, hogy képesek legyünk kiszámolni f(x), f'(x) és f"(x)-et nagyon nagy pontossággal. Az algoritmus kivitelezésének pontossága felül kell múlja az elvárt eredmény pontosságát.

Miután elmozgattuk a pontokat, megismételjük a lineáris egyenletrendszerre vonatkozó részt, új polinomot kapva és a Newton-módszer segítségével újonnan mozgatjuk a pontokat. Ezt a módszert ismételjük addig, mígnem az eredmény az elvárt pontossághoz konvergál. Az algoritmus nagyon gyorsan konvergál; szép függvények esetén kvadratikusan - ha az adott pontok $10^{-15}$-nél közelebb vannak a helyes értéktől, közel $10^{-30}$ távol lesznek az algoritmus következő körében.

Remez algoritmusát tipikusan a $T_n$ Csebisev polinom szélsőértékeit adott pontokként használva kezdjük el, hisz a végső hibafüggvény hasonlítani fog ahhoz a polinomhoz.

Források

• N.I.Achiezer (Akhiezer), Theory of approximation, Translated by Charles J. Hyman Frederick Ungar Publishing Co., New York 1956 x+307 pp.
• A.F.Timan, Theory of approximation of functions of a real variable, 1963 ISBN 048667830X
• 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.
• W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions, Prentice-Hall, 1980, ISBN 0-13-822064-6.
• 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 0817643532
• T. Erdélyi, "Extensions of the Bloch-P ́olya theorem on the number of distinct realzeros of polynomials", Journal de th ́eorie des nombres de Bordeaux 20 (2008), 281–287.
• T. Erdélyi, "The Remez inequality for linear combinations of shifted Gaussians", Math. Proc. Cambridge Phil. Soc. 146 (2009), 523–530.

Külső hivatkozások

• Ez a szócikk részben vagy egészben az Approximation theory című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.
• History of Approximation Theory (HAT)
• Surveys in Approximation Theory (SAT)