Direkt zum Inhalt

Lexikon der Mathematik: Remez-Algorithmus

Algorithmus zur Berechnung der besten Approximation.

Der Remez-Algorithmus ist eine iterative Methode zur Berechnung von besten Approximationen hinsichtlich der Maximumnorm || · ||. Er wurde 1934 für Tschebschew-Systeme G = {g(1), …, g(n)} von E.J.A. Remez entwickelt.

Die Idee des Algorithmus’ ist es, für eine vorgegebene stetige Funktion f auf [a, b] eine Folge gpG, p ∈ ℕ, zu berechnen, welche gegen die beste Approximation gfG an f hinsichüich der Maximumnorm konvergiert. Die beste Approximation gf ist gemäß dem Aiternantensatz charakterisiert durch die Eigenschaft, daß Punkte \begin{eqnarray}a\le {t}_{1}\lt \ldots \lt {t}_{n+1}\le b\end{eqnarray} existieren, so daß \begin{eqnarray}{(-1)}^{i}\sigma (f-{g}_{f})({t}_{i})=\Vert f-{g}_{f}\Vert_{\infty }\end{eqnarray} für i = 1,…, n + 1 gilt, wobei σ ∈ {−1, 1}.

Wir beschreiben die Grundzüge des Remez-Algorithmus’. Man startet mit einer sogenannten Startreferenz \begin{eqnarray}a\le {t}_{1}^{(1)}\lt \ldots \lt {t}_{n+1}^{(1)}\le b.\end{eqnarray}

Im p-ten Schritt des Algorithmus wählt man die aktuelle Menge von Punkten \begin{eqnarray}a\le {t}_{1}^{(p)}\lt \ldots \lt {t}_{n+1}^{(p)}\le b,\end{eqnarray} und bestimmt gpG und eine reelle Zahl λp so, daß gilt: \begin{eqnarray}{(-1)}^{i}(f-{g}_{p})({t}_{i}^{(p)})={\lambda }_{p},i=1,\ldots,n+1.\end{eqnarray}

Da G ein Tschebyschew-System ist, ist das zugehörige lineare Gleichungssystem stets eindeutig lösbar. Man bestimmt nun ein t* ∈ [a, b] so, daß \begin{eqnarray}(f-{g}_{p})(t* )\approx \Vert f-{g}_{f}\Vert_{\infty }.\end{eqnarray}

Nun tauscht man den zu t* benachbarten Punkt \({t}_{j}^{(p)}\) der Punkte des p-ten Schritts mit der Eigenschaft \begin{eqnarray}\text{sgn}(f-{g}_{p})({t}_{j}^{(p)})=\mathrm{sgn}((f-{g}_{p})(t* ))\end{eqnarray} mit t* aus. Falls t* < \({t}^{* }\lt {t}_{1}^{(p)}\) und \begin{eqnarray}\text{sgn}(f-{g}_{p})({t}_{1}^{(p)})=\mathrm{sgn}((f-{g}_{p})(t* ))\end{eqnarray} gelten, dann vertauscht man \({t}_{n+1}^{(p)}\) mit t*. Analog verfährt man am rechten Rand des Intervalls [a, b].

Durch diesen Austauschschritt gelangt man zu der Punktmenge des (p + 1)-ten Schritts \begin{eqnarray}a\le {t}_{1}^{(p+1)}\lt \ldots \lt {t}_{n+1}^{(p+1)}\le b.\end{eqnarray}

Abbildung 1 zum Lexikonartikel Remez-Algorithmus
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Zum Remez-Algonthmus

Der beschriebene Algorithmus basiert auf dem Austausch eines Punktes in jedem Schritt. Modifikationen der Methode vertauschen mehrere Punkte in einem einzelnen Schritt und erzielen schnellere Konvergenz. Man nennt diese Vorgehensweise Simultanaustausch.

Mitte der 80er Jahre wurde von G. Nürnberger und M. Sommer ein Remez-Algorithmus für die Berechnung bester Approximationen für Spline-funktionen entwickelt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Artikel zum Thema

Partnervideos