Approximáció

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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 xi 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 xi-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 xi-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 xi 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ó[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 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[szerkesztés | forrásszöveg szerkesztése]

  • 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 Birkhäuser, 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[szerkesztés | forrásszöveg szerkesztése]