Remezův algoritmus

Aproximace funkce $1/(37/12-x)$ (červeně) polynomem druhého stupně (modře) na intervalu $\langle -1,1\rangle$. Chyba nalezené aproximace je maximální ve čtyřech bodech $x_{0}$ až $x_{3}$ (z toho dva jsou krajní a ostatní se hledají iteračním postupem), přičemž se střídá znaménko této chyby.

Remezův algoritmus je iterační postup, jak aproximovat zadanou funkci $f(x)$ polynomem $p(x)$ požadovaného stupně tak, aby absolutní hodnota chyby aproximace $|f(x)-p(x)|$ byla v požadovaném intervalu $\langle a,b\rangle$ minimální (tzv. minimalizace maxima). Postup publikoval Jevgenij Jakovlevič Remez (Евгений Я́ковлевич Ре́мез) v roce 1934.

Takto nalezená aproximace bývá použita v procesorech (resp. matematických koprocesorech) pro výpočet základních funkcí, např. sinus, kosinus, arkus tangens, logaritmus, exponenciální funkce. U těchto funkcí lze pomocí vhodných vzorců dosáhnout toho, aby jejich vstupní parametr ležel v požadovaném intervalu (např. $sin(2\pi +x)=sin(x)$, $log_{2}(2x)=log_{2}(x)+1$) a koeficienty a stupeň polynomu jsou určeny tak, aby chyba aproximace byla nižší než (ne)přesnost čísel daného procesoru. Tento algoritmus lze použít i při návrhu číslicových filtrů.

Taylorův polynom stupně 1, 3, 5, 7, 9, 11 a 13 funkce sin(x) (černě). Bez ohledu na stupeň polynomu, chyba aproximace postupně od středu vzrůstá.

Taylorův polynom aproximuje funkci tak, že v místě, pro které byly koeficienty Taylorova polynomu spočteny, odpovídá hodnota Taylorova polynomu přesně hodnotě aproximované funkce, ale čím dále od tohoto místa tím více se Taylorův polynom a funkce rozchází a chyba aproximace roste (pro výše uvedené základní funkce). Naopak v případě Remezova polynomu chyba v intervalu $\langle a,b\rangle$ osciluje mezi kladným a záporným maximem, přičemž počet oscilací závisí na stupni polynomu. Tato maximální chyba bývá výrazně menší než chyba Taylorova polynomu stejného stupně na stejném intervalu.

Externí odkazy

• https://homel.vsb.cz/....pdf - VŠB, Nejlepší polynomiální aproximace, bakalářská práce, Tomáš Staško
• anglicky http://www.righto.com/... - Ken Shirriff's blog, Pi in the Pentium: reverse-engineering the constants in its floating-point unit