Remez-algoritme - Remez algorithm

Het Remez-algoritme of Remez-uitwisselingsalgoritme , gepubliceerd door Evgeny Yakovlevich Remez in 1934, is een iteratief algoritme dat wordt gebruikt om eenvoudige benaderingen van functies te vinden, met name benaderingen door functies in een Chebyshev-ruimte die het beste zijn in de uniforme norm L _∞ zin.

Een typisch voorbeeld van een Chebyshev-ruimte is de deelruimte van Chebyshev-polynomen van orde n in de ruimte van reële continue functies op een interval , C [ a , b ]. De polynoom van de beste benadering binnen een gegeven deelruimte wordt gedefinieerd als de polynoom die het maximale absolute verschil tussen de polynoom en de functie minimaliseert . In dit geval wordt de vorm van de oplossing bepaald door de equioscillatiestelling .

Procedure

De Remez algoritme begint met de functie worden benaderd en een reeks van bemonsteringspunten in het benaderingsinterval, meestal de extrema van Chebyshev polynoom lineair toegewezen aan het interval. De stappen zijn: ${\displaystyle f}$${\displaystyle X}$${\displaystyle n+2}$${\displaystyle x_{1},x_{2},...,x_{n+2}}$

• Los het lineaire stelsel vergelijkingen op

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i} )}$(waar ),${\displaystyle i=1,2,...n+2}$

voor de onbekenden en E .${\displaystyle b_{0},b_{1}...b_{n}}$

• Gebruik de as-coëfficiënten om een ​​polynoom te vormen .${\displaystyle b_{i}}$${\displaystyle P_{n}}$
• Zoek de verzameling punten van de lokale maximale fout .${\displaystyle M}$${\displaystyle |P_{n}(x)-f(x)|}$
• Als de fouten bij elk van gelijke grootte zijn en afwisselend van teken zijn, dan is het minimax-benaderingspolynoom. Als dit niet het geval is, vervangt u door en herhaalt u de bovenstaande stappen.${\displaystyle m\in M}$${\displaystyle P_{n}}$${\displaystyle X}$${\displaystyle M}$

Het resultaat wordt de polynoom van de beste benadering of het minimax benaderingsalgoritme genoemd .

Een overzicht van technische details bij het implementeren van het Remez-algoritme wordt gegeven door W. Fraser.

Over de keuze van initialisatie

De Chebyshev-knooppunten zijn een gebruikelijke keuze voor de initiële benadering vanwege hun rol in de theorie van polynomiale interpolatie. Voor de initialisatie van het optimalisatieprobleem voor functie f door de Lagrange-interpolant L _n ( f ), kan worden aangetoond dat deze initiële benadering wordt begrensd door

${\displaystyle \lVert f-L_ {n}(f)\rVert _{\infty} \leq (1+\lVert L_{n}\rVert _{\infty})\inf _{p\in P_{n }}\lVert fp\rVert }$

waarbij de norm of Lebesgue-constante van de Lagrange-interpolatie-operator L _n van de knooppunten ( t ₁ , ..., t _{n  + 1} ) is

${\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{ n}(T;x),}$

T zijn de nullen van de Chebyshev-polynomen, en de Lebesgue-functies zijn

${\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}( x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i })}}.}$

Theodore A. Kilgore, Carl de Boor, en Allan Pinkus bewezen dat er sprake is van een unieke t _i voor elke L _n , hoewel niet expliciet voor de (gewone) veeltermen bekend. Evenzo, en de optimaliteit van een keuze van knooppunten kan worden uitgedrukt als${\displaystyle {\onderstrepen {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$

Voor Chebyshev-knooppunten, die een suboptimale, maar analytisch expliciete keuze bieden, staat het asymptotische gedrag bekend als

${\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\ left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}$

( γ is de Euler-Mascheroni constante ) met

${\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}$ voor ${\displaystyle n\geq 1,}$

en bovengrens

${\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}$

Lev Brutman verkreeg de grens voor , en zijnde de nullen van de geëxpandeerde Chebyshev-polynomen: ${\displaystyle n\geq 3}$${\displaystyle {\hat {T}}}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1 }{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\circa 0,201.}$

Rüdiger Günttner verkregen uit een scherpere schatting voor ${\displaystyle n\geq 40}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}$

Gedetailleerde discussie

In dit gedeelte vindt u meer informatie over de hierboven beschreven stappen. In deze sectie loopt de index i van 0 tot n +1.

Stap 1: Gegeven , los het lineaire stelsel van n +2 vergelijkingen op ${\displaystyle x_{0},x_{1},...x_{n+1}}$

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i} )}$(waar ),${\displaystyle i=0,1,...n+1}$

voor de onbekenden en E .${\displaystyle b_{0},b_{1},...b_{n}}$

Het moet duidelijk zijn dat in deze vergelijking alleen zin heeft als de knooppunten zijn geordend , ofwel strikt toenemend of strikt afnemend. Dan heeft dit lineaire systeem een ​​unieke oplossing. (Zoals bekend heeft niet elk lineair systeem een ​​oplossing.) De oplossing kan ook worden verkregen met alleen rekenkundige bewerkingen, terwijl een standaardoplosser uit de bibliotheek bewerkingen zou uitvoeren. Hier is het simpele bewijs: ${\displaystyle (-1)^{i}E}$${\displaystyle x_{0},...,x_{n+1}}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$

