Remez algoritme

Remez-algoritmen (også Remez-erstatningsalgoritmen) er en iterativ algoritme til ensartet tilnærmelse af funktioner f ∊ C[ a , b ], baseret på P. L. Chebyshevs alternancesætning. Foreslået af E. Ya Remez i 1934 [1] .

Remez-algoritmen bruges i designet af FIR-filtre [2] .

Matematisk grundlag

Chebyshevs teorem

Det teoretiske grundlag for Remez-algoritmen er følgende teorem [3] .

For at et eller andet gradpolynomium højst skal være et polynomium, der afviger mindst fra , er det nødvendigt og tilstrækkeligt, at der findes mindst ét system af punkter , hvor forskellen : $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)$

skiftevis antager værdierne af forskellige tegn,
når den maksimale værdi med modulo . $[a,\b]$

Sådan et system af punkter kaldes Chebyshev alternance .

P. L. Chebyshev , 1854

De la Vallée-Poussin-sætningen

Lad E n være værdien af den bedste tilnærmelse af funktionen f ( x ) ved polynomier af grad n . E n estimeres nedefra ved følgende sætning [4] :

Hvis for en funktion f ∊ C[ a , b ] et polynomium P ( x ) af grad n har den egenskab, at forskellen f ( x ) - P ( x ) på et system af n + 2 ordnede punkter x i tager værdier med skiftende tegn altså

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

Sh.-Zh. Vallee Poussin, 1919

Algoritme

Overvej et system af funktioner , en sekvens af punkter og se efter et tilnærmet polynomium $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}=\sum _{0}^{n}a_{j}\varphi _{j))

Vi løser et system af lineære ligninger for og : $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 finder et punkt sådan, at . $\xi$ $D=f(\xi )-P(\xi )=\max$
Vi erstatter et af punkterne i X med ξ på en sådan måde, at tegnet f - P skifter i punkterne i den nye sekvens. I praksis sørger de kun for, at punkterne x i er ordnet ved hver iteration [5] .
Gentag alle trin fra begyndelsen, indtil der ikke er nogen | d | = D .

På det andet trin kan vi se efter ikke kun et punkt ξ , men et sæt Ξ af punkter, hvor lokale maksima | f - P |. Hvis alle fejl i punkterne i mængden Ξ har den samme absolutte værdi og skifter i fortegn, så er P et minimakspolynomium. Ellers erstatter vi punkter fra X med punkter fra Ξ og gentager proceduren igen.

Valg af startpunkter

Som startsekvens X kan du vælge punkter ensartet fordelt på [ a , b ]. Det er også tilrådeligt at tage point [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

Hvis den approksimerende funktion søges i form af et polynomium, kan du i stedet for at løse systemet i det første trin af algoritmen bruge følgende metode [7] :

Find et polynomium q ( x ) af grad n+1 , således at q ( x i ) = f ( x i ) ( interpolationsproblem ).
Vi finder også et polynomium q * ( x ) af grad n+1 , således at q * ( x i ) = (-1) i .
Ved at vælge d , så polynomiet P ( x ) ≡ q ( x ) - d q * ( x ) har grad n , får vi P ( x i ) + (-1) i d = f ( x i ).

Derefter gentages trinene i henhold til hovedskemaet.

Stop betingelse

Siden ved de la Vallée-Poussin-sætningen | d | ≤ E n ( f ) ≤ D , så kan stopbetingelsen for algoritmen være D — | d | ≤ ε for nogle forudtildelte ε .

Konvergens

Remez-algoritmen konvergerer med hastigheden af en geometrisk progression i følgende betydning [8] :

For enhver funktion f ∊ C[ a , b ] er der tal A > 0 og 0 < q < 1, således at de maksimale afvigelser fra funktionen f ( x ) af polynomier konstrueret af denne algoritme vil tilfredsstille ulighederne $P_{n}^{(k)}(x)$

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

hvor E n ( f ) er værdien af den bedste tilnærmelse på [ a , b ] af funktionen f ( x ) ved brug af polynomier P n ( x ).

E. Ya. Remez , 1957

Eksempel

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

Trin 1.

x1 _	−1	0	en
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 giver P = 1,175 x + 1,272, d = 0,272.
D = max|e ξ - P ( ξ )| = 0,286 ved ξ = 0,16.

Trin 2

x2 _	−1	0,16	en
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 giver P = 1,175 x + 1,265, d = 0,279.
D = max|e ξ - P ( ξ )| = 0,279 ved ξ = 0,16.

Da det samme punkt blev opnået inden for den givne nøjagtighed, bør det fundne polynomium betragtes som den bedste tilnærmelse af den første grad af funktionen e x .

Se også

Weierstrass tilnærmelsessætning

Noter

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

Litteratur

DeVore RA, Lorentz GG Konstruktiv tilnærmelse. - 1993.
Bronstein I. N., Semendyaev K. A. Håndbog i matematik for ingeniører og studerende fra tekniske universiteter. - 1980.
Dzyadyk VK Introduktion til teorien om ensartet tilnærmelse af funktioner ved polynomier. - 1977.
Laurent P.-J. Approksimation og optimering. - 1975.
Rabiner L., Gould B. Teori og anvendelse af digital signalbehandling. - 1978.
Remez E. Ya. Grundlæggende om numeriske metoder til Chebyshev-tilnærmelse. - 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . En ny Remez-type algoritme for bedste polynomielle approksimation // Numeriske beregninger: teori og algoritmer: tredje internationale konference, NUMTA 2019, Crotone, Italien, 15.–21. juni 2019, Reviderede udvalgte papirer, del I , juni 2019 – sider 56 69 doi // Program NUMTA 2019 , 19. juni, onsdag morgen (9.00): Rum 1 // Book of Abstracts, side 50 // books google, side 56-57, 60-64, 67-69