Remez algoritmus

A Remez-algoritmus (a Remez-helyettesítő algoritmus is) egy iteratív algoritmus az f ∊ C[ a , b ] függvények egyenletes közelítésére , amely P. L. Csebisev alternancia tételén alapul. E. Ya. Remez javasolta 1934-ben [1] .

A Remez algoritmust a FIR szűrők tervezésénél alkalmazzák [2] .

Matematikai alapok

Csebisev tétele

A Remez-algoritmus elméleti alapja a következő [3] tétel .

Ahhoz, hogy egy legfeljebb fokszámú polinom olyan polinom legyen, amely a legkevésbé tér el -tól , szükséges és elegendő, hogy találjunk legalább egy olyan pontrendszert , amelynél a különbség : $P^{*}(x)$ $n$ $f\in C[a,b]$ $[a,b]$ $n+2$ $\{x_{i}\},$ $a\leq x_{0}<x_{1}<\pontok <x_{n+1}\leq b,$ $f(x)-P^{*}(x)$

felváltva veszi fel a különböző jelek értékeit,
modulo-val eléri a maximális értéket . $[a,\b]$

Az ilyen pontrendszert Csebisev-alternanciának nevezik .

P. L. Csebisev , 1854

A de la Vallée-Poussin tétel

Legyen E n az f ( x ) függvény n fokú polinomokkal való legjobb közelítésének értéke . Az E n -t alulról a következő [4] tétellel becsüljük meg :

Ha egy f ∊ C[ a , b ] függvényre valamely n fokú P ( x ) polinomnak az a tulajdonsága, hogy az f ( x ) - P ( x ) különbség valamilyen n + 2 x i rendezett pontból álló rendszeren értékeket vesz fel akkor váltakozó jelekkel

E_{n}(f)\geq \min |f(x_{i})-P(x_{i})|.

Sh.-Zh. Vallee Poussin, 1919

Algoritmus

Tekintsünk egy függvényrendszert , egy pontsorozatot, és keressünk egy közelítő polinomot $n+1$ ${\displaystyle \mathbf {\varPhi } =\{\varphi _{0},\dots ,\varphi _{n}\))$ $n+2$ $X=\{x_{i}\},$ $a\leq x_{0}<x_{1}<\pontok <x_{n+1}\leq b,$

{\displaystyle P_{X}=\sum _{0}^{n}a_{j}\varphi _{j))

Megoldunk egy lineáris egyenletrendszert és : $a_{j}$ $d$
$\sum _{j=0}^{n}a_{j}\varphi _{j}(x_{i})+(-1)^{i}d=f(x_{i}), \quad i=0,1,\ldots ,n.$
Találunk egy olyan pontot , hogy . $\xi$ $D=f(\xi )-P(\xi )=\max$
Az X egyik pontját ξ - re cseréljük oly módon, hogy az új sorozat pontjain az f - P előjel váltakozik. A gyakorlatban csak arra ügyelnek, hogy az x i pontok minden iterációnál rendezve legyenek [5] .
Ismételje meg az összes lépést az elejétől, amíg meg nem jelenik | d | = D .

A második lépésben nem csak egy ξ pontot kereshetünk , hanem egy olyan Ξ ponthalmazt, ahol a helyi maximumok | f - P |. Ha a Ξ halmaz pontjaiban minden hiba azonos abszolút értékű és váltakozó előjelű, akkor P egy minimax polinom. Ellenkező esetben az X -ből származó pontokat Ξ -ből származó pontokra cseréljük, és ismételjük meg az eljárást.

Kiindulási pontok kiválasztása

Az X kezdeti sorozatként az [ a , b ] pontokon egyenletesen elosztott pontokat választhatunk . Célszerű a [6] pontokat is figyelembe venni :

x_{i}={\frac {a+b}{2}}+{\frac {ba}{2}}\cos \left({\frac {\pi i}{n+1}} \jobbra),\quad i=0,\ldots ,n+1.

Módosítás

Ha a közelítő függvényt polinom formájában keressük, akkor a rendszer megoldása helyett az algoritmus első lépésében a következő módszert használhatjuk [7] :

