Remez-algoritmi

Remez-algoritmi (myös Remez-korvausalgoritmi) on iteratiivinen algoritmi funktioiden f ∊ C[ a , b ] tasaiseen approksimaatioon , joka perustuu P. L. Chebyshevin alternanssilauseeseen. E. Ya. Remezin ehdottama vuonna 1934 [1] .

FIR-suodattimien suunnittelussa käytetään Remez-algoritmia [2] .

Matemaattiset perusteet

Chebyshevin lause

Remez-algoritmin teoreettinen perusta on seuraava lause [3] .

Jotta jokin korkeintaan astepolynomi olisi polynomi, joka poikkeaa vähiten arvosta , on välttämätöntä ja riittävää, että löydetään ainakin yksi pistejärjestelmä , jossa erotus : $P^{*}(x)$ $n$ $f\in C[a,b]$ $[a,b]$ $n+2$ $\{x_{i}\},$ $a\leq x_{0}<x_{1}<\pisteet <x_{n+1}\leq b,$ $f(x)-P^{*}(x)$

ottaa vuorotellen eri merkkien arvot,
saavuttaa maksimiarvon modulolla . $[a,\b]$

Tällaista pistejärjestelmää kutsutaan Chebyshev-alternanssiksi .

P. L. Chebyshev , 1854

De la Vallée-Poussin -lause

Olkoon E n funktion f ( x ) parhaan approksimoinnin arvo n - asteisten polynomien avulla . E n estimoidaan alta seuraavalla lauseella [4] :

Jos funktiolle f ∊ C[ a , b ] jollain n asteen polynomilla P ( x ) on ominaisuus, että ero f ( x ) - P ( x ) jossain n + 2 järjestetyn pisteen x i järjestelmässä saa arvot sitten vuorotellen

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

Sh.-Zh. Vallee Poussin, 1919

Algoritmi

Harkitse funktiojärjestelmää , pistejonoa ja etsi approksimoiva polynomi $n+1$ ${\displaystyle \mathbf {\varPhi } =\{\varphi _{0},\dots ,\varphi _{n}\))$ $n+2$ $X=\{x_{i}\},$ $a\leq x_{0}<x_{1}<\pisteet <x_{n+1}\leq b,$

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

Ratkaisemme lineaarisen yhtälöjärjestelmän ja : $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.$
Löydämme sellaisen kohdan , että . $\xi$ $D=f(\xi )-P(\xi )=\max$
Korvataan yksi X :n pisteistä ξ :llä siten, että merkki f - P vuorottelee uuden sekvenssin pisteissä. Käytännössä he varmistavat vain, että pisteet x i ovat järjestyksessä jokaisessa iteraatiossa [5] .
Toista kaikki vaiheet alusta, kunnes | d | = D. _

Toisessa vaiheessa emme voi etsiä vain yhtä pistettä ξ , vaan joukkoa Ξ pisteitä, joissa paikalliset maksimit | f - P |. Jos kaikilla joukon Ξ pisteissä olevilla virheillä on sama itseisarvo ja ne vaihtelevat etumerkissä, niin P on minimax-polynomi. Muussa tapauksessa korvaamme pisteet X :stä pisteillä Ξ ja toistamme menettelyn uudelleen.

Lähtöpisteiden valitseminen

Alkusekvenssiksi X voit valita pisteet, jotka jakautuvat tasaisesti [ a , b ]:lle. On myös suositeltavaa ottaa kohdat [6] :

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

Muutos

Jos approksimoivaa funktiota etsitään polynomin muodossa, voit sen sijaan, että ratkaisisit järjestelmän algoritmin ensimmäisessä vaiheessa, käyttämällä seuraavaa menetelmää [7] :

Etsi polynomi q ( x ), jonka aste on n+1 siten, että q ( x i ) = f ( x i ) ( interpolointitehtävä ) .
Löydämme myös polynomin q * ( x ) asteella n+1 siten, että q * ( x i ) = (-1) i .
Valitsemalla d niin, että polynomin P ( x ) ≡ q ( x ) - d q * ( x ) aste on n , saadaan P ( x i ) + (-1) i d = f ( x i ).

Sitten pääkaavion mukaiset vaiheet toistetaan.

Pysäytysehto

Koska de la Vallée-Poussinin lauseella | d | ≤ E n ( f ) ≤ D , niin algoritmin pysäytysehto voi olla D — | d | ≤ ε jollekin ennalta määrätylle ε :lle .

Lähentyminen

Remez-algoritmi konvergoi geometrisen etenemisen nopeudella seuraavassa mielessä [8] :

Jokaiselle funktiolle f ∊ C[ a , b ] on lukuja A > 0 ja 0 < q < 1 siten, että suurimmat poikkeamat tällä algoritmilla muodostettujen polynomien funktiosta f ( x ) täyttävät epäyhtälöt $P_{n}^{(k)}(x)$

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

missä E n ( f ) on funktion f ( x ) parhaan approksimoinnin arvo [ a , b ]:lla käyttämällä polynomeja P n ( x ).

E. Ya. Remez , 1957

Esimerkki

f ( x ) = ex , n = 1, P ( x ) = ax + b .

Vaihe 1.

x1_ _	−1	0	yksi
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))

Järjestelmän ratkaisu antaa P = 1,175 x + 1,272, d = 0,272.
D = max|e ξ - P ( ξ )| = 0,286 ξ = 0,16:ssa.

Vaihe 2

x2_ _	−1	0.16	yksi
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))

Järjestelmän ratkaisu antaa P = 1,175 x + 1,265, d = 0,279.
D = max|e ξ - P ( ξ )| = 0,279 ξ = 0,16:ssa.

Koska sama piste saatiin annetulla tarkkuudella, löydettyä polynomia tulee pitää funktion e x ensimmäisen asteen parhaana approksimaationa .

Katso myös

Weierstrassin approksimaatiolause

Muistiinpanot

↑ 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 , 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.

Kirjallisuus

DeVore RA, Lorentz GG Rakentava likiarvo. – 1993.
Bronstein I. N., Semendyaev K. A. Matematiikan käsikirja insinööreille ja teknisten yliopistojen opiskelijoille. – 1980.
Dzyadyk VK Johdatus funktioiden tasaisen approksimoinnin teoriaan polynomeilla. – 1977.
Laurent P.-J. Lähentäminen ja optimointi. – 1975.
Rabiner L., Gould B. Digitaalisen signaalinkäsittelyn teoria ja sovellus. – 1978.
Remez E. Ya. Tšebyshevin approksimoinnin numeeristen menetelmien perusteet. – 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . Uusi Remez-tyyppinen algoritmi parhaaseen polynomin approximaatioon // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italia, 15.–21.6.2019, Revised Selected Papers, Osa I , kesäkuu 2019– Sivut 69 doi // Ohjelma NUMTA 2019 , 19. kesäkuuta, keskiviikkoaamu (9.00): Huone 1 // Abstracts, sivu 50 // kirjat google, sivut 56-57, 60-64, 67-69