Bereken de standaard n -de graad interpolant tot op de eerste n +1 knopen en ook de standaard n -de graad interpolant tot de ordinaat${\displaystyle p_{1}(x)}$${\displaystyle f(x)}$${\displaystyle p_{2}(x)}$${\displaystyle (-1)^{i}}$

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,..., N.}$

Gebruik hiervoor telkens de interpolatieformule van Newton met de verdeelde verschillen van volgorde en rekenkundige bewerkingen. ${\displaystyle 0,...,n}$${\displaystyle O(n^{2})}$

De polynoom heeft zijn i -de nul tussen en , en dus geen verdere nullen tussen en : en heeft hetzelfde teken . ${\displaystyle p_{2}(x)}$${\displaystyle x_{i-1}}$${\displaystyle x_{i},\ i=1,...,n}$${\displaystyle x_{n}}$${\displaystyle x_{n+1}}$${\displaystyle p_{2}(x_{n})}$${\displaystyle p_{2}(x_{n+1})}$${\displaystyle (-1)^{n}}$

De lineaire combinatie is ook een polynoom van graad n en ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})- (-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

Dit is hetzelfde als de bovenstaande vergelijking voor en voor elke keuze van E . Dezelfde vergelijking voor i = n +1 is ${\displaystyle i=0,...,n}$

${\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}$en heeft een speciale redenering nodig: opgelost voor de variabele E , het is de definitie van E :

${\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+( -1)^{n}}}.}$

Zoals hierboven vermeld, hebben de twee termen in de noemer hetzelfde teken: E en zijn dus altijd goed gedefinieerd. ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$

De fout op de gegeven n +2 geordende knopen is beurtelings positief en negatief omdat

${\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1. }$

De stelling van de La Vallée Poussin stelt dat onder deze voorwaarde geen polynoom van graad n bestaat met een fout kleiner dan E . Inderdaad, als zo'n polynoom zou bestaan, noem het , dan zou het verschil nog steeds positief/negatief zijn op de n +2 knopen en dus minstens n +1 nullen hebben, wat onmogelijk is voor een polynoom van graad n . Deze E is dus een ondergrens voor de minimale fout die kan worden bereikt met polynomen van graad n . ${\displaystyle {\tilde {p}}(x)}$${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$${\displaystyle x_{i}}$

Stap 2 verandert de notatie van in . ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$${\displaystyle p(x)}$

Stap 3 verbetert de invoerknooppunten en hun fouten als volgt. ${\displaystyle x_{0},...,x_{n+1}}$${\displaystyle \pm E}$

In elke P-regio wordt het huidige knooppunt vervangen door de lokale maximalizer en in elke N-regio wordt deze vervangen door de lokale minimalizer. (Verwacht bij A , de nabije , en bij B .) Hier is geen hoge precisie vereist, de standaard zoekactie met een paar kwadratische passingen zou voldoende moeten zijn. (Zien ) ${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{0}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{n+1}}$

Laat . Elke amplitude is groter dan of gelijk aan E . De stelling van de La Vallée Poussin en zijn bewijs zijn ook van toepassing op met als de nieuwe ondergrens voor de best mogelijke fout met veeltermen van graad n . ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$${\displaystyle |z_{i}|}$${\displaystyle z_{0},...,z_{n+1}}$${\displaystyle \min\{|z_{i}|\}\geq E}$

Bovendien is het handig als een voor de hand liggende bovengrens voor die best mogelijke fout. ${\displaystyle \max\{|z_{i}|\}}$

Stap 4: Met en als onder- en bovengrens voor de best mogelijke benaderingsfout heeft men een betrouwbaar stopcriterium: herhaal de stappen totdat deze voldoende klein is of niet meer afneemt. Deze grenzen geven de voortgang aan. ${\displaystyle \min \,\{|z_{i}|\}}$${\displaystyle \max \,\{|z_{i}|\}}$${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$

varianten

Soms wordt meer dan één monsterpunt tegelijkertijd vervangen door de locaties van nabijgelegen maximale absolute verschillen.

Soms worden alle monsterpunten in één iteratie vervangen door de locaties van alle, afwisselende tekens, maximale verschillen.

Soms wordt een relatieve fout gebruikt om het verschil tussen de benadering en de functie te meten, vooral als de benadering wordt gebruikt om de functie te berekenen op een computer die gebruikmaakt van drijvende- kommaberekeningen.

Soms zijn nul-foutpuntbeperkingen opgenomen in een aangepast Remez Exchange-algoritme.

Zie ook

• Benaderingstheorie

Referenties

Externe links

• Minimax Approximations and the Remez Algorithm , achtergrondhoofdstuk in de Boost Math Tools-documentatie, met link naar een implementatie in C++
• Inleiding tot DSP
• Aarts, Ronald M.; Bond, Charles; Mendelsohn, Phil & Weisstein, Eric W. "Remez-algoritme" . MathWereld .