Remez algoritm

Remez-algoritmen (även Remez-ersättningsalgoritmen) är en iterativ algoritm för enhetlig approximation av funktioner f ∊ C[ a , b ], baserad på P. L. Chebyshevs alternanssats. Föreslagen av E. Ya Remez 1934 [1] .

Remez-algoritmen används vid utformningen av FIR-filter [2] .

Matematiska grunder

Chebyshevs teorem

Den teoretiska grunden för Remez-algoritmen är följande teorem [3] .

För att något polynom av grad som mest ska vara ett polynom som avviker minst från , är det nödvändigt och tillräckligt att åtminstone ett system av punkter hittas där skillnaden : $P^{*}(x)$ $n$ $f\in C[a,b]$ $[a,b]$ $n+2$ $\{x_{i}\},$ $a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,$ $f(x)-P^{*}(x)$

växelvis antar värdena för olika tecken,
når maxvärdet med modulo . $[a,\b]$

Ett sådant system av poäng kallas Chebyshev alternance .

P. L. Chebyshev , 1854

De la Vallée-Poussin-satsen

Låt E n vara värdet av den bästa approximationen av funktionen f ( x ) med polynom av grad n . E n uppskattas underifrån av följande teorem [4] :

Om för en funktion f ∊ C[ a , b ] något polynom P ( x ) av grad n har egenskapen att skillnaden f ( x ) - P ( x ) på något system med n + 2 ordnade punkter x i tar värden med alternerande tecken alltså

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

Sh.-Zh. Vallee Poussin, 1919

Algoritm

Betrakta ett system av funktioner , en sekvens av punkter och leta efter ett approximativt polynom $n+1$ ${\displaystyle \mathbf {\varPhi } =\{\varphi _{0},\dots ,\varphi _{n}\))$ $n+2$ $X=\{x_{i}\},$ $a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,$

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

Vi löser ett system av linjära ekvationer för och : $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.$
Vi hittar en punkt sådan att . $\xi$ $D=f(\xi )-P(\xi )=\max$
Vi ersätter en av punkterna i X med ξ på ett sådant sätt att tecknet f - P alternerar i punkterna i den nya sekvensen. I praktiken ser de bara till att punkterna x i ordnas vid varje iteration [5] .
Upprepa alla steg från början tills det inte finns någon | d | = D .

I det andra steget kan vi leta efter inte bara en punkt ξ , utan en uppsättning Ξ av punkter där lokala maxima | f - P |. Om alla fel vid punkterna i mängden Ξ har samma absoluta värde och växlar i tecken, så är P ett minimaxpolynom. Annars ersätter vi punkter från X med punkter från Ξ och upprepar proceduren igen.

Välja startpunkter

Som initialsekvens X kan du välja punkter likformigt fördelade på [ a , b ]. Det är också lämpligt att ta poäng [6] :

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

Ändring

Om den approximerande funktionen söks i form av ett polynom, kan du istället för att lösa systemet i det första steget av algoritmen använda följande metod [7] :

Hitta ett polynom q ( x ) av grad n+1 så att q ( x i ) = f ( x i ) ( interpolationsproblem ) .
Vi hittar också ett polynom q * ( x ) av grad n+1 så att q * ( x i ) = (-1) i .
Genom att välja d så att polynomet P ( x ) ≡ q ( x ) - d q * ( x ) har grad n får vi P ( x i ) + (-1) i d = f ( x i ).

Sedan upprepas stegen enligt huvudschemat.

Stoppvillkor

Sedan av de la Vallée-Poussin-satsen | d | ≤ E n ( f ) ≤ D , då kan stoppvillkoret för algoritmen vara D — | d | ≤ ε för vissa förtilldelade ε .

Konvergens

Remez-algoritmen konvergerar i takt med en geometrisk progression i följande mening [8] :

För alla funktioner f ∊ C[ a , b ] finns det siffror A > 0 och 0 < q < 1 så att de maximala avvikelserna från funktionen f ( x ) för polynom konstruerade av denna algoritm kommer att tillfredsställa olikheterna $P_{n}^{(k)}(x)$

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

där E n ( f ) är värdet av den bästa approximationen på [ a , b ] av funktionen f ( x ) med användning av polynom P n ( x ).

E. Ya. Remez , 1957

Exempel

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

Steg 1.

x1 _	−1	0	ett
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))

Systemets lösning ger P = 1,175 x + 1,272, d = 0,272.
D = max|e ξ - P ( ξ )| = 0,286 vid ξ = 0,16.

Steg 2

x2 _	−1	0,16	ett
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))

Systemets lösning ger P = 1,175 x + 1,265, d = 0,279.
D = max|e ξ - P ( ξ )| = 0,279 vid ξ = 0,16.

Eftersom samma punkt erhölls inom den givna noggrannheten, bör det funna polynomet betraktas som den bästa approximationen av den första graden av funktionen e x .

Se även

Weierstrass approximationssats

Anteckningar

↑ 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 , sid. 157.
↑ Dzyadyk, 1977 , sid. 12.
↑ Dzyadyk, 1977 , sid. 33.
↑ Laurent, 1975 , sid. 117.
↑ Dzyadyk, 1977 , sid. 74.
↑ Laurent, 1975 , sid. 112.
↑ Dzyadyk, 1977 , sid. 76-77.

Litteratur

DeVore RA, Lorentz GG Constructive Approximation. — 1993.
Bronstein I. N., Semendyaev K. A. Handbok i matematik för ingenjörer och studenter vid tekniska universitet. — 1980.
Dzyadyk VK Introduktion till teorin om enhetlig approximation av funktioner med polynom. — 1977.
Laurent P.-J. Approximation och optimering. — 1975.
Rabiner L., Gould B. Teori och tillämpning av digital signalbehandling. — 1978.
Remez E. Ya. Grunderna i numeriska metoder för Chebyshev approximation. — 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . En ny Remez-typalgoritm för bästa polynomapproximation // Numeriska beräkningar: teori och algoritmer: tredje internationella konferensen, NUMTA 2019, Crotone, Italien, 15–21 juni 2019, Revised Selected Papers, Del I , juni 2019– Sidor 56 69 doi // Program NUMTA 2019 , 19 juni, onsdag morgon (9.00): Rum 1 // Book of Abstracts, sid 50 // books google, pages 56-57, 60-64, 67-69