Keressünk egy n+1 fokú q ( x ) polinomot úgy, hogy q ( x i ) = f ( x i ) ( interpolációs feladat ).
Találunk egy n+1 fokú q * ( x ) polinomot is úgy , hogy q * ( x i ) = (-1) i .
Ha úgy választjuk meg a d -t , hogy a P ( x ) ≡ q ( x ) - d q * ( x ) polinomnak n foka legyen, P ( x i ) + (-1) i d = f ( x i ) értéket kapjuk .

Ezután a fő séma szerinti lépéseket megismételjük.

Stop feltétel

Mivel a de la Vallée-Poussin tétel szerint | d | ≤ E n ( f ) ≤ D , akkor az algoritmus leállítási feltétele lehet D — | d | ≤ ε néhány előre hozzárendelt ε esetén .

Konvergencia

A Remez-algoritmus egy geometriai progresszió sebességével konvergál a következő értelemben [8] :

Bármely f ∊ C[ a , b ] függvényhez vannak A > 0 és 0 < q < 1 számok, így az ezzel az algoritmussal szerkesztett polinomok f ( x ) függvényétől való maximális eltérések kielégítik az egyenlőtlenségeket. $P_{n}^{(k)}(x)$

\max |f(x)-P_{n}^{(k)}(x)|-E_{n}(f)\leq Aq^{k},\quad k=1,2,\ ldots,

ahol E n ( f ) az f ( x ) függvény [ a , b ] -én elért legjobb közelítés értéke P n ( x ) polinomok használatával .

E. Ya. Remez , 1957

Példa

f ( x ) = e x , n = 1, P ( x ) = a x + b .

1. lépés.

x1_ _	−1	0	egy
f ( x i )	0,368	1.000	2.718

{\begin{cases}({-}1)a+b+d=0,368\\(0)a+bd=1,000\\(1)a+b+d=2,718\end{cases))

A rendszer megoldása P = 1,175 x + 1,272, d = 0,272.
D = max|e ξ - P ( ξ )| = 0,286 ξ = 0,16-nál.

2. lépés

x2 _	−1	0.16	egy
f ( x i )	0,368	1.174	2.718

{\begin{cases}({-}1)a+b+d=0,368\\(0,16)a+bd=1,174\\(1)a+b+d=2,718\end{cases))

A rendszer megoldása P = 1,175 x + 1,265, d = 0,279.
D = max|e ξ - P ( ξ )| = 0,279 ξ = 0,16-nál.

Mivel ugyanazt a pontot a megadott pontosságon belül kaptuk, a talált polinomot az e x függvény első fokának legjobb közelítésének kell tekinteni .

Lásd még

Weierstrass-közelítési tétel

Jegyzetek

↑ E. Ya. Remes (1934). Sur le calful effectif des polynômes d'approximation de Tschebyscheff. CP Paris 199, 337-340; Ch. 3:78
↑ Rabiner, 1978 , p. 157.
↑ Dzyadyk, 1977 , p. 12.
↑ Dzyadyk, 1977 , p. 33.
↑ Laurent, 1975 , p. 117.
↑ Dzyadyk, 1977 , p. 74.
↑ Laurent, 1975 , p. 112.
↑ Dzyadyk, 1977 , p. 76-77.

Irodalom

DeVore RA, Lorentz GG Konstruktív közelítés. – 1993.
Bronstein I. N., Semendyaev K. A. Matematikai kézikönyv mérnökök és műszaki egyetemi hallgatók számára. – 1980.
Dzyadyk VK Bevezetés a függvények polinomokkal történő egyenletes közelítésének elméletébe. – 1977.
Laurent P.-J. Közelítés és optimalizálás. – 1975.
Rabiner L., Gould B. A digitális jelfeldolgozás elmélete és alkalmazása. – 1978.
Remez E. Ya. A Csebisev-közelítés numerikus módszereinek alapjai. – 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . A New Remez-Type Algorithm for Best Polynomial Approximation // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Olaszország, 2019. június 15–21, Revised Selected Papers, I. rész , 2016. június – Oldalak 69 doi // NUMTA 2019 program , június 19., szerda reggel (9.00): 1. terem // Absztraktok könyve, 50. oldal // könyvek google, 56-57., 60-64., 67-69.