Algoritmul Remez

Algoritmul Remez (de asemenea algoritmul de înlocuire Remez) este un algoritm iterativ pentru aproximarea uniformă a funcțiilor f ∊ C[ a , b ], bazat pe teorema de alternanță a lui P. L. Cebyshev . Propus de E. Ya. Remez în 1934 [1] .

Algoritmul Remez este utilizat în proiectarea filtrelor FIR [2] .

Fundamente matematice

Teorema lui Cebyshev

Baza teoretică a algoritmului Remez este următoarea teoremă [3] .

Pentru ca un polinom de grad cel mult să fie un polinom care se abate cel puțin de la , este necesar și suficient ca cel puțin un sistem de puncte să fie găsit la care diferența : $P^{*}(x)$ $n$ $f\în 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)$

ia alternativ valorile diferitelor semne,
atinge valoarea maximă prin modulo . $[a,\b]$

Un astfel de sistem de puncte se numește alternanță Chebyshev .

P. L. Cebyshev , 1854

Teorema de la Vallée-Poussin

Fie E n valoarea celei mai bune aproximări a funcției f ( x ) prin polinoame de grad n . E n este estimat de jos prin următoarea teoremă [4] :

Dacă pentru o funcție f ∊ C[ a , b ] un polinom P ( x ) de grad n are proprietatea că diferența f ( x ) - P ( x ) pe un sistem de n + 2 puncte ordonate x i ia valori cu semne alternante, atunci

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

Sh.-Zh. Vallee Poussin, 1919

Algoritm

Luați în considerare un sistem de funcții , o secvență de puncte și căutați un polinom de aproximare $n+1$ $\mathbf {\varPhi} =\{\varphi _{0},\dots,\varphi _{n}\)$ $n+2$ $X=\{x_{i}\},$ $a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,$

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

Rezolvăm un sistem de ecuații liniare pentru și : $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.$
Găsim un punct astfel încât . $\xi$ $D=f(\xi )-P(\xi )=\max$
Inlocuim unul dintre punctele din X cu ξ in asa fel incat semnul f - P sa alterneze in punctele noii siruri. În practică, se asigură doar că punctele x i sunt ordonate la fiecare iterație [5] .
Repetați toți pașii de la început până când nu există | d | = D .

La a doua etapă, putem căuta nu doar un punct ξ , ci o mulțime Ξ de puncte în care maximele locale | f - P |. Dacă toate erorile în punctele mulțimii Ξ au aceeași valoare absolută și alternează în semn, atunci P este un polinom minimax. În caz contrar, înlocuim punctele din X cu punctele din Ξ și repetăm procedura.

Selectarea punctelor de plecare

Ca și secvență inițială X , puteți alege puncte distribuite uniform pe [ a , b ]. De asemenea, este recomandabil să luați puncte [6] :

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

Modificare

Dacă funcția de aproximare este căutată sub forma unui polinom, atunci în loc să rezolvați sistemul la primul pas al algoritmului, puteți utiliza următoarea metodă [7] :

Găsiți un polinom q ( x ) de grad n+1 astfel încât q ( x i ) = f ( x i ) ( problema de interpolare ).
Găsim și un polinom q * ( x ) de grad n+1 astfel încât q * ( x i ) = (-1) i .
Alegând d astfel încât polinomul P ( x ) ≡ q ( x ) - d q * ( x ) să aibă gradul n , obținem P ( x i ) + (-1) i d = f ( x i ).

Apoi se repetă pașii conform schemei principale.

Stare de oprire

Deoarece prin teorema de la Vallée-Poussin | d | ≤ E n ( f ) ≤ D , atunci condiția de oprire a algoritmului poate fi D — | d | ≤ ε pentru unele ε prealocate .

Convergență

Algoritmul Remez converge la rata unei progresii geometrice în următorul sens [8] :

Pentru orice funcție f ∊ C[ a , b ] există numere A > 0 și 0 < q < 1 astfel încât abaterile maxime de la funcția f ( x ) de polinoame construite prin acest algoritm vor satisface inegalitățile $P_{n}^{(k)}(x)$

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

unde E n ( f ) este valoarea celei mai bune aproximări pe [ a , b ] a funcției f ( x ) folosind polinoamele P n ( x ).

E. Ya. Remez , 1957

Exemplu

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

Pasul 1.

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

Soluția sistemului dă P = 1,175 x + 1,272, d = 0,272.
D = max|e ξ - P ( ξ )| = 0,286 la ξ = 0,16.

Pasul 2

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

Soluția sistemului dă P = 1,175 x + 1,265, d = 0,279.
D = max|e ξ - P ( ξ )| = 0,279 la ξ = 0,16.

Deoarece același punct a fost obținut în cadrul preciziei date, polinomul găsit ar trebui considerat ca cea mai bună aproximare a primului grad al funcției e x .

Vezi și

Teorema de aproximare Weierstrass

Note

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

Literatură

DeVore RA, Lorentz GG Aproximație constructivă. — 1993.
Bronstein I. N., Semendyaev K. A. Manual de matematică pentru ingineri și studenți ai universităților tehnice. — 1980.
Dzyadyk VK Introducere în teoria aproximării uniforme a funcțiilor prin polinoame. — 1977.
Laurent P.-J. Aproximare și optimizare. — 1975.
Rabiner L., Gould B. Teoria și aplicarea procesării semnalelor digitale. — 1978.
Remez E. Ya. Fundamentele metodelor numerice ale aproximării Cebyshev. — 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . A New Remez-Type Algorithm for Best Polynomial Aproximation // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019, Revised Selected Papers, Part I , iunie 2019– Pagini 56 69 doi // Programul NUMTA 2019 , 19 iunie, miercuri dimineața (9.00): Sala 1 // Cartea de rezumate, pag. 50 // cărți google, paginile 56-57, 60-64, 67-69