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-SystemeG = {g⁽¹⁾, …, g⁽ⁿ⁾} von E.J.A. Remez entwickelt.

Die Idee des Algorithmus’ ist es, für eine vorgegebene stetige Funktion f auf [a, b] eine Folge g_p ∈ G, p ∈ ℕ, zu berechnen, welche gegen die beste Approximation g_f ∈ G an f hinsichtlich der Maximumnorm konvergiert. Die beste Approximation g_f ist gemäß dem Alternantensatz 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 g_p ∈ G 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}

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 Splinefunktionen entwickelt.