Approximáció

A matematikában approximációnak nevezzük azt az eljárást, melyel 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 hibátkorlá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. Ezesetben 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,07x10^{-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,47x10^{-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ő leg roszabb eset hibáját. A cél tehát $\mid P(x)-f(x)\mid$ é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 mindíg 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 rendekező hibafüggvényt, melyneknek azonos a magnitúdója és valtakozó 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})\leq |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})\leq |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^-4

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 egyenletrendzserre 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ül 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

• History of Approximation Theory (HAT)
• Surveys in Approximation Theory (SAT)